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