Module PtsetSource

Sets of integers implemented as Patricia trees.

Following Chris Okasaki and Andrew Gill's paper "Fast Mergeable Integer Maps".

This is a purely applicative data structure implementing a large fragment of Set.S with type elt = int, with identical specifications and similar performances.

One advantage of Patricia trees is unicity of representation. Thus OCaml's structural comparison can be used on sets.

Sourcetype t

sets implemented with little-endian Patricia trees

Sourcetype elt = int
Sourceval empty : t
Sourceval is_empty : t -> bool
Sourceval mem : elt -> t -> bool
Sourceval add : elt -> t -> t
Sourceval singleton : elt -> t
Sourceval remove : elt -> t -> t
Sourceval union : t -> t -> t
Sourceval inter : t -> t -> t
Sourceval diff : t -> t -> t
Sourceval compare : t -> t -> int
Sourceval equal : t -> t -> bool
Sourceval subset : t -> t -> bool
Sourceval iter : (elt -> unit) -> t -> unit
Sourceval fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
Sourceval for_all : (elt -> bool) -> t -> bool
Sourceval exists : (elt -> bool) -> t -> bool
Sourceval filter : (elt -> bool) -> t -> t
Sourceval cardinal : t -> int
Sourceval choose : t -> elt
Sourceval choose_opt : t -> elt option
Sourceval find : elt -> t -> elt
Sourceval find_opt : elt -> t -> elt option
Sourceval of_list : elt list -> t
Sourceval map : (elt -> elt) -> t -> t
Sourceval partition : (elt -> bool) -> t -> t * t
Sourceval split : elt -> t -> t * bool * t

Notes:

Additional functions not appearing in the signature Set.S from ocaml standard library.

Sourceval intersect : t -> t -> bool

intersect u v determines whether sets u and v have a non-empty intersection.

Big-endian Patricia trees

Sourcemodule Big : sig ... end

Big-endian Patricia trees with nonnegative elements only.

Changes:

Sourcemodule BigPos : sig ... end