basicbinomialheap.java

一个关于java 的常用工具包

package org.jutil.java.collections;

import java.util.Comparator;

/**
 * <p>A BasicBinomialHeap is a Heap that consists
 * of a forest of Binomial Trees.<p>
 *
 * <p>Most operations are <b>O(log(n))</b>.</p>
 * 
 * @author Tom Schrijvers
 * @release $Name:  $
 */
class BasicBinomialHeap extends AbstractPriorityQueue {

	/**
	 * The forest of BinomialTrees.
	 */
	private BinomialTree trees;

	/**
	 * The comparator.
	 */
 /*@
   @ private invariant comparator != null;
	 @*/
	private final Comparator comparator;

 /*@
   @ private invariant size >= 0;
	 @*/
	private int size = 0;

	/**
	 * Initialize a new BasicBinomialHeap with the given comparator.
	 *
	 * @param comparator
	 *        The comparator that is used to determine the order
	 *        of the elements.
	 */
 /*@
   @ public behavior
   @
	 @ pre comparator != null;
	 @
	 @ post getComparator() == comparator;
	 @ post size() == 0;
	 @*/
	public BasicBinomialHeap(Comparator comparator) {
		this.comparator = comparator;
	}

	/**
	 * Initialize a new BasicBinomialHeap with the given comparator
	 * and element.
	 *
	 * @param comparator
	 *        The comparator that is used to determine the order
	 *        of the elements.
	 * @param element
	 *        The initial element in the new BasicBinomialHeap.
	 */
 /*@
   @ public behavior
	 @
	 @ pre comparator != null;
	 @ pre element != null;
	 @
	 @ post getComparator() == comparator;
	 @ post nbExplicitOccurrences(element) == 1;
	 @ post size() == 1;
	 @*/
	public BasicBinomialHeap(Comparator comparator, Object element) {
		this.comparator = comparator;
		this.trees = new BinomialTree(element);
		this.size = 1;
	}

	/**
	 * <p>See superclass.</p>
	 */
	public Comparator getComparator() {
		return comparator;
	}
	
	/**
	 * <p>See superclass.</p>
	 *
	 * <p><b>O(log(n))</b></p>
	 */
	protected void addImpl(Object value) {
		addMerge(new BinomialTree(value));
	}

	private void addMerge(BinomialTree otherTree) {

		if ( (size & 1) == 0 ) {
			size++;
			otherTree.setNext(trees);
			trees = otherTree;
			return;
		}
		size++;
		int theSize = size >> 1;
	
		BinomialTree carry_over = trees;
		BinomialTree currentTree = trees.getNext();
		carry_over.merge(otherTree, comparator);

		while ( (theSize & 1) == 0 ) {
			theSize >>= 1;
			otherTree = currentTree.getNext();
			carry_over.merge(currentTree,comparator);
			currentTree = otherTree;
		}
		carry_over.setNext(currentTree);
		trees = carry_over;
	}

	/**
	 * <p>See superclass.</p>
	 *
	 * <p><b>O(log(n))</b></p>
	 */
	public Object min() {
		BinomialTree current = trees;
		Object result = current.getRoot();
		while ( current.getNext() != null ) {
		   current = current.getNext(); 
		   Object value = current.getRoot();
		   if ( comparator.compare(result, value) > 0 ) {
			   result = value;
		   }
		}
		return result;
	}

	/**
	 * <p>See superclass.</p>
	 * 
	 * <p><b>O(log(n))</b></p>
	 */
	public Object pop() {
		BinomialTree previousRTree = null;
		BinomialTree currentRTree = trees;
		BinomialTree previousTree = null;
		BinomialTree currentTree = trees;
		Object result = currentTree.getRoot();
		while ( currentTree.getNext() != null ) {
		   previousTree = currentTree; 
		   currentTree  = currentTree.getNext(); 
		   Object value = currentTree.getRoot();
		   if ( comparator.compare(result, value) > 0 ) {
			   result = value;
			   previousRTree = previousTree;
			   currentRTree = currentTree;
		   }
		}
		if ( previousRTree != null ) {
			previousRTree.setNext(currentRTree.getNext());
		} else {
			trees = currentRTree.getNext();
		}
		size = size - currentRTree.size();
		if ( currentRTree.children() != null ) {
			merge(currentRTree.children().reverse(),currentRTree.size() - 1);
		}
		return result;
	}

