Package minpq

Class DoubleMapMinPQ<E>

java.lang.Object

minpq.DoubleMapMinPQ<E>

Type Parameters:

E - the type of elements in this priority queue.

All Implemented Interfaces:

MinPQ<E>

public class DoubleMapMinPQ<E>
extends Object
implements MinPQ<E>

TreeMap and HashMap implementation of the MinPQ interface.

See Also:

MinPQ

Field Summary

Fields

Modifier and Type	Field	Description
private Map<E,Double>	elementToPriority	Map of elements to their associated priority values.
private NavigableMap<Double,Set<E>>	priorityToElement	NavigableMap of priority values to all elements that share the same priority values.

Constructor Summary

Constructors

Constructor	Description
DoubleMapMinPQ()	Constructs an empty instance.

Method Summary

Modifier and Type	Method	Description
void	add(E element, double priority)	Adds an element with the given priority value.
void	changePriority(E element, double priority)	Updates the given elements' associated priority value.
boolean	contains(E element)	Returns true if the given element is in this priority queue.
private E	firstOf(Iterable<E> it)	Returns any one element from the given iterable.
E	peekMin()	Returns the element with the minimum priority value.
E	removeMin()	Returns and removes the element with the minimum priority value.
int	size()	Returns the number of elements in this priority queue.

Methods inherited from class java.lang.Object

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

Methods inherited from interface minpq.MinPQ

isEmpty

Field Detail

priorityToElement

private final NavigableMap<Double,Set<E>> priorityToElement

NavigableMap of priority values to all elements that share the same priority values.

elementToPriority

private final Map<E,Double> elementToPriority

Map of elements to their associated priority values.

Constructor Detail

DoubleMapMinPQ

public DoubleMapMinPQ()

Constructs an empty instance.

Method Detail

add

public void add(E element,
                double priority)

Description copied from interface: MinPQ

Adds an element with the given priority value.

Specified by:

add in interface MinPQ<E>

Parameters:

element - the element to add.

priority - the priority value for the element.

contains

public boolean contains(E element)

Description copied from interface: MinPQ

Returns true if the given element is in this priority queue.

Specified by:

contains in interface MinPQ<E>

Parameters:

element - element to be checked for containment.

Returns:

true if the given element is in this priority queue.

peekMin

public E peekMin()

Description copied from interface: MinPQ

Returns the element with the minimum priority value.

Specified by:

peekMin in interface MinPQ<E>

Returns:

the element with the minimum priority value.

removeMin

public E removeMin()

Description copied from interface: MinPQ

Returns and removes the element with the minimum priority value.

Specified by:

removeMin in interface MinPQ<E>

Returns:

the element with the minimum priority value.

changePriority

public void changePriority(E element,
                           double priority)

Description copied from interface: MinPQ

Updates the given elements' associated priority value.

Specified by:

changePriority in interface MinPQ<E>

Parameters:

element - the element whose associated priority value should be modified.

priority - the updated priority value.

size

public int size()

Description copied from interface: MinPQ

Returns the number of elements in this priority queue.

Specified by:

size in interface MinPQ<E>

Returns:

the number of elements in this priority queue.

firstOf

private E firstOf(Iterable<E> it)

Returns any one element from the given iterable.

Parameters:

it - the iterable of elements.

Returns:

any one element from the given iterable.