Package fj.data

Class PriorityQueue<K,A>

java.lang.Object
fj.data.PriorityQueue<K,A>

public final class PriorityQueue<K,A> extends 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).
  • Field Details

  • Constructor Details

  • Method Details

    • 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<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,Boolean> f)
      Filters nodes based on the value inside each node.
    • filterKeys

      public PriorityQueue<K,A> filterKeys(F<K,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(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 String toString()
      Overrides:
      toString in class Object