19f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson/* 29f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Licensed to the Apache Software Foundation (ASF) under one 39f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * or more contributor license agreements. See the NOTICE file 49f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * distributed with this work for additional information 59f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * regarding copyright ownership. The ASF licenses this file 69f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * to you under the Apache License, Version 2.0 (the "License"); 79f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * you may not use this file except in compliance with the License. 89f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * You may obtain a copy of the License at 99f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Unless required by applicable law or agreed to in writing, software 139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * See the License for the specific language governing permissions and 169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * limitations under the License. 179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson/* 199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * $Id: NodeSorter.java 468645 2006-10-28 06:57:24Z minchau $ 209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpackage org.apache.xalan.transformer; 229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport java.text.CollationKey; 249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport java.util.Vector; 259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport javax.xml.transform.TransformerException; 279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport org.apache.xml.dtm.DTM; 299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport org.apache.xml.dtm.DTMIterator; 309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport org.apache.xpath.XPathContext; 319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport org.apache.xpath.objects.XNodeSet; 329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport org.apache.xpath.objects.XObject; 339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson/** 359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * This class can sort vectors of DOM nodes according to a select pattern. 369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @xsl.usage internal 379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpublic class NodeSorter 399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson{ 409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Current XPath context */ 429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson XPathContext m_execContext; 439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Vector of NodeSortKeys */ 459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson Vector m_keys; // vector of NodeSortKeys 469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// /** 489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// * TODO: Adjust this for locale. 499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// */ 509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// NumberFormat m_formatter = NumberFormat.getNumberInstance(); 519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Construct a NodeSorter, passing in the XSL TransformerFactory 549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * so it can know how to get the node data according to 559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the proper whitespace rules. 569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param p Xpath context to use 589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public NodeSorter(XPathContext p) 609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_execContext = p; 629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Given a vector of nodes, sort each node according to 669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the criteria in the keys. 679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param v an vector of Nodes. 689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param keys a vector of NodeSortKeys. 699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param support XPath context to use 709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws javax.xml.transform.TransformerException 729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void sort(DTMIterator v, Vector keys, XPathContext support) 749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throws javax.xml.transform.TransformerException 759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_keys = keys; 789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // QuickSort2(v, 0, v.size() - 1 ); 809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int n = v.getLength(); 819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // %OPT% Change mergesort to just take a DTMIterator? 839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // We would also have to adapt DTMIterator to have the function 849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // of NodeCompareElem. 859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Create a vector of node compare elements 879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // based on the input vector of nodes 889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson Vector nodes = new Vector(); 899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < n; i++) 919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson NodeCompareElem elem = new NodeCompareElem(v.item(i)); 939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson nodes.addElement(elem); 959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson Vector scratchVector = new Vector(); 989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson mergesort(nodes, scratchVector, 0, n - 1, support); 1009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // return sorted vector of nodes 1029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < n; i++) 1039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson v.setItem(((NodeCompareElem) nodes.elementAt(i)).m_node, i); 1059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson v.setCurrentPos(0); 1079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // old code... 1099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson //NodeVector scratchVector = new NodeVector(n); 1109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson //mergesort(v, scratchVector, 0, n - 1, support); 1119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Return the results of a compare of two nodes. 1159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * TODO: Optimize compare -- cache the getStringExpr results, key by m_selectPat + hash of node. 1169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param n1 First node to use in compare 1189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param n2 Second node to use in compare 1199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param kIndex Index of NodeSortKey to use for sort 1209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param support XPath context to use 1219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return The results of the compare of the two nodes. 1239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws TransformerException 1259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int compare( 1279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson NodeCompareElem n1, NodeCompareElem n2, int kIndex, XPathContext support) 1289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throws TransformerException 1299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int result = 0; 1329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson NodeSortKey k = (NodeSortKey) m_keys.elementAt(kIndex); 1339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (k.m_treatAsNumbers) 1359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson double n1Num, n2Num; 1379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (kIndex == 0) 1399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n1Num = ((Double) n1.m_key1Value).doubleValue(); 1419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n2Num = ((Double) n2.m_key1Value).doubleValue(); 1429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else if (kIndex == 1) 1449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n1Num = ((Double) n1.m_key2Value).doubleValue(); 1469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n2Num = ((Double) n2.m_key2Value).doubleValue(); 1479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /* Leave this in case we decide to use an array later 1509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (kIndex < maxkey) 1519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson double n1Num = (double)n1.m_keyValue[kIndex]; 1539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson double n2Num = (double)n2.m_keyValue[kIndex]; 1549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson }*/ 1559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 1569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Get values dynamically 1599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node, 1609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson k.m_namespaceContext); 1619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node, 1629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson k.m_namespaceContext); 1639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n1Num = r1.num(); 1649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Can't use NaN for compare. They are never equal. Use zero instead. 1669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // That way we can keep elements in document order. 1679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson //n1Num = Double.isNaN(d) ? 0.0 : d; 1689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n2Num = r2.num(); 1699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson //n2Num = Double.isNaN(d) ? 0.0 : d; 1709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((n1Num == n2Num) && ((kIndex + 1) < m_keys.size())) 1739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson result = compare(n1, n2, kIndex + 1, support); 1759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 1779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson double diff; 1799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (Double.isNaN(n1Num)) 1809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (Double.isNaN(n2Num)) 1829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson diff = 0.0; 1839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 1849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson diff = -1; 1859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else if (Double.isNaN(n2Num)) 1879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson diff = 1; 1889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 1899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson diff = n1Num - n2Num; 1909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // process order parameter 1929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson result = (int) ((diff < 0.0) 1939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ? (k.m_descending ? 1 : -1) 1949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson : (diff > 0.0) ? (k.m_descending ? -1 : 1) : 0); 1959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } // end treat as numbers 1979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 1989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson CollationKey n1String, n2String; 2009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (kIndex == 0) 2029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n1String = (CollationKey) n1.m_key1Value; 2049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n2String = (CollationKey) n2.m_key1Value; 2059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else if (kIndex == 1) 2079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n1String = (CollationKey) n1.m_key2Value; 2099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n2String = (CollationKey) n2.m_key2Value; 2109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /* Leave this in case we decide to use an array later 2139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (kIndex < maxkey) 2149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson String n1String = (String)n1.m_keyValue[kIndex]; 2169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson String n2String = (String)n2.m_keyValue[kIndex]; 2179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson }*/ 2189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 2199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Get values dynamically 2229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node, 2239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson k.m_namespaceContext); 2249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node, 2259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson k.m_namespaceContext); 2269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n1String = k.m_col.getCollationKey(r1.str()); 2289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson n2String = k.m_col.getCollationKey(r2.str()); 2299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Use collation keys for faster compare, but note that whitespaces 2329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // etc... are treated differently from if we were comparing Strings. 2339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson result = n1String.compareTo(n2String); 2349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson //Process caseOrder parameter 2369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (k.m_caseOrderUpper) 2379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson String tempN1 = n1String.getSourceString().toLowerCase(); 2399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson String tempN2 = n2String.getSourceString().toLowerCase(); 2409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (tempN1.equals(tempN2)) 2429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson //java defaults to upper case is greater. 2459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson result = result == 0 ? 0 : -result; 2469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson //Process order parameter 2509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (k.m_descending) 2519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson result = -result; 2539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } //end else 2559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (0 == result) 2579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((kIndex + 1) < m_keys.size()) 2599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson result = compare(n1, n2, kIndex + 1, support); 2619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (0 == result) 2659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // I shouldn't have to do this except that there seems to 2689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // be a glitch in the mergesort 2699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // if(r1.getType() == r1.CLASS_NODESET) 2709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // { 2719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson DTM dtm = support.getDTM(n1.m_node); // %OPT% 2729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson result = dtm.isNodeAfter(n1.m_node, n2.m_node) ? -1 : 1; 2739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // } 2759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return result; 2789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * This implements a standard Mergesort, as described in 2829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Robert Sedgewick's Algorithms book. This is a better 2839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * sort for our purpose than the Quicksort because it 2849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * maintains the original document order of the input if 2859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the order isn't changed by the sort. 2869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param a First vector of nodes to compare 2889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param b Second vector of nodes to compare 2899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param l Left boundary of partition 2909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param r Right boundary of partition 2919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param support XPath context to use 2929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws TransformerException 2949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson void mergesort(Vector a, Vector b, int l, int r, XPathContext support) 2969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throws TransformerException 2979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((r - l) > 0) 3009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int m = (r + l) / 2; 3029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson mergesort(a, b, l, m, support); 3049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson mergesort(a, b, m + 1, r, support); 3059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int i, j, k; 3079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (i = m; i >= l; i--) 3099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // b[i] = a[i]; 3129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Use insert if we need to increment vector size. 3139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (i >= b.size()) 3149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson b.insertElementAt(a.elementAt(i), i); 3159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 3169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson b.setElementAt(a.elementAt(i), i); 3179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson i = l; 3209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (j = (m + 1); j <= r; j++) 3229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // b[r+m+1-j] = a[j]; 3259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (r + m + 1 - j >= b.size()) 3269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson b.insertElementAt(a.elementAt(j), r + m + 1 - j); 3279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 3289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson b.setElementAt(a.elementAt(j), r + m + 1 - j); 3299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson j = r; 3329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int compVal; 3349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (k = l; k <= r; k++) 3369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // if(b[i] < b[j]) 3399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (i == j) 3409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson compVal = -1; 3419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 3429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson compVal = compare((NodeCompareElem) b.elementAt(i), 3439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson (NodeCompareElem) b.elementAt(j), 0, support); 3449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (compVal < 0) 3469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // a[k]=b[i]; 3499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson a.setElementAt(b.elementAt(i), k); 3509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson i++; 3529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else if (compVal > 0) 3549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // a[k]=b[j]; 3579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson a.setElementAt(b.elementAt(j), k); 3589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson j--; 3609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * This is a generic version of C.A.R Hoare's Quick Sort 3679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * algorithm. This will handle arrays that are already 3689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * sorted, and arrays with duplicate keys.<BR> 3699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * If you think of a one dimensional array as going from 3719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the lowest index on the left to the highest index on the right 3729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * then the parameters to this function are lowest index or 3739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * left and highest index or right. The first time you call 3749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * this function it will be with the parameters 0, a.length - 1. 3759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param v a vector of integers 3779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param lo0 left boundary of array partition 3789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param hi0 right boundary of array partition 3799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /* private void QuickSort2(Vector v, int lo0, int hi0, XPathContext support) 3839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throws javax.xml.transform.TransformerException, 3849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson java.net.MalformedURLException, 3859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson java.io.FileNotFoundException, 3869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson java.io.IOException 3879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int lo = lo0; 3899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int hi = hi0; 3909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ( hi0 > lo0) 3929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Arbitrarily establishing partition element as the midpoint of 3949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // the array. 3959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson Node midNode = (Node)v.elementAt( ( lo0 + hi0 ) / 2 ); 3969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // loop through the array until indices cross 3989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson while( lo <= hi ) 3999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // find the first element that is greater than or equal to 4019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // the partition element starting from the left Index. 4029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson while( (lo < hi0) && (compare((Node)v.elementAt(lo), midNode, 0, support) < 0) ) 4039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ++lo; 4059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } // end while 4069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // find an element that is smaller than or equal to 4089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // the partition element starting from the right Index. 4099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson while( (hi > lo0) && (compare((Node)v.elementAt(hi), midNode, 0, support) > 0) ) 4109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson --hi; 4129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // if the indexes have not crossed, swap 4159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if( lo <= hi ) 4169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson swap(v, lo, hi); 4189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ++lo; 4199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson --hi; 4209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // If the right index has not reached the left side of array 4249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // must now sort the left partition. 4259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if( lo0 < hi ) 4269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson QuickSort2( v, lo0, hi, support ); 4289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // If the left index has not reached the right side of array 4319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // must now sort the right partition. 4329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if( lo < hi0 ) 4339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson QuickSort2( v, lo, hi0, support ); 4359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } // end QuickSort2 */ 4389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// /** 4409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// * Simple function to swap two elements in 4419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// * a vector. 4429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// * 4439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// * @param v Vector of nodes to swap 4449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// * @param i Index of first node to swap 4459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// * @param i Index of second node to swap 4469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// */ 4479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// private void swap(Vector v, int i, int j) 4489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// { 4499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// 4509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// int node = (Node) v.elementAt(i); 4519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// 4529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// v.setElementAt(v.elementAt(j), i); 4539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// v.setElementAt(node, j); 4549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson// } 4559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 4579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * This class holds the value(s) from executing the given 4589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * node against the sort key(s). 4599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @xsl.usage internal 4609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 4619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson class NodeCompareElem 4629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Current node */ 4659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int m_node; 4669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** This maxkey value was chosen arbitrarily. We are assuming that the 4689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // maxkey + 1 keys will only hit fairly rarely and therefore, we 4699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // will get the node values for those keys dynamically. 4709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 4719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int maxkey = 2; 4729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Keep this in case we decide to use an array. Right now 4749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // using two variables is cheaper. 4759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson //Object[] m_KeyValue = new Object[2]; 4769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Value from first sort key */ 4789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson Object m_key1Value; 4799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Value from second sort key */ 4819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson Object m_key2Value; 4829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 4849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Constructor NodeCompareElem 4859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param node Current node 4889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws javax.xml.transform.TransformerException 4909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 4919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson NodeCompareElem(int node) throws javax.xml.transform.TransformerException 4929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_node = node; 4949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (!m_keys.isEmpty()) 4969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson NodeSortKey k1 = (NodeSortKey) m_keys.elementAt(0); 4989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson XObject r = k1.m_selectPat.execute(m_execContext, node, 4999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson k1.m_namespaceContext); 5009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson double d; 5029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (k1.m_treatAsNumbers) 5049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson d = r.num(); 5069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Can't use NaN for compare. They are never equal. Use zero instead. 5089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_key1Value = new Double(d); 5099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 5119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_key1Value = k1.m_col.getCollationKey(r.str()); 5139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (r.getType() == XObject.CLASS_NODESET) 5169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // %REVIEW% 5189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson DTMIterator ni = ((XNodeSet)r).iterRaw(); 5199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int current = ni.getCurrentNode(); 5209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(DTM.NULL == current) 5219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson current = ni.nextNode(); 5229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // if (ni instanceof ContextNodeList) // %REVIEW% 5249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // tryNextKey = (DTM.NULL != current); 5259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // else abdicate... should never happen, but... -sb 5279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (m_keys.size() > 1) 5309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson NodeSortKey k2 = (NodeSortKey) m_keys.elementAt(1); 5329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson XObject r2 = k2.m_selectPat.execute(m_execContext, node, 5349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson k2.m_namespaceContext); 5359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (k2.m_treatAsNumbers) { 5379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson d = r2.num(); 5389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_key2Value = new Double(d); 5399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } else { 5409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_key2Value = k2.m_col.getCollationKey(r2.str()); 5419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /* Leave this in case we decide to use an array later 5459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson while (kIndex <= m_keys.size() && kIndex < maxkey) 5469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson NodeSortKey k = (NodeSortKey)m_keys.elementAt(kIndex); 5489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson XObject r = k.m_selectPat.execute(m_execContext, node, k.m_namespaceContext); 5499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(k.m_treatAsNumbers) 5509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_KeyValue[kIndex] = r.num(); 5519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 5529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_KeyValue[kIndex] = r.str(); 5539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } */ 5549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } // end if not empty 5559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } // end NodeCompareElem class 5579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson} 558