	/**
	 * <p>Add all elements in the given BasicBinomialHeap to this heap
	 * and empty that heap.</p>
	 * 
	 * @param heap
	 *        The heap of which the elements are to be added to this heap.
	 *        
	 * <p><b>O(log((n))</b></p>
	 */
 /*@
   @ public behavior
	 @
	 @ pre heap != null;
	 @ 
	 @ post size() == \old(size()) + \old(heap.size());
	 @ post (\forall Object element; ;
	 @               nbExplicitOccurrences(element) == \old(nbExplicitOccurrences(element)) + 
	 @                                                 \old(heap.nbExplicitOccurrences(element)));
	 @ post (\forall Object element; ;
	 @               heap.nbExplicitOccurrences(element) == 0);
	 @*/
	public void merge(BasicBinomialHeap heap) {
		merge(heap.trees, heap.size());
		heap.clear();
	}

	private void merge(BinomialTree otherTree, int otherSize) {

		if ( otherTree == null ) {
			return;
		}
		
		if ( trees == null ) {
			trees = otherTree;
			size = otherSize;
			return;
		}

		if ( otherSize == 1 ) {
			addMerge(otherTree);
			return;
		}
		
		// At least one cell in each chain
		
		BinomialTree tmp = null;
	
		int oldSize = 0;

		// ensure trees contains 'longest' chain
		if ( size < otherSize ) {
			// swap sizes
			oldSize   = otherSize;
			otherSize = size;
			size = oldSize;
			// swap cells
			tmp = trees;
			trees = otherTree;
			otherTree = tmp;
		}
	
		oldSize = size;
		size += otherSize;

		BinomialTree previousTree = null;
		BinomialTree currentTree  = trees;
		BinomialTree carry_over   = null;
		
		int bits = 0;
		oldSize <<= 2;
		otherSize <<= 1;
		
		do {
		
			// Invariant previousTree == null ||
			//           previousTree.getNext() == currentTree
			bits = bits | (oldSize & 4) | (otherSize & 2);
			oldSize >>= 1;
			otherSize >>= 1;
			
			// bits t o c
			switch (bits) {
				case 0: // 0 0 0
					break;
				case 1: // 0 0 1
					if ( previousTree != null ) { 
						previousTree.setNext(carry_over); 
					} else {
						trees = carry_over;
					}
					previousTree = carry_over;
					previousTree.setNext(currentTree);
					bits = 0;
					break;
				case 2: // 0 1 0
					if ( previousTree != null ) {
						previousTree.setNext(otherTree); 
					} else {
						trees = otherTree;
					}
					previousTree = otherTree;
					otherTree = otherTree.getNext();
					previousTree.setNext(currentTree);
					bits = 0;
					break;
				case 3: // 0 1 1
					tmp = otherTree.getNext();
					carry_over.merge(otherTree,comparator);
					otherTree = tmp;
					bits = 1;
					break;
				case 4: // 1 0 0
					previousTree = currentTree;
					currentTree = currentTree.getNext();
					bits = 0;
					break;
				case 5: // 1 0 1
					if ( previousTree != null ) {
						previousTree.setNext(currentTree.getNext());
					}
					tmp = currentTree.getNext();
					carry_over.merge(currentTree,comparator);
					currentTree = tmp;
					bits = 1;
					break;
				case 6: // 1 1 0
					if ( previousTree != null ) { 
						previousTree.setNext(currentTree.getNext()); 
					} 
					carry_over = currentTree;
					currentTree = currentTree.getNext();
					tmp = otherTree.getNext();
					carry_over.merge(otherTree,comparator);
					otherTree = tmp;
					bits = 1;
					break;
				case 7: // 1 1 1
					if ( previousTree == null ) {
						trees = currentTree;
					}
					previousTree = currentTree;
					currentTree = currentTree.getNext();
					tmp = otherTree.getNext();
					carry_over.merge(otherTree,comparator);
					otherTree = tmp;
					bits = 1;
					break;
			} 
		} while ( otherSize > 1 ) ;


		if ( bits > 0 ) { // bits == 1
			if (previousTree != null ) {
				previousTree.setNext(carry_over);
			} else {
				trees = carry_over;
			}
			while ( (oldSize & 4) > 0 ) {
				oldSize >>= 1;
				tmp = currentTree.getNext();
				carry_over.merge(currentTree,comparator);
				currentTree = tmp;
			}
			carry_over.setNext(currentTree);
		}
	}


	
	/**
	 * <p>See superclass</p>
	 */
	public void clear() {
		trees = null;
		size = 0;
	}

	/**
	 * <p>See superclass.</p>
	 *
	 * <p><b>O(n)</b></p>
	 */
	public int nbExplicitOccurrences(Object element) {
		int count = 0;
		BinomialTree current = trees;
		while ( current != null ) {
			count += current.nbExplicitOccurrences(element);
			current = current.getNext();
		}
		return count;
	}

	/**
	 * <p>See superclass.</p>
	 */
	public int size() {
		return size;
	}


	private static class BinomialTree {
		
	 /*@
	   	@ private invariant root != null;
		@*/
		private Object root;

	 	private BinomialTree next;

	 /*@
	   	@ private invariant size > 0;
		@*/
		private int size = 1;
	
		private BinomialTree children;

	 /*@	
	   	@ public behavior
		@
		@ pre value != null;
		@
		@ post size() == 1;
		@ post getRoot() == value;
		@ post nbExplicitOccurrences(value) == 1;
		@ post children() == null;
		@*/
		public BinomialTree(Object value) {
			this.root = value;
		}
	
	 /*@
	   	@ public behavior
		@
		@ post \result != null;
		@*/
		public Object getRoot() {
			return root;
		}
	 /*@
	   	@ public behavior
		@
		@ post getNext() == next;
		@*/
		public void setNext(BinomialTree next) {
			this.next = next;
		}

		public BinomialTree getNext() {
			return next;
		}

		public void merge(BinomialTree other, Comparator comp) {
			if (comp.compare(this.getRoot(), other.getRoot()) <= 0) {
				mergeImpl(other);
			} else {
				BinomialTree children = this.children;
				Object root = this.root;
				this.root = other.root;
				this.children = other.children;
				other.root = root;
				other.children = children;
				mergeImpl(other);
			}
		}

		private void mergeImpl(BinomialTree other) {
			other.setNext(children);
			children = other;
			size <<= 1;
		}
		
	 /*@
	   	@ public behavior
		@
		@ post \result == (\sum Object item; ; nbExplicitOccurrences(item));
		@ post \result > 0;
		@*/
		public int size() {
			return size;
		}
	 /*@
	   	@ public behavior
		@
		@ post \result >= 0;
		@*/
		public int nbExplicitOccurrences(Object element) {
			int count = (root == element ? 1 : 0);
			BinomialTree current = children;
			while ( current != null ) {
				count += current.nbExplicitOccurrences(element);
				current = current.getNext();
			}
			return count;
		}

		public BinomialTree children() {
			return children;
		}

		public BinomialTree reverse() {
			BinomialTree previous = null;
			BinomialTree current = this;
			BinomialTree temp = null;
			do {
				temp = current.getNext();
				current.setNext(previous);
				previous = current;
			        current = temp;	
			} while ( current != null );
			return previous;
		}
		
	}


}
/*
 * <copyright>Copyright (C) 1997-2001. This software is copyrighted by 
 * the people and entities mentioned after the "@author" tags above, on 
 * behalf of the JUTIL.ORG Project. The copyright is dated by the dates 
 * after the "@date" tags above. All rights reserved.
 * This software is published under the terms of the JUTIL.ORG Software
 * License version 1.1 or later, a copy of which has been included with
 * this distribution in the LICENSE file, which can also be found at
 * http://org-jutil.sourceforge.net/LICENSE. This software is distributed 
 * WITHOUT ANY WARRANTY; without even the implied warranty of 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
 * See the JUTIL.ORG Software License for more details. For more information,
 * please see http://org-jutil.sourceforge.net/</copyright>
 */