OST.mli 1.39 KB
Newer Older
POTTIER Francois's avatar
POTTIER Francois committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
(* 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