# ocaml-lib / diet.mli

 ```Sébastien Ferré 3915c77 2012-05-22 ``` ``` 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 49 50 51 52 53 54 55 56 57 58 59 60``` ```(* 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{}} and \mbox{\texttt{}} 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) ```