y.util.pq
Class TreeIntNodePQ

java.lang.Object
  |
  +--y.util.pq.TreeIntNodePQ

All Implemented Interfaces:

IntNodePQ

public class TreeIntNodePQ

extends Object

implements IntNodePQ

Implements a priority queue for nodes based on AVL Trees. The priority values may be non-negative.

Constructor Summary

TreeIntNodePQ(Graph _graph)
Returns an empty Priority-Queue.

TreeIntNodePQ(Graph _graph, DataProvider _initValues)
Returns a new Priority-Queue initialized with all nodes of the graph.

TreeIntNodePQ(NodeMap _valueMap)
Returns an empty Priority-Queue.

Method Summary

void	add(Node n, int value) Insertes a node into the queue.
void	clear() Removes all entires from the queue.
boolean	contains(Node n) Returns whether or not the given node is contained within this queue.
void	decreasePriority(Node n, int value) Decreases the value of a node in the queue to a certain value.
void	dispose() Disposes this queue.
Node	getMin() Returns the node with the minimal value in the queue.
int	getPriority(Node v) Returns the current priority of the given node.
boolean	isEmpty() Time complexity O(1).
void	remove(Node n) Removes a node from the queue.
Node	removeMin() Removes the node with the minimal value from the queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

TreeIntNodePQ

public TreeIntNodePQ(Graph _graph)

Returns an empty Priority-Queue.

Parameters:

_graph - the graph which contains the nodes

TreeIntNodePQ

public TreeIntNodePQ(Graph _graph,
                     DataProvider _initValues)

Returns a new Priority-Queue initialized with all nodes of the graph.

Parameters:

_graph - the graph which contains the nodes

_initValues - the initial priority-values of the nodes.

TreeIntNodePQ

public TreeIntNodePQ(NodeMap _valueMap)

Returns an empty Priority-Queue. This constructor takes a NodeMap as argument which is used to store the priority values.

Parameters:

_valueMap - here the priority values are stored

Method Detail

isEmpty

public boolean isEmpty()

Time complexity O(1).

Specified by:

isEmpty in interface IntNodePQ

contains

public boolean contains(Node n)

Returns whether or not the given node is contained within this queue.
Time complexity O(log(n)).

Specified by:

contains in interface IntNodePQ

add

public void add(Node n,
                int value)

Insertes a node into the queue. Time complexity O(log(n)).

Specified by:

add in interface IntNodePQ

remove

public void remove(Node n)

Removes a node from the queue. Time complexity O(log(n)).

getMin

public Node getMin()

Returns the node with the minimal value in the queue.
Time complexity O(log(n)).

Specified by:

getMin in interface IntNodePQ

removeMin

public Node removeMin()

Removes the node with the minimal value from the queue.
Time complexity O(log(n)).

Specified by:

removeMin in interface IntNodePQ

decreasePriority

public void decreasePriority(Node n,
                             int value)

Decreases the value of a node in the queue to a certain value.
Time complexity O(log(n)).

Specified by:

decreasePriority in interface IntNodePQ

Parameters:

n - a node in the priotity queue.

value - the new priority value of the node.

clear

public void clear()

Removes all entires from the queue.
Time complexity O(1).

Specified by:

clear in interface IntNodePQ

getPriority

public int getPriority(Node v)

Description copied from interface: IntNodePQ

Returns the current priority of the given node.

Specified by:

getPriority in interface IntNodePQ

dispose

public void dispose()

Disposes this queue. It is important to call this method after the queue is not needed anymore, to free hold resources.

Specified by:

dispose in interface IntNodePQ