src/org/apache/xalan/transformer/NodeSorter.java - xalan-j - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements. See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership. The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the  "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 /*
  * $Id$
  */
 package org.apache.xalan.transformer;

 import java.text.CollationKey;
 import java.util.Vector;

 import javax.xml.transform.TransformerException;

 import org.apache.xml.dtm.DTM;
 import org.apache.xml.dtm.DTMIterator;
 import org.apache.xpath.XPathContext;
 import org.apache.xpath.objects.XNodeSet;
 import org.apache.xpath.objects.XObject;

 /**
  * This class can sort vectors of DOM nodes according to a select pattern.
  * @xsl.usage internal
  */
 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);
 //  }

   /**
    * This class holds the value(s) from executing the given
    * node against the sort key(s).
    * @xsl.usage internal
    */
   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
     {
       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);

         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);

           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
 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	/*
	* $Id$
	*/
	package org.apache.xalan.transformer;

	import java.text.CollationKey;
	import java.util.Vector;

	import javax.xml.transform.TransformerException;

	import org.apache.xml.dtm.DTM;
	import org.apache.xml.dtm.DTMIterator;
	import org.apache.xpath.XPathContext;
	import org.apache.xpath.objects.XNodeSet;
	import org.apache.xpath.objects.XObject;

	/**
	* This class can sort vectors of DOM nodes according to a select pattern.
	* @xsl.usage internal
	*/
	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);
	// }

	/**
	* This class holds the value(s) from executing the given
	* node against the sort key(s).
	* @xsl.usage internal
	*/
	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
	{
	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);

	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);

	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
	}