Package com.complexible.common.collect

Class UpdatablePriorityQueue<T>

  • All Implemented Interfaces:
    java.lang.Iterable<T>, java.util.Collection<T>, java.util.Queue<T>
    public class UpdatablePriorityQueue<T>
extends java.util.AbstractCollection<T>
implements java.util.Queue<T>
    PriorityQueue class implemented as a binary heap with the additional function that updates the head element if its priority changes.

    • Constructor Summary

      Constructors 
      Constructor Description
      UpdatablePriorityQueue​(int initialSize, java.util.Comparator<? super T> c)
      Construct a PriorityQueue with an initial size and a specified comparator that can be null if natural .
      UpdatablePriorityQueue​(java.util.Collection<? extends T> coll, java.util.Comparator<? super T> c)
      Construct a PriorityQueue from another Collection.
      UpdatablePriorityQueue​(java.util.Comparator<? super T> c)
      Construct an empty PriorityQueue with a specified comparator.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(T x)
      void clear()
      T element()
      java.util.Iterator<T> iterator()
      Returns an iterator over the elements in this PriorityQueue.
      boolean offer​(T x)  
      T peek()
      T poll()
      T remove()
      T replace​(T newElement)
      Replaces the current head element with the given element.
      int size()
      void update()
      Updates the queue when the priority of head element and only the the priority of the head element changes.

      • Methods inherited from class java.util.AbstractCollection

        addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString

      • Methods inherited from class java.lang.Object

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

      • Methods inherited from interface java.util.Collection

        addAll, contains, containsAll, equals, hashCode, isEmpty, parallelStream, remove, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray, toArray

      • Methods inherited from interface java.lang.Iterable

        forEach

    • Constructor Detail

      • UpdatablePriorityQueue

        public UpdatablePriorityQueue​(java.util.Comparator<? super T> c)
        Construct an empty PriorityQueue with a specified comparator.

      • UpdatablePriorityQueue

        public UpdatablePriorityQueue​(java.util.Collection<? extends T> coll,
                              java.util.Comparator<? super T> c)
        Construct a PriorityQueue from another Collection.

      • UpdatablePriorityQueue

        public UpdatablePriorityQueue​(int initialSize,
                              java.util.Comparator<? super T> c)
        Construct a PriorityQueue with an initial size and a specified comparator that can be null if natural .

    • Method Detail

      • offer

        public boolean offer​(T x)
        Specified by:
        offer in interface java.util.Queue<T>

      • add

        public boolean add​(T x)
        Specified by:
        add in interface java.util.Collection<T>
        Specified by:
        add in interface java.util.Queue<T>
        Overrides:
        add in class java.util.AbstractCollection<T>

      • size

        public int size()
        Specified by:
        size in interface java.util.Collection<T>
        Specified by:
        size in class java.util.AbstractCollection<T>

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Collection<T>
        Overrides:
        clear in class java.util.AbstractCollection<T>

      • iterator

        public java.util.Iterator<T> iterator()
        Returns an iterator over the elements in this PriorityQueue. The iterator does not view the elements in any particular order and its does no support remove operation.
        Specified by:
        iterator in interface java.util.Collection<T>
        Specified by:
        iterator in interface java.lang.Iterable<T>
        Specified by:
        iterator in class java.util.AbstractCollection<T>

      • element

        public T element()
        Specified by:
        element in interface java.util.Queue<T>

      • peek

        public T peek()
        Specified by:
        peek in interface java.util.Queue<T>

      • poll

        public T poll()
        Specified by:
        poll in interface java.util.Queue<T>

      • remove

        public T remove()
        Specified by:
        remove in interface java.util.Queue<T>

      • update

        public void update()
        Updates the queue when the priority of head element and only the the priority of the head element changes.

      • replace

        public T replace​(T newElement)
        Replaces the current head element with the given element. The new element is inserted to the queue but might not be the head if it is not the minimum element according to the comparator. This function is equivalent to the following function but more efficient. 
         public T replace(T newElement) {
    T result = queue.remove();
    queue.add(newElement);   
    return result;
 }