https://openjdk.java.net/ 
/*
 * reserved comment block
 * DO NOT REMOVE OR ALTER!
 */
/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You 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;


MultiValuedNodeHeapIterator takes a set of multi-valued
heap nodes and produces a merged NodeSet in document order with duplicates
removed.


Each multi-valued heap node (which might be a 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.


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, Santiago Pericas-Geertsen
/**
 * <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.

/**
     * 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 HeapNode 
Returns:the next DTM node.
/**
         * 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 HeapNode. The clone is not reset from the current position of the original. 
Returns:the cloned heap node
/**
         * 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 gotoMark(). 
/**
         * Remembers the current node for the next call to {@link #gotoMark()}.
         */
        public void setMark() {
            _markedNode = _node;
        }

        
Restores the current node remembered by setMark(). 
/**
         * Restores the current node remembered by {@link #setMark()}.
         */
        public void gotoMark() {
            _node = _markedNode;
        }

        
Performs a comparison of the two heap nodes

Params:
  • heapNode – the heap node against which to compare
Returns:true if and only if the current node for this
        heap node is before the current node of the argument heap
        node in document order.
/**
         * 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.

Params:
  • node – The new context node
Returns:a HeapNode which may or may not be the same as this 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.

Returns:a HeapNode which may or may not be the same as this HeapNode.
/**
         * 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();
    }

}