KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > icl > saxon > expr > SortKeyEnumeration


1 package com.icl.saxon.expr;
2 import com.icl.saxon.*;
3 import com.icl.saxon.om.*;
4 import com.icl.saxon.sort.*;
5 //import java.util.*;
6
7 /**
8 * A SortKeyEnumeration is NodeEnumeration that delivers the nodes sorted according to
9 * a specified sort key. <BR>
10 *
11 */
12
13 public final class SortKeyEnumeration
14         implements NodeEnumeration, LastPositionFinder, Sortable {
15
16
17     // the nodes to be sorted
18 protected NodeEnumeration base;
19     
20     // the sort key definitions
21 private SortKeyDefinition[] sortkeys;
22     
23     // The nodes and keys are read into an array (nodeKeys) for sorting. This
24 // array contains one "record" representing each node: the "record" contains
25 // first, the NodeInfo itself, then an entry for each of its sort keys, in turn
26 private int recordSize;
27     private Object JavaDoc[] nodeKeys;
28     
29     // The number of nodes to be sorted. -1 means not yet known.
30 private int count = -1;
31     
32     // The next node to be delivered from the sorted enumeration
33 private int index = 0;
34     
35     // The context for the evaluation of sort keys
36 private Context context;
37     private Controller controller;
38     private Comparer[] keyComparers;
39
40     public SortKeyEnumeration(Context context, NodeEnumeration _base,
41                                 SortKeyDefinition[] sortkeys)
42     throws XPathException {
43         this.context = context.newContext();
44         this.controller = context.getController();
45         this.base = _base;
46         this.sortkeys = sortkeys;
47         recordSize = sortkeys.length + 1;
48
49         keyComparers = new Comparer[sortkeys.length];
50         for (int i=0; i<sortkeys.length; i++) {
51             keyComparers[i] = sortkeys[i].getComparer(context);
52         }
53         
54         // If any sortkey depends on position(), we must ensure the base enumeration is
55 // in document order. If it uses last() (unlikely), we must ensure that the number
56 // of nodes is known, so we sort it in this case also
57 if (!base.isSorted()) {
58             boolean mustBeSorted = false;
59             for (int i=0; i<sortkeys.length; i++) {
60                 SortKeyDefinition sk = sortkeys[i];
61                 Expression k = sk.getSortKey();
62                 if ((k.getDependencies() & (Context.POSITION | Context.LAST)) != 0) {
63                     mustBeSorted = true;
64                     break;
65                 }
66             }
67             if (mustBeSorted) {
68                 NodeSetExtent nsv = new NodeSetExtent(base, controller);
69                 nsv.sort();
70                 base = nsv.enumerate();
71             }
72         }
73     }
74
75     /**
76     * Determine whether there are more nodes
77     */
78
79     public boolean hasMoreElements() {
80         if (count<0) {
81             return base.hasMoreElements();
82         } else {
83             return index<count;
84         }
85     }
86
87     /**
88     * Get the next node, in sorted order
89     */
90
91     public NodeInfo nextElement() throws XPathException {
92         if (count<0) {
93             doSort();
94         }
95         return (NodeInfo)nodeKeys[(index++)*recordSize];
96     }
97
98     public boolean isSorted() {
99         return true;
100     }
101
102     public boolean isReverseSorted() {
103         return false;
104     }
105
106     public boolean isPeer() {
107         return base.isPeer();
108     }
109
110     public int getLastPosition() throws XPathException {
111         if (base instanceof LastPositionFinder && !(base instanceof LookaheadEnumerator)) {
112             return ((LastPositionFinder)base).getLastPosition();
113         }
114         if (count<0) doSort();
115         return count;
116     }
117
118     private void buildArray() throws XPathException {
119         int allocated;
120         if (base instanceof LastPositionFinder && !(base instanceof LookaheadEnumerator)) {
121             allocated = ((LastPositionFinder)base).getLastPosition();
122             context.setLast(allocated);
123         } else {
124             allocated = 100;
125         }
126         nodeKeys = new Object JavaDoc[allocated * recordSize];
127         count = 0;
128
129         // initialise the array with data
130
131         while (base.hasMoreElements()) {
132             NodeInfo node = base.nextElement();
133             if (count==allocated) {
134                 allocated *= 2;
135                 Object JavaDoc[] nk2 = new Object JavaDoc[allocated * recordSize];
136                 System.arraycopy(nodeKeys, 0, nk2, 0, count * recordSize);
137                 nodeKeys = nk2;
138             }
139             context.setCurrentNode(node);
140             context.setContextNode(node);
141             context.setPosition(count+1);
142
143             int k = count*recordSize;
144             nodeKeys[k] = node;
145             for (int n=0; n<sortkeys.length; n++) {
146                 nodeKeys[k+n+1] = sortkeys[n].getSortKey().evaluateAsString(context);
147             }
148             count++;
149         }
150         //diag();
151 }
152     
153     private void diag() {
154         System.err.println("Diagnostic print of keys");
155         for (int i=0; i<(count*recordSize); i++) {
156             System.err.println(i + " : " + nodeKeys[i]);
157         }
158     }
159             
160
161     private void doSort() throws XPathException {
162         buildArray();
163         if (count<2) return;
164         
165         // sort the array
166
167         QuickSort.sort(this, 0, count-1);
168     }
169     
170     /**
171     * Compare two nodes in sorted sequence
172     * (needed to implement the Sortable interface)
173     */
174     
175     public int compare(int a, int b) {
176         int a1 = a*recordSize + 1;
177         int b1 = b*recordSize + 1;
178         for (int i=0; i<sortkeys.length; i++) {
179             Comparer c = keyComparers[i];
180             int comp = c.compare(nodeKeys[a1+i], nodeKeys[b1+i]);
181             if (comp!=0) return comp;
182         }
183         // all sort keys equal: return the nodes in document order
184 return controller.compare(
185                     (NodeInfo)nodeKeys[a1-1],
186                     (NodeInfo)nodeKeys[b1-1]);
187     }
188
189     /**
190     * Swap two nodes (needed to implement the Sortable interface)
191     */
192     
193     public void swap(int a, int b) {
194         int a1 = a*recordSize;
195         int b1 = b*recordSize;
196         for (int i=0; i<recordSize; i++) {
197             Object JavaDoc temp = nodeKeys[a1+i];
198             nodeKeys[a1+i] = nodeKeys[b1+i];
199             nodeKeys[b1+i] = temp;
200         }
201     }
202
203
204 }
205     
206
207 //
208 // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
209 // you may not use this file except in compliance with the License. You may obtain a copy of the
210 // License at http://www.mozilla.org/MPL/
211 //
212 // Software distributed under the License is distributed on an "AS IS" basis,
213 // WITHOUT WARRANTY OF ANY KIND, either express or implied.
214 // See the License for the specific language governing rights and limitations under the License.
215 //
216 // The Original Code is: all this file.
217 //
218 // The Initial Developer of the Original Code is
219 // Michael Kay of International Computers Limited (mhkay@iclway.co.uk).
220 //
221 // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
222 //
223 // Contributor(s): none.
224 //
225
Popular Tags