Package it.univr.di.cstnu.util

Class ExtendedPriorityQueue<T>

java.lang.Object
it.univr.di.cstnu.util.ExtendedPriorityQueue<T>
Type Parameters:
T - type of object in the queue.
public class ExtendedPriorityQueue<T> extends Object
Simple implementation priority queue where elements are T objects and priorities are integers.

It is based on BinaryArrayAddressableHeap, and it maintains memory of all the elements that have been inserted and removed (see getStatus(Object)).

In the constructor, it is possible to decide if the queue must be a max priority or a min priority queue.

Version:
$Rev: 732 $
Author:
posenato

  • Constructor Details

    • ExtendedPriorityQueue

      public ExtendedPriorityQueue(int initialCapacity)
      Default constructor for minimum priority queue based on binary heap.
      Parameters:
      initialCapacity - initial capacity

    • ExtendedPriorityQueue

      public ExtendedPriorityQueue(boolean maximum)
      Default constructor for min/max priority queue based on binary heap.
      Parameters:
      maximum - true if it must be a maximum priority queue, false if it must be a minimum priority queue.

    • ExtendedPriorityQueue

      public ExtendedPriorityQueue()
      Default constructor for minimum priority queue based on binary heap.

    • ExtendedPriorityQueue

      ExtendedPriorityQueue(int initialCapacity, boolean maximum)
      General constructor for min/max priority queue based on binary heap.
      Parameters:
      initialCapacity - initial capacity
      maximum - true if it must be a maximum priority queue, false if it must be a minimum priority queue.

  • Method Details

    • clear

      public final void clear()
      Makes the queue empty.

    • delete

      public void delete(T element)
      Removes the element if it is present in the queue.

      It runs in O(log n) time.

      Parameters:
      element - element to remove

    • extractFirst

      public T extractFirst()
      Removes and returns the item with minimum (maximum) priority in this heap.

      It runs in O(1) time.

      Returns:
      the T with minimum priority.

    • extractFirstEntry

      public it.unimi.dsi.fastutil.objects.AbstractObject2IntMap.BasicEntry<T> extractFirstEntry()
      Removes and returns the first entry in this heap.

      It runs in O(1) time.

      Returns:
      the entry <T, int> with minimum priority.

    • getAllDeterminedPriorities

      public it.unimi.dsi.fastutil.objects.Object2IntMap<T> getAllDeterminedPriorities()
      Returns:
      the map (T, priority) of all the elements that are/have been in the queue.

      It runs in O(n) time.

    • getElements

      public it.unimi.dsi.fastutil.objects.ObjectList<T> getElements()
      It runs in O(n) time.
      Returns:
      the element present in the queue (without priority). An empty list, if there is no element.

    • getFirstEntry

      @Nullable public org.jheaps.AddressableHeap.Handle<Integer,T> getFirstEntry()
      It runs in O(1) time.
      Returns:
      the minimum first entry of the queue without modifying it. If the queue is empty, it returns null.

    • getFirstPriority

      @Nullable public Integer getFirstPriority()
      Returns:
      the first priority

    • getPriority

      public int getPriority(T item)
      Returns the priority of the item if it is or was present in the queue, Constants.INT_POS_INFINITE if the item was never inserted, and this is a min queue, Constants.INT_NEG_INFINITE if the item was never inserted and this is a max queue.

      It runs in O(alpha) time because the element is searched in a companion hash table.

      Parameters:
      item - the search element.
      Returns:
      the priority of the item.

    • getStatus

      public ExtendedPriorityQueue.Status getStatus(T obj)
      Usually, in a priority queue, an object is first added and, possibly, removed.

      This class remembers all objects that have been added to the queue.

      Therefore, this method returns the possible state of an element (see ExtendedPriorityQueue.Status).

      It runs in O(alpha) time because the element is searched in a companion hash table.

      Parameters:
      obj - an object.
      Returns:
      a ExtendedPriorityQueue.Status object. If obj is null or the queue is empty, it returns ExtendedPriorityQueue.Status.neverPresent.

    • insertOrUpdate

      public boolean insertOrUpdate(@Nonnull T item, int priority)
      Inserts or updates the given item and its priority into this heap.

      The update is performed only when the new value is lower/greater than the present one, according to the min/max type of the queue.

      If the item was present (i.e., already extracted), the method does nothing.

      It runs in O(log n) time.

      Parameters:
      item - an object.
      priority - the value of priority
      Returns:
      true if 'item' was inserted or updated, or was present with a value smaller/greater than the given one according to the min/max type of the queue; False if the item was present and extracted with a priority greater/smaller than the given one, according to the minimum/maximum type of the queue.
      Throws:
      IllegalArgumentException - if an item is null.

    • isEmpty

      public final boolean isEmpty()
      It runs in O(1) time.
      Returns:
      true if the queue is empty, false otherwise.

    • size

      public final long size()
      It runs in O(1) time.
      Returns:
      the number of elements in the queue.

    • toString

      public String toString()
      Overrides:
      toString in class Object
      Returns:
      a string representing the queue. Be aware that the queue is based on a heap, so only the first element is guaranteed to be the minimum/maximum w.r.t. the other.