inf.util
Class RandomAccessIntPriorityQueue<E>

java.lang.Object
  inf.util.RandomAccessIntPriorityQueue<E>

Type Parameters:

E - the element type for elements queued

All Implemented Interfaces:

IntPriorityQueue<E>, PriorityQueue<E,java.lang.Integer>, java.lang.Iterable<E>

public class RandomAccessIntPriorityQueue<E>
extends java.lang.Object
implements IntPriorityQueue<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 object has a priority associated with it that determines when in relation to the other elements in the queue this element should be retrieved. Priorities are ints here.

The implementation of this priority queue is achieved by maintaining the elements in a sorted tree. The order is determined by the priority and each tree node contains a LinkedList of all the nodes with the same priority. In this way a reasonably efficient execution of most of the operations provided can be guaranteed even for very long queues. The removal of elements from this queue and the contains-test with a given priority are supported but inefficient. Queued elements may be null.

In addition to the operations by IntPriorityQueue which give access to elements with lowest and highest priority, this class also supports getting elements from the queue that are at random positions in a reasonably efficient way. The worst case time complexity for these operations is O(n) though, where n is the number elements queued at the same priority.

Author:

Gerhard Wickler

Nested Class Summary

(package private) static class	RandomAccessIntPriorityQueue.RAIntKeyTreeEntry<E>
(package private) class	RandomAccessIntPriorityQueue.RAIntKeyTreeMapIterator<T>
(package private) class	RandomAccessIntPriorityQueue.RAIntPriorityQueueIterator<T> This class represents an iterator for the elements in an TreeOfListsIntPriorityQueue.

Field Summary

protected RandomAccessIntPriorityQueue.RAIntKeyTreeEntry<E>

root the root of the tree

Constructor Summary

RandomAccessIntPriorityQueue()
This constructor creates an empty PriorityQueue.

Method Summary

void	addElementFirst(E element, int priority) This function adds the given element at the given priority to this priority queue.
void	addElementFirst(E element, java.lang.Integer priority) This function adds the given element at the given priority to this priority queue.
void	addElementLast(E element, int priority) This function adds the given element at the given priority to this priority queue.
void	addElementLast(E element, java.lang.Integer priority) This function adds the given element at the given priority to this priority queue.
protected RandomAccessIntPriorityQueue<E>	clone() This class does not support cloning and an Exception will be thrown if this method is called.
boolean	containsElementAt(E element, int priority) This function tests whether the given element is currently in this queue at the given priority.
boolean	containsElementAt(E element, java.lang.Integer priority) This function tests whether the given element is currently in this queue at the given priority.
boolean	equals(java.lang.Object obj) This class does not support equality testing and an exception will be thrown if this method is called.
E	getHighestFirst() This function returns the element in this priority queue that has the highest priority.
E	getHighestLast() This function returns the element in this priority queue that has the highest priority.
E	getLowestFirst() This function returns the element in this priority queue that has the lowest priority.
E	getLowestLast() This function returns the element in this priority queue that has the lowest priority.
int	getNrOfPriorities() This function returns the number of different priorities currently used in this queue.
int	getNthPriority(int n) This function determines the nth priority value used in this queue.
int	hashCode() This class does not support hashing and an exception will be thrown if this method is called.
boolean	isEmpty() This function tests whether this PriorityQueue is empty.
java.util.Iterator<E>	iterator() This function returns an Iterator for this priority queue.
int	length() This function returns the size of this priority queue.
int	lengthAt(int priority) This function returns the number of elements queued at the given priority.
boolean	removeElementAt(E element, int priority) This function attempts to remove the given element at the given priority from this priority queue.
boolean	removeElementAt(E element, java.lang.Integer priority) This function attempts to remove the given element at the given priority from this priority queue.
E	removeFirstAt(int priority) This function removes and returns the element that is at the front of the queue at the given priority.
E	removeHighestFirst() This function removes and returns the element in this priority queue that has the highest priority.
E	removeHighestLast() This function removes and returns the element in this priority queue that has the highest priority.
E	removeLastAt(int priority) This function removes and returns the element that is at the end of the queue at the given priority.
E	removeLowestFirst() This function removes and returns the element in this priority queue that has the lowest priority.
E	removeLowestLast() This function removes and returns the element in this priority queue that has the lowest priority.
E	removeNthAt(int priority, int n) This function removes and returns the nth element at the given priority in this queue.
E	removeNthElement(int n) This function removes and returns the nth element in this queue.
java.lang.String	toString() This function creates the printable string representation of this priority queue.

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

