bcds.tools
Class PQWithNumericKey<E>

java.lang.Object
  bcds.tools.PQWithNumericKey<E>

All Implemented Interfaces:

java.lang.Iterable<E>

public class PQWithNumericKey<E>
extends java.lang.Object
implements java.lang.Iterable<E>

A priority queue where the key is a value of type double. It is a wrapper on java.util.PriorityQueue, with the operation decreaseKey added.

Notes:

• Elements cannot be duplicated.
• This is priority queue of type "minimum", that is, the element with the smallest key is returned by peek/removeMin.

In this class, an "item" refers to the pair (user data element, key), which is stored as an instance of PQItemWithNumericKey. Such items are internal and are never exposed.

Author:

Juan Segovia S.

Constructor Summary

PQWithNumericKey()
Default constructor.

Method Summary

void	add(E elem, double key) Adds a new item consisting of elem and key.
void	addOrUpdate(E elem, double key) Adds a new item consisting of elem and key, or updates it if it already exists (by calling decreaseKey(elem, key)).
void	clear() Removes all the items.
boolean	contains(E e) Returns true if this priority queue contains the element e, or null if the queue is empty.
void	decreaseKey(E elem, double new_key) Decreases the key of the item corresponding to elem, setting its key to new_key.
double	getKey(E e) Returns the key of the element e.
boolean	isEmpty() Returns true if this priority queue is empty.
java.util.Iterator<E>	iterator() Returns an iterator over the elements, in no particular order.
static <E> PQWithNumericKey<E>	make() Convenience "factory" method.
E	peekData() Returns a reference to the data element of the item with the smallest key, or null if the queue is empty.
double	peekKey() Returns the smallest key in the queue.
E	removeMin() Removes the item with the smallest key and returns its data element.

Methods inherited from class java.lang.Object

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

Constructor Detail

PQWithNumericKey

public PQWithNumericKey()

Default constructor.

Method Detail

make

public static <E> PQWithNumericKey<E> make()

Convenience "factory" method.

add

public void add(E elem,
                double key)

Adds a new item consisting of elem and key.

Throws:

java.lang.IllegalArgumentException - if the element already exists.

addOrUpdate

public void addOrUpdate(E elem,
                        double key)

Adds a new item consisting of elem and key, or updates it if it already exists (by calling decreaseKey(elem, key)).

In its current implementation, this method "updates" the item by temporary removal and reinsertion with the new key.

Throws:

java.lang.IllegalArgumentException - if the new key is larger than the current one.

clear

public void clear()

Removes all the items.

isEmpty

public boolean isEmpty()

Returns true if this priority queue is empty.

removeMin

public E removeMin()

Removes the item with the smallest key and returns its data element.

Throws:

java.util.NoSuchElementException - if the queue is empty.

decreaseKey

public void decreaseKey(E elem,
                        double new_key)

Decreases the key of the item corresponding to elem, setting its key to new_key.

Throws:

java.lang.IllegalArgumentException - if the element does not exist or if the new key is larger than the current one.

peekData

public E peekData()

Returns a reference to the data element of the item with the smallest key, or null if the queue is empty.

peekKey

public double peekKey()

Returns the smallest key in the queue.

Throws:

java.util.NoSuchElementException - if the queue is empty.

contains

public boolean contains(E e)

Returns true if this priority queue contains the element e, or null if the queue is empty.

getKey

public double getKey(E e)

Returns the key of the element e.

Throws:

java.util.NoSuchElementException - if e does not exist.

iterator

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

Returns an iterator over the elements, in no particular order.

Specified by:

iterator in interface java.lang.Iterable<E>