Packagecom.yworks.yfiles.util.pq
Classpublic class ListIntNodePQ
InheritanceListIntNodePQ Inheritance YObject Inheritance 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.


Public Properties
 PropertyDefined By
  empty : Boolean
[read-only] Returns whether or not this queue is empty.
ListIntNodePQ
  min : Node
[read-only] Returns the node with the minimal value in the queue.
ListIntNodePQ
Public Methods
 MethodDefined By
  
ListIntNodePQ(graph:Graph, init:Boolean = true)
Constructs an initially empty PQ.
ListIntNodePQ
  
add(v:Node, value:int):void
Adds a node to this queue with the given priority
ListIntNodePQ
  
clear():void
Removes all entries from the queue.
ListIntNodePQ
  
contains(v:Node):Boolean
Whether or not the given node is contained within this queue.
ListIntNodePQ
  
decreasePriority(v:Node, value:int):void
Decreases the priority of a node in the queue to a certain value.
ListIntNodePQ
  
decrementPriority(v:Node):void
Decrements the associated priority value for the given node by 1 and updates it's position within the queue accordingly.
ListIntNodePQ
  
dispose():void
Disposes this queue.
ListIntNodePQ
 Inherited
equals(o:Object):Boolean
YObject
  
getClass():Class
[override]
ListIntNodePQ
  
getPriority(v:Node):int
ListIntNodePQ
 Inherited
hashCode():int
YObject
  
increasePriority(v:Node, value:int):void
Increases the priority of a node in the queue to a certain value.
ListIntNodePQ
  
incrementPriority(v:Node):void
Increments the associated priority value for the given node by 1 and updates it's position within the queue accordingly.
ListIntNodePQ
  
newListIntNodePQ1(graph:Graph):ListIntNodePQ
[static] Constructs an initially empty PQ.
ListIntNodePQ
  
newListIntNodePQ2(graph:Graph, intData:DataProvider, minValue:int, maxValue:int):ListIntNodePQ
[static] Constructs a PQ that holds all nodes of the given graph.
ListIntNodePQ
  
newListIntNodePQ3(graph:Graph, intData:DataProvider, minValue:int, maxValue:int, wantedNodes:DataProvider):ListIntNodePQ
[static] Like 2().
ListIntNodePQ
  
popMaxNode():Node
Returns a node with highest associated int key within this queue.
ListIntNodePQ
  
popMinNode():Node
Returns a node with smallest associated int key within this queue.
ListIntNodePQ
  
remove(v:Node):void
Removes a node from the queue.
ListIntNodePQ
  
removeMin():Node
Same as popMinNode.
ListIntNodePQ
  
size():int
Returns the number of nodes still in the queue.
ListIntNodePQ
Protected Methods
 MethodDefined By
  
initListIntNodePQ1(graph:Graph):void
Initializes this object.
ListIntNodePQ
  
initListIntNodePQ2(graph:Graph, intData:DataProvider, minValue:int, maxValue:int):void
Initializes this object.
ListIntNodePQ
  
initListIntNodePQ3(graph:Graph, intData:DataProvider, minValue:int, maxValue:int, wantedNodes:DataProvider):void
Initializes this object.
ListIntNodePQ
Property Detail
emptyproperty
empty:Boolean  [read-only]

Returns whether or not this queue is empty.


Implementation
    public function get empty():Boolean
minproperty 
min:Node  [read-only]

Returns the node with the minimal value in the queue.

Precondition !isEmpty()

Complexity Amortized O(1)


Implementation
    public function get min():Node
Constructor Detail
ListIntNodePQ()Constructor
public function ListIntNodePQ(graph:Graph, init:Boolean = true)

Constructs an initially empty PQ.

Parameters
graph:Graph
 
init:Boolean (default = true) — An internally used switch to help handle proper instance initialization in inheritance chains where classes can have multiple constructor-like factory methods. This parameter can safely be ignored/omitted when calling the constructor.
Method Detail
add()method
public function add(v:Node, value:int):void

Adds a node to this queue with the given priority

Parameters

v:Node
 
value:int

clear()method 
public function clear():void

Removes all entries from the queue.

contains()method 
public function contains(v:Node):Boolean

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

Complexity O(1)

Parameters

v:Node

Returns
Boolean
decreasePriority()method 
public function decreasePriority(v:Node, value:int):void

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

Parameters

v:Node — a node in the priority queue.
 
value:int — the new priority value of the node.

decrementPriority()method 
public function decrementPriority(v:Node):void

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)

Parameters

v:Node

dispose()method 
public function dispose():void

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.

getClass()method 
override public function getClass():Class

Returns
Class
getPriority()method 
public function getPriority(v:Node):int

Parameters

v:Node

Returns
int
increasePriority()method 
public function increasePriority(v:Node, value:int):void

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

Parameters

v:Node — a node in the priority queue.
 
value:int — the new priority value of the node.

incrementPriority()method 
public function incrementPriority(v:Node):void

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)

Parameters

v:Node

initListIntNodePQ1()method 
protected final function initListIntNodePQ1(graph:Graph):void

Initializes this object. See the documentation of the corresponding factory method newListIntNodePQ1() for details.

Parameters

graph:Graph

See also

newListIntNodePQ1()
initListIntNodePQ2()method 
protected final function initListIntNodePQ2(graph:Graph, intData:DataProvider, minValue:int, maxValue:int):void

Initializes this object. See the documentation of the corresponding factory method newListIntNodePQ2() for details.

Parameters

graph:Graph
 
intData:DataProvider
 
minValue:int
 
maxValue:int

See also

newListIntNodePQ2()
initListIntNodePQ3()method 
protected final function initListIntNodePQ3(graph:Graph, intData:DataProvider, minValue:int, maxValue:int, wantedNodes:DataProvider):void

Initializes this object. See the documentation of the corresponding factory method newListIntNodePQ3() for details.

Parameters

graph:Graph
 
intData:DataProvider
 
minValue:int
 
maxValue:int
 
wantedNodes:DataProvider

See also

newListIntNodePQ3()
newListIntNodePQ1()method 
public static function newListIntNodePQ1(graph:Graph):ListIntNodePQ

Constructs an initially empty PQ.

Parameters

graph:Graph

Returns
ListIntNodePQ
newListIntNodePQ2()method 
public static function newListIntNodePQ2(graph:Graph, intData:DataProvider, minValue:int, maxValue:int):ListIntNodePQ

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

Parameters

graph:Graph
 
intData:DataProvider
 
minValue:int
 
maxValue:int

Returns
ListIntNodePQ
newListIntNodePQ3()method 
public static function newListIntNodePQ3(graph:Graph, intData:DataProvider, minValue:int, maxValue:int, wantedNodes:DataProvider):ListIntNodePQ

Like 2(). 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.

Parameters

graph:Graph
 
intData:DataProvider
 
minValue:int
 
maxValue:int
 
wantedNodes:DataProvider

Returns
ListIntNodePQ

See also

2()
popMaxNode()method 
public function popMaxNode():Node

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)

Returns
Node
popMinNode()method 
public function popMinNode():Node

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)

Returns
Node
remove()method 
public function remove(v:Node):void

Removes a node from the queue.

Complexity O(1)

Parameters

v:Node

removeMin()method 
public function removeMin():Node

Same as popMinNode.

Returns
Node
size()method 
public function size():int

Returns the number of nodes still in the queue.

Returns
int




Wed Oct 7 2015, 04:43 PM +02:00