Package fj.data

Class PriorityQueue<K,​A>


  • public final class PriorityQueue<K,​A>
    extends java.lang.Object
    A priority queue implementation backed by a FingerTree. The finger tree nodes are annotated with type K, are combined using a monoid of K and both the key and value are stored in the leaf. Priorities of the same value are returned FIFO (first in, first out).
    • Method Detail

      • priorityQueue

        public static <K,​A> PriorityQueue<K,​A> priorityQueue​(Equal<K> e,
                                                                         FingerTree<K,​P2<K,​A>> ft)
        Creates a priority queue from a finger tree.
      • empty

        public static <K,​A> PriorityQueue<K,​A> empty​(Monoid<K> m,
                                                                 Equal<K> e)
        Creates an empty priority queue.
        Parameters:
        m - A monoid to combine node annotations.
        e - A value to compare key equality.
      • emptyInt

        public static <A> PriorityQueue<java.lang.Integer,​A> emptyInt()
        An empty priority queue with integer priorities.
      • map

        public <B> PriorityQueue<K,​B> map​(F<A,​B> f)
        Maps the values in each node with function f.
      • filterValues

        public PriorityQueue<K,​A> filterValues​(F<A,​java.lang.Boolean> f)
        Filters nodes based on the value inside each node.
      • filterKeys

        public PriorityQueue<K,​A> filterKeys​(F<K,​java.lang.Boolean> f)
        Filters the nodes based on the annotation of each node.
      • isEmpty

        public boolean isEmpty()
        Is the tree empty?
      • top

        public Option<P2<K,​A>> top()
        If the tree is not empty, returns the node with highest priority otherwise returns nothing.
      • topN

        public List<P2<K,​A>> topN()
        Returns all the elements of the queue with the highest (same) priority.
      • enqueue

        public PriorityQueue<K,​A> enqueue​(K k,
                                                A a)
        Adds a node with priority k and value a. This operation take O(1).
      • enqueue

        public PriorityQueue<K,​A> enqueue​(List<P2<K,​A>> list)
        Adds nodes using the list of products with priority k and value a. This operation takes O(list.length()).
      • contains

        public boolean contains​(K k)
        Does the priority k exist already?
      • enqueue

        public PriorityQueue<K,​A> enqueue​(java.lang.Iterable<P2<K,​A>> it)
        Adds nodes using the iterable of products with priority k and value a.
      • enqueue

        public PriorityQueue<K,​A> enqueue​(P2<K,​A> p)
        Adds a node with priority k and value a. This operation take O(1).
      • dequeue

        public PriorityQueue<K,​A> dequeue()
        Removes the node with the highest priority.
      • topDequeue

        public P2<Option<P2<K,​A>>,​PriorityQueue<K,​A>> topDequeue()
        Returns a tuple of the node with the highest priority and the rest of the priority queue.
      • unqueue

        public <B> B unqueue​(B empty,
                             F2<P2<K,​A>,​PriorityQueue<K,​A>,​B> topDequeue)
        Performs a reduction on this priority queue using the given arguments.
        Parameters:
        empty - The value to return if this queue is empty.
        topDequeue - The function to apply to the top priority element and the tail of the queue (without its top element).
        Returns:
        A reduction on this queue.
      • dequeue

        public PriorityQueue<K,​A> dequeue​(int n)
        Removes the top n elements with the highest priority.
      • isLessThan

        public boolean isLessThan​(Ord<K> ok,
                                  K k)
        Does the top of the queue have lower priority than k?
      • isGreaterThan

        public boolean isGreaterThan​(Ord<K> ok,
                                     K k)
      • isEqual

        public boolean isEqual​(Ord<K> ok,
                               K k)
      • toStream

        public Stream<P2<K,​A>> toStream()
        Returns a stream of products with priority k and value a.
      • toList

        public List<P2<K,​A>> toList()
        Returns a list of products with priority k and value a.
      • toString

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