Package fj.data
Class PriorityQueue<K,A>
- java.lang.Object
-
- fj.data.PriorityQueue<K,A>
-
public final class PriorityQueue<K,A> extends java.lang.Object
A priority queue implementation backed by aFingerTree
. 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).
-
-
Constructor Summary
Constructors Modifier Constructor Description private
PriorityQueue(Equal<K> e, FingerTree<K,P2<K,A>> ft)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
contains(K k)
Does the priority k exist already?PriorityQueue<K,A>
dequeue()
Removes the node with the highest priority.PriorityQueue<K,A>
dequeue(int n)
Removes the top n elements with the highest priority.static <K,A>
PriorityQueue<K,A>empty(Monoid<K> m, Equal<K> e)
Creates an empty priority queue.static <A> PriorityQueue<java.lang.Integer,A>
emptyInt()
An empty priority queue with integer priorities.PriorityQueue<K,A>
enqueue(List<P2<K,A>> list)
Adds nodes using the list of products with priority k and value a.PriorityQueue<K,A>
enqueue(P2<K,A> p)
Adds a node with priority k and value a.PriorityQueue<K,A>
enqueue(java.lang.Iterable<P2<K,A>> it)
Adds nodes using the iterable of products with priority k and value a.PriorityQueue<K,A>
enqueue(K k, A a)
Adds a node with priority k and value a.PriorityQueue<K,A>
filterKeys(F<K,java.lang.Boolean> f)
Filters the nodes based on the annotation of each node.PriorityQueue<K,A>
filterValues(F<A,java.lang.Boolean> f)
Filters nodes based on the value inside each node.boolean
isEmpty()
Is the tree empty?boolean
isEqual(Ord<K> ok, K k)
boolean
isGreaterThan(Ord<K> ok, K k)
boolean
isLessThan(Ord<K> ok, K k)
Does the top of the queue have lower priority than k?<B> PriorityQueue<K,B>
map(F<A,B> f)
Maps the values in each node with function f.static <K,A>
PriorityQueue<K,A>priorityQueue(Equal<K> e, FingerTree<K,P2<K,A>> ft)
Creates a priority queue from a finger tree.List<P2<K,A>>
toList()
Returns a list of products with priority k and value a.Option<P2<K,A>>
top()
If the tree is not empty, returns the node with highest priority otherwise returns nothing.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.List<P2<K,A>>
topN()
Returns all the elements of the queue with the highest (same) priority.Stream<P2<K,A>>
toStream()
Returns a stream of products with priority k and value a.java.lang.String
toString()
<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.
-
-
-
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?
-
toStream
public Stream<P2<K,A>> toStream()
Returns a stream of products with priority k and value a.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-