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.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	SortedListPriorityQueue.MyEntry<K,V> Inner class for entries

Field Summary

Fields

Modifier and Type	Field and Description
protected Position<Entry<K,V>>	actionPos
protected java.util.Comparator<K>	c
protected PositionList<Entry<K,V>>	entries

Constructor Summary

Constructors

Constructor and Description
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

Modifier and Type	Method and Description
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(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

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

Field Detail

entries

protected PositionList<Entry<K,V>> entries

c

protected java.util.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(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

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 java.lang.String toString()

Overrides:

toString in class java.lang.Object