y.util.pq
Class ArrayIntNodePQ

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

All Implemented Interfaces:

IntNodePQ

public class ArrayIntNodePQ

extends Object

implements IntNodePQ

Implements a priority queue for nodes based on a array with bucket lists. The priority values must be less than a maximal-value which must be provided to the constructor. Certain operations have time-complexity dependend on this value. The priority values of the nodes must be non-negative. While the priority queue is used, the graph must not change.

Constructor Summary

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

ArrayIntNodePQ(Graph _graph, int maxSize)
Returns an empty Priority-Queue.

ArrayIntNodePQ(Graph _graph, NodeMap _valueMap, int maxSize)
Returns an empty Priority-Queue.

Method Summary

void	add(Node n, int value) Insertes a node into the queue.
void	changePriority(Node n, int value) Changes the value of a node in the queue to a certain value.
void	clear() Removes all entries 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.
protected YList	getList(int value) Returns the list for a given slot.
Node	getMin() Returns the node with the minimal value in the queue.
int	getPriority(Node v) Returns the current priority of the given node.
void	increasePriority(Node n, int value) Increases the value of a node in the queue to a certain value.
boolean	isEmpty() Returns whether or not this queue is empty.
void	remove(Node n) Removes a node from the priority 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

ArrayIntNodePQ

public ArrayIntNodePQ(Graph _graph,
                      int maxSize)

Returns an empty Priority-Queue.

Parameters:

_graph - the graph which contains the nodes

maxSize - the maximum value of a node in the priority queue

ArrayIntNodePQ

public ArrayIntNodePQ(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.

ArrayIntNodePQ

public ArrayIntNodePQ(Graph _graph,
                      NodeMap _valueMap,
                      int maxSize)

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

Parameters:

_graph - the graph which contains the nodes

_valueMap - here the priority values are stored

maxSize - the maximum value of a node in the priority queue

Method Detail

clear

public void clear()

Removes all entries from the queue.

Specified by:

clear in interface IntNodePQ

Complexity:

O(maxSize)

isEmpty

public boolean isEmpty()

Returns whether or not this queue is empty.

Specified by:

isEmpty in interface IntNodePQ

Complexity:

O(1)

contains

public boolean contains(Node n)

Returns whether or not the given node is contained within this queue.

Specified by:

contains in interface IntNodePQ

Complexity:

O(1)

add

public void add(Node n,
                int value)

Insertes a node into the queue.

Specified by:

add in interface IntNodePQ

Complexity:

O(1)

remove

public void remove(Node n)

Removes a node from the priority queue.
Time complexity in worst-case O(maxSize).

Complexity:

Amortisized time complexity is O(maxSize), given that the sequence of minimal keys is non-decreasing

getMin

public Node getMin()

Returns the node with the minimal value in the queue.

Specified by:

getMin in interface IntNodePQ

Complexity:

O(1)

decreasePriority

public void decreasePriority(Node n,
                             int value)

Decreases the value of a node in the queue to a certain value.

Specified by:

decreasePriority in interface IntNodePQ

Complexity:

O(1)

Parameters:

n - a node in the priotity queue.

value - the new priority value of the node.

increasePriority

public void increasePriority(Node n,
                             int value)

Increases the value of a node in the queue to a certain value.
Time complexity O(1).

Parameters:

n - a node in the priotity queue.

value - the new priority value of the node.

changePriority

public void changePriority(Node n,
                           int value)

Changes the value of a node in the queue to a certain value.
Time complexity O(1).

Parameters:

n - a node in the priotity queue.

value - the new priority value of the node.

removeMin

public Node removeMin()

Removes the node with the minimal value from the queue.
Time complexity like ArrayIntNodePQ.remove(Node).

Specified by:

removeMin 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()

Description copied from interface: IntNodePQ

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

Specified by:

dispose in interface IntNodePQ

getList

protected YList getList(int value)

Returns the list for a given slot. If there is no list yet, create one.