nodesorter.java

来自「java jdk 1.4的源码」· Java 代码 · 共 619 行 · 第 1/2 页

      // 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
}