001: package net.sf.saxon.sort;
002:
003: import net.sf.saxon.om.Item;
004: import net.sf.saxon.om.NodeInfo;
005: import net.sf.saxon.om.SequenceIterator;
006: import net.sf.saxon.trans.XPathException;
007: import net.sf.saxon.value.SequenceExtent;
008:
009: /**
010: * DocumentOrderIterator takes as input an iteration of nodes in any order, and
011: * returns as output an iteration of the same nodes in document order, eliminating
012: * any duplicates.
013: */
014:
015: public final class DocumentOrderIterator implements SequenceIterator,
016: Sortable {
017:
018: private SequenceIterator iterator;
019: private SequenceExtent sequence;
020: private NodeOrderComparer comparer;
021: private NodeInfo current = null;
022: private int position = 0;
023:
024: /**
025: * Iterate over a sequence in document order.
026: */
027:
028: public DocumentOrderIterator(SequenceIterator base,
029: NodeOrderComparer comparer) throws XPathException {
030:
031: this .comparer = comparer;
032:
033: sequence = new SequenceExtent(base);
034: //System.err.println("sort into document order: sequence length = " + sequence.getLength());
035: if (sequence.getLength() > 1) {
036: //QuickSort.sort(this, 0, sequence.getLength()-1);
037: GenericSorter.quickSort(0, sequence.getLength(), this );
038: //GenericSorter.mergeSort(0, sequence.getLength(), this);
039: }
040: iterator = sequence.iterate(null);
041: }
042:
043: /**
044: * Private constructor used only by getAnother()
045: */
046:
047: private DocumentOrderIterator() {
048: }
049:
050: /**
051: * Compare two nodes in document sequence
052: * (needed to implement the Sortable interface)
053: */
054:
055: public int compare(int a, int b) {
056: //System.err.println("compare " + a + " with " + b);
057: return comparer.compare((NodeInfo) sequence.itemAt(a),
058: (NodeInfo) sequence.itemAt(b));
059: }
060:
061: /**
062: * Swap two nodes (needed to implement the Sortable interface)
063: */
064:
065: public void swap(int a, int b) {
066: sequence.swap(a, b);
067: }
068:
069: // Implement the SequenceIterator as a wrapper around the underlying iterator
070: // over the sequenceExtent, but looking ahead to remove duplicates.
071:
072: public Item next() throws XPathException {
073: while (true) {
074: NodeInfo next = (NodeInfo) iterator.next();
075: if (next == null) {
076: current = null;
077: position = -1;
078: return null;
079: }
080: if (current != null && next.isSameNodeInfo(current)) {
081: continue;
082: } else {
083: position++;
084: current = next;
085: return current;
086: }
087: }
088: }
089:
090: /**
091: * Get properties of this iterator, as a bit-significant integer.
092: *
093: * @return the properties of this iterator. This will be some combination of
094: * properties such as {@link GROUNDED}, {@link LAST_POSITION_FINDER},
095: * and {@link LOOKAHEAD}. It is always
096: * acceptable to return the value zero, indicating that there are no known special properties.
097: * It is acceptable for the properties of the iterator to change depending on its state.
098: */
099:
100: public int getProperties() {
101: return 0;
102: }
103:
104: public Item current() {
105: return current;
106: }
107:
108: public int position() {
109: return position;
110: }
111:
112: public SequenceIterator getAnother() throws XPathException {
113: DocumentOrderIterator another = new DocumentOrderIterator();
114: another.iterator = iterator.getAnother(); // don't need to sort it again
115: return another;
116: }
117:
118: }
119:
120: //
121: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
122: // you may not use this file except in compliance with the License. You may obtain a copy of the
123: // License at http://www.mozilla.org/MPL/
124: //
125: // Software distributed under the License is distributed on an "AS IS" basis,
126: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
127: // See the License for the specific language governing rights and limitations under the License.
128: //
129: // The Original Code is: all this file.
130: //
131: // The Initial Developer of the Original Code is Michael H. Kay.
132: //
133: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
134: //
135: // Contributor(s): none.
136: //
|