root

protected RandomAccessIntPriorityQueue.RAIntKeyTreeEntry<E> root

the root of the tree

Constructor Detail

RandomAccessIntPriorityQueue

public RandomAccessIntPriorityQueue()

This constructor creates an empty PriorityQueue.

Method Detail

clone

protected RandomAccessIntPriorityQueue<E> clone()
                                         throws java.lang.CloneNotSupportedException

This class does not support cloning and an Exception will be thrown if this method is called.

Overrides:

clone in class java.lang.Object

Returns:

nothing

Throws:

java.lang.CloneNotSupportedException - will be thrown

addElementFirst

public void addElementFirst(E element,
                            java.lang.Integer priority)

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

Specified by:

addElementFirst in interface PriorityQueue<E,java.lang.Integer>

Parameters:

element - the element to be added to this IntPriorityQueue

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

addElementLast

public void addElementLast(E element,
                           java.lang.Integer priority)

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

Specified by:

addElementLast in interface PriorityQueue<E,java.lang.Integer>

Parameters:

element - the element to be added to this IntPriorityQueue

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

isEmpty

public boolean isEmpty()

This function tests whether this PriorityQueue is empty.

Specified by:

isEmpty in interface PriorityQueue<E,java.lang.Integer>

Returns:

true if and only if this PriorityQueue contains no elements

length

public int length()

This function returns the size of this priority queue.

Specified by:

length in interface PriorityQueue<E,java.lang.Integer>

Returns:

the number of elements contained in this PriorityQueue

getLowestFirst

public E getLowestFirst()
                 throws java.util.NoSuchElementException

This function returns the element in this priority queue 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.

Specified by:

getLowestFirst in interface PriorityQueue<E,java.lang.Integer>

Returns:

the element that has the lowest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

getLowestLast

public E getLowestLast()
                throws java.util.NoSuchElementException

This function returns the element in this priority queue 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.

Specified by:

getLowestLast in interface PriorityQueue<E,java.lang.Integer>

Returns:

the element that has the lowest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

getHighestFirst

public E getHighestFirst()
                  throws java.util.NoSuchElementException

This function returns the element in this priority queue 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.

Specified by:

getHighestFirst in interface PriorityQueue<E,java.lang.Integer>

Returns:

the element that has the highest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

getHighestLast

public E getHighestLast()
                 throws java.util.NoSuchElementException

This function returns the element in this priority queue 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.

Specified by:

getHighestLast in interface PriorityQueue<E,java.lang.Integer>

Returns:

the element that has the highest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

containsElementAt

public boolean containsElementAt(E element,
                                 java.lang.Integer priority)

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

Specified by:

containsElementAt in interface PriorityQueue<E,java.lang.Integer>

Parameters:

element - element to be tested for

priority - the priority at which it should be queued

Returns:

boolean whether it is indeed in the queue

removeLowestFirst

public E removeLowestFirst()
                    throws java.util.NoSuchElementException

This function removes and returns the element in this priority queue 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.

Specified by:

removeLowestFirst in interface PriorityQueue<E,java.lang.Integer>

Returns:

the element that has the highest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

removeLowestLast

public E removeLowestLast()
                   throws java.util.NoSuchElementException

This function removes and returns the element in this priority queue 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.

Specified by:

removeLowestLast in interface PriorityQueue<E,java.lang.Integer>

Returns:

the element that has the highest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

removeHighestFirst

public E removeHighestFirst()
                     throws java.util.NoSuchElementException

This function removes and returns the element in this priority queue 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.

Specified by:

removeHighestFirst in interface PriorityQueue<E,java.lang.Integer>

Returns:

the element that has the highest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

removeHighestLast

public E removeHighestLast()
                    throws java.util.NoSuchElementException

