y.util.pq
Class ListIntNodePQ

java.lang.Object
  y.util.pq.ListIntNodePQ

All Implemented Interfaces:

IntNodePQ

public class ListIntNodePQ
extends java.lang.Object
implements IntNodePQ

A specialized priority queue that contains nodes which are prioritized by associated int values.

This queue is designed for efficiency in scenario's where the set of possible integral priority keys is small and tight (i.e their values are not far apart). Typical int values chosen are the degree of a node.

Constructor Summary

ListIntNodePQ(Graph graph)
Constructs an initially empty PQ.

ListIntNodePQ(Graph graph, DataProvider intData, int minValue, int maxValue)
Constructs a PQ that holds all nodes of the given graph.

ListIntNodePQ(Graph graph, DataProvider intData, int minValue, int maxValue, DataProvider wantedNodes)
Like ListIntNodePQ(Graph,DataProvider,int,int).

Method Summary

void	add(Node v, int value) Adds a node to this queue with the given priority
void	clear() Removes all entries from the queue.
boolean	contains(Node v) Whether or not the given node is contained within this queue.
void	decreasePriority(Node v, int value) Decreases the priority of a node in the queue to a certain value.
void	decrementPriority(Node v) Decrements the associated priority value for the given node by 1 and updates it's position within the queue accordingly.
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.
void	increasePriority(Node v, int value) Increases the priority of a node in the queue to a certain value.
void	incrementPriority(Node v) Increments the associated priority value for the given node by 1 and updates it's position within the queue accordingly.
boolean	isEmpty() Returns whether or not this queue is empty.
Node	popMaxNode() Returns a node with highest associated int key within this queue. the returned node will be removed from the queue by this method.
Node	popMinNode() Returns a node with smallest associated int key within this queue. the returned node will be removed from the queue by this method.
void	remove(Node v) Removes a node from the queue.
Node	removeMin() Same as popMinNode.
int	size() Returns the number of nodes still in the queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

ListIntNodePQ

public ListIntNodePQ(Graph graph)

Constructs an initially empty PQ.

ListIntNodePQ

public ListIntNodePQ(Graph graph,
                     DataProvider intData,
                     int minValue,
                     int maxValue)

Constructs a PQ that holds all nodes of the given graph.

the given data provider has to provide for each defined node an int value that is not bigger than minValue and not smaller than maxValue

Complexity:

O(nc.size()+(maxValue-minValue))

ListIntNodePQ

public ListIntNodePQ(Graph graph,
                     DataProvider intData,
                     int minValue,
                     int maxValue,
                     DataProvider wantedNodes)

Like ListIntNodePQ(Graph,DataProvider,int,int). Additionally a data provider can be specified, that holds boolean values for each node in the graph. Only nodes for which the data provider returns true will be entered in the queue.

Method Detail

dispose

public void dispose()

Disposes this queue. It is important to call this method after the queue is not needed anymore, since it allocates node maps from the graph that owns the nodes within the queue. Calling this method frees these node maps again.

Specified by:

dispose in interface IntNodePQ

isEmpty

public boolean isEmpty()

Returns whether or not this queue is empty.

Specified by:

isEmpty in interface IntNodePQ

contains

public boolean contains(Node v)

Whether or not the given node is contained within this queue.

Specified by:

contains in interface IntNodePQ

Complexity:

O(1)

size

public int size()

Returns the number of nodes still in the queue.

add

public void add(Node v,
                int value)

Adds a node to this queue with the given priority

Specified by:

add in interface IntNodePQ

decreasePriority

public void decreasePriority(Node v,
                             int value)

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

Specified by:

decreasePriority in interface IntNodePQ

Parameters:

v - a node in the priority queue.

value - the new priority value of the node.

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

increasePriority

public void increasePriority(Node v,
                             int value)

Increases the priority of a node in the queue to a certain value.

Parameters:

v - a node in the priority queue.

value - the new priority value of the node.

getMin

public Node getMin()

Returns the node with the minimal value in the queue.

Specified by:

getMin in interface IntNodePQ

Precondition:

!isEmpty()

Complexity:

Amortized O(1)

clear

public void clear()

Removes all entries from the queue.

Specified by:

clear in interface IntNodePQ

remove

public void remove(Node v)

Removes a node from the queue.

Complexity:

O(1)

removeMin

public Node removeMin()

Same as popMinNode.

Specified by:

removeMin in interface IntNodePQ

popMinNode

public Node popMinNode()

Returns a node with smallest associated int key within this queue. the returned node will be removed from the queue by this method.

Precondition:

!isEmpty()

Complexity:

Amortized O(1)

popMaxNode

public Node popMaxNode()

Returns a node with highest associated int key within this queue. the returned node will be removed from the queue by this method.

Precondition:

!isEmpty()

Complexity:

Amortized O(1)

incrementPriority

public void incrementPriority(Node v)

Increments the associated priority value for the given node by 1 and updates it's position within the queue accordingly.

Precondition:

contains(v)

Complexity:

O(1)

decrementPriority

public void decrementPriority(Node v)

Decrements the associated priority value for the given node by 1 and updates it's position within the queue accordingly.

Precondition:

contains(v)

Complexity:

O(1)