Back to index...

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

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

	}

Back to index...