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.


© Copyright 2000-2003,
yWorks GmbH.
All rights reserved.

2003