1 /*
2 * reserved comment block
3 * DO NOT REMOVE OR ALTER!
4 */
5 /*
6 * Licensed to the Apache Software Foundation (ASF) under one or more
7 * contributor license agreements. See the NOTICE file distributed with
8 * this work for additional information regarding copyright ownership.
9 * The ASF licenses this file to You under the Apache License, Version 2.0
10 * (the "License"); you may not use this file except in compliance with
11 * the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 */
21 /*
22 * $Id: UnionIterator.java 337874 2004-02-16 23:06:53Z minchau $
23 */
24
25 package com.sun.org.apache.xalan.internal.xsltc.dom;
26
27 import com.sun.org.apache.xalan.internal.xsltc.DOM;
28 import com.sun.org.apache.xalan.internal.xsltc.runtime.BasisLibrary;
29 import com.sun.org.apache.xml.internal.dtm.DTMAxisIterator;
30 import com.sun.org.apache.xml.internal.dtm.ref.DTMAxisIteratorBase;
31
32 /**
33 * <p><code>MultiValuedNodeHeapIterator</code> takes a set of multi-valued
34 * heap nodes and produces a merged NodeSet in document order with duplicates
35 * removed.</p>
36 * <p>Each multi-valued heap node (which might be a
37 * {@link org.apache.xml.dtm.DTMAxisIterator}, but that's not necessary)
38 * generates DTM node handles in document order. The class
39 * maintains the multi-valued heap nodes in a heap, not surprisingly, sorted by
40 * the next DTM node handle available form the heap node.</p>
41 * <p>After a DTM node is pulled from the heap node that's at the top of the
42 * heap, the heap node is advanced to the next DTM node handle it makes
43 * available, and the heap nature of the heap is restored to ensure the next
44 * DTM node handle pulled is next in document order overall.
45 *
46 * @author Jacek Ambroziak
47 * @author Santiago Pericas-Geertsen
48 */
49 public abstract class MultiValuedNodeHeapIterator extends DTMAxisIteratorBase {
50 /** wrapper for NodeIterators to support iterator
51 comparison on the value of their next() method
52 */
53
54 /**
55 * An abstract representation of a set of nodes that will be retrieved in
56 * document order.
57 */
58 public abstract class HeapNode implements Cloneable {
59 protected int _node, _markedNode;
60 protected boolean _isStartSet = false;
61
62 /**
63 * Advance to the next node represented by this {@link HeapNode}
64 *
65 * @return the next DTM node.
66 */
67 public abstract int step();
68
69
70 /**
71 * Creates a deep copy of this {@link HeapNode}. The clone is not
72 * reset from the current position of the original.
73 *
74 * @return the cloned heap node
75 */
76 public HeapNode cloneHeapNode() {
77 HeapNode clone;
78
79 try {
80 clone = (HeapNode) super.clone();
81 } catch (CloneNotSupportedException e) {
82 BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
83 e.toString());
84 return null;
85 }
86
87 clone._node = _node;
88 clone._markedNode = _node;
89
90 return clone;
91 }
92
93 /**
94 * Remembers the current node for the next call to {@link #gotoMark()}.
95 */
96 public void setMark() {
97 _markedNode = _node;
98 }
99
100 /**
101 * Restores the current node remembered by {@link #setMark()}.
102 */
103 public void gotoMark() {
104 _node = _markedNode;
105 }
106
107 /**
108 * Performs a comparison of the two heap nodes
109 *
110 * @param heapNode the heap node against which to compare
111 * @return <code>true</code> if and only if the current node for this
112 * heap node is before the current node of the argument heap
113 * node in document order.
114 */
115 public abstract boolean isLessThan(HeapNode heapNode);
116
117 /**
118 * Sets context with respect to which this heap node is evaluated.
119 *
120 * @param node The new context node
121 * @return a {@link HeapNode} which may or may not be the same as
122 * this <code>HeapNode</code>.
123 */
124 public abstract HeapNode setStartNode(int node);
125
126 /**
127 * Reset the heap node back to its beginning.
128 *
129 * @return a {@link HeapNode} which may or may not be the same as
130 * this <code>HeapNode</code>.
131 */
132 public abstract HeapNode reset();
133 } // end of HeapNode
134
135 private static final int InitSize = 8;
136
137 private int _heapSize = 0;
138 private int _size = InitSize;
139 private HeapNode[] _heap = new HeapNode[InitSize];
140 private int _free = 0;
141
142 // Last node returned by this MultiValuedNodeHeapIterator to the caller of
143 // next; used to prune duplicates
144 private int _returnedLast;
145
146 // cached returned last for use in gotoMark
147 private int _cachedReturnedLast = END;
148
149 // cached heap size for use in gotoMark
150 private int _cachedHeapSize;
151
152
153 public DTMAxisIterator cloneIterator() {
154 _isRestartable = false;
155 final HeapNode[] heapCopy = new HeapNode[_heap.length];
156 try {
157 MultiValuedNodeHeapIterator clone =
158 (MultiValuedNodeHeapIterator)super.clone();
159
160 for (int i = 0; i < _free; i++) {
161 heapCopy[i] = _heap[i].cloneHeapNode();
162 }
163 clone.setRestartable(false);
164 clone._heap = heapCopy;
165 return clone.reset();
166 }
167 catch (CloneNotSupportedException e) {
168 BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
169 e.toString());
170 return null;
171 }
172 }
173
174 protected void addHeapNode(HeapNode node) {
175 if (_free == _size) {
176 HeapNode[] newArray = new HeapNode[_size *= 2];
177 System.arraycopy(_heap, 0, newArray, 0, _free);
178 _heap = newArray;
179 }
180 _heapSize++;
181 _heap[_free++] = node;
182 }
183
184 public int next() {
185 while (_heapSize > 0) {
186 final int smallest = _heap[0]._node;
187 if (smallest == END) { // iterator _heap[0] is done
188 if (_heapSize > 1) {
189 // Swap first and last (iterator must be restartable)
190 final HeapNode temp = _heap[0];
191 _heap[0] = _heap[--_heapSize];
192 _heap[_heapSize] = temp;
193 }
194 else {
195 return END;
196 }
197 }
198 else if (smallest == _returnedLast) { // duplicate
199 _heap[0].step(); // value consumed
200 }
201 else {
202 _heap[0].step(); // value consumed
203 heapify(0);
204 return returnNode(_returnedLast = smallest);
205 }
206 // fallthrough if not returned above
207 heapify(0);
208 }
209 return END;
210 }
211
212 public DTMAxisIterator setStartNode(int node) {
213 if (_isRestartable) {
214 _startNode = node;
215 for (int i = 0; i < _free; i++) {
216 if(!_heap[i]._isStartSet){
217 _heap[i].setStartNode(node);
218 _heap[i].step(); // to get the first node
219 _heap[i]._isStartSet = true;
220 }
221 }
222 // build heap
223 for (int i = (_heapSize = _free)/2; i >= 0; i--) {
224 heapify(i);
225 }
226 _returnedLast = END;
227 return resetPosition();
228 }
229 return this;
230 }
231
232 protected void init() {
233 for (int i =0; i < _free; i++) {
234 _heap[i] = null;
235 }
236
237 _heapSize = 0;
238 _free = 0;
239 }
240
241 /* Build a heap in document order. put the smallest node on the top.
242 * "smallest node" means the node before other nodes in document order
243 */
244 private void heapify(int i) {
245 for (int r, l, smallest;;) {
246 r = (i + 1) << 1; l = r - 1;
247 smallest = l < _heapSize
248 && _heap[l].isLessThan(_heap[i]) ? l : i;
249 if (r < _heapSize && _heap[r].isLessThan(_heap[smallest])) {
250 smallest = r;
251 }
252 if (smallest != i) {
253 final HeapNode temp = _heap[smallest];
254 _heap[smallest] = _heap[i];
255 _heap[i] = temp;
256 i = smallest;
257 } else {
258 break;
259 }
260 }
261 }
262
263 public void setMark() {
264 for (int i = 0; i < _free; i++) {
265 _heap[i].setMark();
266 }
267 _cachedReturnedLast = _returnedLast;
268 _cachedHeapSize = _heapSize;
269 }
270
271 public void gotoMark() {
272 for (int i = 0; i < _free; i++) {
273 _heap[i].gotoMark();
274 }
275 // rebuild heap after call last() function. fix for bug 20913
276 for (int i = (_heapSize = _cachedHeapSize)/2; i >= 0; i--) {
277 heapify(i);
278 }
279 _returnedLast = _cachedReturnedLast;
280 }
281
282 public DTMAxisIterator reset() {
283 for (int i = 0; i < _free; i++) {
284 _heap[i].reset();
285 _heap[i].step();
286 }
287
288 // build heap
289 for (int i = (_heapSize = _free)/2; i >= 0; i--) {
290 heapify(i);
291 }
292
293 _returnedLast = END;
294 return resetPosition();
295 }
296
297 }