Packagecom.yworks.yfiles.util.pq
Classpublic class ArrayIntNodePQ
InheritanceArrayIntNodePQ Inheritance YObject Inheritance 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 dependent on this value. The priority values of the nodes must be non-negative. While the priority queue is used, the graph must not change.


Public Properties
 PropertyDefined By
  empty : Boolean
[read-only] Returns whether or not this queue is empty.
ArrayIntNodePQ
  min : Node
[read-only] Returns the node with the minimal value in the queue. Complexity O(1)
ArrayIntNodePQ
Public Methods
 MethodDefined By
  
ArrayIntNodePQ(_graph:Graph, maxSize:int, init:Boolean = true)
Returns an empty Priority-Queue.
ArrayIntNodePQ
  
add(n:Node, value:int):void
Inserts a node into the queue.
ArrayIntNodePQ
  
changePriority(n:Node, value:int):void
Changes the value of a node in the queue to a certain value.
ArrayIntNodePQ
  
clear():void
Removes all entries from the queue.
ArrayIntNodePQ
  
contains(n:Node):Boolean
Returns whether or not the given node is contained within this queue.
ArrayIntNodePQ
  
decreasePriority(n:Node, value:int):void
Decreases the value of a node in the queue to a certain value. Complexity O(1)
ArrayIntNodePQ
  
dispose():void
ArrayIntNodePQ
 Inherited
equals(o:Object):Boolean
YObject
  
getClass():Class
[override]
ArrayIntNodePQ
  
getPriority(v:Node):int
ArrayIntNodePQ
 Inherited
hashCode():int
YObject
  
increasePriority(n:Node, value:int):void
Increases the value of a node in the queue to a certain value. Complexity O(1).
ArrayIntNodePQ
  
newArrayIntNodePQ1(_graph:Graph, maxSize:int):ArrayIntNodePQ
[static] Returns an empty Priority-Queue.
ArrayIntNodePQ
  
newArrayIntNodePQ2(_graph:Graph, _initValues:DataProvider):ArrayIntNodePQ
[static] Returns a new Priority-Queue initialized with all nodes of the graph.
ArrayIntNodePQ
  
newArrayIntNodePQ3(_graph:Graph, _valueMap:NodeMap, maxSize:int):ArrayIntNodePQ
[static] Returns an empty Priority-Queue.
ArrayIntNodePQ
  
remove(n:Node):void
Removes a node from the priority queue. Time complexity in worst-case O(maxSize).
ArrayIntNodePQ
  
removeMin():Node
Removes the node with the minimal value from the queue. Time complexity like remove().
ArrayIntNodePQ
Protected Methods
 MethodDefined By
  
getList(value:int):YList
Returns the list for a given slot.
ArrayIntNodePQ
  
initArrayIntNodePQ1(_graph:Graph, maxSize:int):void
Initializes this object.
ArrayIntNodePQ
  
initArrayIntNodePQ2(_graph:Graph, _initValues:DataProvider):void
Initializes this object.
ArrayIntNodePQ
  
initArrayIntNodePQ3(_graph:Graph, _valueMap:NodeMap, maxSize:int):void
Initializes this object.
ArrayIntNodePQ
Property Detail
emptyproperty
empty:Boolean  [read-only]

Returns whether or not this queue is empty.

Complexity O(1)


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

Returns the node with the minimal value in the queue.

Complexity O(1)


Implementation
    public function get min():Node
Constructor Detail
ArrayIntNodePQ()Constructor
public function ArrayIntNodePQ(_graph:Graph, maxSize:int, init:Boolean = true)

Returns an empty Priority-Queue.

Parameters
_graph:Graph — the graph which contains the nodes
 
maxSize:int — the maximum value of a node in the priority queue
 
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(n:Node, value:int):void

Inserts a node into the queue.

Complexity O(1)

Parameters

n:Node
 
value:int

changePriority()method 
public function changePriority(n:Node, value:int):void

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

Complexity O(1).

Parameters

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

clear()method 
public function clear():void

Removes all entries from the queue.

Complexity O(maxSize)

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

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

Complexity O(1)

Parameters

n:Node

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

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

Complexity O(1)

Parameters

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

dispose()method 
public function dispose():void

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

Returns
Class
getList()method 
protected function getList(value:int):YList

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

Parameters

value:int

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

Parameters

v:Node

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

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

Complexity O(1).

Parameters

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

initArrayIntNodePQ1()method 
protected final function initArrayIntNodePQ1(_graph:Graph, maxSize:int):void

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

Parameters

_graph:Graph
 
maxSize:int

See also

newArrayIntNodePQ1()
initArrayIntNodePQ2()method 
protected final function initArrayIntNodePQ2(_graph:Graph, _initValues:DataProvider):void

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

Parameters

_graph:Graph
 
_initValues:DataProvider

See also

newArrayIntNodePQ2()
initArrayIntNodePQ3()method 
protected final function initArrayIntNodePQ3(_graph:Graph, _valueMap:NodeMap, maxSize:int):void

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

Parameters

_graph:Graph
 
_valueMap:NodeMap
 
maxSize:int

See also

newArrayIntNodePQ3()
newArrayIntNodePQ1()method 
public static function newArrayIntNodePQ1(_graph:Graph, maxSize:int):ArrayIntNodePQ

Returns an empty Priority-Queue.

Parameters

_graph:Graph — the graph which contains the nodes
 
maxSize:int — the maximum value of a node in the priority queue

Returns
ArrayIntNodePQ
newArrayIntNodePQ2()method 
public static function newArrayIntNodePQ2(_graph:Graph, _initValues:DataProvider):ArrayIntNodePQ

Returns a new Priority-Queue initialized with all nodes of the graph.

Parameters

_graph:Graph — the graph which contains the nodes
 
_initValues:DataProvider — the initial priority values of the nodes.

Returns
ArrayIntNodePQ
newArrayIntNodePQ3()method 
public static function newArrayIntNodePQ3(_graph:Graph, _valueMap:NodeMap, maxSize:int):ArrayIntNodePQ

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

Parameters

_graph:Graph — the graph which contains the nodes
 
_valueMap:NodeMap — here the priority values are stored
 
maxSize:int — the maximum value of a node in the priority queue

Returns
ArrayIntNodePQ
remove()method 
public function remove(n:Node):void

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

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

Parameters

n:Node

removeMin()method 
public function removeMin():Node

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

Returns
Node

See also

remove()




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