FheapFunctional heaps (implemented as pairing heaps).
t_of_sexp is not supported, because of the difficulty involved in recreating the comparison function.
val sexp_of_t : ('a -> Sexplib0.Sexp.t) -> 'a t -> Sexplib0.Sexp.tEven though min_elt, max_elt, and to_list are in Container.S1, they are documented separately to make sure there is no confusion.
include Core.Container.S1 with type 'a t := 'a tinclude sig ... endval length : 'a 'p1 'p2. 'a t -> intval is_empty : 'a 'p1 'p2. 'a t -> boolval iter : 'a 'p1 'p2. 'a t -> f:('a -> unit) @ local -> unititer must allow exceptions raised in f to escape, terminating the iteration cleanly. The same holds for all functions below taking an f.
val exists : 'a 'p1 'p2. 'a t -> f:('a -> bool) @ local -> boolReturns true if and only if there exists an element for which the provided function evaluates to true. This is a short-circuiting operation.
val for_all : 'a 'p1 'p2. 'a t -> f:('a -> bool) @ local -> boolReturns true if and only if the provided function evaluates to true for all elements. This is a short-circuiting operation.
val count : 'a 'p1 'p2. 'a t -> f:('a -> bool) @ local -> intReturns the number of elements for which the provided function evaluates to true.
val find : 'a 'p1 'p2. 'a t -> f:('a -> bool) @ local -> 'a Option.tReturns as an option the first element for which f evaluates to true.
val sum :
'a 'sum 'p1 'p2. (module Base.Container.Summable with type t = 'sum) ->
'a t ->
f:('a -> 'sum) @ local ->
'sumReturns the sum of f i for all i in the container. The order in which the elements will be summed is unspecified.
val iter_until :
'a 'p1 'p2 'final. 'a t ->
f:('a -> (unit, 'final) Base.Container.Continue_or_stop.t) @ local ->
(finish:(unit -> 'final) @ local ->
'final) @ localiter_until t ~f ~finish is a short-circuiting version of iter. If f returns Stop x the computation ceases and returns x. If f always returns Continue () the final result is computed by finish.
val fold :
'a 'p1 'p2 'acc. 'a t ->
init:'acc ->
f:('acc -> ('a -> 'acc) @ local) @ local ->
'accfold t ~init ~f returns f (... f (f (f init e1) e2) e3 ...) en, where e1..en are the elements of t.
val fold_result :
'a 'p1 'p2 'acc 'e. 'a t ->
init:'acc ->
f:('acc -> ('a -> ('acc, 'e) Result.t) @ local) @ local ->
('acc, 'e) Result.tfold_result t ~init ~f is a short-circuiting version of fold that runs in the Result monad. If f returns an Error _, that value is returned without any additional invocations of f.
val find_map :
'a 'p1 'p2 'b. 'a t ->
f:('a -> 'b Option.t) @ local ->
'b Option.tReturns the first evaluation of f that returns Some, and returns None if there is no such element.
val fold_until :
'a 'p1 'p2 'acc 'final. 'a t ->
init:'acc ->
f:
('acc -> ('a -> ('acc, 'final) Base.Container.Continue_or_stop.t) @ local) @ local ->
(finish:('acc -> 'final) @ local ->
'final) @ localfold_until t ~init ~f ~finish is a short-circuiting version of fold. If f returns Stop _ the computation ceases and results in that value. If f returns Continue _, the fold will proceed. If f never returns Stop _, the final result is computed by finish.
Example:
type maybe_negative =
| Found_negative of int
| All_nonnegative of { sum : int }
(** [first_neg_or_sum list] returns the first negative number in [list], if any,
otherwise returns the sum of the list. *)
let first_neg_or_sum =
List.fold_until ~init:0
~f:(fun sum x ->
if x < 0
then Stop (Found_negative x)
else Continue (sum + x))
~finish:(fun sum -> All_nonnegative { sum })
;;
let x = first_neg_or_sum [1; 2; 3; 4; 5]
val x : maybe_negative = All_nonnegative {sum = 15}
let y = first_neg_or_sum [1; 2; -3; 4; 5]
val y : maybe_negative = Found_negative -3val mem :
'a 'p1 'p2. 'a t ->
'a ->
equal:('a -> ('a -> bool) @ local) @ local ->
boolChecks whether the provided element is there, using equal.
val to_array : 'a. 'a t -> 'a arrayFheap may be used as the module argument to Sequence.merge_all.
include Core.Sequence.Heap with type 'a t := 'a tval min_elt : 'a t -> compare:('a -> 'a -> int) -> 'a option @@ portableThe comparison functions in min_elt and max_elt are independent of the one used to order the heap. Since the provided compare may be different from the one used to create the heap, it is necessary for these functions to traverse the entire heap. If you want to access the smallest element of the heap according to the heap's comparison function, you should use top.
val max_elt : 'a t -> compare:('a -> 'a -> int) -> 'a option @@ portableval to_list : 'a t -> 'a list @@ portableThe elements of to_list t are not in any particular order. You need to sort the list afterwards if you want to get a sorted list.
val create : compare:('a -> 'a -> int) -> 'a t @@ portablecreate ~compare returns a new min-heap that uses ordering function compare.
The top of the heap is the smallest element as determined by the provided comparison function.
val of_array : 'a array -> compare:('a -> 'a -> int) -> 'a t @@ portableval of_list : 'a list -> compare:('a -> 'a -> int) -> 'a t @@ portableadd t v returns the new heap after addition. Complexity O(1).
val top : 'a t -> 'a option @@ portableThis returns the top (i.e., smallest) element of the heap. Complexity O(1).
val top_exn : 'a t -> 'a @@ portableremove_top t returns the new heap after a remove. It does nothing if t is empty.
The amortized time per remove_top t (or pop t, pop_exn t, pop_if t) is O(lg n). The complexity of the worst case is O(n).
This removes and returns the top (i.e., least) element and the modified heap.
pop_if t cond returns Some (top_element, rest_of_heap) if t is not empty and its top element satisfies condition cond, or None in any other case.
val to_sequence : 'a t -> 'a Base.Sequence.t @@ portableto_sequence t is a sequence of the elements of t in ascending order.