Library
Module
Module type
Parameter
Class
Class type
Make(K)(P)
is the priority search queue with bindings K.t -> P.t
.
Parameters
Signature
Priority Search Queue
val empty : t
empty
is the search queue that contains no bindings.
val size : t -> int
size t
is the number of distinct bindings in t
.
Access by k
find k t
is Some p
if t
contains the binding k -> p
, or None
otherwise.
add k p t
is t
with the binding k -> p
. If k
is already bound in t
, that binding is replaced.
adjust k f t
is t
with the binding k -> p
replaced by k -> f p
. When k
is not bound in t
, the result is t
.
update k f t
is t
with the binding for k
given by f
.
When t
contains a binding k -> p
, the new binding is given by f (Some p)
; otherwise, by f None
.
When the result of applying f
is Some p'
, the binding k -> p'
is added to t
; otherwise, the binding for k
is removed from t
.
Access by min p
min t
is the binding Some (k, p)
where p
is minimal in t
, or None
if t
is empty
.
Note that min t
is actually the smallest (p, k)
in t
— when multiple bindings share p
, min t
is the one with the smallest k
.
fold_at_most p0 f z q
folds f
over bindings k -> p
where p
is not larger than p0
, in key-ascending order.
iter_at_most p0 f q
applies f
to the bindings k -> p
where p
is not larger than p0
, in key-ascending order.
iter_at_most p0 f q
is the sequence of bindings k -> p
where p
not larger than p0
, in key-ascending order.
Aggregate construction
of_list kps
is t
with bindings kps
.
When there are multiple bindings for a given k
, the rightmost binding is chosen.
of_sorted_list kps
is t
with bindings kps
. kps
must contain the bindings in key-ascending order without repetitions. When this is not the case, the result is undefined.
Note This operation is faster than of_list
.
Whole-structure access
fold f z t
is f k0 p0 (f k1 p1 ... (f kn pn z))
, where k0, k1, ..., kn
are in ascending order.
iter f t
applies f
to all bindings in t
in key-ascending order.
to_priority_list t
are the bindings in t
in priority-ascending order.
Note Priority-ordered traversal is slower than key-ordered traversal.
to_priority_seq t
is the sequence version of to_priority_list
.
Note For traversing the whole t
, to_priority_list
is more efficient.
filter p t
is the search queue with exactly the bindings in t
which satisfy the predicate p
.
partition p t
is (filter p t, filter np t)
where np
is the negation of p
.
Pretty-printing
val pp :
?sep:(Format.formatter -> unit -> unit) ->
(Format.formatter -> (k * p) -> unit) ->
Format.formatter ->
t ->
unit
pp ?sep pp_kp ppf t
pretty-prints t
to ppf
, using pp_kp
to print the bindings and ~sep
to separate them.
~sep
defaults to Format.print_space
.
val pp_dump :
(Format.formatter -> k -> unit) ->
(Format.formatter -> p -> unit) ->
Format.formatter ->
t ->
unit
pp_dump pp_k pp_f ppf t
is a handier pretty-printer for development.