Interface UpdatablePriorityQueue<T,P extends java.lang.Comparable<? super P>>

Type Parameters:

T - the type of the items stored in the queue.

P - the type of the priority of each item.

All Superinterfaces:

PriorityQueue<PriorityPair<T,P>>

All Known Implementing Classes:

MysteryUpdatablePriorityQueueImplementation

public interface UpdatablePriorityQueue<T,P extends java.lang.Comparable<? super P>>
extends PriorityQueue<PriorityPair<T,P>>

A Java interface for the Updatable Priority Queue ADT. This allows the user to query and change the priority of items in the queue.

The items in an updatable priority queue must be unique; otherwise the operations of getting or setting an item's priority would not be well-defined (which copy of the item would we mean?).

Each implementation of this interface shall define a special "sentinel" priority value that indicates an item is not in the queue. Setting an item's priority to this value in fact removes it from the queue. Removing a non-member item is a no-op.

In addition, adding an item may be accomplished, from the user side, simply by setting its priority to a non-sentinel value.

Method Summary

Modifier and Type	Method and Description
void	add(PriorityPair<T,P> itemPair) Adds an item, with the priority given in the pair, to the queue.
void	add(T item, P priority) Adds an item, with the given priority, to the queue.
P	getPriority(T item) Returns the priority of the given item, or, if that item is not in the queue, an implementation-specific sentinel value.
P	nonMemberPriority() Returns the sentinel value used by getPriority() to indicate items not currently stored in the queue.
boolean	setPriority(T item, P newPriority) Sets the priority of a given item.

Methods inherited from interface PriorityQueue

clear, isEmpty, peek, remove

Method Detail

add

void add(PriorityPair<T,P> itemPair)

Adds an item, with the priority given in the pair, to the queue. This is equivalent to setPriority(itemPair.item(), itemPair.priority()), and therefore may, depending on the priority and the current state of the queue, add, remove, or modify the priority of the item.

Specified by:

add in interface PriorityQueue<PriorityPair<T,P extends java.lang.Comparable<? super P>>>

add

void add(T item,
         P priority)

Adds an item, with the given priority, to the queue. This is equivalent to setPriority(item, priority), and therefore may, depending on the priority and the current state of the queue, add, remove, or modify the priority of the item.

setPriority

boolean setPriority(T item,
                    P newPriority)

Sets the priority of a given item. The "given item" is, specifically, the element x in the PQ for which x.equals(item) is true.

The consequences of this operation vary depending on two conditions:

• NEW: the item is not already in the queue.
• DEL: "newPriority" is the non-member priority sentinel value.

The four cases covered by combinations of these conditions are:

• 1. If !NEW and !DEL, this method changes the item's priority.
• 2. If NEW and !DEL, this method adds the item.
• 3. If !NEW and DEL, this method removes the item.
• 4. If NEW and DEL, this method is a no-op (removing a non-member).

The method returns true if the pair (item, newPriority) is in the queue after the call. (This is !DEL: true in cases 1 and 2; false in 3 and 4.)

getPriority

P getPriority(T item)

Returns the priority of the given item, or, if that item is not in the queue, an implementation-specific sentinel value. (As in setPriority(), this queries the element x in the PQ for which x.equals(item) is true.)

nonMemberPriority

P nonMemberPriority()

Returns the sentinel value used by getPriority() to indicate items not currently stored in the queue.