001: /*
002: * Copyright 2001-2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: /*
017: * $Id: UnionIterator.java,v 1.18 2004/02/16 22:54:59 minchau Exp $
018: */
019:
020: package org.apache.xalan.xsltc.dom;
021:
022: import org.apache.xalan.xsltc.DOM;
023: import org.apache.xalan.xsltc.runtime.BasisLibrary;
024: import org.apache.xml.dtm.DTMAxisIterator;
025: import org.apache.xml.dtm.ref.DTMAxisIteratorBase;
026:
027: /**
028: * UnionIterator takes a set of NodeIterators and produces
029: * a merged NodeSet in document order with duplicates removed
030: * The individual iterators are supposed to generate nodes
031: * in document order
032: * @author Jacek Ambroziak
033: * @author Santiago Pericas-Geertsen
034: */
035: public final class UnionIterator extends DTMAxisIteratorBase {
036: /** wrapper for NodeIterators to support iterator
037: comparison on the value of their next() method
038: */
039: final private DOM _dom;
040:
041: private final static class LookAheadIterator {
042: public int node, markedNode;
043: public DTMAxisIterator iterator;
044: public boolean isStartSet = false;
045:
046: public LookAheadIterator(DTMAxisIterator iterator) {
047: this .iterator = iterator;
048: }
049:
050: public int step() {
051: node = iterator.next();
052: return node;
053: }
054:
055: public LookAheadIterator cloneIterator() {
056: final LookAheadIterator clone = new LookAheadIterator(
057: iterator.cloneIterator());
058: clone.node = node;
059: clone.markedNode = node;
060: return clone;
061: }
062:
063: public void setMark() {
064: markedNode = node;
065: iterator.setMark();
066: }
067:
068: public void gotoMark() {
069: node = markedNode;
070: iterator.gotoMark();
071: }
072:
073: } // end of LookAheadIterator
074:
075: private static final int InitSize = 8;
076:
077: private int _heapSize = 0;
078: private int _size = InitSize;
079: private LookAheadIterator[] _heap = new LookAheadIterator[InitSize];
080: private int _free = 0;
081:
082: // last node returned by this UnionIterator to the caller of next
083: // used to prune duplicates
084: private int _returnedLast;
085:
086: // cached returned last for use in gotoMark
087: private int _cachedReturnedLast = END;
088: // cached heap size for use in gotoMark
089: private int _cachedHeapSize;
090:
091: public UnionIterator(DOM dom) {
092: _dom = dom;
093: }
094:
095: public DTMAxisIterator cloneIterator() {
096: _isRestartable = false;
097: final LookAheadIterator[] heapCopy = new LookAheadIterator[_heap.length];
098: try {
099: final UnionIterator clone = (UnionIterator) super .clone();
100: for (int i = 0; i < _free; i++) {
101: heapCopy[i] = _heap[i].cloneIterator();
102: }
103: clone.setRestartable(false);
104: clone._heap = heapCopy;
105: return clone.reset();
106: } catch (CloneNotSupportedException e) {
107: BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
108: e.toString());
109: return null;
110: }
111: }
112:
113: public UnionIterator addIterator(DTMAxisIterator iterator) {
114: if (_free == _size) {
115: LookAheadIterator[] newArray = new LookAheadIterator[_size *= 2];
116: System.arraycopy(_heap, 0, newArray, 0, _free);
117: _heap = newArray;
118: }
119: _heapSize++;
120: _heap[_free++] = new LookAheadIterator(iterator);
121: return this ;
122: }
123:
124: public int next() {
125: while (_heapSize > 0) {
126: final int smallest = _heap[0].node;
127: if (smallest == END) { // iterator _heap[0] is done
128: if (_heapSize > 1) {
129: // Swap first and last (iterator must be restartable)
130: final LookAheadIterator temp = _heap[0];
131: _heap[0] = _heap[--_heapSize];
132: _heap[_heapSize] = temp;
133: } else {
134: return END;
135: }
136: } else if (smallest == _returnedLast) { // duplicate
137: _heap[0].step(); // value consumed
138: } else {
139: _heap[0].step(); // value consumed
140: heapify(0);
141: return returnNode(_returnedLast = smallest);
142: }
143: // fallthrough if not returned above
144: heapify(0);
145: }
146: return END;
147: }
148:
149: public DTMAxisIterator setStartNode(int node) {
150: if (_isRestartable) {
151: _startNode = node;
152: for (int i = 0; i < _free; i++) {
153: if (!_heap[i].isStartSet) {
154: _heap[i].iterator.setStartNode(node);
155: _heap[i].step(); // to get the first node
156: _heap[i].isStartSet = true;
157: }
158: }
159: // build heap
160: for (int i = (_heapSize = _free) / 2; i >= 0; i--) {
161: heapify(i);
162: }
163: _returnedLast = END;
164: return resetPosition();
165: }
166: return this ;
167: }
168:
169: /* Build a heap in document order. put the smallest node on the top.
170: * "smallest node" means the node before other nodes in document order
171: */
172: private void heapify(int i) {
173: for (int r, l, smallest;;) {
174: r = (i + 1) << 1;
175: l = r - 1;
176: smallest = l < _heapSize
177: && _dom.lessThan(_heap[l].node, _heap[i].node) ? l
178: : i;
179: if (r < _heapSize
180: && _dom.lessThan(_heap[r].node,
181: _heap[smallest].node)) {
182: smallest = r;
183: }
184: if (smallest != i) {
185: final LookAheadIterator temp = _heap[smallest];
186: _heap[smallest] = _heap[i];
187: _heap[i] = temp;
188: i = smallest;
189: } else
190: break;
191: }
192: }
193:
194: public void setMark() {
195: for (int i = 0; i < _free; i++) {
196: _heap[i].setMark();
197: }
198: _cachedReturnedLast = _returnedLast;
199: _cachedHeapSize = _heapSize;
200: }
201:
202: public void gotoMark() {
203: for (int i = 0; i < _free; i++) {
204: _heap[i].gotoMark();
205: }
206: // rebuild heap after call last() function. fix for bug 20913
207: for (int i = (_heapSize = _cachedHeapSize) / 2; i >= 0; i--) {
208: heapify(i);
209: }
210: _returnedLast = _cachedReturnedLast;
211: }
212:
213: public DTMAxisIterator reset() {
214: for (int i = 0; i < _free; i++) {
215: _heap[i].iterator.reset();
216: _heap[i].step();
217: }
218: // build heap
219: for (int i = (_heapSize = _free) / 2; i >= 0; i--) {
220: heapify(i);
221: }
222: _returnedLast = END;
223: return resetPosition();
224: }
225:
226: }
|