Package org.jacop.jasat.utils.structures
Class IntPriorityQueue
- java.lang.Object
-
- org.jacop.jasat.utils.structures.IntPriorityQueue
-
public final class IntPriorityQueue extends java.lang.Object
A mix of a priority queue and a hashmap, specialized for ints- Version:
- 4.7
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
IntPriorityQueue.Node
a node containing the data associated with each int
-
Field Summary
Fields Modifier and Type Field Description private IntHashMap<IntPriorityQueue.Node>
map
private IntPriorityQueue.Node
root
-
Constructor Summary
Constructors Constructor Description IntPriorityQueue()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int
addPriority(int i, int amount)
the priority of i is now the old priority (or 0) + the amount.private IntPriorityQueue.Node
findLastNode()
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 void
percolateDown()
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 void
percolateUp(IntPriorityQueue.Node n)
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 Detail
-
map
private final IntHashMap<IntPriorityQueue.Node> map
-
root
private IntPriorityQueue.Node root
-
-
Method Detail
-
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
private IntPriorityQueue.Node 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
private final void percolateUp(IntPriorityQueue.Node n)
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
-
-