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)
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.