Search this API

y.util.pq
Class TreeIntNodePQ

java.lang.Object
  extended by y.util.pq.TreeIntNodePQ
All Implemented Interfaces:
IntNodePQ

public class TreeIntNodePQ
extends java.lang.Object
implements IntNodePQ

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

 
Your browser does not support SVG content.

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)
          Inserts a node into the queue.
 void clear()
          Removes all entities 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()
          Returns whether or not this queue is empty.
 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()
Description copied from interface: IntNodePQ
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(log(n)).

add

public void add(Node n,
                int value)
Inserts a node into the queue.

Specified by:
add in interface IntNodePQ
Complexity:
O(log(n)).

remove

public void remove(Node n)
Removes a node from the queue.

Complexity:
O(log(n)).

getMin

public Node getMin()
Returns the node with the minimal value in the queue.

Specified by:
getMin in interface IntNodePQ
Complexity:
O(log(n)).

removeMin

public Node removeMin()
Removes the node with the minimal value from the queue.

Specified by:
removeMin in interface IntNodePQ
Complexity:
O(log(n)).

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(log(n)).
Parameters:
n - a node in the priority queue.
value - the new priority value of the node.

clear

public void clear()
Removes all entities from the queue.

Specified by:
clear in interface IntNodePQ
Complexity:
O(1).

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

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