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