package mset

  1. Overview
  2. Docs

Module Mset.ENSource

type elt = char

the type of elements

type t

The type of multisets. Immutable. Polymorphic equality, comparison, and hashing can be used on this type.

val empty : t

the empty multiset

val full : t

the full multiset, where each element has its maximal multiplicity

val size : t -> int

returns the size of the multiset i.e. the sum of all multiplicities

val is_empty : t -> bool

returns true if and only if the multiset is empty; this is equivalent to checking that the size is zero.

val is_full : t -> bool

returns true if and only if the multiset is full (the multiplicity of each element is maximal).

val occ : elt -> t -> int

returns the mutiplicity of an element (and 0 if the element does not belong to the multiset)

val add1 : elt -> t -> t

adds one occurrence of an element (and fails with Invalid_argument if the capacity for that element is exceeded)

val add : elt -> int -> t -> t

add x n ms adds n occurrences of element x to the multiset ms (or subtract from it if n is negative)

val remove1 : elt -> t -> t

removes one occurrence of an element (and does nothing if the element does not belong to the multiset)

val clear : elt -> t -> t

removes all occurrences of a given element (and does nothing if the element does not belong to the multiset)

val min_elt : t -> elt

returns a minimal element, if any, and raises Invalid_argument if the multiset is empty

val inclusion : t -> t -> bool

inclusion ms1 ms2 tests whether the multiset ms1 is included is the multiset ms2 i.e. for any element from the universe, its multiplicity in ms1 is no larger than its multiplicity in ms2.

val diff : t -> t -> t

diff ms2 ms1 computes the difference of the multiset ms2 and the multiset ms1 i.e. for any element from the universe, the difference from its multiplicity in ms2 and its multiplicity in ms1. Raises Invalid_argument if ms1 is not included in ms2.

val diff_no_check : t -> t -> t

diff_no_check ms2 ms1 computes the difference of the multiset ms2 and the multiset ms1 assuming that ms1 is included in ms2. This is a programming error to use this function when ms1 is not included in ms2, and the result is not even guaranteed to be a valid multiset.

val union : t -> t -> t

union ms1 ms2 computes the union of the multisets ms1 and ms2 i.e. for any element from the universe, the sum from its multiplicity in ms1 and its multiplicity in ms2. Raises Invalid_argument if the capacity is exceeded.

val union_no_check : t -> t -> t

union_no_check ms1 ms2 computes the union of the multiset ms1 and the multiset ms2 assuming no capacity overflow. This is a programming error to use this function when the union exceeds the capacity, and the result is not even guaranteed to be a valid multiset.

val iter : (elt -> int -> unit) -> t -> unit

Iterates over all the elements of the universe, in ascending order. For each element, it applies the given function to the element and its multiplicity in the given multiset. This iteration includes elements for which the multiplicity is zero.

val iter_sub : (t -> t -> unit) -> t -> unit

iter_sub f ms iterates f over all the sub-multisets of ms. For each sub-multiset x, function f is applied to x and diff ms x.

val fold_sub : (t -> t -> 'a -> 'a) -> t -> 'a -> 'a

fold_sub f ms folds f over all the sub-multisets of ms. For each sub-multiset x, function f is applied to x and diff ms x.

val nb_sub : t -> int

Total number of sub-multisets

val equal : t -> t -> bool
val hash : t -> int
val compare : t -> t -> int

This is a total order over multisets.

This implements multiset ordering if we consider the elements being ordered according to the list given to function create below.

val print : (Format.formatter -> elt -> unit) -> Format.formatter -> t -> unit

Prints a multiset in the following format:

{ a:3; b:0; c:1 }

Elements appear in ascending order.

val print_nat : (Format.formatter -> elt -> unit) -> Format.formatter -> t -> unit

Prints a multiset in the following format:

{ a,a,a,c }

Elements appear in ascending order.

val print_compact : (Format.formatter -> elt -> unit) -> Format.formatter -> t -> unit

Prints a multiset in the following format:

a3c

Elements appear in ascending order.

Sourcemodule Internals : sig ... end

some internal information for curious users