Class DynamicHeap

java.lang.Object
  DynamicHeap

All Implemented Interfaces:

FIFOQueue, PriorityQueue

public class DynamicHeap

extends java.lang.Object

implements PriorityQueue, FIFOQueue

Generic heap that also supports FIFO access, backed by a dynamic array; stores items of type Object with priorities of type Comparable, and correctly handles multiple items with the same priority.

Constructor Summary

DynamicHeap()
Initializes this heap to be empty.

Method Summary

void	decreasePriority(java.lang.Object item, java.lang.Comparable priority) Decreases the priority of the given item to the given priority value if the new priority is less than the old, does nothing otherwise.
java.lang.Object	deleteMinPriority() Removes the first item with smallest priority from this queue, and returns this item.
java.lang.Object	dequeueFIFO() Removes the item that was inserted first into this queue, and returns this item.
java.lang.Object	getMinPriority() Returns the first item with smallest priority value in this queue.
int	getSize() Returns the current size (number of items) in this queue.
java.lang.Object	headFIFO() Returns the item that was inserted first into this queue.
void	insert(java.lang.Object item, java.lang.Comparable priority) Adds the given item with the given priority to this queue.
boolean	isEmpty() Returns true if the queue is empty and false otherwise.
java.lang.String	toString() Returns a String representation of this heap.
java.lang.String	toStringDebug() Returns a String representation of this queue that tries to include all information, for debugging.
java.lang.String	toStringFIFO() Returns a String representation of this FIFO queue.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

DynamicHeap

public DynamicHeap()

Initializes this heap to be empty.

Method Detail

toString

public java.lang.String toString()

Returns a String representation of this heap.

Returns:

a String representation of this heap

toStringFIFO

public java.lang.String toStringFIFO()

Returns a String representation of this FIFO queue.

Returns:

a String representation of this FIFO queue

toStringDebug

public java.lang.String toStringDebug()

Returns a String representation of this queue that tries to include all information, for debugging.

Returns:

a String representation of this queue for debugging

isEmpty

public boolean isEmpty()

Description copied from interface: PriorityQueue

Returns true if the queue is empty and false otherwise.

Specified by:

isEmpty in interface PriorityQueue

Returns:

true if the queue is empty, false otherwise.

getMinPriority

public java.lang.Object getMinPriority()

Returns the first item with smallest priority value in this queue. Precondition: this queue is not empty

Specified by:

getMinPriority in interface PriorityQueue

Returns:

the first item with smallest priority value in this queue

Throws:

java.lang.NullPointerException - if this queue is empty

See Also:

PriorityQueue.getMinPriority()

deleteMinPriority

public java.lang.Object deleteMinPriority()

Removes the first item with smallest priority from this queue, and returns this item. Precondition: this queue is not empty

Specified by:

deleteMinPriority in interface PriorityQueue

Returns:

the first item with smallest priority in this queue

Throws:

java.lang.NullPointerException - if this queue is empty

See Also:

PriorityQueue.deleteMinPriority()

insert

public void insert(java.lang.Object item,
                   java.lang.Comparable priority)

Adds the given item with the given priority to this queue. Precondition: item != null, priority != null

Specified by:

insert in interface PriorityQueue

Parameters:

item - the item to add to this queue

priority - the priority for item

Throws:

java.lang.NullPointerException - if item == null or priority == null

See Also:

PriorityQueue.insert()

decreasePriority

public void decreasePriority(java.lang.Object item,
                             java.lang.Comparable priority)

Decreases the priority of the given item to the given priority value if the new priority is less than the old, does nothing otherwise. Precondition: item != null, priority != null

Specified by:

decreasePriority in interface PriorityQueue

Parameters:

item - whose priority will be decreased

priority - the new priority value for item

Throws:

java.lang.NullPointerException - if item == null or priority == null

headFIFO

public java.lang.Object headFIFO()

Returns the item that was inserted first into this queue. Precondition: this queue is not empty

Specified by:

headFIFO in interface FIFOQueue

Returns:

the first item in this queue

Throws:

java.lang.IndexOutOfBoundsException - if this queue is empty

See Also:

FIFOQueue.headFIFO()

dequeueFIFO

public java.lang.Object dequeueFIFO()

Removes the item that was inserted first into this queue, and returns this item. Precondition: this queue is not empty

Specified by:

dequeueFIFO in interface FIFOQueue

Returns:

the first item in this queue

Throws:

java.lang.IndexOutOfBoundsException - if this queue is empty

See Also:

FIFOQueue.dequeueFIFO()

getSize

public int getSize()

Returns the current size (number of items) in this queue.

Specified by:

getSize in interface FIFOQueue

Returns:

the current size (number of items) in this queue

See Also:

FIFOQueue.getSize()