goldman.collection.tagged.priority
Interface TaggedPriorityQueue<T,E>

All Superinterfaces:
Iterable<TaggedElement<T,E>>, TaggedCollection<T,E>
All Known Implementing Classes:
TaggedBinaryHeap, TaggedFibonacciHeap, TaggedLeftistHeap, TaggedPairingHeap, TaggedPriorityQueueWrapper

public interface TaggedPriorityQueue<T,E>
extends TaggedCollection<T,E>

The TaggedPriorityQueue ADT is a tagged version of the priority queue ADT. While the comparator used within a priority queue might use a single field of the element (that can be viewed as a tag), in a tagged priority queue there is an explicit association created from the tag to the associated data element. Also, the comparator is required to be based upon only the tags. The tags held within a tagged priority queue need not be unique.


Method Summary
 TaggedElement<T,E> extractMax()
          Removes and returns a tagged element with a highest priority tag.
 PriorityQueueLocator<TaggedElement<T,E>> getLocator(T tag)
          Returns a priority queue locator that has been initialized at a tagged element with the given tag.
 Iterator<TaggedElement<T,E>> iterator()
          Returns an iterator that has been initialized to FORE.
 TaggedElement<T,E> max()
          Returns a tagged element with a highest priority tag.
 PriorityQueueLocator<TaggedElement<T,E>> putTracked(T tag, E element)
          This method creates a new tagged element using the given tag and element, and inserts it into this collection.
 void updateTag(T tag, PriorityQueueLocator<TaggedElement<T,E>> loc)
          This method replaces the tag of the tagged element at the given locator position by tag, and makes any required updates to the underlying data structure.
 
Methods inherited from interface goldman.collection.tagged.TaggedCollection
accept, clear, contains, elements, ensureCapacity, get, getCapacity, getSize, isEmpty, put, putAll, remove, tags, toString, trimToSize, values
 

Method Detail

extractMax

TaggedElement<T,E> extractMax()
Removes and returns a tagged element with a highest priority tag. It throws a NoSuchElementException when this collection is empty.


getLocator

PriorityQueueLocator<TaggedElement<T,E>> getLocator(T tag)
Returns a priority queue locator that has been initialized at a tagged element with the given tag. It throws a NoSuchElementException if there is no element in this collection with an equivalent tag.

Specified by:
getLocator in interface TaggedCollection<T,E>

iterator

Iterator<TaggedElement<T,E>> iterator()
Returns an iterator that has been initialized to FORE.

Specified by:
iterator in interface Iterable<TaggedElement<T,E>>
Specified by:
iterator in interface TaggedCollection<T,E>

max

TaggedElement<T,E> max()
Returns a tagged element with a highest priority tag. It throws a NoSuchElementException when this collection is empty.


putTracked

PriorityQueueLocator<TaggedElement<T,E>> putTracked(T tag,
                                                    E element)
This method creates a new tagged element using the given tag and element, and inserts it into this collection. A priority queue locator that tracks the new tagged element is returned. An AtCapacityException, an unchecked exception, is thrown if the collection is already at capacity.


updateTag

void updateTag(T tag,
               PriorityQueueLocator<TaggedElement<T,E>> loc)
This method replaces the tag of the tagged element at the given locator position by tag, and makes any required updates to the underlying data structure.