- /*
- * The Apache Software License, Version 1.1
- *
- *
- * Copyright (c) 1999 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- *
- * 3. The end-user documentation included with the redistribution,
- * if any, must include the following acknowledgment:
- * "This product includes software developed by the
- * Apache Software Foundation (http://www.apache.org/)."
- * Alternately, this acknowledgment may appear in the software itself,
- * if and wherever such third-party acknowledgments normally appear.
- *
- * 4. The names "Xalan" and "Apache Software Foundation" must
- * not be used to endorse or promote products derived from this
- * software without prior written permission. For written
- * permission, please contact apache@apache.org.
- *
- * 5. Products derived from this software may not be called "Apache",
- * nor may "Apache" appear in their name, without prior written
- * permission of the Apache Software Foundation.
- *
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
- * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
- * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
- * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- * ====================================================================
- *
- * This software consists of voluntary contributions made by many
- * individuals on behalf of the Apache Software Foundation and was
- * originally based on software copyright (c) 1999, Lotus
- * Development Corporation., http://www.lotus.com. For more
- * information on the Apache Software Foundation, please see
- * <http://www.apache.org/>.
- */
- package org.apache.xalan.transformer;
-
- import java.util.Vector;
-
- import java.text.NumberFormat;
- import java.text.CollationKey;
-
- //import org.w3c.dom.Node;
- //import org.w3c.dom.traversal.NodeIterator;
- import org.apache.xml.dtm.DTM;
- import org.apache.xml.dtm.DTMIterator;
-
- import org.apache.xpath.axes.ContextNodeList;
- import org.apache.xpath.XPathContext;
- import org.apache.xpath.NodeSetDTM;
- import org.apache.xpath.objects.XObject;
- import org.apache.xpath.objects.XNodeSet;
- import org.apache.xml.utils.NodeVector;
-
- import javax.xml.transform.TransformerException;
-
- /**
- * <meta name="usage" content="internal"/>
- * This class can sort vectors of DOM nodes according to a select pattern.
- */
- public class NodeSorter
- {
-
- /** Current XPath context */
- XPathContext m_execContext;
-
- /** Vector of NodeSortKeys */
- Vector m_keys; // vector of NodeSortKeys
-
- // /**
- // * TODO: Adjust this for locale.
- // */
- // NumberFormat m_formatter = NumberFormat.getNumberInstance();
-
- /**
- * Construct a NodeSorter, passing in the XSL TransformerFactory
- * so it can know how to get the node data according to
- * the proper whitespace rules.
- *
- * @param p Xpath context to use
- */
- public NodeSorter(XPathContext p)
- {
- m_execContext = p;
- }
-
- /**
- * Given a vector of nodes, sort each node according to
- * the criteria in the keys.
- * @param v an vector of Nodes.
- * @param keys a vector of NodeSortKeys.
- * @param support XPath context to use
- *
- * @throws javax.xml.transform.TransformerException
- */
- public void sort(DTMIterator v, Vector keys, XPathContext support)
- throws javax.xml.transform.TransformerException
- {
-
- m_keys = keys;
-
- // QuickSort2(v, 0, v.size() - 1 );
- int n = v.getLength();
-
- // %OPT% Change mergesort to just take a DTMIterator?
- // We would also have to adapt DTMIterator to have the function
- // of NodeCompareElem.
-
- // Create a vector of node compare elements
- // based on the input vector of nodes
- Vector nodes = new Vector();
-
- for (int i = 0; i < n; i++)
- {
- NodeCompareElem elem = new NodeCompareElem(v.item(i));
-
- nodes.addElement(elem);
- }
-
- Vector scratchVector = new Vector();
-
- mergesort(nodes, scratchVector, 0, n - 1, support);
-
- // return sorted vector of nodes
- for (int i = 0; i < n; i++)
- {
- v.setItem(((NodeCompareElem) nodes.elementAt(i)).m_node, i);
- }
- v.setCurrentPos(0);
-
- // old code...
- //NodeVector scratchVector = new NodeVector(n);
- //mergesort(v, scratchVector, 0, n - 1, support);
- }
-
- /**
- * Return the results of a compare of two nodes.
- * TODO: Optimize compare -- cache the getStringExpr results, key by m_selectPat + hash of node.
- *
- * @param n1 First node to use in compare
- * @param n2 Second node to use in compare
- * @param kIndex Index of NodeSortKey to use for sort
- * @param support XPath context to use
- *
- * @return The results of the compare of the two nodes.
- *
- * @throws TransformerException
- */
- int compare(
- NodeCompareElem n1, NodeCompareElem n2, int kIndex, XPathContext support)
- throws TransformerException
- {
-
- int result = 0;
- NodeSortKey k = (NodeSortKey) m_keys.elementAt(kIndex);
-
- if (k.m_treatAsNumbers)
- {
- double n1Num, n2Num;
-
- if (kIndex == 0)
- {
- n1Num = ((Double) n1.m_key1Value).doubleValue();
- n2Num = ((Double) n2.m_key1Value).doubleValue();
- }
- else if (kIndex == 1)
- {
- n1Num = ((Double) n1.m_key2Value).doubleValue();
- n2Num = ((Double) n2.m_key2Value).doubleValue();
- }
-
- /* Leave this in case we decide to use an array later
- if (kIndex < maxkey)
- {
- double n1Num = (double)n1.m_keyValue[kIndex];
- double n2Num = (double)n2.m_keyValue[kIndex];
- }*/
- else
- {
-
- // Get values dynamically
- XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node,
- k.m_namespaceContext);
- XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node,
- k.m_namespaceContext);
- n1Num = r1.num();
-
- // Can't use NaN for compare. They are never equal. Use zero instead.
- // That way we can keep elements in document order.
- //n1Num = Double.isNaN(d) ? 0.0 : d;
- n2Num = r2.num();
- //n2Num = Double.isNaN(d) ? 0.0 : d;
- }
-
- if ((n1Num == n2Num) && ((kIndex + 1) < m_keys.size()))
- {
- result = compare(n1, n2, kIndex + 1, support);
- }
- else
- {
- double diff;
- if (Double.isNaN(n1Num))
- {
- if (Double.isNaN(n2Num))
- diff = 0.0;
- else
- diff = -1;
- }
- else if (Double.isNaN(n2Num))
- diff = 1;
- else
- diff = n1Num - n2Num;
-
- // process order parameter
- result = (int) ((diff < 0.0)
- ? (k.m_descending ? 1 : -1)
- : (diff > 0.0) ? (k.m_descending ? -1 : 1) : 0);
- }
- } // end treat as numbers
- else
- {
- CollationKey n1String, n2String;
-
- if (kIndex == 0)
- {
- n1String = (CollationKey) n1.m_key1Value;
- n2String = (CollationKey) n2.m_key1Value;
- }
- else if (kIndex == 1)
- {
- n1String = (CollationKey) n1.m_key2Value;
- n2String = (CollationKey) n2.m_key2Value;
- }
-
- /* Leave this in case we decide to use an array later
- if (kIndex < maxkey)
- {
- String n1String = (String)n1.m_keyValue[kIndex];
- String n2String = (String)n2.m_keyValue[kIndex];
- }*/
- else
- {
-
- // Get values dynamically
- XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node,
- k.m_namespaceContext);
- XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node,
- k.m_namespaceContext);
-
- n1String = k.m_col.getCollationKey(r1.str());
- n2String = k.m_col.getCollationKey(r2.str());
- }
-
- // Use collation keys for faster compare, but note that whitespaces
- // etc... are treated differently from if we were comparing Strings.
- result = n1String.compareTo(n2String);
-
- //Process caseOrder parameter
- if (k.m_caseOrderUpper)
- {
- String tempN1 = n1String.getSourceString().toLowerCase();
- String tempN2 = n2String.getSourceString().toLowerCase();
-
- if (tempN1.equals(tempN2))
- {
-
- //java defaults to upper case is greater.
- result = result == 0 ? 0 : -result;
- }
- }
-
- //Process order parameter
- if (k.m_descending)
- {
- result = -result;
- }
- } //end else
-
- if (0 == result)
- {
- if ((kIndex + 1) < m_keys.size())
- {
- result = compare(n1, n2, kIndex + 1, support);
- }
- }
-
- if (0 == result)
- {
-
- // I shouldn't have to do this except that there seems to
- // be a glitch in the mergesort
- // if(r1.getType() == r1.CLASS_NODESET)
- // {
- DTM dtm = support.getDTM(n1.m_node); // %OPT%
- result = dtm.isNodeAfter(n1.m_node, n2.m_node) ? -1 : 1;
-
- // }
- }
-
- return result;
- }
-
- /**
- * This implements a standard Mergesort, as described in
- * Robert Sedgewick's Algorithms book. This is a better
- * sort for our purpose than the Quicksort because it
- * maintains the original document order of the input if
- * the order isn't changed by the sort.
- *
- * @param a First vector of nodes to compare
- * @param b Second vector of nodes to compare
- * @param l Left boundary of partition
- * @param r Right boundary of partition
- * @param support XPath context to use
- *
- * @throws TransformerException
- */
- void mergesort(Vector a, Vector b, int l, int r, XPathContext support)
- throws TransformerException
- {
-
- if ((r - l) > 0)
- {
- int m = (r + l) / 2;
-
- mergesort(a, b, l, m, support);
- mergesort(a, b, m + 1, r, support);
-
- int i, j, k;
-
- for (i = m; i >= l; i--)
- {
-
- // b[i] = a[i];
- // Use insert if we need to increment vector size.
- if (i >= b.size())
- b.insertElementAt(a.elementAt(i), i);
- else
- b.setElementAt(a.elementAt(i), i);
- }
-
- i = l;
-
- for (j = (m + 1); j <= r; j++)
- {
-
- // b[r+m+1-j] = a[j];
- if (r + m + 1 - j >= b.size())
- b.insertElementAt(a.elementAt(j), r + m + 1 - j);
- else
- b.setElementAt(a.elementAt(j), r + m + 1 - j);
- }
-
- j = r;
-
- int compVal;
-
- for (k = l; k <= r; k++)
- {
-
- // if(b[i] < b[j])
- if (i == j)
- compVal = -1;
- else
- compVal = compare((NodeCompareElem) b.elementAt(i),
- (NodeCompareElem) b.elementAt(j), 0, support);
-
- if (compVal < 0)
- {
-
- // a[k]=b[i];
- a.setElementAt(b.elementAt(i), k);
-
- i++;
- }
- else if (compVal > 0)
- {
-
- // a[k]=b[j];
- a.setElementAt(b.elementAt(j), k);
-
- j--;
- }
- }
- }
- }
-
- /**
- * This is a generic version of C.A.R Hoare's Quick Sort
- * algorithm. This will handle arrays that are already
- * sorted, and arrays with duplicate keys.<BR>
- *
- * If you think of a one dimensional array as going from
- * the lowest index on the left to the highest index on the right
- * then the parameters to this function are lowest index or
- * left and highest index or right. The first time you call
- * this function it will be with the parameters 0, a.length - 1.
- *
- * @param v a vector of integers
- * @param lo0 left boundary of array partition
- * @param hi0 right boundary of array partition
- *
- */
-
- /* private void QuickSort2(Vector v, int lo0, int hi0, XPathContext support)
- throws javax.xml.transform.TransformerException,
- java.net.MalformedURLException,
- java.io.FileNotFoundException,
- java.io.IOException
- {
- int lo = lo0;
- int hi = hi0;
-
- if ( hi0 > lo0)
- {
- // Arbitrarily establishing partition element as the midpoint of
- // the array.
- Node midNode = (Node)v.elementAt( ( lo0 + hi0 ) / 2 );
-
- // loop through the array until indices cross
- while( lo <= hi )
- {
- // find the first element that is greater than or equal to
- // the partition element starting from the left Index.
- while( (lo < hi0) && (compare((Node)v.elementAt(lo), midNode, 0, support) < 0) )
- {
- ++lo;
- } // end while
-
- // find an element that is smaller than or equal to
- // the partition element starting from the right Index.
- while( (hi > lo0) && (compare((Node)v.elementAt(hi), midNode, 0, support) > 0) )
- {
- --hi;
- }
-
- // if the indexes have not crossed, swap
- if( lo <= hi )
- {
- swap(v, lo, hi);
- ++lo;
- --hi;
- }
- }
-
- // If the right index has not reached the left side of array
- // must now sort the left partition.
- if( lo0 < hi )
- {
- QuickSort2( v, lo0, hi, support );
- }
-
- // If the left index has not reached the right side of array
- // must now sort the right partition.
- if( lo < hi0 )
- {
- QuickSort2( v, lo, hi0, support );
- }
- }
- } // end QuickSort2 */
-
- // /**
- // * Simple function to swap two elements in
- // * a vector.
- // *
- // * @param v Vector of nodes to swap
- // * @param i Index of first node to swap
- // * @param i Index of second node to swap
- // */
- // private void swap(Vector v, int i, int j)
- // {
- //
- // int node = (Node) v.elementAt(i);
- //
- // v.setElementAt(v.elementAt(j), i);
- // v.setElementAt(node, j);
- // }
-
- /**
- * <meta name="usage" content="internal"/>
- * This class holds the value(s) from executing the given
- * node against the sort key(s).
- */
- class NodeCompareElem
- {
-
- /** Current node */
- int m_node;
-
- /** This maxkey value was chosen arbitrarily. We are assuming that the
- // maxkey + 1 keys will only hit fairly rarely and therefore, we
- // will get the node values for those keys dynamically.
- */
- int maxkey = 2;
-
- // Keep this in case we decide to use an array. Right now
- // using two variables is cheaper.
- //Object[] m_KeyValue = new Object[2];
-
- /** Value from first sort key */
- Object m_key1Value;
-
- /** Value from second sort key */
- Object m_key2Value;
-
- /**
- * Constructor NodeCompareElem
- *
- *
- * @param node Current node
- *
- * @throws javax.xml.transform.TransformerException
- */
- NodeCompareElem(int node) throws javax.xml.transform.TransformerException
- {
-
- boolean tryNextKey = true;
-
- m_node = node;
-
- if (!m_keys.isEmpty())
- {
- NodeSortKey k1 = (NodeSortKey) m_keys.elementAt(0);
- XObject r = k1.m_selectPat.execute(m_execContext, node,
- k1.m_namespaceContext);
-
- if (r == null)
- tryNextKey = false;
-
- double d;
-
- if (k1.m_treatAsNumbers)
- {
- d = r.num();
-
- // Can't use NaN for compare. They are never equal. Use zero instead.
- m_key1Value = new Double(d);
- }
- else
- {
- m_key1Value = k1.m_col.getCollationKey(r.str());
- }
-
- if (r.getType() == XObject.CLASS_NODESET)
- {
- // %REVIEW%
- DTMIterator ni = ((XNodeSet)r).iterRaw();
- int current = ni.getCurrentNode();
- if(DTM.NULL == current)
- current = ni.nextNode();
-
- // if (ni instanceof ContextNodeList) // %REVIEW%
- tryNextKey = (DTM.NULL != current);
-
- // else abdicate... should never happen, but... -sb
- }
-
- if (m_keys.size() > 1)
- {
- NodeSortKey k2 = (NodeSortKey) m_keys.elementAt(1);
-
- if (!tryNextKey)
- {
- if (k2.m_treatAsNumbers)
- m_key2Value = new Double(0.0);
- else
- m_key2Value = k2.m_col.getCollationKey("");
- }
- else
- {
- XObject r2 = k2.m_selectPat.execute(m_execContext, node,
- k2.m_namespaceContext);
-
- if (k2.m_treatAsNumbers)
- {
- d = r2.num();
- m_key2Value = new Double(d);
- }
- else
- m_key2Value = k2.m_col.getCollationKey(r2.str());
- }
- }
-
- /* Leave this in case we decide to use an array later
- while (kIndex <= m_keys.size() && kIndex < maxkey)
- {
- NodeSortKey k = (NodeSortKey)m_keys.elementAt(kIndex);
- XObject r = k.m_selectPat.execute(m_execContext, node, k.m_namespaceContext);
- if(k.m_treatAsNumbers)
- m_KeyValue[kIndex] = r.num();
- else
- m_KeyValue[kIndex] = r.str();
- } */
- } // end if not empty
- }
- } // end NodeCompareElem class
- }