Opus5
Class Deap

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

All Implemented Interfaces:

Comparable, Container, DoubleEndedPriorityQueue, PriorityQueue

public class Deap

extends AbstractContainer

implements DoubleEndedPriorityQueue

A double-ended priority queue implemented as a binary heap.

Version:

$Id: Deap.java,v 3.4 1998/07/28 20:06:20 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

Field Summary

protected Comparable[]

array The heap.

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.DoubleEndedPriorityQueue

copyright

Constructor Summary

Deap(int length)
Constructs a Deap with the specified length.

Method Summary

void	accept(Visitor visitor) Accepts the specified visitor and makes it visit all the objects in this deap.
protected int	compareTo(Comparable arg) Compares this deap with the specified comparable object.
Comparable	dequeueMax() Dequeues and returns the "largest" object in this deap.
Comparable	dequeueMin() Dequeues and returns the "smallest" object in this deap.
protected int	dual(int i) Returns the position in this deap of the dual of the object at the specified position.
void	enqueue(Comparable object) Inserts the specified object into this deap.
Comparable	findMax() Returns the "largest" object in this deap.
Comparable	findMin() Returns the "smallest" object in this deap.
Enumeration	getEnumeration() Returns an enumeration that enumerates all the objects in this deap.
protected void	insertMax(int pos, Comparable object) Inserts the specified object starting at the specified position in the max-heap side of this deap.
protected void	insertMin(int pos, Comparable object) Inserts the specified object starting at the specified position in the min-heap side of this deap.
boolean	isFull() Tests whether this deap is full.
void	purge() Purges this deap, making it empty.

Methods inherited from class Opus5.AbstractContainer

getCount, hashCode, isEmpty, toString

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

Methods inherited from interface Opus5.Comparable

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

Field Detail

array

protected Comparable[] array

The heap.

Constructor Detail

Deap

public Deap(int length)

Constructs a Deap with the specified length.

Parameters:

length - The desired length.

Method Detail

purge

public void purge()

Purges this deap, making it empty.

Specified by:

purge in interface Container

dual

protected int dual(int i)

Returns the position in this deap of the dual of the object at the specified position.

Parameters:

i - The specified position.

Returns:

The position in this deap of the dual of the object at the specified position.

findMin

public Comparable findMin()

Returns the "smallest" object in this deap. The smallest object in this deap is the object which is less than or equal to all other objects in this deap.

Specified by:

findMin in interface PriorityQueue

Returns:

The "smallest" object in this deap.

Throws:

ContainerEmptyException - If this deap is empty.

findMax

public Comparable findMax()

Returns the "largest" object in this deap. The largest object in this deap is the object which is greater than or equal to all other objects in this deap.

Specified by:

findMax in interface DoubleEndedPriorityQueue

Returns:

The "largest" object in this deap.

Throws:

ContainerEmptyException - If this deap is empty.

insertMin

protected void insertMin(int pos,
                         Comparable object)

Inserts the specified object starting at the specified position in the min-heap side of this deap.

Parameters:

pos - The position at which to start.

object - The object to insert.

insertMax

protected void insertMax(int pos,
                         Comparable object)

Inserts the specified object starting at the specified position in the max-heap side of this deap.

Parameters:

pos - The position at which to start.

object - The object to insert.

enqueue

public void enqueue(Comparable object)

Inserts the specified object into this deap.

Specified by:

enqueue in interface PriorityQueue

Parameters:

object - The object to insert.

Throws:

ContainerFullException - If this deap is full.

dequeueMin

public Comparable dequeueMin()

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

Specified by:

dequeueMin in interface PriorityQueue

Returns:

The "smallest" object in this deap.

Throws:

ContainerEmptyException - If this deap is empty.

dequeueMax

public Comparable dequeueMax()

Dequeues and returns the "largest" object in this deap. The largest object in this deap is the object which is larger than or equal to all other objects in this deap.

Specified by:

dequeueMax in interface DoubleEndedPriorityQueue

Returns:

The "largest" object in this deap.

Throws:

ContainerEmptyException - If this deap is empty.

isFull

public boolean isFull()

Tests whether this deap is full.

Specified by:

isFull in interface Container

Overrides:

isFull in class AbstractContainer

Returns:

True if this deap is full; false otherwise.

accept

public void accept(Visitor visitor)

Accepts the specified visitor and makes it visit all the objects in this deap.

Specified by:

accept in interface Container

Overrides:

accept in class AbstractContainer

Parameters:

The - visitor to accept.

getEnumeration

public Enumeration getEnumeration()

Returns an enumeration that enumerates all the objects in this deap.

Specified by:

getEnumeration in interface Container

Returns:

an enumeration that enumerates all the objects in this deap.

compareTo

protected int compareTo(Comparable arg)

Compares this deap 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 deap.

Throws:

MethodNotImplemented - Always.