KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2  * Copyright 2001-2004 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,v 1.18 2004/02/16 22:54:59 minchau Exp $
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  * UnionIterator takes a set of NodeIterators and produces
29  * a merged NodeSet in document order with duplicates removed
30  * The individual iterators are supposed to generate nodes
31  * in document order
32  * @author Jacek Ambroziak
33  * @author Santiago Pericas-Geertsen
34  */
35 public final class UnionIterator extends DTMAxisIteratorBase {
36     /** wrapper for NodeIterators to support iterator
37     comparison on the value of their next() method
38     */
39     final private DOM _dom;
40
41     private final static class LookAheadIterator {
42     public int node, markedNode;
43     public DTMAxisIterator iterator;
44     public boolean isStartSet = false;
45         
46     public LookAheadIterator(DTMAxisIterator iterator) {
47         this.iterator = iterator;
48     }
49         
50     public int step() {
51         node = iterator.next();
52         return node;
53     }
54
55     public LookAheadIterator cloneIterator() {
56         final LookAheadIterator clone =
57          new LookAheadIterator(iterator.cloneIterator());
58         clone.node = node;
59         clone.markedNode = node;
60         return clone;
61     }
62
63     public void setMark() {
64         markedNode = node;
65         iterator.setMark();
66     }
67
68     public void gotoMark() {
69         node = markedNode;
70         iterator.gotoMark();
71     }
72
73     } // end of LookAheadIterator
74
75     private static final int InitSize = 8;
76   
77     private int _heapSize = 0;
78     private int _size = InitSize;
79     private LookAheadIterator[] _heap = new LookAheadIterator[InitSize];
80     private int _free = 0;
81   
82     // last node returned by this UnionIterator to the caller of next
83 // used to prune duplicates
84 private int _returnedLast;
85
86     // cached returned last for use in gotoMark
87 private int _cachedReturnedLast = END;
88     // cached heap size for use in gotoMark
89 private int _cachedHeapSize;
90
91     public UnionIterator(DOM dom) {
92     _dom = dom;
93     }
94
95
96     public DTMAxisIterator cloneIterator() {
97     _isRestartable = false;
98     final LookAheadIterator[] heapCopy =
99         new LookAheadIterator[_heap.length];
100     try {
101         final UnionIterator clone = (UnionIterator)super.clone();
102             for (int i = 0; i < _free; i++) {
103                 heapCopy[i] = _heap[i].cloneIterator();
104             }
105         clone.setRestartable(false);
106         clone._heap = heapCopy;
107         return clone.reset();
108     }
109     catch (CloneNotSupportedException JavaDoc e) {
110         BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
111                       e.toString());
112         return null;
113     }
114     }
115     
116     public UnionIterator addIterator(DTMAxisIterator iterator) {
117     if (_free == _size) {
118         LookAheadIterator[] newArray = new LookAheadIterator[_size *= 2];
119         System.arraycopy(_heap, 0, newArray, 0, _free);
120         _heap = newArray;
121     }
122     _heapSize++;
123     _heap[_free++] = new LookAheadIterator(iterator);
124     return this;
125     }
126   
127     public int next() {
128     while (_heapSize > 0) {
129         final int smallest = _heap[0].node;
130         if (smallest == END) { // iterator _heap[0] is done
131 if (_heapSize > 1) {
132             // Swap first and last (iterator must be restartable)
133 final LookAheadIterator temp = _heap[0];
134             _heap[0] = _heap[--_heapSize];
135             _heap[_heapSize] = temp;
136         }
137         else {
138             return END;
139         }
140         }
141         else if (smallest == _returnedLast) { // duplicate
142 _heap[0].step(); // value consumed
143 }
144         else {
145         _heap[0].step(); // value consumed
146 heapify(0);
147         return returnNode(_returnedLast = smallest);
148         }
149         // fallthrough if not returned above
150 heapify(0);
151     }
152     return END;
153     }
154   
155     public DTMAxisIterator setStartNode(int node) {
156     if (_isRestartable) {
157         _startNode = node;
158         for (int i = 0; i < _free; i++) {
159             if(!_heap[i].isStartSet){
160                _heap[i].iterator.setStartNode(node);
161                _heap[i].step(); // to get the first node
162 _heap[i].isStartSet = true;
163             }
164         }
165         // build heap
166 for (int i = (_heapSize = _free)/2; i >= 0; i--) {
167         heapify(i);
168         }
169         _returnedLast = END;
170         return resetPosition();
171     }
172     return this;
173     }
174     
175     /* Build a heap in document order. put the smallest node on the top.
176      * "smallest node" means the node before other nodes in document order
177      */
178     private void heapify(int i) {
179     for (int r, l, smallest;;) {
180         r = (i + 1) << 1; l = r - 1;
181         smallest = l < _heapSize
182         && _dom.lessThan(_heap[l].node, _heap[i].node) ? l : i;
183         if (r < _heapSize && _dom.lessThan(_heap[r].node,
184                            _heap[smallest].node)) {
185         smallest = r;
186         }
187         if (smallest != i) {
188         final LookAheadIterator temp = _heap[smallest];
189         _heap[smallest] = _heap[i];
190         _heap[i] = temp;
191         i = smallest;
192         }
193         else
194         break;
195     }
196     }
197
198     public void setMark() {
199     for (int i = 0; i < _free; i++) {
200         _heap[i].setMark();
201     }
202     _cachedReturnedLast = _returnedLast;
203     _cachedHeapSize = _heapSize;
204     }
205
206     public void gotoMark() {
207     for (int i = 0; i < _free; i++) {
208         _heap[i].gotoMark();
209     }
210     // rebuild heap after call last() function. fix for bug 20913
211 for (int i = (_heapSize = _cachedHeapSize)/2; i >= 0; i--) {
212         heapify(i);
213     }
214     _returnedLast = _cachedReturnedLast;
215     }
216
217     public DTMAxisIterator reset() {
218     for (int i = 0; i < _free; i++) {
219         _heap[i].iterator.reset();
220         _heap[i].step();
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
230 }
231
Popular Tags