net.datastructures
Class SortedListPriorityQueue<K,V>

java.lang.Object
  net.datastructures.SortedListPriorityQueue<K,V>

All Implemented Interfaces:

PriorityQueue<K,V>

Direct Known Subclasses:

SortedListAdaptablePriorityQueue

public class SortedListPriorityQueue<K,V>
extends Object
implements PriorityQueue<K,V>

Realization of a priority queue by means of a sorted node list in nondecreasing order.

Author:

Roberto Tamassia, Michael Goodrich, Eric Zamore

Nested Class Summary

protected static class

SortedListPriorityQueue.MyEntry<K,V> Inner class for entries

Field Summary

protected Position<Entry<K,V>>	actionPos
protected Comparator<K>	c
protected PositionList<Entry<K,V>>	entries

Constructor Summary

SortedListPriorityQueue()
Creates the priority queue with the default comparator.

SortedListPriorityQueue(Comparator<K> comp)
Creates the priority queue with the given comparator.

SortedListPriorityQueue(PositionList<Entry<K,V>> list, Comparator<K> comp)
Creates the priority queue with the given comparator and list.

Method Summary

protected boolean	checkKey(K key) Determines whether a key is valid.
Entry<K,V>	insert(K k, V v) Inserts a key-value pair and return the entry created.
protected void	insertEntry(Entry<K,V> e) Auxiliary method used for insertion.
boolean	isEmpty() Returns whether the priority queue is empty.
Entry<K,V>	min() Returns but does not remove an entry with minimum key.
Entry<K,V>	removeMin() Removes and returns an entry with minimum key.
void	setComparator(Comparator<K> comp) Sets the comparator for this priority queue.
int	size() Returns the number of elements in the priority queue.
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

entries

protected PositionList<Entry<K,V>> entries

c

protected Comparator<K> c

actionPos

protected Position<Entry<K,V>> actionPos

Constructor Detail

SortedListPriorityQueue

public SortedListPriorityQueue()

Creates the priority queue with the default comparator.

SortedListPriorityQueue

public SortedListPriorityQueue(Comparator<K> comp)

Creates the priority queue with the given comparator.

SortedListPriorityQueue

public SortedListPriorityQueue(PositionList<Entry<K,V>> list,
                               Comparator<K> comp)

Creates the priority queue with the given comparator and list. The list is assumed to be sorted in nondecreasing order.

Method Detail

setComparator

public void setComparator(Comparator<K> comp)
                   throws IllegalStateException

Sets the comparator for this priority queue.

Throws:

IllegalStateException - if priority queue is not empty

size

public int size()

Returns the number of elements in the priority queue.

Specified by:

size in interface PriorityQueue<K,V>

isEmpty

public boolean isEmpty()

Returns whether the priority queue is empty.

Specified by:

isEmpty in interface PriorityQueue<K,V>

min

public Entry<K,V> min()
               throws EmptyPriorityQueueException

Returns but does not remove an entry with minimum key.

Specified by:

min in interface PriorityQueue<K,V>

Throws:

EmptyPriorityQueueException

insert

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

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

Specified by:

insert in interface PriorityQueue<K,V>

Throws:

InvalidKeyException

insertEntry

protected void insertEntry(Entry<K,V> e)

Auxiliary method used for insertion.

removeMin

public Entry<K,V> removeMin()
                     throws EmptyPriorityQueueException

Removes and returns an entry with minimum key.

Specified by:

removeMin in interface PriorityQueue<K,V>

Throws:

EmptyPriorityQueueException

checkKey

protected boolean checkKey(K key)
                    throws InvalidKeyException

Determines whether a key is valid.

Throws:

InvalidKeyException

toString

public String toString()

Overrides:

toString in class Object