net.datastructures

Class HeapAdaptablePriorityQueue<K,V>

java.lang.Object

net.datastructures.HeapPriorityQueue<K,V>

net.datastructures.HeapAdaptablePriorityQueue<K,V>

All Implemented Interfaces:

AdaptablePriorityQueue<K,V>, PriorityQueue<K,V>

public class HeapAdaptablePriorityQueue<K,V>
extends HeapPriorityQueue<K,V>
implements AdaptablePriorityQueue<K,V>

Realization of an adaptable priority queue by means of a heap. Much functionality is inherited.

See Also:

HeapPriorityQueue

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	HeapAdaptablePriorityQueue.LocationAwareEntry<K,V> Inner class for a location-aware entry.

Nested classes/interfaces inherited from class net.datastructures.HeapPriorityQueue

HeapPriorityQueue.MyEntry<K,V>

Field Summary

Fields inherited from class net.datastructures.HeapPriorityQueue

comp, heap

Constructor Summary

Constructors

Constructor and Description
HeapAdaptablePriorityQueue() Creates an empty heap with a default comparator.
HeapAdaptablePriorityQueue(java.util.Comparator comp) Creates an empty heap with the given comparator.

Method Summary

Modifier and Type	Method and Description
protected HeapAdaptablePriorityQueue.LocationAwareEntry<K,V>	checkEntry(Entry<K,V> ent) Check whether a given entry is valid.
protected HeapAdaptablePriorityQueue.LocationAwareEntry<K,V>	getEntry(Position p) Returns the entry stored at a heap node.
Entry<K,V>	insert(K k, V v) Inserts a key-value pair and returns the entry created.
Entry<K,V>	remove(Entry<K,V> entry) Removes and returns the given entry from the heap.
protected Position	replaceEntry(Position v, HeapAdaptablePriorityQueue.LocationAwareEntry<K,V> e) Replaces the element of the given position with the given location-aware entry.
K	replaceKey(Entry<K,V> entry, K k) Replaces the key of the given entry.
V	replaceValue(Entry<K,V> e, V value) Replaces the value of the given entry.
protected void	swap(Position<Entry<K,V>> u, Position<Entry<K,V>> v) Swaps the elements of the two positions.

Methods inherited from class net.datastructures.HeapPriorityQueue

checkKey, downHeap, isEmpty, min, removeMin, setComparator, size, toString, upHeap

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface net.datastructures.PriorityQueue

isEmpty, min, removeMin, size

Constructor Detail

HeapAdaptablePriorityQueue

public HeapAdaptablePriorityQueue()

Creates an empty heap with a default comparator.

HeapAdaptablePriorityQueue

public HeapAdaptablePriorityQueue(java.util.Comparator comp)

Creates an empty heap with the given comparator.

Method Detail

insert

public Entry<K,V> insert(K k,
                         V v)
                  throws InvalidKeyException

Inserts a key-value pair and returns the entry created.

Specified by:

insert in interface PriorityQueue<K,V>

Overrides:

insert in class HeapPriorityQueue<K,V>

Throws:

InvalidKeyException

remove

public Entry<K,V> remove(Entry<K,V> entry)
                  throws InvalidEntryException

Removes and returns the given entry from the heap.

Specified by:

remove in interface AdaptablePriorityQueue<K,V>

Throws:

InvalidEntryException

replaceKey

public K replaceKey(Entry<K,V> entry,
                    K k)
             throws InvalidEntryException

Replaces the key of the given entry.

Specified by:

replaceKey in interface AdaptablePriorityQueue<K,V>

Throws:

InvalidEntryException

replaceValue

public V replaceValue(Entry<K,V> e,
                      V value)
               throws InvalidEntryException

Replaces the value of the given entry.

Specified by:

replaceValue in interface AdaptablePriorityQueue<K,V>

Throws:

InvalidEntryException

swap

protected void swap(Position<Entry<K,V>> u,
                    Position<Entry<K,V>> v)

Swaps the elements of the two positions. This method is called when up-heaping and down-heaping.

Overrides:

swap in class HeapPriorityQueue<K,V>

replaceEntry

protected Position replaceEntry(Position v,
                                HeapAdaptablePriorityQueue.LocationAwareEntry<K,V> e)

Replaces the element of the given position with the given location-aware entry.

getEntry

protected HeapAdaptablePriorityQueue.LocationAwareEntry<K,V> getEntry(Position p)

Returns the entry stored at a heap node.

checkEntry

protected HeapAdaptablePriorityQueue.LocationAwareEntry<K,V> checkEntry(Entry<K,V> ent)
                                                                 throws InvalidEntryException

Check whether a given entry is valid.

Throws:

InvalidEntryException