inf.util
Interface PriorityQueue<E,N extends java.lang.Number>

Type Parameters:

E - the element type for elements queued

N - the priority type for priorities of the elements

All Superinterfaces:

java.lang.Iterable<E>

All Known Subinterfaces:

DoublePriorityQueue<E>, IntPriorityQueue<E>

All Known Implementing Classes:

ArrayOfHashedListsIntPriorityQueue, ArrayOfListsIntPriorityQueue, RandomAccessIntPriorityQueue, TreeOfListsDoublePriorityQueue

public interface PriorityQueue<E,N extends java.lang.Number>
extends java.lang.Iterable<E>

This class represents a priority queue, that is a queue in which elements can be held and from which they can be retrieved by priority. For this purpose, each element has a numeric priority associated with it that determines when in relation to the other elements in the queue this element should be retrieved. Priorities are Numbers here.

If there are several elements in the queue that have the same priority their order can be managed by adding to the front or the end of the list of elements at that priority. Similarly, retrieval can be from the front or the end of the list of elements with the same priority.

Author:

Gerhard Wickler

Method Summary

void	addElementFirst(E elt, N priority) This function adds the given element at the given priority to this PriorityQueue.
void	addElementLast(E elt, N priority) This function adds the given element at the given priority to this PriorityQueue.
boolean	containsElementAt(E elt, N priority) This function tests whether the given element is currently in this queue at the given priority.
E	getHighestFirst() This function returns the element in this PriorityQueue that has the highest priority.
E	getHighestLast() This function returns the element in this PriorityQueue that has the highest priority.
E	getLowestFirst() This function returns the element in this PriorityQueue that has the lowest priority.
E	getLowestLast() This function returns the element in this PriorityQueue that has the lowest priority.
boolean	isEmpty() This function tests whether this PriorityQueue is empty.
int	length() This function returns the size of this PriorityQueue.
boolean	removeElementAt(E elt, N priority) This function attempts to remove the given element at the given priority from this PriorityQueue.
E	removeHighestFirst() This function removes and returns the element in this PriorityQueue that has the highest priority.
E	removeHighestLast() This function removes and returns the element in this PriorityQueue that has the highest priority.
E	removeLowestFirst() This function removes and returns the element in this PriorityQueue that has the lowest priority.
E	removeLowestLast() This function removes and returns the element in this PriorityQueue that has the lowest priority.

Methods inherited from interface java.lang.Iterable

iterator

Method Detail

addElementFirst

void addElementFirst(E elt,
                     N priority)

This function adds the given element at the given priority to this PriorityQueue. If there are already elements queued at this priority, the new element will be queued at the front.

Parameters:

elt - the element to be added to this PriorityQueue

priority - the priority with which the element is to be queued

addElementLast

void addElementLast(E elt,
                    N priority)

This function adds the given element at the given priority to this PriorityQueue. If there are already elements queued at this priority, the new element will be queued at the end.

Parameters:

elt - the element to be added to this PriorityQueue

priority - the priority with which the element is to be queued

isEmpty

boolean isEmpty()

This function tests whether this PriorityQueue is empty.

Returns:

true if and only if this PriorityQueue contains no elements

length

int length()

This function returns the size of this PriorityQueue.

Returns:

the number of elements contained in this PriorityQueue

getLowestFirst

E getLowestFirst()
                 throws java.util.NoSuchElementException

This function returns the element in this PriorityQueue that has the lowest priority. If there are several elements queued at that priority, the element at the front of the list is retrieved. An exception is thrown if there is no such element, i.e. if this PriorityQueue is empty.

Returns:

an element that has the lowest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

getLowestLast

E getLowestLast()
                throws java.util.NoSuchElementException

This function returns the element in this PriorityQueue that has the lowest priority. If there are several elements queued at that priority, the element at the end of the list is retrieved. An exception is thrown if there is no such element, i.e. if this PriorityQueue is empty.

Returns:

an element that has the lowest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

getHighestFirst

E getHighestFirst()
                  throws java.util.NoSuchElementException

This function returns the element in this PriorityQueue that has the highest priority. If there are several elements queued at that priority, the element at the front of the list is retrieved. An exception is thrown if there is no such element, i.e. if this PriorityQueue is empty.

Returns:

an element that has the highest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

getHighestLast

E getHighestLast()
                 throws java.util.NoSuchElementException

This function returns the element in this PriorityQueue that has the highest priority. If there are several elements queued at that priority, the element at the end of the list is retrieved. An exception is thrown if there is no such element, i.e. if this PriorityQueue is empty.

Returns:

an element that has the highest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

containsElementAt

boolean containsElementAt(E elt,
                          N priority)

This function tests whether the given element is currently in this queue at the given priority.

Parameters:

elt - the element to be tested for

priority - the priority at which it should be queued

Returns:

whether it is indeed in the queue

removeLowestFirst

E removeLowestFirst()
                    throws java.util.NoSuchElementException

This function removes and returns the element in this PriorityQueue that has the lowest priority. If there are several elements queued at that priority, the element at the front of the list is retrieved. An exception is thrown if there is no such element, i.e. if this priority queue is empty.

Returns:

an element that has the lowest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

removeLowestLast

E removeLowestLast()
                   throws java.util.NoSuchElementException

This function removes and returns the element in this PriorityQueue that has the lowest priority. If there are several elements queued at that priority, the element at the end of the list is retrieved. An exception is thrown if there is no such element, i.e. if this priority queue is empty.

Returns:

an element that has the lowest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

removeHighestFirst

E removeHighestFirst()
                     throws java.util.NoSuchElementException

This function removes and returns the element in this PriorityQueue that has the highest priority. If there are several elements queued at that priority, the element at the front of the list is retrieved. An exception is thrown if there is no such element, i.e. if this priority queue is empty.

Returns:

an element that has the highest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

removeHighestLast

E removeHighestLast()
                    throws java.util.NoSuchElementException

This function removes and returns the element in this PriorityQueue that has the highest priority. If there are several elements queued at that priority, the element at the end of the list is retrieved. An exception is thrown if there is no such element, i.e. if this priority queue is empty.

Returns:

an element that has the highest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

removeElementAt

boolean removeElementAt(E elt,
                        N priority)

This function attempts to remove the given element at the given priority from this PriorityQueue. Whether the removal was successful is returned.

Parameters:

elt - the element to be removed from this PriorityQueue

priority - the priority at which the element is currently queued

Returns:

true if and only if the element was indeed removed from the queue