cs2110

Class AdjustablePriorityQueue<T>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractQueue<T>

cs2110.AdjustablePriorityQueue<T>

Type Parameters:

T - the type of elements contained in this PriorityQueue.

All Implemented Interfaces:

java.lang.Iterable<T>, java.util.Collection<T>, java.util.Queue<T>

public class AdjustablePriorityQueue<T>
extends java.util.AbstractQueue<T>

A priority queue implementation supporting in situ adjustment of priorities. Priorities are double values. Elements themselves are used as keys in the getPriority(Object) and setPriority(Object, double) methods, therefore the elements in the queue must be unique and the notion of equality used to access them must be identity (==), in constrast to PriorityQueue, which relies on the natural ordering of the elements or a supplied Comparator. An attempt to insert an element that is already there results in an IllegalArgumentException.

Constructor Summary

Constructors

Constructor and Description
AdjustablePriorityQueue() Constructs a PriorityQueue min queue.
AdjustablePriorityQueue(boolean orientation) Constructs a PriorityQueue that extracts elements according to priority.

Method Summary

Modifier and Type	Method and Description
boolean	contains(java.lang.Object item) Tests whether the data structure contains the given item.
double	getPriority(T item) Gets the current priority of the given item.
java.util.Iterator<T>	iterator() See Collection.iterator().
boolean	offer(T item) Inserts an item with the default priority: Double.POSITIVE_INFINITY for a min queue, Double.NEGATIVE_INFINITY for a max queue.
T	peek() See Queue.peek().
T	poll() See Queue.poll().
void	setPriority(T item, double newPriority) Sets the priority of the given item.
int	size() See Collection.size().

Methods inherited from class java.util.AbstractQueue

add, addAll, clear, element, remove

Methods inherited from class java.util.AbstractCollection

containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

containsAll, equals, hashCode, isEmpty, parallelStream, remove, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

AdjustablePriorityQueue

public AdjustablePriorityQueue(boolean orientation)

Constructs a PriorityQueue that extracts elements according to priority. Priorities are doubles that are supplied in the constructor, but can be changed in situ. The priority queue can be either a max queue (extract max supported) or a min queue (extract min supported) depending on the value of the parameter.

Parameters:

orientation - the orientation of the queue - true=min, false=max.

AdjustablePriorityQueue

public AdjustablePriorityQueue()

Constructs a PriorityQueue min queue. The element with the smallest priority value is the next extracted.

Method Detail

offer

public boolean offer(T item)

Inserts an item with the default priority: Double.POSITIVE_INFINITY for a min queue, Double.NEGATIVE_INFINITY for a max queue.

Parameters:

item - the item to insert

Throws:

java.lang.IllegalArgumentException - if the item is already in the queue

contains

public boolean contains(java.lang.Object item)

Tests whether the data structure contains the given item. This is implemented in the AbstractQueue adapter, but overridden here to do in constant time.

Specified by:

contains in interface java.util.Collection<T>

Overrides:

contains in class java.util.AbstractCollection<T>

Parameters:

item - the item to test

Returns:

true if the data structure contains the item

poll

public T poll()

See Queue.poll().

peek

public T peek()

See Queue.peek().

getPriority

public double getPriority(T item)
                   throws java.util.NoSuchElementException

Gets the current priority of the given item.

Parameters:

item - the item

Returns:

the priority of the given item

Throws:

java.util.NoSuchElementException - if the item is not in the queue

setPriority

public void setPriority(T item,
                        double newPriority)
                 throws java.util.NoSuchElementException

Sets the priority of the given item.

Parameters:

item - the item to be adjusted

newPriority - the new priority

Throws:

java.util.NoSuchElementException - if the item is not in the queue

size

public int size()

See Collection.size().

Specified by:

size in interface java.util.Collection<T>

Specified by:

size in class java.util.AbstractCollection<T>

iterator

public java.util.Iterator<T> iterator()

See Collection.iterator().

Specified by:

iterator in interface java.lang.Iterable<T>

Specified by:

iterator in interface java.util.Collection<T>

Specified by:

iterator in class java.util.AbstractCollection<T>