Package org.jacop.jasat.utils.structures

Class IntPriorityQueue

  • public final class IntPriorityQueue
extends java.lang.Object
    A mix of a priority queue and a hashmap, specialized for ints
    Version:
    4.8

    • 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

    • 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 depth
      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
      private void percolateDown()
      heapify the tree by swapping nodes (from the root) until the tree becomes a heap
      int 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.

      • 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

      • 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