org.jacop.jasat.utils.structures

Class IntPriorityQueue

java.lang.Object

org.jacop.jasat.utils.structures.IntPriorityQueue

public final class IntPriorityQueue
extends Object

A mix of a priority queue and a hashmap, specialized for ints

Version:

4.9

Author:

Simon Cruanes and Radoslaw Szymanek

Constructor Summary

Constructors

Constructor and Description
IntPriorityQueue()

Method Summary

Modifier and Type	Method and Description
int	addPriority(int i, int amount) the priority of i is now the old priority (or 0) + the amount.
int	getPriority(int i) accesses the priority of i.
int	getTop() access the element with highest priority, or 0 if it is empty
boolean	isEmpty() checks if the priority queue is empty
int	percolateDown(int i) equivalent to addPriority(i, -1);
int	percolateUp(int i) equivalent to addPriority(i, 1)
void	remove(int i) forget about i.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

IntPriorityQueue

public IntPriorityQueue()

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 priority

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