ix.isim.util
Class TreeOfListsLongPriorityQueue

java.lang.Object
  ix.isim.util.TreeOfListsLongPriorityQueue

All Implemented Interfaces:

LongPriorityQueue

public class TreeOfListsLongPriorityQueue
extends java.lang.Object
implements LongPriorityQueue

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 longs here.

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

The implementation of this priority queue is achieved by maintaining the objects in a sorted tree. The order is determined by the priority and each tree node contains a linked list of all the nodes with the same priority. In this way a reasonably efficient execution of all the operations provided can be guaranteed even for very long queues. Note, however, that the removal of elements from this queue and the contains-test with a given priority is not supported.

Field Summary

protected LongKeyTreeMap

pTree the data structure that contains a tree of lists of nodes

Constructor Summary

TreeOfListsLongPriorityQueue()
This constructor creates an empty PriorityQueue.

TreeOfListsLongPriorityQueue(java.lang.Object object, long priority)
This constructor creates a priority queue with exactly one element, the given object queued at the given priority.

Method Summary

void	addElementAtEnd(java.lang.Object object, long priority) This function adds the given object at the given priority to this priority queue.
void	addElementAtFront(java.lang.Object object, long priority) This function adds the given object at the given priority to this priority queue.
protected java.lang.Object	clone() This class does not support cloning and an Exception will be thrown if this method is called.
boolean	containsElementAt(java.lang.Object object, long priority) This function throws an UnsupportedOperationException as there is no efficient implementation of this operation for this class.
java.util.Iterator	elements() This function returns an Iterator for this priority queue.
boolean	equals(java.lang.Object obj) This class does not support equality testing and an exception will be thrown if this method is called.
java.lang.Object	getHighestEnd() This function returns the element in this priority queue that has the highest priority.
java.lang.Object	getHighestFront() This function returns the element in this priority queue that has the highest priority.
java.lang.Object	getLowestEnd() This function returns the element in this priority queue that has the lowest priority.
java.lang.Object	getLowestFront() This function returns the element in this priority queue that has the lowest priority.
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 priority queue is empty.
int	length() This function returns the size of this priority queue.
boolean	removeElementAt(java.lang.Object obj, long p) This function throws an UnsupportedOperationException as there is no efficient implementation of this operation for this class.
java.lang.Object	removeHighestEnd() This function removes and returns the element in this priority queue that has the highest priority.
java.lang.Object	removeHighestFront() This function removes and returns the element in this priority queue that has the highest priority.
java.lang.Object	removeLowestEnd() This function removes and returns the element in this priority queue that has the lowest priority.
java.lang.Object	removeLowestFront() This function removes and returns the element in this priority queue that has the lowest priority.
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

pTree

protected LongKeyTreeMap pTree

the data structure that contains a tree of lists of nodes

Constructor Detail

TreeOfListsLongPriorityQueue

public TreeOfListsLongPriorityQueue()

This constructor creates an empty PriorityQueue.

TreeOfListsLongPriorityQueue

public TreeOfListsLongPriorityQueue(java.lang.Object object,
                                    long priority)

This constructor creates a priority queue with exactly one element, the given object queued at the given priority.

Parameters:

object - the Object to be the initial member of this PriorityQueue

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

Method Detail

clone

protected java.lang.Object 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

addElementAtFront

public void addElementAtFront(java.lang.Object object,
                              long priority)

This function adds the given object 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:

addElementAtFront in interface LongPriorityQueue

Parameters:

object - the Object to be added to this LongPriorityQueue

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

addElementAtEnd

public void addElementAtEnd(java.lang.Object object,
                            long priority)

This function adds the given object 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:

addElementAtEnd in interface LongPriorityQueue

Parameters:

object - the Object to be added to this LongPriorityQueue

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

isEmpty

public boolean isEmpty()

This function tests whether this priority queue is empty.

Specified by:

isEmpty in interface LongPriorityQueue

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 LongPriorityQueue

Returns:

the number of elements contained in this PriorityQueue

containsElementAt

public boolean containsElementAt(java.lang.Object object,
                                 long priority)

This function throws an UnsupportedOperationException as there is no efficient implementation of this operation for this class.

Specified by:

containsElementAt in interface LongPriorityQueue

Parameters:

object - Object the element to be tested for

priority - int the priority at which it should be queued

Returns:

boolean whether it is indeed in the queue

Throws:

java.lang.UnsupportedOperationException - will be thrown

getLowestFront

public java.lang.Object getLowestFront()
                                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:

getLowestFront in interface LongPriorityQueue

Returns:

the Object that has the lowest priority in this LongPriorityQueue

Throws:

java.util.NoSuchElementException - if this LongPriorityQueue is empty

getLowestEnd

public java.lang.Object getLowestEnd()
                              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:

getLowestEnd in interface LongPriorityQueue

Returns:

the Object that has the lowest priority in this LongPriorityQueue

Throws:

java.util.NoSuchElementException - if this LongPriorityQueue is empty

getHighestFront

public java.lang.Object getHighestFront()
                                 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:

getHighestFront in interface LongPriorityQueue

Returns:

the Object that has the highest priority in this LongPriorityQueue

Throws:

java.util.NoSuchElementException - if this LongPriorityQueue is empty

getHighestEnd

public java.lang.Object getHighestEnd()
                               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:

getHighestEnd in interface LongPriorityQueue

Returns:

the Object that has the highest priority in this LongPriorityQueue

Throws:

java.util.NoSuchElementException - if this LongPriorityQueue is empty

removeLowestFront

public java.lang.Object removeLowestFront()
                                   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:

removeLowestFront in interface LongPriorityQueue

Returns:

the Object that has the lowest priority in this LongPriorityQueue

Throws:

java.util.NoSuchElementException - if this LongPriorityQueue is empty

removeLowestEnd

public java.lang.Object removeLowestEnd()
                                 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:

removeLowestEnd in interface LongPriorityQueue

Returns:

the Object that has the lowest priority in this LongPriorityQueue

Throws:

java.util.NoSuchElementException - if this LongPriorityQueue is empty

removeHighestFront

public java.lang.Object removeHighestFront()
                                    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:

removeHighestFront in interface LongPriorityQueue

Returns:

the Object that has the highest priority in this LongPriorityQueue

Throws:

java.util.NoSuchElementException - if this LongPriorityQueue is empty

removeHighestEnd

public java.lang.Object removeHighestEnd()
                                  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:

removeHighestEnd in interface LongPriorityQueue

Returns:

the Object that has the highest priority in this LongPriorityQueue

Throws:

java.util.NoSuchElementException - if this LongPriorityQueue is empty

removeElementAt

public boolean removeElementAt(java.lang.Object obj,
                               long p)

This function throws an UnsupportedOperationException as there is no efficient implementation of this operation for this class.

Specified by:

removeElementAt in interface LongPriorityQueue

Parameters:

obj - the Object to be removed from this PriorityQueue

p - the priority at which the element is queued

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - will be thrown

elements

public java.util.Iterator elements()

This function returns an Iterator for this priority queue.

Specified by:

elements in interface LongPriorityQueue

Returns:

an Iterator for this PriorityQueue

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

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 Objectobject 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