/*
 * 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$
 */

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();
    }

}