001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018 /*
019 * $Id: MultiValuedNodeHeapIterator.java 1225426 2011-12-29 04:13:08Z mrglavas $
020 */
021
022 package org.apache.xalan.xsltc.dom;
023
024 import org.apache.xalan.xsltc.DOM;
025 import org.apache.xalan.xsltc.runtime.BasisLibrary;
026 import org.apache.xml.dtm.DTMAxisIterator;
027 import org.apache.xml.dtm.ref.DTMAxisIteratorBase;
028
029 /**
030 * <p><code>MultiValuedNodeHeapIterator</code> takes a set of multi-valued
031 * heap nodes and produces a merged NodeSet in document order with duplicates
032 * removed.</p>
033 * <p>Each multi-valued heap node (which might be a
034 * {@link org.apache.xml.dtm.DTMAxisIterator}, but that's not necessary)
035 * generates DTM node handles in document order. The class
036 * maintains the multi-valued heap nodes in a heap, not surprisingly, sorted by
037 * the next DTM node handle available form the heap node.</p>
038 * <p>After a DTM node is pulled from the heap node that's at the top of the
039 * heap, the heap node is advanced to the next DTM node handle it makes
040 * available, and the heap nature of the heap is restored to ensure the next
041 * DTM node handle pulled is next in document order overall.
042 *
043 * @author Jacek Ambroziak
044 * @author Santiago Pericas-Geertsen
045 */
046 public abstract class MultiValuedNodeHeapIterator extends DTMAxisIteratorBase {
047 /** wrapper for NodeIterators to support iterator
048 comparison on the value of their next() method
049 */
050
051 /**
052 * An abstract representation of a set of nodes that will be retrieved in
053 * document order.
054 */
055 public abstract class HeapNode implements Cloneable {
056 protected int _node, _markedNode;
057 protected boolean _isStartSet = false;
058
059 /**
060 * Advance to the next node represented by this {@link HeapNode}
061 *
062 * @return the next DTM node.
063 */
064 public abstract int step();
065
066
067 /**
068 * Creates a deep copy of this {@link HeapNode}. The clone is not
069 * reset from the current position of the original.
070 *
071 * @return the cloned heap node
072 */
073 public HeapNode cloneHeapNode() {
074 HeapNode clone;
075
076 try {
077 clone = (HeapNode) super.clone();
078 } catch (CloneNotSupportedException e) {
079 BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
080 e.toString());
081 return null;
082 }
083
084 clone._node = _node;
085 clone._markedNode = _node;
086
087 return clone;
088 }
089
090 /**
091 * Remembers the current node for the next call to {@link #gotoMark()}.
092 */
093 public void setMark() {
094 _markedNode = _node;
095 }
096
097 /**
098 * Restores the current node remembered by {@link #setMark()}.
099 */
100 public void gotoMark() {
101 _node = _markedNode;
102 }
103
104 /**
105 * Performs a comparison of the two heap nodes
106 *
107 * @param heapNode the heap node against which to compare
108 * @return <code>true</code> if and only if the current node for this
109 * heap node is before the current node of the argument heap
110 * node in document order.
111 */
112 public abstract boolean isLessThan(HeapNode heapNode);
113
114 /**
115 * Sets context with respect to which this heap node is evaluated.
116 *
117 * @param node The new context node
118 * @return a {@link HeapNode} which may or may not be the same as
119 * this <code>HeapNode</code>.
120 */
121 public abstract HeapNode setStartNode(int node);
122
123 /**
124 * Reset the heap node back to its beginning.
125 *
126 * @return a {@link HeapNode} which may or may not be the same as
127 * this <code>HeapNode</code>.
128 */
129 public abstract HeapNode reset();
130 } // end of HeapNode
131
132 private static final int InitSize = 8;
133
134 private int _heapSize = 0;
135 private int _size = InitSize;
136 private HeapNode[] _heap = new HeapNode[InitSize];
137 private int _free = 0;
138
139 // Last node returned by this MultiValuedNodeHeapIterator to the caller of
140 // next; used to prune duplicates
141 private int _returnedLast;
142
143 // cached returned last for use in gotoMark
144 private int _cachedReturnedLast = END;
145
146 // cached heap size for use in gotoMark
147 private int _cachedHeapSize;
148
149
150 public DTMAxisIterator cloneIterator() {
151 _isRestartable = false;
152 final HeapNode[] heapCopy = new HeapNode[_heap.length];
153 try {
154 MultiValuedNodeHeapIterator clone =
155 (MultiValuedNodeHeapIterator)super.clone();
156
157 for (int i = 0; i < _free; i++) {
158 heapCopy[i] = _heap[i].cloneHeapNode();
159 }
160 clone.setRestartable(false);
161 clone._heap = heapCopy;
162 return clone.reset();
163 }
164 catch (CloneNotSupportedException e) {
165 BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
166 e.toString());
167 return null;
168 }
169 }
170
171 protected void addHeapNode(HeapNode node) {
172 if (_free == _size) {
173 HeapNode[] newArray = new HeapNode[_size *= 2];
174 System.arraycopy(_heap, 0, newArray, 0, _free);
175 _heap = newArray;
176 }
177 _heapSize++;
178 _heap[_free++] = node;
179 }
180
181 public int next() {
182 while (_heapSize > 0) {
183 final int smallest = _heap[0]._node;
184 if (smallest == END) { // iterator _heap[0] is done
185 if (_heapSize > 1) {
186 // Swap first and last (iterator must be restartable)
187 final HeapNode temp = _heap[0];
188 _heap[0] = _heap[--_heapSize];
189 _heap[_heapSize] = temp;
190 }
191 else {
192 return END;
193 }
194 }
195 else if (smallest == _returnedLast) { // duplicate
196 _heap[0].step(); // value consumed
197 }
198 else {
199 _heap[0].step(); // value consumed
200 heapify(0);
201 return returnNode(_returnedLast = smallest);
202 }
203 // fallthrough if not returned above
204 heapify(0);
205 }
206 return END;
207 }
208
209 public DTMAxisIterator setStartNode(int node) {
210 if (_isRestartable) {
211 _startNode = node;
212 for (int i = 0; i < _free; i++) {
213 if(!_heap[i]._isStartSet){
214 _heap[i].setStartNode(node);
215 _heap[i].step(); // to get the first node
216 _heap[i]._isStartSet = true;
217 }
218 }
219 // build heap
220 for (int i = (_heapSize = _free)/2; i >= 0; i--) {
221 heapify(i);
222 }
223 _returnedLast = END;
224 return resetPosition();
225 }
226 return this;
227 }
228
229 protected void init() {
230 for (int i =0; i < _free; i++) {
231 _heap[i] = null;
232 }
233
234 _heapSize = 0;
235 _free = 0;
236 }
237
238 /* Build a heap in document order. put the smallest node on the top.
239 * "smallest node" means the node before other nodes in document order
240 */
241 private void heapify(int i) {
242 for (int r, l, smallest;;) {
243 r = (i + 1) << 1; l = r - 1;
244 smallest = l < _heapSize
245 && _heap[l].isLessThan(_heap[i]) ? l : i;
246 if (r < _heapSize && _heap[r].isLessThan(_heap[smallest])) {
247 smallest = r;
248 }
249 if (smallest != i) {
250 final HeapNode temp = _heap[smallest];
251 _heap[smallest] = _heap[i];
252 _heap[i] = temp;
253 i = smallest;
254 } else {
255 break;
256 }
257 }
258 }
259
260 public void setMark() {
261 for (int i = 0; i < _free; i++) {
262 _heap[i].setMark();
263 }
264 _cachedReturnedLast = _returnedLast;
265 _cachedHeapSize = _heapSize;
266 }
267
268 public void gotoMark() {
269 for (int i = 0; i < _free; i++) {
270 _heap[i].gotoMark();
271 }
272 // rebuild heap after call last() function. fix for bug 20913
273 for (int i = (_heapSize = _cachedHeapSize)/2; i >= 0; i--) {
274 heapify(i);
275 }
276 _returnedLast = _cachedReturnedLast;
277 }
278
279 public DTMAxisIterator reset() {
280 for (int i = 0; i < _free; i++) {
281 _heap[i].reset();
282 _heap[i].step();
283 }
284
285 // build heap
286 for (int i = (_heapSize = _free)/2; i >= 0; i--) {
287 heapify(i);
288 }
289
290 _returnedLast = END;
291 return resetPosition();
292 }
293
294 }