net.datastructures
Class HeapAdaptablePriorityQueue

java.lang.Object
  net.datastructures.HeapPriorityQueue
      net.datastructures.HeapAdaptablePriorityQueue

All Implemented Interfaces:

AdaptablePriorityQueue, PriorityQueue

public class HeapAdaptablePriorityQueue

extends HeapPriorityQueue

implements AdaptablePriorityQueue

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

Author:

Eric Zamore

See Also:

HeapPriorityQueue

Nested Class Summary

protected static class

HeapAdaptablePriorityQueue.LocationAwareEntry Inner class for a location-aware entry.

Nested classes inherited from class net.datastructures.HeapPriorityQueue

HeapPriorityQueue.DefaultComparator, HeapPriorityQueue.MyEntry

Field Summary

Fields inherited from class net.datastructures.HeapPriorityQueue

comp, T

Constructor Summary

HeapAdaptablePriorityQueue()
Creates an empty heap with a default comparator.

HeapAdaptablePriorityQueue(Comparator comp)
Creates an empty heap with the given comparator.

Method Summary

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

Methods inherited from class net.datastructures.HeapPriorityQueue

checkKey, downHeap, entry, isEmpty, key, 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(Comparator comp)

Creates an empty heap with the given comparator.

Method Detail

insert

public Entry insert(Object k,
                    Object v)
             throws InvalidKeyException

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

Specified by:

insert in interface PriorityQueue

Overrides:

insert in class HeapPriorityQueue

Throws:

InvalidKeyException

remove

public Entry remove(Entry entry)
             throws InvalidEntryException

Removes and returns the given entry from the heap.

Specified by:

remove in interface AdaptablePriorityQueue

Throws:

InvalidEntryException

replaceKey

public Object replaceKey(Entry entry,
                         Object k)
                  throws InvalidEntryException

Replaces the key of the given entry.

Specified by:

replaceKey in interface AdaptablePriorityQueue

Throws:

InvalidEntryException

replaceValue

public Object replaceValue(Entry e,
                           Object value)
                    throws InvalidEntryException

Replaces the value of the given entry.

Specified by:

replaceValue in interface AdaptablePriorityQueue

Throws:

InvalidEntryException

swapElements

protected void swapElements(Position u,
                            Position v)

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

Overrides:

swapElements in class HeapPriorityQueue

replaceEntry

protected Object replaceEntry(Position v,
                              HeapAdaptablePriorityQueue.LocationAwareEntry e)

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

getEntry

protected HeapAdaptablePriorityQueue.LocationAwareEntry getEntry(Position p)

Returns the entry stored at a heap node.

checkEntry

protected HeapAdaptablePriorityQueue.LocationAwareEntry checkEntry(Entry ent)
                                                            throws InvalidEntryException

Check whether a given entry is valid.

Throws:

InvalidEntryException