code: /*
   * 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
  }
  