KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > org > apache > xalan > internal > xsltc > dom > MultiValuedNodeHeapIterator


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