Adaptive Priority Queue Specification

Here is the fully specified Adaptive Priority Queue ADT:

/**
 * An AdaptivePriorityQueue serves the item with the smallest priority first,
 * and lets an item's priority be changed after it is added. Priorities are
 * compared by their natural ordering. The items must be distinct: the queue
 * holds no two equal items, so an item always refers to exactly one element.
 *
 * @param <T> the type of items in this priority queue
 * @param <P> the type of priorities
 */
public interface AdaptivePriorityQueue<T, P extends Comparable<P>> {
  /**
   * Adds an item to this priority queue with the given priority.
   * @param item the item to add
   * @param priority the item's priority; the smallest priority is served first
   * @throws IllegalArgumentException if the item or the priority is null, or if
   *     the item is already in this priority queue
   */
  void add(T item, P priority);

  /**
   * Returns, without removing, the highest-priority item in this priority queue.
   * @return the highest-priority item
   * @throws NoSuchElementException if this priority queue is empty
   */
  T peek();

  /**
   * Removes the highest-priority item from this priority queue. To inspect that
   * item, call peek before removing it.
   * @throws NoSuchElementException if this priority queue is empty
   */
  void remove();

  /**
   * Changes the priority of an item already in this priority queue, moving it to
   * its new place in the order.
   * @param item the item whose priority to change
   * @param priority the new priority; the smallest priority is served first
   * @throws IllegalArgumentException if the item or the priority is null
   * @throws NoSuchElementException if the item is not in this priority queue
   */
  void changePriority(T item, P priority);

  /**
   * Reports whether the given item is in this priority queue.
   * @param item the item to look for
   * @return true if the item is in this priority queue, false otherwise
   * @throws IllegalArgumentException if the item is null
   */
  boolean contains(T item);

  /**
   * Returns the number of items in this priority queue.
   * @return the number of items in this priority queue
   */
  int size();
}

The largest change from the priority queue chapter is that the items must be distinct. There, duplicates were allowed, and two equal elements could both be in the queue at once. Here they cannot, because of changePriority. When we call changePriority(item, ...), the queue has to find the one element that item refers to. If two equal items were in the queue, the call could not tell which of them to change. So the queue holds no two equal items, and add rejects an item equal to one already there, throwing IllegalArgumentException.

The items must be distinct, but the priorities do not have to be. Two different items can share a priority. For example, two patients can both be at level 2. When several items tie for the highest priority, the contract does not say which one peek returns and remove removes.

A null has no identity to store or to find, so the queue does not accept it. add, changePriority, and contains all throw IllegalArgumentException for it, as the set’s contains and the map’s containsKey did. A null priority cannot be compared with another priority, so add and changePriority throw the same exception for a null priority.

peek and remove on an empty queue throw a NoSuchElementException, as they did in the priority queue. changePriority on an item that is not in the queue throws it too, since there is nothing to change. A caller who is unsure whether an item is present can ask contains first.