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
25package com.sun.org.apache.xalan.internal.xsltc.dom;
26
27import com.sun.org.apache.xalan.internal.xsltc.DOM;
28import com.sun.org.apache.xalan.internal.xsltc.runtime.BasisLibrary;
29import com.sun.org.apache.xml.internal.dtm.DTMAxisIterator;
30import 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 */
49public 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}
298