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 java.lang.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

Constructor Summary

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

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

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

Method Summary

Entry<K,V>	insert(K k, V v) Inserts a key-value pair and return the entry created.
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(java.util.Comparator<K> comp) Sets the comparator for this priority queue.
int	size() Returns the number of elements in the priority queue.
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

SortedListPriorityQueue

public SortedListPriorityQueue()

Creates the priority queue with the default comparator.

SortedListPriorityQueue

public SortedListPriorityQueue(java.util.Comparator<K> comp)

Creates the priority queue with the given comparator.

SortedListPriorityQueue

public SortedListPriorityQueue(PositionList<Entry<K,V>> list,
                               java.util.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(java.util.Comparator<K> comp)
                   throws java.lang.IllegalStateException

Sets the comparator for this priority queue.

Throws:

java.lang.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

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

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object