Part of fix for XALANJ-2294. Refactored UnionIterator so that it is derived
from a new MultiValuedNodeHeapIterator class. The latter is responsible for
the basic management of a heap, each of whose nodes contains multiple DTM
node handles, while the former handles the specific case of implementing a
union of other iterators.
In the original heap implementation of UnionIterator, each node contained a
DTMAxisIterator, but in MultiValuedNodeHeapIterator, each node contains
something that returns node handles; that doesn't have to be a DTMAxisIterator,
though in the of UnionIterator, it still is.
Reviewed by Christine Li (jycli () ca ! ibm ! com)
diff --git a/src/org/apache/xalan/xsltc/dom/MultiValuedNodeHeapIterator.java b/src/org/apache/xalan/xsltc/dom/MultiValuedNodeHeapIterator.java
new file mode 100644
index 0000000..f7a9aef
--- /dev/null
+++ b/src/org/apache/xalan/xsltc/dom/MultiValuedNodeHeapIterator.java
@@ -0,0 +1,292 @@
+/*
+ * Copyright 2001-2006 The Apache Software Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+/*
+ * $Id: UnionIterator.java 337874 2004-02-16 23:06:53Z minchau $
+ */
+
+package org.apache.xalan.xsltc.dom;
+
+import org.apache.xalan.xsltc.DOM;
+import org.apache.xalan.xsltc.runtime.BasisLibrary;
+import org.apache.xml.dtm.DTMAxisIterator;
+import org.apache.xml.dtm.ref.DTMAxisIteratorBase;
+
+/**
+ * <p><code>MultiValuedNodeHeapIterator</code> takes a set of multi-valued
+ * heap nodes and produces a merged NodeSet in document order with duplicates
+ * removed.</p>
+ * <p>Each multi-valued heap node (which might be a
+ * {@link org.apache.xml.dtm.DTMAxisIterator}, but that's not necessary)
+ * generates DTM node handles in document order. The class
+ * maintains the multi-valued heap nodes in a heap, not surprisingly, sorted by
+ * the next DTM node handle available form the heap node.</p>
+ * <p>After a DTM node is pulled from the heap node that's at the top of the
+ * heap, the heap node is advanced to the next DTM node handle it makes
+ * available, and the heap nature of the heap is restored to ensure the next
+ * DTM node handle pulled is next in document order overall.
+ *
+ * @author Jacek Ambroziak
+ * @author Santiago Pericas-Geertsen
+ */
+public abstract class MultiValuedNodeHeapIterator extends DTMAxisIteratorBase {
+ /** wrapper for NodeIterators to support iterator
+ comparison on the value of their next() method
+ */
+
+ /**
+ * An abstract representation of a set of nodes that will be retrieved in
+ * document order.
+ */
+ public abstract class HeapNode implements Cloneable {
+ protected int _node, _markedNode;
+ protected boolean _isStartSet = false;
+
+ /**
+ * Advance to the next node represented by this {@link HeapNode}
+ *
+ * @return the next DTM node.
+ */
+ public abstract int step();
+
+
+ /**
+ * Creates a deep copy of this {@link HeapNode}. The clone is not
+ * reset from the current position of the original.
+ *
+ * @return the cloned heap node
+ */
+ public HeapNode cloneHeapNode() {
+ HeapNode clone;
+
+ try {
+ clone = (HeapNode) super.clone();
+ } catch (CloneNotSupportedException e) {
+ BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
+ e.toString());
+ return null;
+ }
+
+ clone._node = _node;
+ clone._markedNode = _node;
+
+ return clone;
+ }
+
+ /**
+ * Remembers the current node for the next call to {@link #gotoMark()}.
+ */
+ public void setMark() {
+ _markedNode = _node;
+ }
+
+ /**
+ * Restores the current node remembered by {@link #setMark()}.
+ */
+ public void gotoMark() {
+ _node = _markedNode;
+ }
+
+ /**
+ * Performs a comparison of the two heap nodes
+ *
+ * @param heapNode the heap node against which to compare
+ * @return <code>true</code> if and only if the current node for this
+ * heap node is before the current node of the argument heap
+ * node in document order.
+ */
+ public abstract boolean isLessThan(HeapNode heapNode);
+
+ /**
+ * Sets context with respect to which this heap node is evaluated.
+ *
+ * @param node The new context node
+ * @return a {@link HeapNode} which may or may not be the same as
+ * this <code>HeapNode</code>.
+ */
+ public abstract HeapNode setStartNode(int node);
+
+ /**
+ * Reset the heap node back to its beginning.
+ *
+ * @return a {@link HeapNode} which may or may not be the same as
+ * this <code>HeapNode</code>.
+ */
+ public abstract HeapNode reset();
+ } // end of HeapNode
+
+ private static final int InitSize = 8;
+
+ private int _heapSize = 0;
+ private int _size = InitSize;
+ private HeapNode[] _heap = new HeapNode[InitSize];
+ private int _free = 0;
+
+ // Last node returned by this MultiValuedNodeHeapIterator to the caller of
+ // next; used to prune duplicates
+ private int _returnedLast;
+
+ // cached returned last for use in gotoMark
+ private int _cachedReturnedLast = END;
+
+ // cached heap size for use in gotoMark
+ private int _cachedHeapSize;
+
+
+ public DTMAxisIterator cloneIterator() {
+ _isRestartable = false;
+ final HeapNode[] heapCopy = new HeapNode[_heap.length];
+ try {
+ MultiValuedNodeHeapIterator clone =
+ (MultiValuedNodeHeapIterator)super.clone();
+
+ for (int i = 0; i < _free; i++) {
+ heapCopy[i] = _heap[i].cloneHeapNode();
+ }
+ clone.setRestartable(false);
+ clone._heap = heapCopy;
+ return clone.reset();
+ }
+ catch (CloneNotSupportedException e) {
+ BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
+ e.toString());
+ return null;
+ }
+ }
+
+ protected void addHeapNode(HeapNode node) {
+ if (_free == _size) {
+ HeapNode[] newArray = new HeapNode[_size *= 2];
+ System.arraycopy(_heap, 0, newArray, 0, _free);
+ _heap = newArray;
+ }
+ _heapSize++;
+ _heap[_free++] = node;
+ }
+
+ public int next() {
+ while (_heapSize > 0) {
+ final int smallest = _heap[0]._node;
+ if (smallest == END) { // iterator _heap[0] is done
+ if (_heapSize > 1) {
+ // Swap first and last (iterator must be restartable)
+ final HeapNode temp = _heap[0];
+ _heap[0] = _heap[--_heapSize];
+ _heap[_heapSize] = temp;
+ }
+ else {
+ return END;
+ }
+ }
+ else if (smallest == _returnedLast) { // duplicate
+ _heap[0].step(); // value consumed
+ }
+ else {
+ _heap[0].step(); // value consumed
+ heapify(0);
+ return returnNode(_returnedLast = smallest);
+ }
+ // fallthrough if not returned above
+ heapify(0);
+ }
+ return END;
+ }
+
+ public DTMAxisIterator setStartNode(int node) {
+ if (_isRestartable) {
+ _startNode = node;
+ for (int i = 0; i < _free; i++) {
+ if(!_heap[i]._isStartSet){
+ _heap[i].setStartNode(node);
+ _heap[i].step(); // to get the first node
+ _heap[i]._isStartSet = true;
+ }
+ }
+ // build heap
+ for (int i = (_heapSize = _free)/2; i >= 0; i--) {
+ heapify(i);
+ }
+ _returnedLast = END;
+ return resetPosition();
+ }
+ return this;
+ }
+
+ protected void init() {
+ for (int i =0; i < _free; i++) {
+ _heap[i] = null;
+ }
+
+ _heapSize = 0;
+ _free = 0;
+ }
+
+ /* Build a heap in document order. put the smallest node on the top.
+ * "smallest node" means the node before other nodes in document order
+ */
+ private void heapify(int i) {
+ for (int r, l, smallest;;) {
+ r = (i + 1) << 1; l = r - 1;
+ smallest = l < _heapSize
+ && _heap[l].isLessThan(_heap[i]) ? l : i;
+ if (r < _heapSize && _heap[r].isLessThan(_heap[smallest])) {
+ smallest = r;
+ }
+ if (smallest != i) {
+ final HeapNode temp = _heap[smallest];
+ _heap[smallest] = _heap[i];
+ _heap[i] = temp;
+ i = smallest;
+ } else {
+ break;
+ }
+ }
+ }
+
+ public void setMark() {
+ for (int i = 0; i < _free; i++) {
+ _heap[i].setMark();
+ }
+ _cachedReturnedLast = _returnedLast;
+ _cachedHeapSize = _heapSize;
+ }
+
+ public void gotoMark() {
+ for (int i = 0; i < _free; i++) {
+ _heap[i].gotoMark();
+ }
+ // rebuild heap after call last() function. fix for bug 20913
+ for (int i = (_heapSize = _cachedHeapSize)/2; i >= 0; i--) {
+ heapify(i);
+ }
+ _returnedLast = _cachedReturnedLast;
+ }
+
+ public DTMAxisIterator reset() {
+ for (int i = 0; i < _free; i++) {
+ _heap[i].reset();
+ _heap[i].step();
+ }
+
+ // build heap
+ for (int i = (_heapSize = _free)/2; i >= 0; i--) {
+ heapify(i);
+ }
+
+ _returnedLast = END;
+ return resetPosition();
+ }
+
+}
diff --git a/src/org/apache/xalan/xsltc/dom/UnionIterator.java b/src/org/apache/xalan/xsltc/dom/UnionIterator.java
index f2150c9..12d1061 100644
--- a/src/org/apache/xalan/xsltc/dom/UnionIterator.java
+++ b/src/org/apache/xalan/xsltc/dom/UnionIterator.java
@@ -1,5 +1,5 @@
/*
- * Copyright 2001-2004 The Apache Software Foundation.
+ * Copyright 2001-2006 The Apache Software Foundation.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
@@ -32,199 +32,65 @@
* @author Jacek Ambroziak
* @author Santiago Pericas-Geertsen
*/
-public final class UnionIterator extends DTMAxisIteratorBase {
+public final class UnionIterator extends MultiValuedNodeHeapIterator {
/** wrapper for NodeIterators to support iterator
comparison on the value of their next() method
*/
final private DOM _dom;
- private final static class LookAheadIterator {
- public int node, markedNode;
+ private final class LookAheadIterator
+ extends MultiValuedNodeHeapIterator.HeapNode
+ {
public DTMAxisIterator iterator;
- public boolean isStartSet = false;
public LookAheadIterator(DTMAxisIterator iterator) {
+ super();
this.iterator = iterator;
}
public int step() {
- node = iterator.next();
- return node;
+ _node = iterator.next();
+ return _node;
}
- public LookAheadIterator cloneIterator() {
- final LookAheadIterator clone =
- new LookAheadIterator(iterator.cloneIterator());
- clone.node = node;
- clone.markedNode = node;
+ public HeapNode cloneHeapNode() {
+ LookAheadIterator clone = (LookAheadIterator) super.cloneHeapNode();
+ clone.iterator = iterator.cloneIterator();
return clone;
}
public void setMark() {
- markedNode = node;
+ super.setMark();
iterator.setMark();
}
public void gotoMark() {
- node = markedNode;
+ super.gotoMark();
iterator.gotoMark();
}
+ public boolean isLessThan(HeapNode heapNode) {
+ LookAheadIterator comparand = (LookAheadIterator) heapNode;
+ return _dom.lessThan(_node, heapNode._node);
+ }
+
+ public HeapNode setStartNode(int node) {
+ iterator.setStartNode(node);
+ return this;
+ }
+
+ public HeapNode reset() {
+ iterator.reset();
+ return this;
+ }
} // end of LookAheadIterator
- private static final int InitSize = 8;
-
- private int _heapSize = 0;
- private int _size = InitSize;
- private LookAheadIterator[] _heap = new LookAheadIterator[InitSize];
- private int _free = 0;
-
- // last node returned by this UnionIterator to the caller of next
- // used to prune duplicates
- private int _returnedLast;
-
- // cached returned last for use in gotoMark
- private int _cachedReturnedLast = END;
- // cached heap size for use in gotoMark
- private int _cachedHeapSize;
-
public UnionIterator(DOM dom) {
_dom = dom;
}
-
- public DTMAxisIterator cloneIterator() {
- _isRestartable = false;
- final LookAheadIterator[] heapCopy =
- new LookAheadIterator[_heap.length];
- try {
- final UnionIterator clone = (UnionIterator)super.clone();
- for (int i = 0; i < _free; i++) {
- heapCopy[i] = _heap[i].cloneIterator();
- }
- clone.setRestartable(false);
- clone._heap = heapCopy;
- return clone.reset();
- }
- catch (CloneNotSupportedException e) {
- BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
- e.toString());
- return null;
- }
- }
-
public UnionIterator addIterator(DTMAxisIterator iterator) {
- if (_free == _size) {
- LookAheadIterator[] newArray = new LookAheadIterator[_size *= 2];
- System.arraycopy(_heap, 0, newArray, 0, _free);
- _heap = newArray;
- }
- _heapSize++;
- _heap[_free++] = new LookAheadIterator(iterator);
- return this;
+ addHeapNode(new LookAheadIterator(iterator));
+ return this;
}
-
- public int next() {
- while (_heapSize > 0) {
- final int smallest = _heap[0].node;
- if (smallest == END) { // iterator _heap[0] is done
- if (_heapSize > 1) {
- // Swap first and last (iterator must be restartable)
- final LookAheadIterator temp = _heap[0];
- _heap[0] = _heap[--_heapSize];
- _heap[_heapSize] = temp;
- }
- else {
- return END;
- }
- }
- else if (smallest == _returnedLast) { // duplicate
- _heap[0].step(); // value consumed
- }
- else {
- _heap[0].step(); // value consumed
- heapify(0);
- return returnNode(_returnedLast = smallest);
- }
- // fallthrough if not returned above
- heapify(0);
- }
- return END;
- }
-
- public DTMAxisIterator setStartNode(int node) {
- if (_isRestartable) {
- _startNode = node;
- for (int i = 0; i < _free; i++) {
- if(!_heap[i].isStartSet){
- _heap[i].iterator.setStartNode(node);
- _heap[i].step(); // to get the first node
- _heap[i].isStartSet = true;
- }
- }
- // build heap
- for (int i = (_heapSize = _free)/2; i >= 0; i--) {
- heapify(i);
- }
- _returnedLast = END;
- return resetPosition();
- }
- return this;
- }
-
- /* Build a heap in document order. put the smallest node on the top.
- * "smallest node" means the node before other nodes in document order
- */
- private void heapify(int i) {
- for (int r, l, smallest;;) {
- r = (i + 1) << 1; l = r - 1;
- smallest = l < _heapSize
- && _dom.lessThan(_heap[l].node, _heap[i].node) ? l : i;
- if (r < _heapSize && _dom.lessThan(_heap[r].node,
- _heap[smallest].node)) {
- smallest = r;
- }
- if (smallest != i) {
- final LookAheadIterator temp = _heap[smallest];
- _heap[smallest] = _heap[i];
- _heap[i] = temp;
- i = smallest;
- }
- else
- break;
- }
- }
-
- public void setMark() {
- for (int i = 0; i < _free; i++) {
- _heap[i].setMark();
- }
- _cachedReturnedLast = _returnedLast;
- _cachedHeapSize = _heapSize;
- }
-
- public void gotoMark() {
- for (int i = 0; i < _free; i++) {
- _heap[i].gotoMark();
- }
- // rebuild heap after call last() function. fix for bug 20913
- for (int i = (_heapSize = _cachedHeapSize)/2; i >= 0; i--) {
- heapify(i);
- }
- _returnedLast = _cachedReturnedLast;
- }
-
- public DTMAxisIterator reset() {
- for (int i = 0; i < _free; i++) {
- _heap[i].iterator.reset();
- _heap[i].step();
- }
- // build heap
- for (int i = (_heapSize = _free)/2; i >= 0; i--) {
- heapify(i);
- }
- _returnedLast = END;
- return resetPosition();
- }
-
}
