SortedIterator


1   package net.sf.saxon.sort;
2   import net.sf.saxon.expr.LastPositionFinder;
3   import net.sf.saxon.expr.XPathContext;
4   import net.sf.saxon.om.Item;
5   import net.sf.saxon.om.SequenceIterator;
6   import net.sf.saxon.trace.Location;
7   import net.sf.saxon.trans.DynamicError;
8   import net.sf.saxon.trans.XPathException;
9   
10  import java.util.Comparator  ;
11  
12  /**
13  * Class to do a sorted iteration
14  */
15  
16  public class SortedIterator implements SequenceIterator, LastPositionFinder, Sortable {
17  
18      // the items to be sorted
19      protected SequenceIterator base;
20  
21      // the sort key definitions
22      protected FixedSortKeyDefinition[] sortkeys;
23  
24      // The items and keys are read into an array (nodeKeys) for sorting. This
25      // array contains one "record" representing each node: the "record" contains
26      // first, the Item itself, then an entry for each of its sort keys, in turn;
27      // the last sort key is the position of the Item in the original sequence.
28      protected int recordSize;
29      protected Object  [] nodeKeys;
30  
31      // The number of items to be sorted. -1 means not yet known.
32      protected int count = -1;
33  
34      // The next item to be delivered from the sorted iteration
35      protected int index = 0;
36  
37      // The context for the evaluation of sort keys
38      protected XPathContext context;
39      private Comparator  [] keyComparers;
40  
41      private SortedIterator(){}
42  
43      public SortedIterator(XPathContext context, SequenceIterator base,
44                                  FixedSortKeyDefinition[] sortkeys)
45      throws XPathException {
46          this.context = context.newMinorContext();
47          this.context.setOriginatingConstructType(Location.SORT_KEY);
48          this.context.setCurrentIterator(base);
49          this.base = base;
50          this.sortkeys = sortkeys;
51          recordSize = sortkeys.length + 2;
52  
53          keyComparers = new Comparator  [sortkeys.length];
54          for (int i=0; i<sortkeys.length; i++) {
55              keyComparers[i] = sortkeys[i].getComparer(context);
56          }
57  
58          // Avoid doing the sort until the user wants the first item. This is because
59          // sometimes the user only wants to know whether the collection is empty.
60      }
61  
62      /**
63      * Get the next item, in sorted order
64      */
65  
66      public Item next() throws XPathException {
67          if (index < 0) {
68              return null;
69          }
70          if (count<0) {
71              doSort();
72          }
73          if (index < count) {
74              return (Item)nodeKeys[(index++)*recordSize];
75          } else {
76              index = -1;
77              return null;
78          }
79      }
80  
81      public Item current() {
82          if (index < 1) {
83              return null;
84          }
85          return (Item)nodeKeys[(index-1)*recordSize];
86      }
87  
88      public int position() {
89          return index;
90      }
91  
92      public int getLastPosition() throws XPathException {
93          if (count<0) {
94              doSort();
95          }
96          return count;
97      }
98  
99      public SequenceIterator getAnother() throws XPathException {
100         // make sure the sort has been done, so that multiple iterators over the
101         // same sorted data only do the sorting once.
102         if (count<0) {
103             doSort();
104         }
105         SortedIterator s = new SortedIterator();
106         // the new iterator is the same as the old ...
107         s.base = base.getAnother();
108         s.sortkeys = sortkeys;
109         s.recordSize = recordSize;
110         s.nodeKeys = nodeKeys;
111         s.count = count;
112         s.context = context;
113         s.keyComparers = keyComparers;
114         // ... except for its start position.
115         s.index = 0;
116         return s;
117     }
118 
119     /**
120      * Get properties of this iterator, as a bit-significant integer.
121      *
122      * @return the properties of this iterator. This will be some combination of
123      *         properties such as {@link GROUNDED}, {@link LAST_POSITION_FINDER},
124      *         and {@link LOOKAHEAD}. It is always
125      *         acceptable to return the value zero, indicating that there are no known special properties.
126      *         It is acceptable for the properties of the iterator to change depending on its state.
127      */
128 
129     public int getProperties() {
130         return LAST_POSITION_FINDER;
131     }
132 
133     protected void buildArray() throws XPathException {
134         int allocated;
135         if ((base.getProperties() & SequenceIterator.LAST_POSITION_FINDER) != 0) {
136             allocated = ((LastPositionFinder)base).getLastPosition();
137         } else {
138             allocated = 100;
139         }
140 
141         nodeKeys = new Object  [allocated * recordSize];
142         count = 0;
143 
144         XPathContext c2 = context;
145 
146         // initialise the array with data
147 
148         while (true) {
149             Item item = base.next();
150             if (item == null) {
151                 break;
152             }
153             if (count==allocated) {
154                 allocated *= 2;
155                 Object  [] nk2 = new Object  [allocated * recordSize];
156                 System.arraycopy(nodeKeys, 0, nk2, 0, count * recordSize);
157                 nodeKeys = nk2;
158             }
159             int k = count*recordSize;
160             nodeKeys[k] = item;
161             // TODO: delay evaluating the sort keys until we know they are needed. Often the 2nd and subsequent
162             // sort key values will never be used. The only problem is with sort keys that depend on position().
163             for (int n=0; n<sortkeys.length; n++) {
164                 nodeKeys[k+n+1] = sortkeys[n].getSortKey().evaluateItem(c2);
165             }
166             // make the sort stable by adding the record number
167             nodeKeys[k+sortkeys.length+1] = new Integer  (count);
168             count++;
169         }
170     }
171 
172     private void doSort() throws XPathException {
173         buildArray();
174         if (count<2) return;
175 
176         // sort the array
177 
178         //QuickSort.sort(this, 0, count-1);
179         try {
180             GenericSorter.quickSort(0, count, this);
181         } catch (ClassCastException   e) {
182             DynamicError err = new DynamicError("Non-comparable types found while sorting: " + e.getMessage());
183             err.setErrorCode("XPTY0004");
184             // TODO: in XSLT, return error code XTDE1030 (test date905err)
185             throw err;
186         }
187         //GenericSorter.mergeSort(0, count, this);
188     }
189 
190     /**
191     * Compare two items in sorted sequence
192     * (needed to implement the Sortable interface)
193     */
194 
195     public int compare(int a, int b) {
196         int a1 = a*recordSize + 1;
197         int b1 = b*recordSize + 1;
198         for (int i=0; i<sortkeys.length; i++) {
199             int comp;
200             // System.err.println("Comparing " + nodeKeys[a1+i] + " with " + nodeKeys[b1+i]);
201             if (nodeKeys[a1+i] == null) {
202                 // first sort key value is ()
203                 comp = (nodeKeys[b1+i]==null ? 0 : (sortkeys[i].getEmptyFirst() ? -1 : +1));
204             } else if (nodeKeys[b1+i]==null) {
205                 // second sort key value is ()
206                 comp = (sortkeys[i].getEmptyFirst() ? +1 : -1);
207             } else {
208                 comp = keyComparers[i].compare(nodeKeys[a1+i], nodeKeys[b1+i]);
209             }
210             if (comp != 0) {
211                 // we have found a difference, so we can return
212                 return comp;
213             }
214         }
215 
216         // all sort keys equal: return the items in their original order
217 
218         return ((Integer  )nodeKeys[a1+sortkeys.length]).intValue() -
219                 ((Integer  )nodeKeys[b1+sortkeys.length]).intValue();
220     }
221 
222     /**
223     * Swap two items (needed to implement the Sortable interface)
224     */
225 
226     public void swap(int a, int b) {
227         int a1 = a*recordSize;
228         int b1 = b*recordSize;
229         for (int i=0; i<recordSize; i++) {
230             Object   temp = nodeKeys[a1+i];
231             nodeKeys[a1+i] = nodeKeys[b1+i];
232             nodeKeys[b1+i] = temp;
233         }
234     }
235 
236 }
237 
238 //
239 // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
240 // you may not use this file except in compliance with the License. You may obtain a copy of the
241 // License at http://www.mozilla.org/MPL/
242 //
243 // Software distributed under the License is distributed on an "AS IS" basis,
244 // WITHOUT WARRANTY OF ANY KIND, either express or implied.
245 // See the License for the specific language governing rights and limitations under the License.
246 //
247 // The Original Code is: all this file.
248 //
249 // The Initial Developer of the Original Code is Michael H. Kay.
250 //
251 // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
252 //
253 // Contributor(s): none.
254 //
255
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags