Opus5
Class BinomialQueue

java.lang.Object
  |
  +--Opus5.AbstractObject
        |
        +--Opus5.AbstractContainer
              |
              +--Opus5.BinomialQueue

All Implemented Interfaces:

Comparable, Container, MergeablePriorityQueue, PriorityQueue

public class BinomialQueue

extends AbstractContainer

implements MergeablePriorityQueue

A mergeable priority queue implemented as a forest of binomial trees.

Version:

$Id: BinomialQueue.java,v 3.7 1998/07/29 14:24:26 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

Inner Class Summary

protected static class

BinomialQueue.BinomialTree A node in a binomial tree.

Field Summary

protected LinkedList

treeList A linked list of binomial trees---the forest.

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.MergeablePriorityQueue

copyright

Constructor Summary

BinomialQueue()
Constructs an empty BinomialQueue.

Method Summary

void	accept(Visitor visitor) Accepts the specified visitor and makes it visit all the objects contained in this binomial queue.
protected void	addTree(BinomialQueue.BinomialTree tree) Adds the specified binomial tree to this binomial queue.
protected BinomialQueue.BinomialTree	carry(BinomialQueue.BinomialTree a, BinomialQueue.BinomialTree b, BinomialQueue.BinomialTree c) Returns the "carry" which results when three binomial trees are "added".
protected int	compareTo(Comparable arg) Compares this binomial queue with the specified comparable object.
Comparable	dequeueMin() Dequeues and returns the "smallest" object in this binomial queue.
void	enqueue(Comparable object) Enqueues the specified object in this binomial queue.
Comparable	findMin() Returns the "smallest" object in this binomial queue.
protected BinomialQueue.BinomialTree	findMinTree() Returns the binomial tree in this binomial queue that has the "smallest" root.
Enumeration	getEnumeration() Returns an enumeration that enumerates the objects contained in this binomial queue.
void	merge(MergeablePriorityQueue queue) Merges the specified mergeable priority queue with this binomial queue.
void	purge() Purges this binomial queue, making it empty.
protected void	removeTree(BinomialQueue.BinomialTree tree) Removes the specified binomial tree from this binomial queue.
protected BinomialQueue.BinomialTree	sum(BinomialQueue.BinomialTree a, BinomialQueue.BinomialTree b, BinomialQueue.BinomialTree c) Returns the "sum" which results when three binomial trees are "added".
java.lang.String	toString() Returns a string representation of this binomial queue.

Methods inherited from class Opus5.AbstractContainer

getCount, hashCode, isEmpty, isFull

Methods inherited from class Opus5.AbstractObject

compare, equals, isEQ, isGE, isGT, isLE, isLT, isNE

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Opus5.Container

getCount, isEmpty, isFull

Methods inherited from interface Opus5.Comparable

compare, isEQ, isGE, isGT, isLE, isLT, isNE

Field Detail

treeList

protected LinkedList treeList

A linked list of binomial trees---the forest.

Constructor Detail

BinomialQueue

public BinomialQueue()

Constructs an empty BinomialQueue.

Method Detail

addTree

protected void addTree(BinomialQueue.BinomialTree tree)

Adds the specified binomial tree to this binomial queue.

Parameters:

tree - The binomial tree to add.

removeTree

protected void removeTree(BinomialQueue.BinomialTree tree)

Removes the specified binomial tree from this binomial queue.

Parameters:

tree - The binomial tree to remove.

purge

public void purge()

Purges this binomial queue, making it empty.

Specified by:

purge in interface Container

accept

public void accept(Visitor visitor)

Accepts the specified visitor and makes it visit all the objects contained in this binomial queue.

Specified by:

accept in interface Container

Overrides:

accept in class AbstractContainer

Parameters:

visitor - The visitor to accept.

findMinTree

protected BinomialQueue.BinomialTree findMinTree()

Returns the binomial tree in this binomial queue that has the "smallest" root. The smallest root is the root which is less than or equal to all other roots.

Returns:

The binomial tree in this binomial queue that has the "smallest" root.

findMin

public Comparable findMin()

Returns the "smallest" object in this binomial queue. The smallest object in this binomial queue is the object that is less than or equal to all other objects in this binomial queue.

Specified by:

findMin in interface PriorityQueue

Returns:

The "smallest" object in this binomial queue.

Throws:

ContainerEmptyException - If this binomial queue is empty.

merge

public void merge(MergeablePriorityQueue queue)

Merges the specified mergeable priority queue with this binomial queue. The specified binomial queue is assuemed to be a BinomialQueue instance. After merging, the specified queue is empty.

Specified by:

merge in interface MergeablePriorityQueue

Parameters:

queue - The mergeable priority queue to merge with this binomial queue.

sum

protected BinomialQueue.BinomialTree sum(BinomialQueue.BinomialTree a,
                                         BinomialQueue.BinomialTree b,
                                         BinomialQueue.BinomialTree c)

Returns the "sum" which results when three binomial trees are "added". Each argument is either a binomial tree or null. All three trees are assumed to have the same order.

Parameters:

a - A binomial tree.

b - A binomial tree.

c - A binomial tree.

Returns:

The "sum" which results when three binomial trees are "added".

See Also:

carry(Opus5.BinomialQueue.BinomialTree, Opus5.BinomialQueue.BinomialTree, Opus5.BinomialQueue.BinomialTree)

carry

protected BinomialQueue.BinomialTree carry(BinomialQueue.BinomialTree a,
                                           BinomialQueue.BinomialTree b,
                                           BinomialQueue.BinomialTree c)

Returns the "carry" which results when three binomial trees are "added". Each argument is either a binomial tree or null. All three trees are assumed to have the same order.

Parameters:

a - A binomial tree.

b - A binomial tree.

c - A binomial tree.

Returns:

The "carry" which results when three binomial trees are "added".

See Also:

sum(Opus5.BinomialQueue.BinomialTree, Opus5.BinomialQueue.BinomialTree, Opus5.BinomialQueue.BinomialTree)

enqueue

public void enqueue(Comparable object)

Enqueues the specified object in this binomial queue.

Specified by:

enqueue in interface PriorityQueue

Parameters:

object - The object to enqueue.

dequeueMin

public Comparable dequeueMin()

Dequeues and returns the "smallest" object in this binomial queue. The smallest object in this binomial queue is the object that is less than or equal to all other objects in this binomial queue.

Specified by:

dequeueMin in interface PriorityQueue

Returns:

The "smallest" object in this binomial queue.

Throws:

ContainerEmptyException - If this binomial queue is empty.

toString

public java.lang.String toString()

Returns a string representation of this binomial queue.

Overrides:

toString in class AbstractContainer

Returns:

a string representation of this binomial queue.

getEnumeration

public Enumeration getEnumeration()

Returns an enumeration that enumerates the objects contained in this binomial queue. This method is not implemented.

Specified by:

getEnumeration in interface Container

Throws:

MethodNotImplemented - Always.

compareTo

protected int compareTo(Comparable arg)

Compares this binomial queue with the specified comparable object. This method is not implemented.

Overrides:

compareTo in class AbstractObject

Parameters:

arg - The comparable object with which to compare this binomial queue.

Throws:

MethodNotImplemented - Always.