14c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson/* 24c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * Licensed to the Apache Software Foundation (ASF) under one 34c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * or more contributor license agreements. See the NOTICE file 44c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * distributed with this work for additional information 54c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * regarding copyright ownership. The ASF licenses this file 64c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * to you under the Apache License, Version 2.0 (the "License"); 74c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * you may not use this file except in compliance with the License. 84c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * You may obtain a copy of the License at 94c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 104c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 114c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 124c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * Unless required by applicable law or agreed to in writing, software 134c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 144c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 154c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * See the License for the specific language governing permissions and 164c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * limitations under the License. 174c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson */ 184c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson/* 194c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * $Id: NodeSorter.java 468645 2006-10-28 06:57:24Z minchau $ 204c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson */ 214c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilsonpackage org.apache.xalan.transformer; 224c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 234c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilsonimport java.text.CollationKey; 244c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilsonimport java.util.Vector; 254c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 264c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilsonimport javax.xml.transform.TransformerException; 274c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 284c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilsonimport org.apache.xml.dtm.DTM; 294c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilsonimport org.apache.xml.dtm.DTMIterator; 304c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilsonimport org.apache.xpath.XPathContext; 314c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilsonimport org.apache.xpath.objects.XNodeSet; 324c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilsonimport org.apache.xpath.objects.XObject; 334c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 344c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson/** 354c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * This class can sort vectors of DOM nodes according to a select pattern. 364c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @xsl.usage internal 374c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson */ 384c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilsonpublic class NodeSorter 394c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson{ 404c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 414c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** Current XPath context */ 424c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson XPathContext m_execContext; 434c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 444c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** Vector of NodeSortKeys */ 454c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson Vector m_keys; // vector of NodeSortKeys 464c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 474c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// /** 484c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// * TODO: Adjust this for locale. 494c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// */ 504c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// NumberFormat m_formatter = NumberFormat.getNumberInstance(); 514c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 524c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** 534c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * Construct a NodeSorter, passing in the XSL TransformerFactory 544c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * so it can know how to get the node data according to 554c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * the proper whitespace rules. 564c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 574c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param p Xpath context to use 584c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson */ 594c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson public NodeSorter(XPathContext p) 604c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 614c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson m_execContext = p; 624c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 634c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 644c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** 654c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * Given a vector of nodes, sort each node according to 664c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * the criteria in the keys. 674c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param v an vector of Nodes. 684c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param keys a vector of NodeSortKeys. 694c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param support XPath context to use 704c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 714c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @throws javax.xml.transform.TransformerException 724c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson */ 734c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson public void sort(DTMIterator v, Vector keys, XPathContext support) 744c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson throws javax.xml.transform.TransformerException 754c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 764c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 774c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson m_keys = keys; 784c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 794c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // QuickSort2(v, 0, v.size() - 1 ); 804c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson int n = v.getLength(); 814c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 824c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // %OPT% Change mergesort to just take a DTMIterator? 834c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // We would also have to adapt DTMIterator to have the function 844c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // of NodeCompareElem. 854c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 864c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // Create a vector of node compare elements 874c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // based on the input vector of nodes 884c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson Vector nodes = new Vector(); 894c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 904c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson for (int i = 0; i < n; i++) 914c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 924c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson NodeCompareElem elem = new NodeCompareElem(v.item(i)); 934c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 944c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson nodes.addElement(elem); 954c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 964c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 974c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson Vector scratchVector = new Vector(); 984c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 994c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson mergesort(nodes, scratchVector, 0, n - 1, support); 1004c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 1014c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // return sorted vector of nodes 1024c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson for (int i = 0; i < n; i++) 1034c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 1044c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson v.setItem(((NodeCompareElem) nodes.elementAt(i)).m_node, i); 1054c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 1064c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson v.setCurrentPos(0); 1074c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 1084c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // old code... 1094c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson //NodeVector scratchVector = new NodeVector(n); 1104c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson //mergesort(v, scratchVector, 0, n - 1, support); 1114c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 1124c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 1134c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** 1144c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * Return the results of a compare of two nodes. 1154c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * TODO: Optimize compare -- cache the getStringExpr results, key by m_selectPat + hash of node. 1164c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 1174c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param n1 First node to use in compare 1184c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param n2 Second node to use in compare 1194c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param kIndex Index of NodeSortKey to use for sort 1204c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param support XPath context to use 1214c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 1224c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @return The results of the compare of the two nodes. 1234c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 1244c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @throws TransformerException 1254c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson */ 1264c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson int compare( 1274c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson NodeCompareElem n1, NodeCompareElem n2, int kIndex, XPathContext support) 1284c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson throws TransformerException 1294c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 1304c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 1314c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson int result = 0; 1324c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson NodeSortKey k = (NodeSortKey) m_keys.elementAt(kIndex); 1334c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 1344c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (k.m_treatAsNumbers) 1354c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 1364c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson double n1Num, n2Num; 1374c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 1384c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (kIndex == 0) 1394c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 1404c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n1Num = ((Double) n1.m_key1Value).doubleValue(); 1414c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n2Num = ((Double) n2.m_key1Value).doubleValue(); 1424c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 1434c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else if (kIndex == 1) 1444c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 1454c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n1Num = ((Double) n1.m_key2Value).doubleValue(); 1464c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n2Num = ((Double) n2.m_key2Value).doubleValue(); 1474c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 1484c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 1494c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /* Leave this in case we decide to use an array later 1504c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (kIndex < maxkey) 1514c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 1524c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson double n1Num = (double)n1.m_keyValue[kIndex]; 1534c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson double n2Num = (double)n2.m_keyValue[kIndex]; 1544c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson }*/ 1554c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else 1564c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 1574c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 1584c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // Get values dynamically 1594c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node, 1604c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson k.m_namespaceContext); 1614c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node, 1624c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson k.m_namespaceContext); 1634c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n1Num = r1.num(); 1644c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 1654c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // Can't use NaN for compare. They are never equal. Use zero instead. 1664c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // That way we can keep elements in document order. 1674c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson //n1Num = Double.isNaN(d) ? 0.0 : d; 1684c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n2Num = r2.num(); 1694c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson //n2Num = Double.isNaN(d) ? 0.0 : d; 1704c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 1714c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 1724c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if ((n1Num == n2Num) && ((kIndex + 1) < m_keys.size())) 1734c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 1744c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson result = compare(n1, n2, kIndex + 1, support); 1754c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 1764c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else 1774c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 1784c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson double diff; 1794c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (Double.isNaN(n1Num)) 1804c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 1814c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (Double.isNaN(n2Num)) 1824c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson diff = 0.0; 1834c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else 1844c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson diff = -1; 1854c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 1864c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else if (Double.isNaN(n2Num)) 1874c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson diff = 1; 1884c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else 1894c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson diff = n1Num - n2Num; 1904c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 1914c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // process order parameter 1924c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson result = (int) ((diff < 0.0) 1934c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson ? (k.m_descending ? 1 : -1) 1944c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson : (diff > 0.0) ? (k.m_descending ? -1 : 1) : 0); 1954c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 1964c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } // end treat as numbers 1974c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else 1984c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 1994c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson CollationKey n1String, n2String; 2004c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2014c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (kIndex == 0) 2024c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 2034c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n1String = (CollationKey) n1.m_key1Value; 2044c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n2String = (CollationKey) n2.m_key1Value; 2054c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 2064c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else if (kIndex == 1) 2074c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 2084c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n1String = (CollationKey) n1.m_key2Value; 2094c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n2String = (CollationKey) n2.m_key2Value; 2104c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 2114c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2124c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /* Leave this in case we decide to use an array later 2134c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (kIndex < maxkey) 2144c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 2154c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson String n1String = (String)n1.m_keyValue[kIndex]; 2164c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson String n2String = (String)n2.m_keyValue[kIndex]; 2174c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson }*/ 2184c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else 2194c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 2204c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2214c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // Get values dynamically 2224c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node, 2234c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson k.m_namespaceContext); 2244c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node, 2254c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson k.m_namespaceContext); 2264c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2274c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n1String = k.m_col.getCollationKey(r1.str()); 2284c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson n2String = k.m_col.getCollationKey(r2.str()); 2294c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 2304c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2314c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // Use collation keys for faster compare, but note that whitespaces 2324c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // etc... are treated differently from if we were comparing Strings. 2334c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson result = n1String.compareTo(n2String); 2344c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2354c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson //Process caseOrder parameter 2364c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (k.m_caseOrderUpper) 2374c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 2384c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson String tempN1 = n1String.getSourceString().toLowerCase(); 2394c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson String tempN2 = n2String.getSourceString().toLowerCase(); 2404c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2414c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (tempN1.equals(tempN2)) 2424c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 2434c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2444c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson //java defaults to upper case is greater. 2454c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson result = result == 0 ? 0 : -result; 2464c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 2474c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 2484c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2494c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson //Process order parameter 2504c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (k.m_descending) 2514c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 2524c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson result = -result; 2534c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 2544c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } //end else 2554c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2564c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (0 == result) 2574c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 2584c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if ((kIndex + 1) < m_keys.size()) 2594c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 2604c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson result = compare(n1, n2, kIndex + 1, support); 2614c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 2624c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 2634c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2644c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (0 == result) 2654c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 2664c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2674c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // I shouldn't have to do this except that there seems to 2684c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // be a glitch in the mergesort 2694c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // if(r1.getType() == r1.CLASS_NODESET) 2704c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // { 2714c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson DTM dtm = support.getDTM(n1.m_node); // %OPT% 2724c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson result = dtm.isNodeAfter(n1.m_node, n2.m_node) ? -1 : 1; 2734c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2744c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // } 2754c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 2764c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2774c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson return result; 2784c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 2794c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2804c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** 2814c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * This implements a standard Mergesort, as described in 2824c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * Robert Sedgewick's Algorithms book. This is a better 2834c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * sort for our purpose than the Quicksort because it 2844c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * maintains the original document order of the input if 2854c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * the order isn't changed by the sort. 2864c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 2874c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param a First vector of nodes to compare 2884c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param b Second vector of nodes to compare 2894c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param l Left boundary of partition 2904c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param r Right boundary of partition 2914c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param support XPath context to use 2924c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 2934c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @throws TransformerException 2944c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson */ 2954c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson void mergesort(Vector a, Vector b, int l, int r, XPathContext support) 2964c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson throws TransformerException 2974c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 2984c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 2994c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if ((r - l) > 0) 3004c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 3014c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson int m = (r + l) / 2; 3024c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3034c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson mergesort(a, b, l, m, support); 3044c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson mergesort(a, b, m + 1, r, support); 3054c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3064c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson int i, j, k; 3074c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3084c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson for (i = m; i >= l; i--) 3094c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 3104c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3114c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // b[i] = a[i]; 3124c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // Use insert if we need to increment vector size. 3134c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (i >= b.size()) 3144c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson b.insertElementAt(a.elementAt(i), i); 3154c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else 3164c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson b.setElementAt(a.elementAt(i), i); 3174c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 3184c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3194c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson i = l; 3204c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3214c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson for (j = (m + 1); j <= r; j++) 3224c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 3234c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3244c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // b[r+m+1-j] = a[j]; 3254c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (r + m + 1 - j >= b.size()) 3264c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson b.insertElementAt(a.elementAt(j), r + m + 1 - j); 3274c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else 3284c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson b.setElementAt(a.elementAt(j), r + m + 1 - j); 3294c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 3304c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3314c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson j = r; 3324c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3334c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson int compVal; 3344c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3354c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson for (k = l; k <= r; k++) 3364c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 3374c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3384c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // if(b[i] < b[j]) 3394c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (i == j) 3404c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson compVal = -1; 3414c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else 3424c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson compVal = compare((NodeCompareElem) b.elementAt(i), 3434c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson (NodeCompareElem) b.elementAt(j), 0, support); 3444c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3454c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (compVal < 0) 3464c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 3474c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3484c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // a[k]=b[i]; 3494c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson a.setElementAt(b.elementAt(i), k); 3504c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3514c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson i++; 3524c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 3534c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else if (compVal > 0) 3544c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 3554c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3564c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // a[k]=b[j]; 3574c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson a.setElementAt(b.elementAt(j), k); 3584c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3594c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson j--; 3604c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 3614c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 3624c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 3634c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 3644c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3654c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** 3664c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * This is a generic version of C.A.R Hoare's Quick Sort 3674c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * algorithm. This will handle arrays that are already 3684c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * sorted, and arrays with duplicate keys.<BR> 3694c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 3704c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * If you think of a one dimensional array as going from 3714c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * the lowest index on the left to the highest index on the right 3724c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * then the parameters to this function are lowest index or 3734c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * left and highest index or right. The first time you call 3744c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * this function it will be with the parameters 0, a.length - 1. 3754c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 3764c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param v a vector of integers 3774c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param lo0 left boundary of array partition 3784c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param hi0 right boundary of array partition 3794c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 3804c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson */ 3814c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3824c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /* private void QuickSort2(Vector v, int lo0, int hi0, XPathContext support) 3834c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson throws javax.xml.transform.TransformerException, 3844c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson java.net.MalformedURLException, 3854c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson java.io.FileNotFoundException, 3864c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson java.io.IOException 3874c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 3884c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson int lo = lo0; 3894c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson int hi = hi0; 3904c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3914c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if ( hi0 > lo0) 3924c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 3934c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // Arbitrarily establishing partition element as the midpoint of 3944c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // the array. 3954c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson Node midNode = (Node)v.elementAt( ( lo0 + hi0 ) / 2 ); 3964c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 3974c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // loop through the array until indices cross 3984c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson while( lo <= hi ) 3994c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 4004c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // find the first element that is greater than or equal to 4014c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // the partition element starting from the left Index. 4024c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson while( (lo < hi0) && (compare((Node)v.elementAt(lo), midNode, 0, support) < 0) ) 4034c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 4044c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson ++lo; 4054c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } // end while 4064c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4074c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // find an element that is smaller than or equal to 4084c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // the partition element starting from the right Index. 4094c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson while( (hi > lo0) && (compare((Node)v.elementAt(hi), midNode, 0, support) > 0) ) 4104c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 4114c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson --hi; 4124c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 4134c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4144c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // if the indexes have not crossed, swap 4154c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if( lo <= hi ) 4164c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 4174c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson swap(v, lo, hi); 4184c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson ++lo; 4194c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson --hi; 4204c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 4214c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 4224c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4234c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // If the right index has not reached the left side of array 4244c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // must now sort the left partition. 4254c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if( lo0 < hi ) 4264c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 4274c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson QuickSort2( v, lo0, hi, support ); 4284c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 4294c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4304c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // If the left index has not reached the right side of array 4314c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // must now sort the right partition. 4324c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if( lo < hi0 ) 4334c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 4344c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson QuickSort2( v, lo, hi0, support ); 4354c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 4364c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 4374c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } // end QuickSort2 */ 4384c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4394c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// /** 4404c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// * Simple function to swap two elements in 4414c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// * a vector. 4424c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// * 4434c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// * @param v Vector of nodes to swap 4444c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// * @param i Index of first node to swap 4454c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// * @param i Index of second node to swap 4464c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// */ 4474c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// private void swap(Vector v, int i, int j) 4484c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// { 4494c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// 4504c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// int node = (Node) v.elementAt(i); 4514c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// 4524c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// v.setElementAt(v.elementAt(j), i); 4534c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// v.setElementAt(node, j); 4544c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson// } 4554c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4564c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** 4574c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * This class holds the value(s) from executing the given 4584c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * node against the sort key(s). 4594c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @xsl.usage internal 4604c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson */ 4614c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson class NodeCompareElem 4624c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 4634c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4644c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** Current node */ 4654c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson int m_node; 4664c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4674c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** This maxkey value was chosen arbitrarily. We are assuming that the 4684c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // maxkey + 1 keys will only hit fairly rarely and therefore, we 4694c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // will get the node values for those keys dynamically. 4704c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson */ 4714c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson int maxkey = 2; 4724c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4734c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // Keep this in case we decide to use an array. Right now 4744c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // using two variables is cheaper. 4754c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson //Object[] m_KeyValue = new Object[2]; 4764c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4774c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** Value from first sort key */ 4784c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson Object m_key1Value; 4794c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4804c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** Value from second sort key */ 4814c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson Object m_key2Value; 4824c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4834c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /** 4844c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * Constructor NodeCompareElem 4854c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 4864c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 4874c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @param node Current node 4884c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * 4894c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson * @throws javax.xml.transform.TransformerException 4904c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson */ 4914c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson NodeCompareElem(int node) throws javax.xml.transform.TransformerException 4924c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 4934c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson m_node = node; 4944c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 4954c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (!m_keys.isEmpty()) 4964c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 4974c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson NodeSortKey k1 = (NodeSortKey) m_keys.elementAt(0); 4984c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson XObject r = k1.m_selectPat.execute(m_execContext, node, 4994c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson k1.m_namespaceContext); 5004c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 5014c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson double d; 5024c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 5034c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (k1.m_treatAsNumbers) 5044c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 5054c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson d = r.num(); 5064c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 5074c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // Can't use NaN for compare. They are never equal. Use zero instead. 5084c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson m_key1Value = new Double(d); 5094c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 5104c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else 5114c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 5124c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson m_key1Value = k1.m_col.getCollationKey(r.str()); 5134c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 5144c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 5154c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (r.getType() == XObject.CLASS_NODESET) 5164c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 5174c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // %REVIEW% 5184c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson DTMIterator ni = ((XNodeSet)r).iterRaw(); 5194c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson int current = ni.getCurrentNode(); 5204c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if(DTM.NULL == current) 5214c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson current = ni.nextNode(); 5224c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 5234c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // if (ni instanceof ContextNodeList) // %REVIEW% 5244c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // tryNextKey = (DTM.NULL != current); 5254c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 5264c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson // else abdicate... should never happen, but... -sb 5274c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 5284c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 5294c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (m_keys.size() > 1) 5304c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 5314c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson NodeSortKey k2 = (NodeSortKey) m_keys.elementAt(1); 5324c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 5334c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson XObject r2 = k2.m_selectPat.execute(m_execContext, node, 5344c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson k2.m_namespaceContext); 5354c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 5364c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if (k2.m_treatAsNumbers) { 5374c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson d = r2.num(); 5384c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson m_key2Value = new Double(d); 5394c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } else { 5404c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson m_key2Value = k2.m_col.getCollationKey(r2.str()); 5414c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 5424c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 5434c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson 5444c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson /* Leave this in case we decide to use an array later 5454c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson while (kIndex <= m_keys.size() && kIndex < maxkey) 5464c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson { 5474c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson NodeSortKey k = (NodeSortKey)m_keys.elementAt(kIndex); 5484c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson XObject r = k.m_selectPat.execute(m_execContext, node, k.m_namespaceContext); 5494c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson if(k.m_treatAsNumbers) 5504c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson m_KeyValue[kIndex] = r.num(); 5514c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson else 5524c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson m_KeyValue[kIndex] = r.str(); 5534c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } */ 5544c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } // end if not empty 5554c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } 5564c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson } // end NodeCompareElem class 5574c7a0d97cf2b27790e6236965a1d798d710d7ec7Jesse Wilson} 558