module type T = sig .. end
This module defines the common interface to functional priority queues in
the Cf library.
type +'a t
The priority queue type
module Key: sig .. end
A module defining the type of the key.
val nil : 'a t
The empty priority queue.
val empty : 'a t -> bool
Use empty q to test whether the priority queue q is empty.
val size : 'a t -> int
Use size q to count the number of elements in the priority queue q.
val head : 'a t -> Key.t * 'a
Use head q to obtain the element on the top of the priority queue
q. Raises Not_found if the queue is empty.
val tail : 'a t -> 'a t
Use tail q to obtain the heap produced by discarding the element on
the top of the priority queue q. If q is the empty queue, then the
empty queue is returned.
val pop : 'a t -> ((Key.t * 'a) * 'a t) option
Use pop q to obtain the head and the tail of a priority queue q in
one operation. Returns None if the queue q is empty.
val put : Key.t * 'a -> 'a t -> 'a t
Use put e q to obtain a new priority queue that is the result of
inserting the element e into the queue q.
val merge : 'a t -> 'a t -> 'a t
Use merge q1 q2 to obtain a new priority queue that is the result of
merging all the elements of q1 and q2 into a single heap.
val iterate : (Key.t * 'a -> unit) -> 'a t -> unit
Use iterate f q to apply f to every element in the priority queue
q in an arbitrary order (not top to bottom).
val predicate : (Key.t * 'a -> bool) -> 'a t -> bool
Use predicate f q to test whether all the elements in priority queue
q satisfy the predicate function f. Visits the elements in the
queue in arbitrary order (not top to bottom).
val fold : ('b -> Key.t * 'a -> 'b) -> 'b -> 'a t -> 'b
Use fold f s q to produce the result of folding a value s into
the elements of priority queue q with the folding function f in an
arbitrary order (not top to bottom).
val filter : (Key.t * 'a -> bool) -> 'a t -> 'a t
Use filter f q to apply f to each element in the priority queue q
in an arbitrary order (not to top bottom), and produce a new heap that
contains only those elements for which f pair returned true.
val map : (Key.t * 'a -> 'b) -> 'a t -> 'b t
Use map f q to obtain a new heap by applying the mapping function f
to the key and the value of every element in the priority queue q to
obtain a mapped element with the same key and a new value. The
elements of q are visited in an arbitrary order (not top to bottom).
val optmap : (Key.t * 'a -> 'b option) -> 'a t -> 'b t
Use optmap f q to obtain a new heap by applying the mapping function
f to the key and the value of every element in priority queue q to
obtain a mapped element with the same key and a new value. The
elements of q are visited in an arbitrary order (not top to bottom).
When f returns None for a given key, that key will not be present
in the new queue.
val partition : (Key.t * 'a -> bool) ->
'a t -> 'a t * 'a t
Use partition f q to obtain a pair of new priority queues that are
the result of applying the partitioning function f to each element in
the queue q in an arbitrary order (not top to bottom). The first
queue returned will contain all the elements for which f pair
returned true, and the second queue will return all the remaining
elements.
val of_seq : (Key.t * 'a) Cf_seq.t -> 'a t
Use of_seq z to construct a priority queue from a sequence of
elements. Evaluates the whole sequence.
val of_list : (Key.t * 'a) list -> 'a t
Use of_list s to construct a priority queue from a list of elements.
val to_seq : 'a t -> (Key.t * 'a) Cf_seq.t
Use to_seq q to produce a sequence of elements in top to bottom order
from the priority queue q.
val to_seq2 : 'a t -> ((Key.t * 'a) * 'a t) Cf_seq.t
Use to_seq2 q to produce a sequence of elements from the priority
queue q, where the first element of each pair is a key-value pair
obtained from the head of the queue, and the second element of the
pair is the corresponding tail of the queue.