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
  • Field Details

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