Package org.jacop.jasat.utils.structures
Class IntPriorityQueue
java.lang.Object
org.jacop.jasat.utils.structures.IntPriorityQueue
A mix of a priority queue and a hashmap, specialized for ints
- Version:
- 4.10
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) static final class
a node containing the data associated with each int -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final IntHashMap
<IntPriorityQueue.Node> private IntPriorityQueue.Node
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionint
addPriority
(int i, int amount) the priority of i is now the old priority (or 0) + the amount.private IntPriorityQueue.Node
finds the rightmost node, at the last level of depthint
getPriority
(int i) accesses the priority of i.int
getTop()
access the element with highest priority, or 0 if it is emptyboolean
isEmpty()
checks if the priority queue is emptyprivate final void
heapify the tree by swapping nodes (from the root) until the tree becomes a heapint
percolateDown
(int i) equivalent to addPriority(i, -1);int
percolateUp
(int i) equivalent to addPriority(i, 1)private final void
balances the tree again so that the given node moves up (to be called when the current node has highest priority than its parent)void
remove
(int i) forget about i.
-
Field Details
-
map
-
root
-
-
Constructor Details
-
IntPriorityQueue
public IntPriorityQueue()
-
-
Method Details
-
addPriority
public int addPriority(int i, int amount) the priority of i is now the old priority (or 0) + the amount. The priority stays >= 0.- Parameters:
i
- the int of which we want to modify the priorityamount
- the amount by which we modify the priority- Returns:
- the new priority of i
-
percolateUp
public int percolateUp(int i) equivalent to addPriority(i, 1)- Parameters:
i
- the int of which we want to modify the priority- Returns:
- the new priority of i
-
percolateDown
public int percolateDown(int i) equivalent to addPriority(i, -1);- Parameters:
i
- the int of which we want to modify the priority- Returns:
- the new priority of i
-
getPriority
public int getPriority(int i) accesses the priority of i. If i had no priority, returns 0.- Parameters:
i
- the int- Returns:
- the priority of i
-
remove
public void remove(int i) forget about i. Next call to getPriority(i) will be 0.- Parameters:
i
- the int to forget
-
getTop
public int getTop()access the element with highest priority, or 0 if it is empty- Returns:
- the element with highest priority, or 0 if it is empty
-
isEmpty
public boolean isEmpty()checks if the priority queue is empty- Returns:
- true if the priority queue is empty and false otherwise
-
findLastNode
finds the rightmost node, at the last level of depth- Returns:
- this node, or null
-
percolateDown
private final void percolateDown()heapify the tree by swapping nodes (from the root) until the tree becomes a heap -
percolateUp
balances the tree again so that the given node moves up (to be called when the current node has highest priority than its parent)- Parameters:
n
- the node
-