Package com.zybooks.dsaj.pq

Class AbstractPriorityQueue<K,V>

java.lang.Object

com.zybooks.dsaj.pq.AbstractPriorityQueue<K,V>

Type Parameters:

K - The key type (keys must be unique and comparable)

V - The value type stored with each entry

All Implemented Interfaces:

PriorityQueue<K,V>

Direct Known Subclasses:

HeapPriorityQueue, SortedPriorityQueue, UnsortedPriorityQueue

public abstract class AbstractPriorityQueue<K,V>
extends Object
implements PriorityQueue<K,V>

An abstract base class to ease the implementation of the PriorityQueue interface. The base class provides three means of support: 1) It defines a PQEntry class as a concrete implementation of the entry interface 2) It provides an instance variable for a general Comparator and a protected method, compare(a, b), that makes use of the comparator. 3) It provides an isEmpty implementation based upon the abstract size() method.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	AbstractPriorityQueue.PQEntry<K,V>	A concrete implementation of the Entry interface to be used within a PriorityQueue implementation.

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	AbstractPriorityQueue()	Creates an empty priority queue based on the natural ordering of its keys.
protected	AbstractPriorityQueue(Comparator<K> c)	Creates an empty priority queue using the given comparator to order keys.

Method Summary

Modifier and Type	Method	Description
protected int	compare(Entry<K,V> a, Entry<K,V> b)	Method for comparing two entries according to key
protected AbstractPriorityQueue.PQEntry<K,V>	createEntry(K key, V value)	Factory function to create an entry storing key,value.
boolean	isEmpty()	Tests whether the priority queue is empty.

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.zybooks.dsaj.pq.PriorityQueue

insert, min, removeMin, size

Constructor Details

AbstractPriorityQueue

protected AbstractPriorityQueue(Comparator<K> c)

Creates an empty priority queue using the given comparator to order keys.

Parameters:

c - comparator defining the order of keys in the priority queue

AbstractPriorityQueue

protected AbstractPriorityQueue()

Creates an empty priority queue based on the natural ordering of its keys.

Method Details

createEntry

protected AbstractPriorityQueue.PQEntry<K,V> createEntry(K key,
 V value)

Factory function to create an entry storing key,value.

Parameters:

key - the key

value - the value

Returns:

the new PQEntry

compare

protected int compare(Entry<K,V> a,
 Entry<K,V> b)

Method for comparing two entries according to key

Parameters:

a - the first entry to be compared

b - the second entry to be compared

Returns:

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

isEmpty

public boolean isEmpty()

Tests whether the priority queue is empty.

Specified by:

isEmpty in interface PriorityQueue<K,V>

Returns:

true if the priority queue is empty, false otherwise