javaslam.util
Class PriorityQueue

java.lang.Object
  |
  +--javaslam.util.PriorityQueue

public class PriorityQueue

extends Object

A priority queue.

Nested Class Summary

protected class	PriorityQueue.QueueElement An item in a priority queue.
protected class	PriorityQueue.QueueItemIterator An iterator over queue items.

Field Summary

protected ArrayList	elements A list of QueueElement objects ordered by their priorities.
protected Map	itemsToElements Maps items to their elements.

Constructor Summary

PriorityQueue()
Constructor.

Method Summary

void	clear() Removes all items from this queue.
Object	dequeue() Dequeues the item with the highest priority.
void	enqueue(Object item, Comparable priority) Enqueues a new item with the supplied priority.
Comparable	highest() Returns the priority of the highest priority item in the queue.
boolean	isEmpty() Returns true iff this queue is empty.
Iterator	iterator() Returns an iterator over the items in this priority queue in order of decreasing priority.
Object	peek() Returns the item with the highest priority without removing it from the queue.
void	remove(Object item) Removes a particular item from the queue, if it exists.
void	reprioritize(Object item, Comparable priority) Updates the priority of an item already in the queue.
int	size() Returns the number of items in this queue.
String	toString() Returns a string representation of this priority queue.

Methods inherited from class java.lang.Object

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

Field Detail

elements

protected ArrayList elements

A list of QueueElement objects ordered by their priorities.

itemsToElements

protected Map itemsToElements

Maps items to their elements.

Constructor Detail

PriorityQueue

public PriorityQueue()

Constructor.

Method Detail

isEmpty

public boolean isEmpty()

Returns true iff this queue is empty.

iterator

public Iterator iterator()

Returns an iterator over the items in this priority queue in order of decreasing priority.

size

public int size()

Returns the number of items in this queue.

clear

public void clear()

Removes all items from this queue.

enqueue

public void enqueue(Object item,
                    Comparable priority)

Enqueues a new item with the supplied priority. If the item was already present in the queue, then this method has no effect; in particular, it does not change the priority of item to priority.

Parameters:

item - the new item to enqueue

priority - the priority of the new item

Throws:

ClassCastException - if the supplied priority is not comparable to the priorities of the previously enqueued items

dequeue

public Object dequeue()

Dequeues the item with the highest priority. If this queue is empty, then null is returned.

Returns:

the item with the highest priority or null if this queue is empty

remove

public void remove(Object item)

Removes a particular item from the queue, if it exists.

Parameters:

item - the item to be removed

peek

public Object peek()

Returns the item with the highest priority without removing it from the queue. If this queue is empty, then null is returned.

Returns:

the item with the highest priority or null if this queue is empty

highest

public Comparable highest()

Returns the priority of the highest priority item in the queue.

Returns:

the highest priority of any item in the queue or null if this queue is empty

reprioritize

public void reprioritize(Object item,
                         Comparable priority)

Updates the priority of an item already in the queue. If the item was not in the queue, then it is enqueued with the supplied priority.

Parameters:

item - the item whose priority is to be changed

priority - the new priority of the item

Throws:

ClassCastException - if the supplied priority is not comparable to the priorities of the previously enqueued items

toString

public String toString()

Returns a string representation of this priority queue.

Overrides:

toString in class Object