Module Multiset.Make

Parameters

module Elt : sig ... end
module Mul : MULTIPLICITY

Signature

type mul = Mul.t
type elt = Elt.t
type t = (Elt.t, Mul.t, Elt.compare) t
include Ppx_compare_lib.Comparable.S with type t := t
val compare : t Base__Ppx_compare_lib.compare
include Ppx_compare_lib.Equal.S with type t := t
val equal : t Base__Ppx_compare_lib.equal
val sexp_of_t : t -> Sexplib0.Sexp.t
type ('a, 'compare_a) comparer := 'a -> 'a -> int
type compare = (Elt.compare, Mul.compare) compare

compare types are equipped with functions to support use of @@deriving compare, equal, sexp on types parameterized by such singleton types for compare functions. These derived functions are never actually called, since the compare type parameters are phantom.

val compare_compare : compare -> compare -> int
val equal_compare : compare -> compare -> bool
val sexp_of_compare : compare -> Sexplib0.Sexp.t
val compare_of_sexp : Sexplib0.Sexp.t -> compare
val comparer : (t, compare) comparer
module Provide_of_sexp (_ : sig ... end) : sig ... end
val pp : ?pre:(unit, Stdlib.Format.formatter, unit, unit) Stdlib.format4 -> ?suf:(unit, Stdlib.Format.formatter, unit, unit) Stdlib.format4 -> (unit, Stdlib.Format.formatter, unit, unit) Stdlib.format4 -> (Stdlib.Format.formatter -> (elt * mul) -> unit) -> Stdlib.Format.formatter -> t -> unit
val empty : t

The empty multiset over the provided order.

val of_ : elt -> mul -> t
val add : elt -> mul -> t -> t

Add to multiplicity of single element. O(log n)

val remove : elt -> t -> t

Set the multiplicity of an element to zero. O(log n)

val union : t -> t -> t

Add multiplicities pointwise. O(n + m)

val diff : t -> t -> t

Subtract multiplicities pointwise. O(n + m)

val map : t -> f:(elt -> mul -> elt * mul) -> t

Map over the elements in ascending order. Preserves physical equality if f does.

val map_counts : t -> f:(mul -> mul) -> t

Map over the multiplicities of the elements in ascending order.

val mapi_counts : t -> f:(elt -> mul -> mul) -> t

Map over the multiplicities of the elements in ascending order.

val flat_map : t -> f:(elt -> mul -> t) -> t

Flat map over the elements in ascending order. Preserves physical equality if f e m is a singleton (e', m') with e == e' and Mul.equal m m' for all elements.

val partition : t -> f:(elt -> mul -> bool) -> t * t
val partition_map : t -> f:(elt -> mul -> (mul, mul) Either.t) -> t * t
val is_empty : t -> bool
val is_singleton : t -> bool
val length : t -> int

Number of elements with non-zero multiplicity. O(1).

val count : elt -> t -> mul

Multiplicity of an element. O(log n).

val only_elt : t -> (elt * mul) option

The only element of a singleton multiset. O(1).

val min_elt : t -> (elt * mul) option

Minimum element. O(log n).

val pop_min_elt : t -> (elt * mul * t) option

Find and remove minimum element. O(log n).

val classify : t -> (elt, mul) NS__.NS0.zero_one_many2

Classify a set as either empty, singleton, or otherwise.

val find_and_remove : elt -> t -> mul option * t

Find and remove an element.

val to_iter : t -> ((elt * mul) -> unit) -> unit

Enumerate elements in ascending order.

val iter : t -> f:(elt -> mul -> unit) -> unit

Iterate over the elements in ascending order.

val exists : t -> f:(elt -> mul -> bool) -> bool

Search for an element satisfying a predicate.

val for_all : t -> f:(elt -> mul -> bool) -> bool

Test whether all elements satisfy a predicate.

val fold : t -> 's -> f:(elt -> mul -> 's -> 's) -> 's

Fold over the elements in ascending order.