001: package net.sf.saxon.sort;
002:
003: import net.sf.saxon.expr.LastPositionFinder;
004: import net.sf.saxon.expr.XPathContext;
005: import net.sf.saxon.om.Item;
006: import net.sf.saxon.om.SequenceIterator;
007: import net.sf.saxon.trace.Location;
008: import net.sf.saxon.trans.DynamicError;
009: import net.sf.saxon.trans.XPathException;
010: import net.sf.saxon.Configuration;
011:
012: import java.util.Comparator;
013:
014: /**
015: * Class to do a sorted iteration
016: */
017:
018: public class SortedIterator implements SequenceIterator,
019: LastPositionFinder, Sortable {
020:
021: // the items to be sorted
022: protected SequenceIterator base;
023:
024: // the sort key definitions
025: protected FixedSortKeyDefinition[] sortkeys;
026:
027: // The items and keys are read into an array (nodeKeys) for sorting. This
028: // array contains one "record" representing each node: the "record" contains
029: // first, the Item itself, then an entry for each of its sort keys, in turn;
030: // the last sort key is the position of the Item in the original sequence.
031: protected int recordSize;
032: protected Object[] nodeKeys;
033:
034: // The number of items to be sorted. -1 means not yet known.
035: protected int count = -1;
036:
037: // The next item to be delivered from the sorted iteration
038: protected int index = 0;
039:
040: // The context for the evaluation of sort keys
041: protected XPathContext context;
042: private Comparator[] keyComparers;
043:
044: private SortedIterator() {
045: }
046:
047: public SortedIterator(XPathContext context, SequenceIterator base,
048: FixedSortKeyDefinition[] sortkeys) throws XPathException {
049: this .context = context.newMinorContext();
050: this .context.setOriginatingConstructType(Location.SORT_KEY);
051: this .context.setCurrentIterator(base);
052: this .base = base;
053: this .sortkeys = sortkeys;
054: recordSize = sortkeys.length + 2;
055:
056: keyComparers = new Comparator[sortkeys.length];
057: for (int i = 0; i < sortkeys.length; i++) {
058: keyComparers[i] = sortkeys[i].getComparer(context);
059: }
060:
061: // Avoid doing the sort until the user wants the first item. This is because
062: // sometimes the user only wants to know whether the collection is empty.
063: }
064:
065: /**
066: * Get the next item, in sorted order
067: */
068:
069: public Item next() throws XPathException {
070: if (index < 0) {
071: return null;
072: }
073: if (count < 0) {
074: doSort();
075: }
076: if (index < count) {
077: return (Item) nodeKeys[(index++) * recordSize];
078: } else {
079: index = -1;
080: return null;
081: }
082: }
083:
084: public Item current() {
085: if (index < 1) {
086: return null;
087: }
088: return (Item) nodeKeys[(index - 1) * recordSize];
089: }
090:
091: public int position() {
092: return index;
093: }
094:
095: public int getLastPosition() throws XPathException {
096: if (count < 0) {
097: doSort();
098: }
099: return count;
100: }
101:
102: public SequenceIterator getAnother() throws XPathException {
103: // make sure the sort has been done, so that multiple iterators over the
104: // same sorted data only do the sorting once.
105: if (count < 0) {
106: doSort();
107: }
108: SortedIterator s = new SortedIterator();
109: // the new iterator is the same as the old ...
110: s.base = base.getAnother();
111: s.sortkeys = sortkeys;
112: s.recordSize = recordSize;
113: s.nodeKeys = nodeKeys;
114: s.count = count;
115: s.context = context;
116: s.keyComparers = keyComparers;
117: // ... except for its start position.
118: s.index = 0;
119: return s;
120: }
121:
122: /**
123: * Get properties of this iterator, as a bit-significant integer.
124: *
125: * @return the properties of this iterator. This will be some combination of
126: * properties such as {@link GROUNDED}, {@link LAST_POSITION_FINDER},
127: * and {@link LOOKAHEAD}. It is always
128: * acceptable to return the value zero, indicating that there are no known special properties.
129: * It is acceptable for the properties of the iterator to change depending on its state.
130: */
131:
132: public int getProperties() {
133: return LAST_POSITION_FINDER;
134: }
135:
136: protected void buildArray() throws XPathException {
137: int allocated;
138: if ((base.getProperties() & SequenceIterator.LAST_POSITION_FINDER) != 0) {
139: allocated = ((LastPositionFinder) base).getLastPosition();
140: } else {
141: allocated = 100;
142: }
143:
144: nodeKeys = new Object[allocated * recordSize];
145: count = 0;
146:
147: XPathContext c2 = context;
148:
149: // initialise the array with data
150:
151: while (true) {
152: Item item = base.next();
153: if (item == null) {
154: break;
155: }
156: if (count == allocated) {
157: allocated *= 2;
158: Object[] nk2 = new Object[allocated * recordSize];
159: System.arraycopy(nodeKeys, 0, nk2, 0, count
160: * recordSize);
161: nodeKeys = nk2;
162: }
163: int k = count * recordSize;
164: nodeKeys[k] = item;
165: // TODO: delay evaluating the sort keys until we know they are needed. Often the 2nd and subsequent
166: // sort key values will never be used. The only problem is with sort keys that depend on position().
167: for (int n = 0; n < sortkeys.length; n++) {
168: nodeKeys[k + n + 1] = sortkeys[n].getSortKey()
169: .evaluateItem(c2);
170: }
171: // make the sort stable by adding the record number
172: nodeKeys[k + sortkeys.length + 1] = new Integer(count);
173: count++;
174: }
175: }
176:
177: private void doSort() throws XPathException {
178: buildArray();
179: if (count < 2)
180: return;
181:
182: // sort the array
183:
184: //QuickSort.sort(this, 0, count-1);
185: try {
186: GenericSorter.quickSort(0, count, this );
187: } catch (ClassCastException e) {
188: DynamicError err = new DynamicError(
189: "Non-comparable types found while sorting: "
190: + e.getMessage());
191: if (context.getController().getExecutable()
192: .getHostLanguage() == Configuration.XSLT) {
193: err.setErrorCode("XTDE1030");
194: } else {
195: err.setErrorCode("XPTY0004");
196: }
197: throw err;
198: }
199: //GenericSorter.mergeSort(0, count, this);
200: }
201:
202: /**
203: * Compare two items in sorted sequence
204: * (needed to implement the Sortable interface)
205: */
206:
207: public int compare(int a, int b) {
208: int a1 = a * recordSize + 1;
209: int b1 = b * recordSize + 1;
210: for (int i = 0; i < sortkeys.length; i++) {
211: int comp;
212: // System.err.println("Comparing " + nodeKeys[a1+i] + " with " + nodeKeys[b1+i]);
213: if (nodeKeys[a1 + i] == null) {
214: // first sort key value is ()
215: comp = (nodeKeys[b1 + i] == null ? 0 : (sortkeys[i]
216: .getEmptyFirst() ? -1 : +1));
217: } else if (nodeKeys[b1 + i] == null) {
218: // second sort key value is ()
219: comp = (sortkeys[i].getEmptyFirst() ? +1 : -1);
220: } else {
221: comp = keyComparers[i].compare(nodeKeys[a1 + i],
222: nodeKeys[b1 + i]);
223: }
224: if (comp != 0) {
225: // we have found a difference, so we can return
226: return comp;
227: }
228: }
229:
230: // all sort keys equal: return the items in their original order
231:
232: return ((Integer) nodeKeys[a1 + sortkeys.length]).intValue()
233: - ((Integer) nodeKeys[b1 + sortkeys.length]).intValue();
234: }
235:
236: /**
237: * Swap two items (needed to implement the Sortable interface)
238: */
239:
240: public void swap(int a, int b) {
241: int a1 = a * recordSize;
242: int b1 = b * recordSize;
243: for (int i = 0; i < recordSize; i++) {
244: Object temp = nodeKeys[a1 + i];
245: nodeKeys[a1 + i] = nodeKeys[b1 + i];
246: nodeKeys[b1 + i] = temp;
247: }
248: }
249:
250: }
251:
252: //
253: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
254: // you may not use this file except in compliance with the License. You may obtain a copy of the
255: // License at http://www.mozilla.org/MPL/
256: //
257: // Software distributed under the License is distributed on an "AS IS" basis,
258: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
259: // See the License for the specific language governing rights and limitations under the License.
260: //
261: // The Original Code is: all this file.
262: //
263: // The Initial Developer of the Original Code is Michael H. Kay.
264: //
265: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
266: //
267: // Contributor(s): none.
268: //
|