MysteryUpdatablePriorityQueueImplementation (Dr. Miles's Data Structures)

java.lang.Object
- MysteryUpdatablePriorityQueueImplementation

All Implemented Interfaces:

PriorityQueue<PriorityPair<java.lang.Integer,java.lang.Double>>, UpdatablePriorityQueue<java.lang.Integer,java.lang.Double>
```
public class MysteryUpdatablePriorityQueueImplementation
extends java.lang.Object
implements UpdatablePriorityQueue<java.lang.Integer,java.lang.Double>
```
A mysterious implementation of the Updatable Priority Queue ADT!
This implementation is optimized for one particular, specialized use: when the items are densely-packed unique integers in some fixed range [0, N] (for example, node IDs in a graph) and the priorities are Doubles.
Any method call that attempts to refer to an item less than zero or greater than maxValue (which is set at construction time) will throw an IndexOutOfBoundsException.
The "non-member priority" for this queue is Double.NEGATIVE_INFINITY. This will be the reported priority of any item not currently stored in the queue. In addition, setting the priority of any item to this special value is equivalent to removing it from the queue.
Note that, as an implementer of the PriorityQueue interface (by way of UpdatablePriorityQueue), this class is a *max* priority queue --- remove() and peek() give the PriorityPair with the highest priority. This means that users who want a *min* priority queue should negate all their priorities.

Constructor Summary

Constructors
Constructor and Description

MysteryUpdatablePriorityQueueImplementation(int maxValue)
Constructs a queue, given the maximum item value that the queue shall be able to store.

Constructors
Constructor and Description
`MysteryUpdatablePriorityQueueImplementation(int maxValue)` Constructs a queue, given the maximum item value that the queue shall be able to store.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`add(java.lang.Integer item, java.lang.Double priority)` Adds an item, with the given priority, to the queue.
`void`	`add(PriorityPair<java.lang.Integer,java.lang.Double> itemPair)` Adds an item, with the priority given in the pair, to the queue.
`void`	`clear()` Removes all items from the queue.
`java.lang.Double`	`getPriority(java.lang.Integer item)` Returns the priority of the given item, or, if that item is not in the queue, an implementation-specific sentinel value.
`boolean`	`isEmpty()` Returns true if the queue is empty.
`java.lang.Double`	`nonMemberPriority()` Returns the sentinel value used by getPriority() to indicate items not currently stored in the queue.
`PriorityPair<java.lang.Integer,java.lang.Double>`	`peek()` Returns the maximum item in the queue, without removing it.
`PriorityPair<java.lang.Integer,java.lang.Double>`	`remove()` Removes the maximum item from the queue, and returns it.
`boolean`	`setPriority(java.lang.Integer item, java.lang.Double newPriority)` Sets the priority of a given item.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - MysteryUpdatablePriorityQueueImplementation
```
public MysteryUpdatablePriorityQueueImplementation(int maxValue)
```
    Constructs a queue, given the maximum item value that the queue shall be able to store.
- Method Detail
  - add
```
public void add(PriorityPair<java.lang.Integer,java.lang.Double> itemPair)
```
    Description copied from interface: UpdatablePriorityQueue
    
    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<java.lang.Integer,java.lang.Double>>
    
    Specified by:
    
    add in interface UpdatablePriorityQueue<java.lang.Integer,java.lang.Double>
  - add
```
public void add(java.lang.Integer item,
                java.lang.Double priority)
```
    Description copied from interface: UpdatablePriorityQueue
    
    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.
    
    Specified by:
    
    add in interface UpdatablePriorityQueue<java.lang.Integer,java.lang.Double>
  - remove
```
public PriorityPair<java.lang.Integer,java.lang.Double> remove()
```
    Description copied from interface: PriorityQueue
    
    Removes the maximum item from the queue, and returns it.
    
    Specified by:
    
    remove in interface PriorityQueue<PriorityPair<java.lang.Integer,java.lang.Double>>
    
    Returns:
    
    null if the queue is empty.
  - setPriority
```
public boolean setPriority(java.lang.Integer item,
                           java.lang.Double newPriority)
```
    Description copied from interface: UpdatablePriorityQueue
    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.)
    Specified by:
    
    setPriority in interface UpdatablePriorityQueue<java.lang.Integer,java.lang.Double>
  - peek
```
public PriorityPair<java.lang.Integer,java.lang.Double> peek()
```
    Description copied from interface: PriorityQueue
    
    Returns the maximum item in the queue, without removing it.
    
    Specified by:
    
    peek in interface PriorityQueue<PriorityPair<java.lang.Integer,java.lang.Double>>
    
    Returns:
    
    null if the queue is empty.
  - isEmpty
```
public boolean isEmpty()
```
    Description copied from interface: PriorityQueue
    
    Returns true if the queue is empty.
    
    Specified by:
    
    isEmpty in interface PriorityQueue<PriorityPair<java.lang.Integer,java.lang.Double>>
  - clear
```
public void clear()
```
    Description copied from interface: PriorityQueue
    
    Removes all items from the queue.
    
    Specified by:
    
    clear in interface PriorityQueue<PriorityPair<java.lang.Integer,java.lang.Double>>
  - nonMemberPriority
```
public java.lang.Double nonMemberPriority()
```
    Description copied from interface: UpdatablePriorityQueue
    
    Returns the sentinel value used by getPriority() to indicate items not currently stored in the queue.
    
    Specified by:
    
    nonMemberPriority in interface UpdatablePriorityQueue<java.lang.Integer,java.lang.Double>
  - getPriority
```
public java.lang.Double getPriority(java.lang.Integer item)
```
    Description copied from interface: UpdatablePriorityQueue
    
    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.)
    
    Specified by:
    
    getPriority in interface UpdatablePriorityQueue<java.lang.Integer,java.lang.Double>

Class MysteryUpdatablePriorityQueueImplementation

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

MysteryUpdatablePriorityQueueImplementation

Method Detail

add

add

remove

setPriority

peek

isEmpty

clear

nonMemberPriority

getPriority