NodeSorter


1   /*
2    * Copyright 1999-2004 The Apache Software Foundation.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *     http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  /*
17   * $Id: NodeSorter.java,v 1.19 2004/02/16 20:41:29 minchau Exp $
18   */
19  package org.apache.xalan.transformer;
20  
21  import java.text.CollationKey  ;
22  import java.util.Vector  ;
23  
24  import javax.xml.transform.TransformerException  ;
25  
26  import org.apache.xml.dtm.DTM;
27  import org.apache.xml.dtm.DTMIterator;
28  import org.apache.xpath.XPathContext;
29  import org.apache.xpath.objects.XNodeSet;
30  import org.apache.xpath.objects.XObject;
31  
32  /**
33   * This class can sort vectors of DOM nodes according to a select pattern.
34   * @xsl.usage internal
35   */
36  public class NodeSorter
37  {
38  
39    /** Current XPath context           */
40    XPathContext m_execContext;
41  
42    /** Vector of NodeSortKeys          */
43    Vector   m_keys;  // vector of NodeSortKeys
44  
45  //  /**
46  //   * TODO: Adjust this for locale.
47  //   */
48  //  NumberFormat m_formatter = NumberFormat.getNumberInstance();
49  
50    /**
51     * Construct a NodeSorter, passing in the XSL TransformerFactory
52     * so it can know how to get the node data according to
53     * the proper whitespace rules.
54     *
55     * @param p Xpath context to use
56     */
57    public NodeSorter(XPathContext p)
58    {
59      m_execContext = p;
60    }
61  
62    /**
63     * Given a vector of nodes, sort each node according to
64     * the criteria in the keys.
65     * @param v an vector of Nodes.
66     * @param keys a vector of NodeSortKeys.
67     * @param support XPath context to use
68     *
69     * @throws javax.xml.transform.TransformerException
70     */
71    public void sort(DTMIterator v, Vector   keys, XPathContext support)
72            throws javax.xml.transform.TransformerException  
73    {
74  
75      m_keys = keys;
76  
77      // QuickSort2(v, 0, v.size() - 1 );
78      int n = v.getLength();
79  
80      // %OPT% Change mergesort to just take a DTMIterator?
81      // We would also have to adapt DTMIterator to have the function 
82      // of NodeCompareElem.
83      
84      // Create a vector of node compare elements
85      // based on the input vector of nodes
86      Vector   nodes = new Vector  ();
87  
88      for (int i = 0; i < n; i++)
89      {
90        NodeCompareElem elem = new NodeCompareElem(v.item(i));
91  
92        nodes.addElement(elem);
93      }
94  
95      Vector   scratchVector = new Vector  ();
96  
97      mergesort(nodes, scratchVector, 0, n - 1, support);
98  
99      // return sorted vector of nodes
100     for (int i = 0; i < n; i++)
101     {
102       v.setItem(((NodeCompareElem) nodes.elementAt(i)).m_node, i);
103     }
104     v.setCurrentPos(0);
105 
106     // old code...
107     //NodeVector scratchVector = new NodeVector(n);
108     //mergesort(v, scratchVector, 0, n - 1, support);
109   }
110 
111   /**
112    * Return the results of a compare of two nodes.
113    * TODO: Optimize compare -- cache the getStringExpr results, key by m_selectPat + hash of node.
114    *
115    * @param n1 First node to use in compare
116    * @param n2 Second node to use in compare
117    * @param kIndex Index of NodeSortKey to use for sort
118    * @param support XPath context to use
119    *
120    * @return The results of the compare of the two nodes.
121    *
122    * @throws TransformerException
123    */
124   int compare(
125           NodeCompareElem n1, NodeCompareElem n2, int kIndex, XPathContext support)
126             throws TransformerException  
127   {
128 
129     int result = 0;
130     NodeSortKey k = (NodeSortKey) m_keys.elementAt(kIndex);
131 
132     if (k.m_treatAsNumbers)
133     {
134       double n1Num, n2Num;
135 
136       if (kIndex == 0)
137       {
138         n1Num = ((Double  ) n1.m_key1Value).doubleValue();
139         n2Num = ((Double  ) n2.m_key1Value).doubleValue();
140       }
141       else if (kIndex == 1)
142       {
143         n1Num = ((Double  ) n1.m_key2Value).doubleValue();
144         n2Num = ((Double  ) n2.m_key2Value).doubleValue();
145       }
146 
147       /* Leave this in case we decide to use an array later
148       if (kIndex < maxkey)
149       {
150       double n1Num = (double)n1.m_keyValue[kIndex];
151       double n2Num = (double)n2.m_keyValue[kIndex];
152       }*/
153       else
154       {
155 
156         // Get values dynamically
157         XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node,
158                                            k.m_namespaceContext);
159         XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node,
160                                            k.m_namespaceContext);
161         n1Num = r1.num();
162 
163         // Can't use NaN for compare. They are never equal. Use zero instead.
164         // That way we can keep elements in document order. 
165         //n1Num = Double.isNaN(d) ? 0.0 : d;
166         n2Num = r2.num();
167         //n2Num = Double.isNaN(d) ? 0.0 : d;
168       }
169 
170       if ((n1Num == n2Num) && ((kIndex + 1) < m_keys.size()))
171       {
172         result = compare(n1, n2, kIndex + 1, support);
173       }
174       else
175       {
176         double diff;
177         if (Double.isNaN(n1Num))
178         {
179           if (Double.isNaN(n2Num))
180             diff = 0.0;
181           else
182             diff = -1;
183         }
184         else if (Double.isNaN(n2Num))
185            diff = 1;
186         else
187           diff = n1Num - n2Num;
188 
189         // process order parameter 
190         result = (int) ((diff < 0.0)
191                         ? (k.m_descending ? 1 : -1)
192                         : (diff > 0.0) ? (k.m_descending ? -1 : 1) : 0);
193       }
194     }  // end treat as numbers 
195     else
196     {
197       CollationKey   n1String, n2String;
198 
199       if (kIndex == 0)
200       {
201         n1String = (CollationKey  ) n1.m_key1Value;
202         n2String = (CollationKey  ) n2.m_key1Value;
203       }
204       else if (kIndex == 1)
205       {
206         n1String = (CollationKey  ) n1.m_key2Value;
207         n2String = (CollationKey  ) n2.m_key2Value;
208       }
209 
210       /* Leave this in case we decide to use an array later
211       if (kIndex < maxkey)
212       {
213         String n1String = (String)n1.m_keyValue[kIndex];
214         String n2String = (String)n2.m_keyValue[kIndex];
215       }*/
216       else
217       {
218 
219         // Get values dynamically
220         XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node,
221                                            k.m_namespaceContext);
222         XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node,
223                                            k.m_namespaceContext);
224 
225         n1String = k.m_col.getCollationKey(r1.str());
226         n2String = k.m_col.getCollationKey(r2.str());
227       }
228 
229       // Use collation keys for faster compare, but note that whitespaces 
230       // etc... are treated differently from if we were comparing Strings.
231       result = n1String.compareTo(n2String);
232 
233       //Process caseOrder parameter
234       if (k.m_caseOrderUpper)
235       {
236         String   tempN1 = n1String.getSourceString().toLowerCase();
237         String   tempN2 = n2String.getSourceString().toLowerCase();
238 
239         if (tempN1.equals(tempN2))
240         {
241 
242           //java defaults to upper case is greater.
243           result = result == 0 ? 0 : -result;
244         }
245       }
246 
247       //Process order parameter
248       if (k.m_descending)
249       {
250         result = -result;
251       }
252     }  //end else
253 
254     if (0 == result)
255     {
256       if ((kIndex + 1) < m_keys.size())
257       {
258         result = compare(n1, n2, kIndex + 1, support);
259       }
260     }
261 
262     if (0 == result)
263     {
264 
265       // I shouldn't have to do this except that there seems to 
266       // be a glitch in the mergesort
267       // if(r1.getType() == r1.CLASS_NODESET)
268       // {
269       DTM dtm = support.getDTM(n1.m_node); // %OPT%
270       result = dtm.isNodeAfter(n1.m_node, n2.m_node) ? -1 : 1;
271 
272       // }
273     }
274 
275     return result;
276   }
277 
278   /**
279    * This implements a standard Mergesort, as described in
280    * Robert Sedgewick's Algorithms book.  This is a better
281    * sort for our purpose than the Quicksort because it
282    * maintains the original document order of the input if
283    * the order isn't changed by the sort.
284    *
285    * @param a First vector of nodes to compare
286    * @param b Second vector of  nodes to compare 
287    * @param l Left boundary of  partition
288    * @param r Right boundary of  partition
289    * @param support XPath context to use
290    *
291    * @throws TransformerException
292    */
293   void mergesort(Vector   a, Vector   b, int l, int r, XPathContext support)
294           throws TransformerException  
295   {
296 
297     if ((r - l) > 0)
298     {
299       int m = (r + l) / 2;
300 
301       mergesort(a, b, l, m, support);
302       mergesort(a, b, m + 1, r, support);
303 
304       int i, j, k;
305 
306       for (i = m; i >= l; i--)
307       {
308 
309         // b[i] = a[i];
310         // Use insert if we need to increment vector size.
311         if (i >= b.size())
312           b.insertElementAt(a.elementAt(i), i);
313         else
314           b.setElementAt(a.elementAt(i), i);
315       }
316 
317       i = l;
318 
319       for (j = (m + 1); j <= r; j++)
320       {
321 
322         // b[r+m+1-j] = a[j];
323         if (r + m + 1 - j >= b.size())
324           b.insertElementAt(a.elementAt(j), r + m + 1 - j);
325         else
326           b.setElementAt(a.elementAt(j), r + m + 1 - j);
327       }
328 
329       j = r;
330 
331       int compVal;
332 
333       for (k = l; k <= r; k++)
334       {
335 
336         // if(b[i] < b[j])
337         if (i == j)
338           compVal = -1;
339         else
340           compVal = compare((NodeCompareElem) b.elementAt(i),
341                             (NodeCompareElem) b.elementAt(j), 0, support);
342 
343         if (compVal < 0)
344         {
345 
346           // a[k]=b[i];
347           a.setElementAt(b.elementAt(i), k);
348 
349           i++;
350         }
351         else if (compVal > 0)
352         {
353 
354           // a[k]=b[j]; 
355           a.setElementAt(b.elementAt(j), k);
356 
357           j--;
358         }
359       }
360     }
361   }
362 
363   /**
364    * This is a generic version of C.A.R Hoare's Quick Sort
365    * algorithm.  This will handle arrays that are already
366    * sorted, and arrays with duplicate keys.<BR>
367    *
368    * If you think of a one dimensional array as going from
369    * the lowest index on the left to the highest index on the right
370    * then the parameters to this function are lowest index or
371    * left and highest index or right.  The first time you call
372    * this function it will be with the parameters 0, a.length - 1.
373    *
374    * @param v       a vector of integers 
375    * @param lo0     left boundary of array partition
376    * @param hi0     right boundary of array partition
377    *
378    */
379 
380   /*  private void QuickSort2(Vector v, int lo0, int hi0, XPathContext support)
381       throws javax.xml.transform.TransformerException,
382              java.net.MalformedURLException,
383              java.io.FileNotFoundException,
384              java.io.IOException
385     {
386       int lo = lo0;
387       int hi = hi0;
388 
389       if ( hi0 > lo0)
390       {
391         // Arbitrarily establishing partition element as the midpoint of
392         // the array.
393         Node midNode = (Node)v.elementAt( ( lo0 + hi0 ) / 2 );
394 
395         // loop through the array until indices cross
396         while( lo <= hi )
397         {
398           // find the first element that is greater than or equal to
399           // the partition element starting from the left Index.
400           while( (lo < hi0) && (compare((Node)v.elementAt(lo), midNode, 0, support) < 0) )
401           {
402             ++lo;
403           } // end while
404 
405           // find an element that is smaller than or equal to
406           // the partition element starting from the right Index.
407           while( (hi > lo0) && (compare((Node)v.elementAt(hi), midNode, 0, support) > 0) )
408           {
409             --hi;
410           }
411 
412           // if the indexes have not crossed, swap
413           if( lo <= hi )
414           {
415             swap(v, lo, hi);
416             ++lo;
417             --hi;
418           }
419         }
420 
421         // If the right index has not reached the left side of array
422         // must now sort the left partition.
423         if( lo0 < hi )
424         {
425           QuickSort2( v, lo0, hi, support );
426         }
427 
428         // If the left index has not reached the right side of array
429         // must now sort the right partition.
430         if( lo < hi0 )
431         {
432           QuickSort2( v, lo, hi0, support );
433         }
434       }
435     } // end QuickSort2  */
436 
437 //  /**
438 //   * Simple function to swap two elements in
439 //   * a vector.
440 //   * 
441 //   * @param v Vector of nodes to swap
442 //   * @param i Index of first node to swap
443 //   * @param i Index of second node to swap
444 //   */
445 //  private void swap(Vector v, int i, int j)
446 //  {
447 //
448 //    int node = (Node) v.elementAt(i);
449 //
450 //    v.setElementAt(v.elementAt(j), i);
451 //    v.setElementAt(node, j);
452 //  }
453 
454   /**
455    * This class holds the value(s) from executing the given
456    * node against the sort key(s). 
457    * @xsl.usage internal
458    */
459   class NodeCompareElem
460   {
461 
462     /** Current node          */
463     int m_node;
464 
465     /** This maxkey value was chosen arbitrarily. We are assuming that the    
466     // maxkey + 1 keys will only hit fairly rarely and therefore, we
467     // will get the node values for those keys dynamically.
468     */
469     int maxkey = 2;
470 
471     // Keep this in case we decide to use an array. Right now
472     // using two variables is cheaper.
473     //Object[] m_KeyValue = new Object[2];
474 
475     /** Value from first sort key           */
476     Object   m_key1Value;
477 
478     /** Value from second sort key            */
479     Object   m_key2Value;
480 
481     /**
482      * Constructor NodeCompareElem
483      *
484      *
485      * @param node Current node
486      *
487      * @throws javax.xml.transform.TransformerException
488      */
489     NodeCompareElem(int node) throws javax.xml.transform.TransformerException  
490     {
491       m_node = node;
492 
493       if (!m_keys.isEmpty())
494       {
495         NodeSortKey k1 = (NodeSortKey) m_keys.elementAt(0);
496         XObject r = k1.m_selectPat.execute(m_execContext, node,
497                                            k1.m_namespaceContext);
498 
499         double d;
500 
501         if (k1.m_treatAsNumbers)
502         {
503           d = r.num();
504 
505           // Can't use NaN for compare. They are never equal. Use zero instead.  
506           m_key1Value = new Double  (d);
507         }
508         else
509         {
510           m_key1Value = k1.m_col.getCollationKey(r.str());
511         }
512 
513         if (r.getType() == XObject.CLASS_NODESET)
514         {
515           // %REVIEW%
516           DTMIterator ni = ((XNodeSet)r).iterRaw();
517           int current = ni.getCurrentNode();
518           if(DTM.NULL == current)
519             current = ni.nextNode();
520 
521           // if (ni instanceof ContextNodeList) // %REVIEW%
522           // tryNextKey = (DTM.NULL != current);
523 
524           // else abdicate... should never happen, but... -sb
525         }
526 
527         if (m_keys.size() > 1)
528         {
529           NodeSortKey k2 = (NodeSortKey) m_keys.elementAt(1);
530 
531           XObject r2 = k2.m_selectPat.execute(m_execContext, node,
532                                               k2.m_namespaceContext);
533 
534           if (k2.m_treatAsNumbers) {
535             d = r2.num();
536             m_key2Value = new Double  (d);
537           } else {
538             m_key2Value = k2.m_col.getCollationKey(r2.str());
539           }
540         }
541 
542         /* Leave this in case we decide to use an array later
543         while (kIndex <= m_keys.size() && kIndex < maxkey)
544         {
545           NodeSortKey k = (NodeSortKey)m_keys.elementAt(kIndex);
546           XObject r = k.m_selectPat.execute(m_execContext, node, k.m_namespaceContext);
547           if(k.m_treatAsNumbers)
548             m_KeyValue[kIndex] = r.num();
549           else
550             m_KeyValue[kIndex] = r.str();
551         } */
552       }  // end if not empty    
553     }
554   }  // end NodeCompareElem class
555 }
556
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags