Source

ocaml-lib / diet.mli

(*
   Copyright Š 2001, Olivier Andrieu.
   Code licensed under GNU Library Public License (LGPL).

   Implements Discrete Interval Encoding Tree (diet), a datastrucure 
   for sets of integers.

   Reference:
     Martin Erwig.
     Diets for Fat Sets.
     Journal of Functional Programming, Vol. 8, No. 6, 627-632, 1998
     http://www.cs.orst.edu/~erwig/papers/Diet_JFP98.pdf
     http://www.cs.orst.edu/~erwig/diet/
*)

(*TeX
  Discrete Interval Encoding Tree is an efficient datastrucure 
  for sets of integers. See \mbox{\texttt{<http://www.cs.orst.edu/~erwig/diet/>}}
  and \mbox{\texttt{<http://www.cs.orst.edu/~erwig/papers/Diet_JFP98.pdf>}} for 
  explanations on the algorithm.
*)

type t

val empty  : t
val mem    : t -> int -> bool
val add    : t -> int -> t
val remove : t -> int -> t
val iter   : (int -> unit) -> t -> unit
val fold   : ('a -> int -> 'a) -> 'a -> t -> 'a

(*TeX
  \paragraph{Functorial interface}
  This datastructure can also be used with any type that is totally
  ordered and with a predecessor and successor function.
*)

module type ORD =
  sig
    type t
    val compare : t -> t -> int
    val pred : t -> t
    val succ : t -> t
  end

module type DIET = 
  sig
    type elt
    type t
    val empty  : t
    val mem    : t -> elt -> bool
    val add    : t -> elt -> t
    val remove : t -> elt -> t
    val iter   : (elt -> unit) -> t -> unit
    val fold   : ('a -> elt -> 'a) -> 'a -> t -> 'a
  end

module Make :
  functor (O : ORD) ->
    (DIET with type elt = O.t)