net.datastructures
Class SortedListPriorityQueue

java.lang.Object
  net.datastructures.SortedListPriorityQueue

All Implemented Interfaces:

PriorityQueue

Direct Known Subclasses:

SortedListAdaptablePriorityQueue

public class SortedListPriorityQueue

extends Object

implements PriorityQueue

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

Author:

Roberto Tamassia, Michael Goodrich, Eric Zamore

Nested Class Summary

protected static class	SortedListPriorityQueue.DefaultComparator Inner class for a default comparator using the natural ordering
protected static class	SortedListPriorityQueue.MyEntry Inner class for entries

Field Summary

protected Position	actionPos
protected Comparator	c
protected List	L

Constructor Summary

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

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

SortedListPriorityQueue(List list, Comparator comp)
Creates the priority queue with the given comparator and list.

Method Summary

protected boolean	checkKey(Object key) Determines whether a key is valid.
Entry	insert(Object k, Object v) Inserts a key-value pair and return the entry created.
protected void	insertEntry(Entry e) Auxiliary method used for insertion.
boolean	isEmpty() Returns whether the priority queue is empty.
protected Object	key(Position pos) Returns the key stored at a given node.
Entry	min() Returns but does not remove an entry with minimum key.
Entry	removeMin() Removes and returns an entry with minimum key.
void	setComparator(Comparator 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

L

protected List L

c

protected Comparator c

actionPos

protected Position actionPos

Constructor Detail

SortedListPriorityQueue

public SortedListPriorityQueue()

Creates the priority queue with the default comparator.

SortedListPriorityQueue

public SortedListPriorityQueue(Comparator comp)

Creates the priority queue with the given comparator.

SortedListPriorityQueue

public SortedListPriorityQueue(List list,
                               Comparator 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 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

isEmpty

public boolean isEmpty()

Returns whether the priority queue is empty.

Specified by:

isEmpty in interface PriorityQueue

min

public Entry min()
          throws EmptyPriorityQueueException

Returns but does not remove an entry with minimum key.

Specified by:

min in interface PriorityQueue

Throws:

EmptyPriorityQueueException

insert

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

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

Specified by:

insert in interface PriorityQueue

Throws:

InvalidKeyException

insertEntry

protected void insertEntry(Entry e)

Auxiliary method used for insertion.

removeMin

public Entry removeMin()
                throws EmptyPriorityQueueException

Removes and returns an entry with minimum key.

Specified by:

removeMin in interface PriorityQueue

Throws:

EmptyPriorityQueueException

key

protected Object key(Position pos)

Returns the key stored at a given node.

checkKey

protected boolean checkKey(Object key)
                    throws InvalidKeyException

Determines whether a key is valid.

Throws:

InvalidKeyException

toString

public String toString()