jwo.utils.structure
Class JWPriorityQueue

java.lang.Object
  jwo.utils.structure.JWPriorityQueue

public class JWPriorityQueue

extends Object

Class for handling priority queues. A priority queue is an ordered list of objects whose order is determined by a user-supplied priority. The queue can have entries sharing identical priorities, although it should be noted that this version is not optimised for queues with a small number of priorities in comparison to the number of queue entries.

Version:

2.2, 4th November, 2004.

Author:

Jo Wood.

Constructor Summary

JWPriorityQueue()
Creates an empty priority queue.

Method Summary

boolean	containsValue(float priority) Reports whether or not the priority queue contains an element with the given priority.
boolean	containsValue(Object element) Reports whether or not the priority queue contains the given element.
Object	getFirst() Reports the highest priority element in the queue without removing it.
Object	getLast() Reports the lowest priority element in the queue without removing it.
float	getPriority(Object element) Reports the priority associated with the given object.
void	insert(Object element) Adds an item to the priority queue using the default priority of 0.
void	insert(Object element, float priority) Adds ('pushes') an item to the priority queue using the given priority.
static void	main(String[] args) Used for testing the priority queue
boolean	remove(Object element) Removes the given element from the queue regardless of its priority.
Object	removeFirst() Reports and removes ('pops') the highest priority element in the queue.
Object	removeLast() Reports and removes ('pops') the lowest priority element in the queue.
boolean	setPriority(Object element, float priority) Sets the priority associated with the given object.
int	size() Reports the number of elements stored in this priority queue.
String	toString() Provides a formatted piece of text representing the contents of the priority queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

JWPriorityQueue

public JWPriorityQueue()

Creates an empty priority queue.

Method Detail

main

public static void main(String[] args)

Used for testing the priority queue

insert

public void insert(Object element)

Adds an item to the priority queue using the default priority of 0. If an element with equal priority already exists, the new item will be stored in the natural (Comparable) order of the other elements sharing its priority. If the elments do not have a natural order (ie they do not implement the Comparable interface), they are stored in the order in which they were added.

Parameters:

element - Item to add to the queue.

insert

public void insert(Object element,
                   float priority)

Adds ('pushes') an item to the priority queue using the given priority. If an element with equal priority already exists, the new item will be stored in the natural (Comparable) order of the other elements sharing its priority. If the elments do not have a natural order (ie they do not implement the Comparable interface), they are stored in the order in which they were added. Priority values can be any number including non-integers.

Parameters:

element - Item to add to the queue.

priority - Priority to give added item.

getFirst

public Object getFirst()

Reports the highest priority element in the queue without removing it. In the case of elements with equal priority, the retrieved item will be the first one in the natural (Comparable) order of the other elements sharing its priority. If the elments do not have a natural order (ie they do not implement the Comparable interface), they are retrieved in the order in which they were added.

Returns:

Highest priority item in queue or null if queue is empty.

getLast

public Object getLast()

Reports the lowest priority element in the queue without removing it. In the case of elements with equal priority, the retrieved item will be the last one in the natural (Comparable) order of the other elements sharing its priority. If the elments do not have a natural order (ie they do not implement the Comparable interface), they are retrieved in the opposite order in which they were added.

Returns:

Lowest priority item in queue or null if queue is empty.

removeFirst

public Object removeFirst()

Reports and removes ('pops') the highest priority element in the queue. In the case of elements with equal priority, they are ordered in the same order that entries were originally entered.

Returns:

Highest priority item in queue or null if queue is empty.

removeLast

public Object removeLast()

Reports and removes ('pops') the lowest priority element in the queue. In the case of elements with equal priority, they are ordered in the same order that entries were originally entered.

Returns:

Lowest priority item in queue or null if queue is empty.

remove

public boolean remove(Object element)

Removes the given element from the queue regardless of its priority.

Parameters:

element - Element to remove from queue.

Returns:

True if element removed, or false if element not found.

getPriority

public float getPriority(Object element)

Reports the priority associated with the given object.

Parameters:

element - Element from which to find priority.

Returns:

Priority associated with the given element or -Float.MAX_VALUE if not found.

setPriority

public boolean setPriority(Object element,
                           float priority)

Sets the priority associated with the given object.

Parameters:

element - Element to set with new priority.

priority - New priority to attach to element.

Returns:

True if element found.

size

public int size()

Reports the number of elements stored in this priority queue.

Returns:

Number of stored elements.

containsValue

public boolean containsValue(Object element)

Reports whether or not the priority queue contains the given element. Note that if the priority value is known, call containsValue(element, priority) instead which has O(logN) complexity rather than this method which O(n).

Parameters:

element - Element to search for.

Returns:

true if the queue contains the given value.

containsValue

public boolean containsValue(float priority)

Reports whether or not the priority queue contains an element with the given priority. Note that this method is preferable to containsValue(element) as it has O(logN) complexity rather than the other which is O(n).

Returns:

true if the queue contains the given value.

toString

public String toString()

Provides a formatted piece of text representing the contents of the priority queue. Items are displayed in their priority order with elements that share the same priority displayed in their natural order if they have one, or the order in which they were added if they do not.

Returns:

Textual representation of the queue.