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.1, 19th March, 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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, 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, they are stored in the order in which they were added (i.e. this one is placed after any exising elements with equal priority).

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, they are stored in the order in which they were added (i.e. this one is placed after any exising elements with equal priority). 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, they are ordered in the same order that entries were originally entered.

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, they are ordered in the same order that entries were originally entered.

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.