package net.datastructures;
import java.util.Comparator;
/** Implementation of a priority queue by means of a sorted list */
/**
* Realization of a priority queue by means of a sorted linked-list in
* nondecreasing order.
* @author Roberto Tamassia, Michael Goodrich, Eric Zamore
*/
public class SortedListPriorityQueue implements PriorityQueue {
protected List L;
protected Comparator c;
protected Position actionPos; // variable used by subclasses
/** Inner class for entries */
protected static class MyEntry implements Entry {
protected Object k; // key
protected Object v; // value
public MyEntry(Object key, Object value) {
k = key;
v = value;
}
// methods of the Entry interface
public Object key() { return k; }
public Object value() { return v; }
// overrides Object.toString, useful for debugging
public String toString() { return "(" + k + "," + v + ")"; }
}
/** Inner class for a default comparator using the natural ordering */
protected static class DefaultComparator implements Comparator {
public DefaultComparator() { /* default constructor */ }
public int compare(Object a, Object b) throws ClassCastException {
return ((Comparable) a).compareTo(b);
}
}
/** Creates the priority queue with the default comparator. */
public SortedListPriorityQueue () {
L = new NodeList();
c = new DefaultComparator();
}
/** Creates the priority queue with the given comparator. */
public SortedListPriorityQueue (Comparator comp) {
L = new NodeList();
c = comp;
}
/** Creates the priority queue with the given comparator and list.
* The list is assumed to be sorted in nondecreasing order.*/
public SortedListPriorityQueue (List list, Comparator comp) {
L = list;
c = comp;
}
/** Sets the comparator for this priority queue.
* @throws IllegalStateException if priority queue is not empty */
public void setComparator(Comparator comp) throws IllegalStateException {
if(!isEmpty()) // this is only allowed if the priority queue is empty
throw new IllegalStateException("Priority queue is not empty");
c = comp;
}
/** Returns the number of elements in the priority queue. */
public int size () {return L.size(); }
/** Returns whether the priority queue is empty. */
public boolean isEmpty () { return L.isEmpty(); }
/** Returns but does not remove an entry with minimum key. */
public Entry min () throws EmptyPriorityQueueException {
if (L.isEmpty())
throw new EmptyPriorityQueueException("priority queue is empty");
else
return (Entry) L.first().element();
}
/** Inserts a key-value pair and return the entry created. */
public Entry insert (Object k, Object v) throws InvalidKeyException {
checkKey(k); // auxiliary key-checking method (could throw exception)
Entry entry = new MyEntry(k, v);
insertEntry(entry); // auxiliary insertion method
return entry;
}
/** Auxiliary method used for insertion. */
protected void insertEntry(Entry e) {
Object k = e.key();
if (L.isEmpty()) {
actionPos = L.insertFirst(e); // insert into empty list
}
else if (c.compare(k, key(L.last())) > 0) {
actionPos = L.insertLast(e); // insert at the end of the list
}
else {
Position curr = L.first();
while (c.compare(k, key(curr))> 0) {
curr = L.next(curr); // advance toward insertion position
}
actionPos = L.insertBefore(curr, e); // useful for subclasses
}
}
/** Removes and returns an entry with minimum key. */
public Entry removeMin() throws EmptyPriorityQueueException {
if (L.isEmpty())
throw new EmptyPriorityQueueException("priority queue is empty");
else
return (Entry) (L.remove(L.first()));
}
/** Returns the key stored at a given node. */
protected Object key(Position pos) { return ((Entry) pos.element()).key(); }
/** Determines whether a key is valid. */
protected boolean checkKey(Object key) throws InvalidKeyException {
boolean result;
try { // check if the key can be compared to itself
result = (c.compare(key,key)==0);
} catch (ClassCastException e)
{ throw new InvalidKeyException("key cannot be compared"); }
return result;
}
// overrides Object.toString, useful for debugging
public String toString() {
return L.toString();
}
}
|