Module org.cicirello.core
Package org.cicirello.ds

Interface PriorityQueue<E>

Type Parameters:
E - The type of object contained in the PriorityQueue.
All Superinterfaces:
Collection<PriorityQueueNode.Integer<E>>, Iterable<PriorityQueueNode.Integer<E>>, Queue<PriorityQueueNode.Integer<E>>
All Known Subinterfaces:
MergeablePriorityQueue<E,T>
All Known Implementing Classes:
BinaryHeap, FibonacciHeap, SimpleBinaryHeap, SimpleFibonacciHeap
public interface PriorityQueue<E> extends Queue<PriorityQueueNode.Integer<E>>
Interface common to the classes that provide implementations of a priority queue with int valued priorities.

  • Method Summary

    Modifier and Type
    Method
    Description
    default boolean
    add(E element, int priority)
    Adds an (element, priority) pair to the priority queue with a specified priority.
    default boolean
    add(PriorityQueueNode.Integer<E> pair)
    Adds an (element, priority) pair to the priority queue.
    default boolean
    addAll(Collection<? extends PriorityQueueNode.Integer<E>> c)
    Adds all (element, priority) pairs from a Collection to the priority queue.
    boolean
    change(E element, int priority)
    Changes the priority of an element if the element is present in the priority queue, and otherwise adds the (element, priority) pair to the priority queue.
    void
    clear()
    Clears the priority queue, removing all elements.
    boolean
    contains(Object o)
    Checks if this priority queue contains a given element or an (element, priority) pair with a given element.
    default boolean
    containsAll(Collection<?> c)
    Checks if this priority queue contains all elements or (element, priority) pairs from a given Collection.
    boolean
    demote(E element, int priority)
    Demotes an element relative to priority order if the element is present in the priority queue.
    default PriorityQueueNode.Integer<E>
    element()
    Gets the next (element, priority) pair in priority order from this priority queue, without removing it.
    boolean
    isEmpty()
    Checks if the priority queue is empty.
    Iterator<PriorityQueueNode.Integer<E>>
    iterator()
    Returns an iterator over the (element, priority) pairs in a mostly arbitrary order (i.e., you must not assume any particular order).
    boolean
    offer(E element, int priority)
    Adds an (element, priority) pair to the priority queue with a specified priority.
    boolean
    offer(PriorityQueueNode.Integer<E> pair)
    Adds an (element, priority) pair to the priority queue.
    PriorityQueueNode.Integer<E>
    peek()
    Gets the next (element, priority) pair in priority order from this priority queue, without removing it.
    E
    peekElement()
    Gets the next element in priority order from this priority queue, without removing it.
    int
    peekPriority()
    Gets the priority of the next element in priority order in the priority queue.
    int
    peekPriority(E element)
    Gets the priority of a specified element if it is present in the priority queue.
    PriorityQueueNode.Integer<E>
    poll()
    Removes and returns the next (element, priority) pair in priority order from this priority queue.
    E
    pollElement()
    Removes and returns the next element in priority order from this priority queue.
    default E
    pollThenAdd(E element, int priority)
    Removes and returns the next element in priority order from this priority queue, adding a new (element, priority) pair to the priority queue with a specified priority.
    default PriorityQueueNode.Integer<E>
    pollThenAdd(PriorityQueueNode.Integer<E> pair)
    Removes and returns the next (element, priority) pair in priority order from this priority queue, adding a new (element, priority) pair prior to returning.
    boolean
    promote(E element, int priority)
    Promotes an element relative to priority order if the element is present in the priority queue.
    default PriorityQueueNode.Integer<E>
    remove()
    Removes and returns the next (element, priority) pair in priority order from this priority queue.
    boolean
    remove(Object o)
    Removes from this priority queue the (element, priority) pair, if present, for a specified element or element from a specified (element, priority) pair.
    boolean
    removeAll(Collection<?> c)
    Removes from this priority queue all (element, priority) pairs such that a given Collection c either contains the element or contains an (element, priority) pair with the same element.
    default E
    removeElement()
    Removes and returns the next element in priority order from this priority queue.
    boolean
    retainAll(Collection<?> c)
    Removes from this priority queue all (element, priority) pairs except for the elements or (element, priority) pairs contained in a given Collection c.
    int
    size()
    Gets the current size of the priority queue, which is the number of (element, value) pairs that it contains.
    Object[]
    toArray()
    Returns an array containing all of the (element, priority) pairs contained in the priority queue.
    <T> T[]
    toArray(T[] array)
    Returns an array containing all of the (element, priority) pairs contained in the priority queue.

    Methods inherited from interface java.util.Collection

    equals, hashCode, parallelStream, removeIf, spliterator, stream, toArray

    Methods inherited from interface java.lang.Iterable

    forEach

  • Method Details

    • add

      default boolean add(E element, int priority)
      Adds an (element, priority) pair to the priority queue with a specified priority.

      This method differs from offer(Object, int) in that it throws an exception if the add fails, while the offer method instead returns false, which will occur for the class implementations that require distinct elements. For classes implementing this interface that do not require distinctness, this method should never fail.

      Parameters:
      element - The element.
      priority - The priority of the element.
      Returns:
      true if the (element, priority) pair was added.
      Throws:
      IllegalArgumentException - if the add fails for those implementations that require distinctness.

    • add

      default boolean add(PriorityQueueNode.Integer<E> pair)
      Adds an (element, priority) pair to the priority queue.

      This method differs from offer(PriorityQueueNode.Integer) in that it throws an exception if the add fails, while the offer method instead returns false, which will occur for the class implementations that require distinct elements. For classes implementing this interface that do not require distinctness, this method should never fail.

      Specified by:
      add in interface Collection<E>
      Specified by:
      add in interface Queue<E>
      Parameters:
      pair - The (element, priority) pair to add.
      Returns:
      true if the (element, priority) pair was added.
      Throws:
      IllegalArgumentException - if the add fails for those implementations that require distinctness.

    • addAll

      default boolean addAll(Collection<? extends PriorityQueueNode.Integer<E>> c)
      Adds all (element, priority) pairs from a Collection to the priority queue.
      Specified by:
      addAll in interface Collection<E>
      Parameters:
      c - the Collection of (element, priority) pairs to add.
      Returns:
      true if the (element, priority) pairs were added.
      Throws:
      IllegalArgumentException - if the priority queue fails to add any of the (element, priority) pairs, which will occur only for the implementations that require distinctness.

    • change

      boolean change(E element, int priority)
      Changes the priority of an element if the element is present in the priority queue, and otherwise adds the (element, priority) pair to the priority queue.

      For those implementations that allow duplicate elements, this method changes the priority of only one element, without defining which is chosen when such duplicates exist.

      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the priority queue changed as a consequence of this method call.

    • clear

      void clear()
      Clears the priority queue, removing all elements.
      Specified by:
      clear in interface Collection<E>

    • contains

      boolean contains(Object o)
      Checks if this priority queue contains a given element or an (element, priority) pair with a given element.
      Specified by:
      contains in interface Collection<E>
      Parameters:
      o - An element or (element, priority) pair to check for containment of the element.
      Returns:
      true if and only if this priority queue contains the element.

    • containsAll

      default boolean containsAll(Collection<?> c)
      Checks if this priority queue contains all elements or (element, priority) pairs from a given Collection.
      Specified by:
      containsAll in interface Collection<E>
      Parameters:
      c - A Collection of elements or (element, priority) pairs to check for containment.
      Returns:
      true if and only if this priority queue contains all of the elements or (element, priority) pairs in c.

    • demote

      boolean demote(E element, int priority)
      Demotes an element relative to priority order if the element is present in the priority queue. For a min-heap, demotion means increasing the element's priority, while for a max-heap, demotion means decreasing its priority. If the element is not in the priority queue, or if its new priority is not a demotion, then this method does nothing.

      For those implementations that allow duplicate elements, this method changes the priority of only one element, without defining which is chosen when such duplicates exist.

      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the priority queue changed as a consequence of this method call.

    • element

      default PriorityQueueNode.Integer<E> element()
      Gets the next (element, priority) pair in priority order from this priority queue, without removing it.

      This method differs from peek() in that if the priority queue is empty, this method throws an exception, while peek() returns null.

      This method serves a different purpose than peekElement(). The peekElement() methods returns only the element of the (element, priority) pair, while this method returns the (element, priority) pair. This element() method is included only for full implementation of the superinterface Queue.

      Specified by:
      element in interface Queue<E>
      Returns:
      the next (element, priority) pair in priority order.
      Throws:
      NoSuchElementException - if the priority queue is empty

    • isEmpty

      boolean isEmpty()
      Checks if the priority queue is empty.
      Specified by:
      isEmpty in interface Collection<E>
      Returns:
      true if and only if it is empty

    • iterator

      Iterator<PriorityQueueNode.Integer<E>> iterator()
      Returns an iterator over the (element, priority) pairs in a mostly arbitrary order (i.e., you must not assume any particular order).
      Specified by:
      iterator in interface Collection<E>
      Specified by:
      iterator in interface Iterable<E>
      Returns:
      an iterator over the (element, priority) pairs

    • offer

      boolean offer(E element, int priority)
      Adds an (element, priority) pair to the priority queue with a specified priority.
      Parameters:
      element - The element.
      priority - The priority of the element.
      Returns:
      true if the (element, priority) pair was added, and false otherwise such as for those implementations that enforce distinct elements. For those implementations that allow duplicate elements, this method should always return true.

    • offer

      boolean offer(PriorityQueueNode.Integer<E> pair)
      Adds an (element, priority) pair to the priority queue.
      Specified by:
      offer in interface Queue<E>
      Parameters:
      pair - The (element, priority) pair to add.
      Returns:
      true if the (element, priority) pair was added, and false otherwise such as for those implementations that enforce distinct elements. For those implementations that allow duplicate elements, this method should always return true.

    • peek

      PriorityQueueNode.Integer<E> peek()
      Gets the next (element, priority) pair in priority order from this priority queue, without removing it.
      Specified by:
      peek in interface Queue<E>
      Returns:
      the next (element, priority) pair in priority order, or null if empty.

    • peekPriority

      int peekPriority()
      Gets the priority of the next element in priority order in the priority queue.
      Returns:
      the priority of the next element in priority order.

    • peekPriority

      int peekPriority(E element)
      Gets the priority of a specified element if it is present in the priority queue. This interface does not define the behavior when the element is not present. Implementations may define the behavior when the element is not present.

      For those implementations that allow duplicate elements, it returns the priority of any one of them, without defining which is chosen.

      Parameters:
      element - The element whose priority is returned.
      Returns:
      the priority of a specified element.

    • peekElement

      E peekElement()
      Gets the next element in priority order from this priority queue, without removing it.
      Returns:
      the next element in priority order, or null if empty.

    • poll

      PriorityQueueNode.Integer<E> poll()
      Removes and returns the next (element, priority) pair in priority order from this priority queue.
      Specified by:
      poll in interface Queue<E>
      Returns:
      the next (element, priority) pair in priority order, or null if empty.

    • pollElement

      E pollElement()
      Removes and returns the next element in priority order from this priority queue.
      Returns:
      the next element in priority order, or null if empty.

    • pollThenAdd

      default PriorityQueueNode.Integer<E> pollThenAdd(PriorityQueueNode.Integer<E> pair)
      Removes and returns the next (element, priority) pair in priority order from this priority queue, adding a new (element, priority) pair prior to returning.

      The behavior of this method is equivalent to calling poll(), followed by calling add(PriorityQueueNode.Integer), although some implementing classes may implement this differently where it is possible to do so more efficiently.

      Parameters:
      pair - The (element, priority) pair to add.
      Returns:
      the next (element, priority) pair in priority order, or null if empty prior to the call.

    • pollThenAdd

      default E pollThenAdd(E element, int priority)
      Removes and returns the next element in priority order from this priority queue, adding a new (element, priority) pair to the priority queue with a specified priority.

      The behavior of this method is equivalent to calling pollElement(), followed by calling add(E, int), although some implementing classes may implement this differently where it is possible to do so more efficiently.

      Parameters:
      element - The new element.
      priority - The priority of the new element.
      Returns:
      the next element in priority order, or null if empty prior to the call.

    • promote

      boolean promote(E element, int priority)
      Promotes an element relative to priority order if the element is present in the priority queue. For a min-heap, promotion means decreasing the element's priority, while for a max-heap, promotion means increasing its priority. If the element is not in the priority queue, or if its new priority is not a promotion, then this method does nothing.

      For those implementations that allow duplicate elements, this method changes the priority of only one element, without defining which is chosen when such duplicates exist.

      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the priority queue changed as a consequence of this method call.

    • remove

      default PriorityQueueNode.Integer<E> remove()
      Removes and returns the next (element, priority) pair in priority order from this priority queue. This method differs from poll() in that if the priority queue is empty, this method throws an exception, while poll() returns null.
      Specified by:
      remove in interface Queue<E>
      Returns:
      the next (element, priority) pair in priority order.
      Throws:
      NoSuchElementException - if the priority queue is empty

    • remove

      boolean remove(Object o)
      Removes from this priority queue the (element, priority) pair, if present, for a specified element or element from a specified (element, priority) pair.

      For those implementations that allow duplicate elements, this method removes only one element, without defining which is chosen when such duplicates exist.

      Specified by:
      remove in interface Collection<E>
      Parameters:
      o - An element or (element, priority) pair, such that element designates the desired pair to remove (note that if you pass an (element, priority) pair, only the element must match to cause removal.
      Returns:
      true if and only if an (element, priority) pair was removed as a result of this method call.

    • removeAll

      boolean removeAll(Collection<?> c)
      Removes from this priority queue all (element, priority) pairs such that a given Collection c either contains the element or contains an (element, priority) pair with the same element.
      Specified by:
      removeAll in interface Collection<E>
      Parameters:
      c - A Collection of elements or (element, priority) pairs for removal.
      Returns:
      true if and only if this priority queue changed as a result of this method.

    • removeElement

      default E removeElement()
      Removes and returns the next element in priority order from this priority queue. This method differs from pollElement() in that if the priority queue is empty, this method throws an exception, while pollElement() returns null.
      Returns:
      the next element in priority order.
      Throws:
      NoSuchElementException - if the priority queue is empty

    • retainAll

      boolean retainAll(Collection<?> c)
      Removes from this priority queue all (element, priority) pairs except for the elements or (element, priority) pairs contained in a given Collection c.
      Specified by:
      retainAll in interface Collection<E>
      Parameters:
      c - A Collection of elements or (element, priority) pairs to keep.
      Returns:
      true if and only if this priority queue changed as a result of this method.

    • size

      int size()
      Gets the current size of the priority queue, which is the number of (element, value) pairs that it contains.
      Specified by:
      size in interface Collection<E>
      Returns:
      the current size of the priority queue.

    • toArray

      Object[] toArray()
      Returns an array containing all of the (element, priority) pairs contained in the priority queue. The order is not guaranteed. The runtime component type is Object. The priority queue does not maintain any references to the array that is returned, instead creating a new array upon each call to the toArray method. The length of the array that is returned is equal to the current size() of the priority queue.
      Specified by:
      toArray in interface Collection<E>
      Returns:
      an array, whose runtime component type is Object, containing all of the (element, priority) pairs currently in the priority queue.

    • toArray

      <T> T[] toArray(T[] array)
      Returns an array containing all of the (element, priority) pairs contained in the priority queue. The order is not guaranteed. The runtime component type is the same as the array passed to it as a parameter. If the specified array is large enough, then it is used, otherwise a new array is allocated whose length is equal to the current size() of the priority queue. If the specified array is larger than the current size() of the priority queue, the first extra cell is set to null.
      Specified by:
      toArray in interface Collection<E>
      Type Parameters:
      T - The component type of the array to contain the (element, priority) pairs
      Parameters:
      array - The array in which to place the (element, priority) pairs, if it is sufficiently large, otherwise a new array of length size() is allocated of the same runtime type as array.
      Returns:
      The array in which the (element, priority) pairs have been inserted.
      Throws:
      ArrayStoreException - if the runtime component type of array is not compatible with the type of the (element, priority) pairs.
      NullPointerException - if array is null