This function removes and returns the element in this priority queue 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.

Specified by:

removeHighestLast in interface PriorityQueue<E,java.lang.Integer>

Returns:

the element that has the highest priority in this PriorityQueue

Throws:

java.util.NoSuchElementException - if this PriorityQueue is empty

removeElementAt

public boolean removeElementAt(E element,
                               java.lang.Integer priority)

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

Specified by:

removeElementAt in interface PriorityQueue<E,java.lang.Integer>

Parameters:

element - the element to be removed from this PriorityQueue

priority - the priority at which the element is queued

Returns:

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

addElementFirst

public void addElementFirst(E element,
                            int priority)

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

Specified by:

addElementFirst in interface IntPriorityQueue<E>

Parameters:

element - the element to be added to this IntPriorityQueue

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

addElementLast

public void addElementLast(E element,
                           int priority)

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

Specified by:

addElementLast in interface IntPriorityQueue<E>

Parameters:

element - the element to be added to this IntPriorityQueue

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

containsElementAt

public boolean containsElementAt(E element,
                                 int priority)

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

Specified by:

containsElementAt in interface IntPriorityQueue<E>

Parameters:

element - element to be tested for

priority - the priority at which it should be queued

Returns:

boolean whether it is indeed in the queue

removeElementAt

public boolean removeElementAt(E element,
                               int priority)

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

Specified by:

removeElementAt in interface IntPriorityQueue<E>

Parameters:

element - the element to be removed from this PriorityQueue

priority - the priority at which the element is queued

Returns:

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

iterator

public java.util.Iterator<E> iterator()

This function returns an Iterator for this priority queue.

Specified by:

iterator in interface java.lang.Iterable<E>

Returns:

an Iterator for this PriorityQueue

getNrOfPriorities

public int getNrOfPriorities()

This function returns the number of different priorities currently used in this queue.

Returns:

the number of nodes in the tree that holds the Lists of elements that have the same priority

getNthPriority

public int getNthPriority(int n)

This function determines the nth priority value used in this queue. Counting starts with zero. For example, if the queue contains values at priorities 2, 4, 6 and 9 then getNthPriority(1) will return 4.

Parameters:

n - the rank of the sought priority (lowest has rank 0)

Returns:

the priority value at rank n

lengthAt

public int lengthAt(int priority)

This function returns the number of elements queued at the given priority.

Parameters:

priority - the priority at which elements are queued

Returns:

the length of the List holding elements of the given priority, or zero if there is no such List

removeFirstAt

public E removeFirstAt(int priority)

This function removes and returns the element that is at the front of the queue at the given priority. If there is no element queued at the given priority this function returns null.

Parameters:

priority - the priority at which the sought element is queued

Returns:

the first element queued at the given priority

removeLastAt

public E removeLastAt(int priority)

This function removes and returns the element that is at the end of the queue at the given priority. If there is no element queued at the given priority this function returns null.

Parameters:

priority - the priority at which the sought element is queued

Returns:

the last element queued at the given priority

removeNthAt

public E removeNthAt(int priority,
                     int n)

This function removes and returns the nth element at the given priority in this queue. If there is no nth element queued at the given priority this function returns null.

Parameters:

priority - the priority at which the sought element is queued

n - the position in the List at the given priority

Returns:

the nth element queued at the given priority

removeNthElement

public E removeNthElement(int n)

This function removes and returns the nth element in this queue. The first element has index 0.

Parameters:

n - the position in this queue

Returns:

the nth element queued at here

equals

public boolean equals(java.lang.Object obj)
               throws java.lang.UnsupportedOperationException

This class does not support equality testing and an exception will be thrown if this method is called.

Overrides:

equals in class java.lang.Object

Parameters:

obj - the Object this should be compared to

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - will be thrown

hashCode

public int hashCode()
             throws java.lang.UnsupportedOperationException

This class does not support hashing and an exception will be thrown if this method is called.

Overrides:

hashCode in class java.lang.Object

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - will be thrown

toString

public java.lang.String toString()

This function creates the printable string representation of this priority queue.

Overrides:

toString in class java.lang.Object

Returns:

the String representing this PriorityQueue