y.util.pq
Class DoubleObjectPQ

java.lang.Object
  y.util.pq.DoubleObjectPQ

public class DoubleObjectPQ
extends java.lang.Object

This class implements a priority queue for objects whose priority values are of type double.

The implementation is based on binary heaps.

Constructor Summary

DoubleObjectPQ(int initialSize, DataProvider provider, DataAcceptor acceptor)
Creates an empty ObjectPQ using the given DataProvider and DataAcceptor to store and retrieve Object support information.

Method Summary

void	add(java.lang.Object o, double priority) Adds the given object with given priority to this queue.
void	changePriority(java.lang.Object o, double priority) Changes the priority value of the given object.
void	clear() Makes this queue the empty queue.
boolean	contains(java.lang.Object o) Returns whether or not the given object is contained.
void	decreasePriority(java.lang.Object o, double priority) Decreases the priority value of the given object.
void	dispose() Does nothing.
java.lang.Object	getMin() Returns the object with smallest priority in this queue.
double	getMinPriority() Returns the minimum priority value in this queue.
double	getPriority(java.lang.Object o) Returns the current priority of the given object.
void	increasePriority(java.lang.Object o, double priority) Increases the priority value of the given object.
boolean	isEmpty() Returns whether or not this queue is empty.
void	remove(java.lang.Object o) Removes the given object from this queue.
java.lang.Object	removeMin() Removes the object with smallest priority from this queue.
int	size() Returns the number of nodes currently in this queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

DoubleObjectPQ

public DoubleObjectPQ(int initialSize,
                      DataProvider provider,
                      DataAcceptor acceptor)

Creates an empty ObjectPQ using the given DataProvider and DataAcceptor to store and retrieve Object support information. The contents of the provider should be modified through the use of the acceptor, i.e. they should be based on the same initially empty backing store. Additionally this backing store should not be modified externally as long as this PQ is still in use.

Method Detail

add

public void add(java.lang.Object o,
                double priority)

Adds the given object with given priority to this queue.

Precondition:

!contains(o)

Complexity:

O(log(size()))

decreasePriority

public void decreasePriority(java.lang.Object o,
                             double priority)

Decreases the priority value of the given object.

Preconditions:

contains(o)

priority < getPriority(o)

Complexity:

O(log(size()))

increasePriority

public void increasePriority(java.lang.Object o,
                             double priority)

Increases the priority value of the given object.

Preconditions:

contains(o)

priority > getPriority(o)

Complexity:

O(log(size()))

changePriority

public void changePriority(java.lang.Object o,
                           double priority)

Changes the priority value of the given object.

Precondition:

contains(o)

Complexity:

O(log(size()))

removeMin

public java.lang.Object removeMin()

Removes the object with smallest priority from this queue.

Precondition:

!isEmpty()

Complexity:

O(log(size()))

Returns:

the removed object with smallest priority

getMin

public java.lang.Object getMin()

Returns the object with smallest priority in this queue.

Precondition:

!isEmpty()

getMinPriority

public double getMinPriority()

Returns the minimum priority value in this queue.

contains

public boolean contains(java.lang.Object o)

Returns whether or not the given object is contained. in this queue.

Complexity:

O(1)

isEmpty

public boolean isEmpty()

Returns whether or not this queue is empty.

Complexity:

O(1)

size

public int size()

Returns the number of nodes currently in this queue.

Complexity:

O(1)

getPriority

public double getPriority(java.lang.Object o)

Returns the current priority of the given object.

Precondition:

contains(o)

remove

public void remove(java.lang.Object o)

Removes the given object from this queue.

Precondition:

contains(o)

Complexity:

O(log(size()))

clear

public void clear()

Makes this queue the empty queue.

Complexity:

O(size())

dispose

public void dispose()

Does nothing.