ix.isim.util
Class TreeOfListsLongPriorityQueue

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