gishur.core
Interface PriorityQueue

All Known Implementing Classes:
FibonacciHeap

public interface PriorityQueue

An interface that defines the basic methods for priority queues. The elements of the priority queue are KeyValueHolders.
The key defines the priority and can be any object (e.g. a Number), which will be compared to the keys of the other KeyValueHolders by a Comparitor selected by setComparitor(gishur.core.Comparitor).
The elements are queued in increasing order, thus a lower key indicates a higher priority.
The value contains the actual object, inserted into the priority queue.

Version:
1.0
Author:
Simon Weidmann

Method Summary
 Comparitor comparitor()
          Returns the Comparitor used to compare the elements of this PriorityQueue
 void decreaseKey(java.lang.Object k, KeyValueHolder p)
          Decreases the key of p to k, if k is Comparitor.SMALLER than the current key of p.
 void delete(KeyValueHolder p)
          Deletes the element p from the PriorityQueue
 boolean empty()
          Tests, if the PriorityQueue is empty.
 KeyValueHolder extractMin()
          Deletes the the entry with the minimum key and returns it
 KeyValueHolder insert(KeyValueHolder p)
          Inserts an element with a priority equal to p.{
 void meld(PriorityQueue Q)
          Melds this PriorityQueue with the PriorityQueue Q
 KeyValueHolder min()
          Returns the entry with the minimum key
 void setComparitor(Comparitor c)
          Sets the Comparitor, used to compare the priorities of the queue elements
 

Method Detail

setComparitor

public void setComparitor(Comparitor c)
Sets the Comparitor, used to compare the priorities of the queue elements
Parameters:
Comparitor - for comparing the priorities of the queue elements

comparitor

public Comparitor comparitor()
Returns the Comparitor used to compare the elements of this PriorityQueue
Returns:
the Comparitor used to compare the elements of this PriorityQueue

empty

public boolean empty()
Tests, if the PriorityQueue is empty.
Returns:
true, if the PriorityQueue is empty, false otherwise.

insert

public KeyValueHolder insert(KeyValueHolder p)
Inserts an element with a priority equal to p.key() and an object equal to p.value() into the PriorityQueue
Parameters:
p - object to be inserted
Returns:
the KeyValueHolder, inserted into the PriorityQueue
See Also:
KeyValueHolder

meld

public void meld(PriorityQueue Q)
Melds this PriorityQueue with the PriorityQueue Q
Parameters:
Q - PriorityQueue, which should be melded with this

extractMin

public KeyValueHolder extractMin()
Deletes the the entry with the minimum key and returns it
Returns:
element with the minimum key

decreaseKey

public void decreaseKey(java.lang.Object k,
                        KeyValueHolder p)
Decreases the key of p to k, if k is Comparitor.SMALLER than the current key of p. This operation increases the priority of p.
Parameters:
k - new key of p
p - element the key of which will be decreased

min

public KeyValueHolder min()
Returns the entry with the minimum key
Returns:
the entry with the minimum key

delete

public void delete(KeyValueHolder p)
Deletes the element p from the PriorityQueue
Parameters:
p - element to be deleted