Make (psq.Psq.Make)

Priority Search Queue

Parameters

module K : Ordered

module P : Ordered

Signature

type t

A search queue.

type k = K.t

Keys in t.

type p = P.t

Priorities in t.

val empty : t

empty is the search queue that contains no bindings.

val sg : k -> p -> t

sg k p is the singleton search queue, containing only the binding k -> p.

val (++) : t -> t -> t

t1 ++ t2 adds bindings in t2 to t1.

val is_empty : t -> bool

is_empty t is true iff t is empty.

val size : t -> int

size t is the number of distinct bindings in t.

Access by `k`

val mem : k -> t -> bool

find k t is true iff k is bound in t.

val find : k -> t -> p option

find k t is Some p if t contains the binding k -> p, or None otherwise.

val add : k -> p -> t -> t

add k p t is t with the binding k -> p. If k is already bound in t, that binding is replaced.

val remove : k -> t -> t

remove k t is t without the binding for k, or t, if k is not bound in t.

val adjust : k -> (p -> p) -> t -> t

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.

val update : k -> (p option -> p option) -> t -> 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`

val min : t -> (k * p) option

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.

val rest : t -> t option

rest t is t without the binding min t, or None.

val pop : t -> ((k * p) * t) option

pop t is (min t, rest t), or None.

val fold_at_most : p -> (k -> p -> 'a -> 'a) -> 'a -> t -> 'a

fold_at_most p0 f z q folds f over bindings k -> p where p is not larger than p0, in key-ascending order.

val iter_at_most : p -> (k -> p -> unit) -> t -> unit

iter_at_most p0 f q applies f to the bindings k -> p where p is not larger than p0, in key-ascending order.

val to_seq_at_most : p -> t -> (k * p) Seq.t

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

val of_list : (k * p) list -> t

of_list kps is t with bindings kps.

When there are multiple bindings for a given k, the rightmost binding is chosen.

val of_sorted_list : (k * p) list -> t

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.

val of_seq : (k * p) Seq.t -> t

of_seq kps is of_list (List.of_seq kps).

val add_seq : (k * p) Seq.t -> t -> t

of_seq kps t is t ++ of_seq kps.

Whole-structure access

val to_list : t -> (k * p) list

to_list t are all the bindings in t in key-ascending order.

val to_seq : t -> (k * p) Seq.t

to_seq t iterates over bindings in t in key-ascending order.

val fold : (k -> p -> 'a -> 'a) -> 'a -> t -> 'a

fold f z t is f k0 p0 (f k1 p1 ... (f kn pn z)), where k0, k1, ..., kn are in ascending order.

val iter : (k -> p -> unit) -> t -> unit

iter f t applies f to all bindings in t in key-ascending order.

val to_priority_list : t -> (k * p) list

to_priority_list t are the bindings in t in priority-ascending order.

Note Priority-ordered traversal is slower than key-ordered traversal.

val to_priority_seq : t -> (k * p) Seq.t

to_priority_seq t is the sequence version of to_priority_list.

Note For traversing the whole t, to_priority_list is more efficient.

val filter : (k -> p -> bool) -> t -> t

filter p t is the search queue with exactly the bindings in t which satisfy the predicate p.

val partition : (k -> p -> bool) -> t -> t * t

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.