goldman.collection.tagged.priority
Class TaggedPriorityQueueWrapper<T,E>

java.lang.Object
  extended by goldman.collection.tagged.TaggedCollectionWrapper<T,E>
      extended by goldman.collection.tagged.priority.TaggedPriorityQueueWrapper<T,E>
All Implemented Interfaces:
TaggedPriorityQueue<T,E>, TaggedCollection<T,E>, Iterable<TaggedElement<T,E>>
Direct Known Subclasses:
TaggedBinaryHeap, TaggedFibonacciHeap, TaggedLeftistHeap, TaggedPairingHeap

public abstract class TaggedPriorityQueueWrapper<T,E>
extends TaggedCollectionWrapper<T,E>
implements TaggedPriorityQueue<T,E>

The tagged priority queue wrapper can wrap any priority queue implementation, where each element in the priority queue is a tagged element. It is required that the comparator depends only on the tag, and the tag is immutable except through the use of the update method.


Field Summary
 
Fields inherited from class goldman.collection.tagged.TaggedCollectionWrapper
pairs, target
 
Constructor Summary
TaggedPriorityQueueWrapper(Collection<TaggedElement<T,E>> pairs)
           
 
Method Summary
 TaggedElement<T,E> extractMax()
          Removes a tagged element with a highest priority tag
 PriorityQueueLocator<TaggedElement<T,E>> getLocator(T tag)
          Returns a locator that has been initialized to a tagged element with an equivalent tag.
 Iterator<TaggedElement<T,E>> iterator()
          Creates and returns new iterator initialized to FORE.
 TaggedElement<T,E> max()
          Returns a tagged element with a highest priority tag.
 void put(T tag, E data)
          Creates a new tagged element with the given values, and inserts this tagged element into this collection.
 PriorityQueueLocator<TaggedElement<T,E>> putTracked(T tag, E data)
          Creates a new tagged element with the given values, and inserts this tagged element into this collection
 void updateTag(T tag, PriorityQueueLocator<TaggedElement<T,E>> loc)
          Replaces the tag of the tagged element at the locator position by tag, and makes any required updates in the wrapped priority queue.
 
Methods inherited from class goldman.collection.tagged.TaggedCollectionWrapper
accept, clear, contains, elements, ensureCapacity, get, getCapacity, getSize, isEmpty, putAll, remove, tags, toString, trimToSize, values
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.tagged.TaggedCollection
accept, clear, contains, elements, ensureCapacity, get, getCapacity, getSize, isEmpty, putAll, remove, tags, toString, trimToSize, values
 

Constructor Detail

TaggedPriorityQueueWrapper

public TaggedPriorityQueueWrapper(Collection<TaggedElement<T,E>> pairs)
Method Detail

max

public TaggedElement<T,E> max()
Description copied from interface: TaggedPriorityQueue
Returns a tagged element with a highest priority tag. It throws a NoSuchElementException when this collection is empty.

Specified by:
max in interface TaggedPriorityQueue<T,E>
Returns:
a tagged element with a highest priority tag
Throws:
NoSuchElementException - this collection is empty.

getLocator

public PriorityQueueLocator<TaggedElement<T,E>> getLocator(T tag)
Description copied from interface: TaggedCollection
Returns a locator that has been initialized to a tagged element with an equivalent tag. Like the iterator method, this method enables navigation, but from a specified starting point. This method throws a NoSuchElementException if there is no tagged element with an equivalent tag in the collection.

Specified by:
getLocator in interface TaggedPriorityQueue<T,E>
Specified by:
getLocator in interface TaggedCollection<T,E>
Overrides:
getLocator in class TaggedCollectionWrapper<T,E>
Parameters:
tag - the target tag
Returns:
a priority queue locator that has been placed at a tagged element with an equivalent tag
Throws:
NoSuchElementException - there is no element with an equivalent tag

put

public void put(T tag,
                E data)
Creates a new tagged element with the given values, and inserts this tagged element into this collection.

Specified by:
put in interface TaggedCollection<T,E>
Overrides:
put in class TaggedCollectionWrapper<T,E>
Parameters:
tag - the tag for the tagged element to add
data - the associated data
Throws:
AtCapacityException - the collection is already at capacity.

putTracked

public PriorityQueueLocator<TaggedElement<T,E>> putTracked(T tag,
                                                           E data)
Creates a new tagged element with the given values, and inserts this tagged element into this collection

Specified by:
putTracked in interface TaggedPriorityQueue<T,E>
Parameters:
tag - the tag for the tagged element to add
data - the associated data
Returns:
a priority queue locator that tracks the new tagged element
Throws:
AtCapacityException - the collection is already at capacity.

extractMax

public TaggedElement<T,E> extractMax()
Removes a tagged element with a highest priority tag

Specified by:
extractMax in interface TaggedPriorityQueue<T,E>
Returns:
the removed tagged element
Throws:
NoSuchElementException - this collection is empty.

updateTag

public void updateTag(T tag,
                      PriorityQueueLocator<TaggedElement<T,E>> loc)
Replaces the tag of the tagged element at the locator position by tag, and makes any required updates in the wrapped priority queue.

Specified by:
updateTag in interface TaggedPriorityQueue<T,E>
Parameters:
tag - the new tag
loc - a priority queue locator specifying the tagged element to update

iterator

public Iterator<TaggedElement<T,E>> iterator()
Creates and returns new iterator initialized to FORE.

Specified by:
iterator in interface TaggedPriorityQueue<T,E>
Specified by:
iterator in interface TaggedCollection<T,E>
Specified by:
iterator in interface Iterable<TaggedElement<T,E>>
Overrides:
iterator in class TaggedCollectionWrapper<T,E>