tauzaman.calendricsystem.granularitylattice.minpriorityqueue
Class MinPriorityQueue

java.lang.Object
  |
  +--tauzaman.calendricsystem.granularitylattice.minpriorityqueue.MinPriorityQueue

public class MinPriorityQueue

extends java.lang.Object

Constructor Summary

MinPriorityQueue()
Constructs a minimum priority queue by initializing its array to the default size and intializing the value -> index hashtable.

Method Summary

boolean	decreasePriority(java.lang.Object value, java.lang.Comparable newPriority) Given a particular element already in the queue, decrease its priority to the given priority.
MPQElement	dequeue() Deletes and returns the element at the root (the element with the minimum priority) of the heap.
void	enqueue(java.lang.Comparable priority, java.lang.Object value) Inserts a new element into the priority queue.
int	getSize() Returns the number of elements currently in the queue.
boolean	isEmpty() Returns whether or not the queue is empty.
static void	main(java.lang.String[] args)
java.lang.String	toString() Returns a string representation of the minimum priority queue.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

MinPriorityQueue

public MinPriorityQueue()

Constructs a minimum priority queue by initializing its array to the default size and intializing the value -> index hashtable.

Method Detail

enqueue

public void enqueue(java.lang.Comparable priority,
                    java.lang.Object value)

Inserts a new element into the priority queue. First it inserts the element at the end of the queue (after possibly adjusting the size of the queue such that the new element will fit). Second, it bubbles the element up the heap until it is smaller than its parent.

Parameters:

priority - The priority of the new element.

value - The value of the new element.

dequeue

public MPQElement dequeue()

Deletes and returns the element at the root (the element with the minimum priority) of the heap. First, save the element at the root to return. Then delete the last element in the heap and give its value to be the new root. Lastly, bubble this element down until its children are both less than this element or until this element is at a leaf.

Returns:

The element with the minimum priority (or null if the queue is empty.

decreasePriority

public boolean decreasePriority(java.lang.Object value,
                                java.lang.Comparable newPriority)

Given a particular element already in the queue, decrease its priority to the given priority.

Parameters:

value - The element whose priority we want to decrease.

newPriority - The new priority for the element.

Returns:

true if the priority was changed, false if the priority given was greater than the original priority or if the element is not in the queue

getSize

public int getSize()

Returns the number of elements currently in the queue.

Returns:

The number of elements currently in the queue.

isEmpty

public boolean isEmpty()

Returns whether or not the queue is empty.

Returns:

true if the queue is empty, false if the queue has elements

toString

public java.lang.String toString()

Returns a string representation of the minimum priority queue.

Overrides:

toString in class java.lang.Object

Returns:

a string representation of the minimum priority queue

main

public static void main(java.lang.String[] args)