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