Module type `Psq.S`Source

Signature of priority search queues.

Priority Search Queue

Sourcetype t

A search queue.

Sourcetype k

Keys in t.

Sourcetype p

Priorities in t.

Sourceval empty : t

empty is the search queue that contains no bindings.

Sourceval sg : k -> p -> t

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

Sourceval is_empty : t -> bool

is_empty t is true iff t is empty.

Sourceval size : t -> int

size t is the number of distinct bindings in t.

Access by `k`

Sourceval mem : k -> t -> bool

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

Sourceval find : k -> t -> p option

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

Sourceval 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.

Sourceval remove : k -> t -> t

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

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

adjust f k t is t with the binding k -> p replaced by k -> f p. When k is not bound in t, the result is t.

Access by min `p`

Sourceval 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.

Sourceval rest : t -> t option

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

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

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

Sourceval 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.

Sourceval 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.

Sourceval 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 access

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

fold f z t is f k0 p0 (f k1 p1 ... (f kn pn z)). Bindings are folded over in key-ascending order.

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

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

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

partition p t splits t into (t1, t2), where t1 contains the bindings in t which satisfy the predicate p, and t2 contains those that don't.

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

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

Conversions

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

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

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

of_list kps is t with bindings kps. When there are multiple bindings for a given k, it is unspecified which one is chosen.

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

of_sorted_list kps is t with bindings kps. This operation is generally faster than of_list. kps must contain the bindings in key-ascending order without repetitions. When this is not the case, the result is undefined.

Iterators

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

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

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

of_seq kps builds t from bindings kps. When there are multiple bindings for a given k, it is unspecified which one is chosen.

Pretty-printing

Source

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.

package psq

Module type Psq.SSource