aboutsummaryrefslogtreecommitdiff
path: root/src/com/sun/org/apache/xalan/internal/xsltc/dom/MultiValuedNodeHeapIterator.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/com/sun/org/apache/xalan/internal/xsltc/dom/MultiValuedNodeHeapIterator.java')
-rw-r--r--src/com/sun/org/apache/xalan/internal/xsltc/dom/MultiValuedNodeHeapIterator.java296
1 files changed, 0 insertions, 296 deletions
diff --git a/src/com/sun/org/apache/xalan/internal/xsltc/dom/MultiValuedNodeHeapIterator.java b/src/com/sun/org/apache/xalan/internal/xsltc/dom/MultiValuedNodeHeapIterator.java
deleted file mode 100644
index efc2251..0000000
--- a/src/com/sun/org/apache/xalan/internal/xsltc/dom/MultiValuedNodeHeapIterator.java
+++ /dev/null
@@ -1,296 +0,0 @@
-/*
- * reserved comment block
- * DO NOT REMOVE OR ALTER!
- */
-/*
- * 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 com.sun.org.apache.xalan.internal.xsltc.dom;
-
-import com.sun.org.apache.xalan.internal.xsltc.DOM;
-import com.sun.org.apache.xalan.internal.xsltc.runtime.BasisLibrary;
-import com.sun.org.apache.xml.internal.dtm.DTMAxisIterator;
-import com.sun.org.apache.xml.internal.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();
- }
-
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-25 02:47:10 +0000