(* This is a variant of OCaml's [Set] module, where each node in the binary
search tree carries its size (i.e., the number of its elements). The tree
is thus an ordered statistics tree, and supports [select] and [rank] in
logarithmic time and [cardinal] in constant time. *)
(* This implementation is minimalistic -- many set operations are missing. *)
module Make (Ord : Set.OrderedType) : sig
(* The type of set elements. *)
type elt = Ord.t
(* The type of sets. *)
type t
(* [empty] is the empty set. *)
val empty: t
(* [add x xs] is the union of the singleton set [x] and of the set [xs]. *)
val add: elt -> t -> t
(* [cardinal xs] is the number of elements in the set [xs]. *)
val cardinal: t -> int
(* [select i xs] returns the [i]-th element of the set [xs], viewed as an
increasing sequence. The index [i] must lie between 0 (included) and
[cardinal xs] (excluded). *)
val select: int -> t -> elt
(* [pick xs] returns a randomly-distributed random element of the set [xs].
If [xs] is empty, the exception [Not_found] is raised. *)
val pick: t -> elt
(* [rank x xs] returns the rank of the element [x] in the set [xs], viewed
as an increasing sequence. This rank is comprised between 0 (included) and
[cardinal xs] (excluded). If [x] is not a member of [xs], the exception
[Not_found] is raised. *)
val rank: elt -> t -> int
end