y.util.pq
Class IntObjectPQ

java.lang.Object
  y.util.pq.IntObjectPQ

public class IntObjectPQ
extends java.lang.Object

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

The implementation is based on binary heaps.

Constructor Summary

IntObjectPQ(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, int priority) Adds the given node with with given priority to this queue.
void	changePriority(java.lang.Object o, int p) Changes the priority value of the given node.
void	clear() Makes this queue the empty queue.
boolean	contains(java.lang.Object o) Returns whether or not the given node is contained in this queue.
void	decreasePriority(java.lang.Object o, int priority) Decreases the priority value of the given node.
void	dispose() Does nothing.
java.lang.Object	getMin() Returns he node with smallest priority in this queue.
int	getMinPriority() Returns the minimum priority value in this queue.
int	getPriority(java.lang.Object o) Returns the current priority of the given node.
void	increasePriority(java.lang.Object o, int priority) Increases the priority value of the given node.
boolean	isEmpty() Returns whether or not this queue is empty
void	remove(java.lang.Object o) Removes the given node from this queue.
java.lang.Object	removeMin() Removes the node 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

IntObjectPQ

public IntObjectPQ(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,
                int priority)

Adds the given node with with given priority to this queue.

Precondition:

!contains(v)

Complexity:

O(log(size()))

decreasePriority

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

Decreases the priority value of the given node.

Preconditions:

contains(v)

priority < getPriority(v)

Complexity:

O(log(size()))

increasePriority

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

Increases the priority value of the given node.

Preconditions:

contains(v)

priority > getPriority(v)

Complexity:

O(log(size()))

changePriority

public void changePriority(java.lang.Object o,
                           int p)

Changes the priority value of the given node.

Precondition:

contains(v)

Complexity:

O(log(size()))

removeMin

public java.lang.Object removeMin()

Removes the node with smallest priority from this queue

Precondition:

!isEmpty()

Complexity:

O(log(size()))

Returns:

the removed node with smallest priority

getMin

public java.lang.Object getMin()

Returns he node with smallest priority in this queue.

Precondition:

!isEmpty()

getMinPriority

public int getMinPriority()

Returns the minimum priority value in this queue.

contains

public boolean contains(java.lang.Object o)

Returns whether or not the given node 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 int getPriority(java.lang.Object o)

Returns the current priority of the given node.

Precondition:

contains(v)

remove

public void remove(java.lang.Object o)

Removes the given node from this queue.

Precondition:

contains(v)

Complexity:

O(log(size()))

clear

public void clear()

Makes this queue the empty queue. in this queue.

Complexity:

O(graph.N())

dispose

public void dispose()

Does nothing.