Package org.processmining.earthmoversstochasticconformancechecking.datastructures

Class HashBackedPriorityQueue<T>

  • Type Parameters:
    T -
    All Implemented Interfaces:
    java.lang.Iterable<T>, java.util.Collection<T>, java.util.Queue<T>
    public class HashBackedPriorityQueue<T>
extends java.lang.Object
implements java.util.Queue<T>
    Adapted implementation of the HashBackedPriorityQueue by bvdongen to support generics. Besides, this implementation is less memory efficient than the original implementation but therefore is easier to maintain and relies only on java-native libraries. It is IMPORTANT that Object.equals(Object) and Object.hashCode() are implemented. Moreover, it is possible that the comparator has a stronger assumption on what is equal. -> Idea: Hash code and equals consider the state (e.g. replay state) -> Comparator: More sophisticated ordering based on state evaluation values
    Author:
    brockhoff

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected java.util.Map<T,​java.lang.Integer> locationMap  
      protected static int NEV  
      protected java.util.ArrayList<T> queue
      Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)].

    • Constructor Summary

      Constructors 
      Constructor Description
      HashBackedPriorityQueue​(int initialCapacity, java.util.Comparator<T> itemComparator)  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(T object)
      Inserts the specified element into this priority queue.
      boolean addAll​(java.util.Collection<? extends T> c)  
      boolean addOrUpdate​(T object)  
      boolean addOrUpdateIfBetter​(T object)  
      protected boolean checkInv​(int loc)  
      void clear()  
      boolean contains​(java.lang.Object object)  
      boolean containsAll​(java.util.Collection<?> c)  
      T element()  
      T get​(java.lang.Object o)  
      java.util.Comparator<T> getItemComparator()  
      java.util.Map<T,​java.lang.Integer> getLocationMap()  
      protected boolean isBetter​(T object1, T object2)
      First order sorting is based on F score alone.
      boolean isEmpty()  
      java.util.Iterator<T> iterator()  
      boolean offer​(T object)
      Inserts the specified element into this priority queue.
      T peek()  
      protected T peek​(int location)  
      T poll()  
      T remove()  
      boolean remove​(java.lang.Object o)  
      boolean removeAll​(java.util.Collection<?> c)  
      boolean retainAll​(java.util.Collection<?> c)  
      protected void siftDown​(int positionToFill, T object)
      Inserts item x at position k, maintaining heap invariant by demoting x down the tree repeatedly until it is less than or equal to its children or is a leaf.
      protected void siftUp​(int fromPosition, T object)
      Inserts item x at position k, maintaining heap invariant by promoting x up the tree until it is greater than or equal to its parent, or is the root.
      int size()  
      java.lang.Object[] toArray()  
      <T> T[] toArray​(T[] a)  
      java.lang.String 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

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

      • Methods inherited from interface java.lang.Iterable

        forEach

    • Field Detail

      • locationMap

        protected final java.util.Map<T,​java.lang.Integer> locationMap

      • queue

        protected java.util.ArrayList<T> queue
        Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The priority queue is ordered by the record's natural ordering: For each node n in the heap and each descendant d of n, n <= d. The element with the best value is in queue[0], assuming the queue is nonempty.

    • Constructor Detail

      • HashBackedPriorityQueue

        public HashBackedPriorityQueue​(int initialCapacity,
                               java.util.Comparator<T> itemComparator)

    • Method Detail

      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Collection<T>

      • contains

        public boolean contains​(java.lang.Object object)
        Specified by:
        contains in interface java.util.Collection<T>

      • peek

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

      • peek

        protected T peek​(int location)

      • size

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

      • poll

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

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object

      • add

        public boolean add​(T object)
        Inserts the specified element into this priority queue. Does not allow to add two objects with the same hash code.
        Specified by:
        add in interface java.util.Collection<T>
        Specified by:
        add in interface java.util.Queue<T>
        Returns:
        true (as specified by Collection.add(E))

      • addOrUpdate

        public boolean addOrUpdate​(T object)

      • addOrUpdateIfBetter

        public boolean addOrUpdateIfBetter​(T object)

      • isBetter

        protected boolean isBetter​(T object1,
                           T object2)
        First order sorting is based on F score alone.

      • offer

        public boolean offer​(T object)
        Inserts the specified element into this priority queue.
        Specified by:
        offer in interface java.util.Queue<T>
        Returns:
        true (as specified by Queue.offer(E))

      • siftUp

        protected void siftUp​(int fromPosition,
                      T object)
        Inserts item x at position k, maintaining heap invariant by promoting x up the tree until it is greater than or equal to its parent, or is the root.
        Parameters:
        fromPosition -
        marking - the item to insert

      • siftDown

        protected void siftDown​(int positionToFill,
                        T object)
        Inserts item x at position k, maintaining heap invariant by demoting x down the tree repeatedly until it is less than or equal to its children or is a leaf.
        Parameters:
        positionToFill - the position to fill
        marking - the item to insert

      • checkInv

        protected boolean checkInv​(int loc)

      • iterator

        public java.util.Iterator<T> iterator()
        Specified by:
        iterator in interface java.util.Collection<T>
        Specified by:
        iterator in interface java.lang.Iterable<T>

      • toArray

        public java.lang.Object[] toArray()
        Specified by:
        toArray in interface java.util.Collection<T>

      • toArray

        public <T> T[] toArray​(T[] a)
        Specified by:
        toArray in interface java.util.Collection<T>

      • remove

        public boolean remove​(java.lang.Object o)
        Specified by:
        remove in interface java.util.Collection<T>

      • containsAll

        public boolean containsAll​(java.util.Collection<?> c)
        Specified by:
        containsAll in interface java.util.Collection<T>

      • addAll

        public boolean addAll​(java.util.Collection<? extends T> c)
        Specified by:
        addAll in interface java.util.Collection<T>

      • removeAll

        public boolean removeAll​(java.util.Collection<?> c)
        Specified by:
        removeAll in interface java.util.Collection<T>

      • retainAll

        public boolean retainAll​(java.util.Collection<?> c)
        Specified by:
        retainAll in interface java.util.Collection<T>

      • clear

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

      • remove

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

      • element

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

      • getLocationMap

        public java.util.Map<T,​java.lang.Integer> getLocationMap()

      • getItemComparator

        public java.util.Comparator<T> getItemComparator()

      • get

        public T get​(java.lang.Object o)