ocaml-lib / cis.mli

(**
   Cis : compact integer sets

   This module implements compact integer sets, represented as a (custom) list
   of integer intervals. Usual set operations are provided.
   The advantage compared to ordered lists is that the actual size may be smaller
   than the cardinal of a set when many elements are contiguous. Most set operations
   are linear w.r.t. the size of the structure, not the cardinal of the set.

   Author: Sébastien Ferré <ferre@irisa.fr>
   License: LGPL
*)

type t (** Type of cis *)

val max_elt : t -> int
    (** [max_elt cis] returns the maximum integer in [cis]. Takes constant time. *)
val min_elt : t -> int
    (** [min_elt cis] returns the minimum integer in [cis]. Takes linear time. *)
val step : t -> nil:(unit -> 'a) -> single:(int -> t -> 'a) -> interv:(int * int -> t -> 'a) -> 'a
val cons_single : int -> t -> t
val cons_interv : int * int -> t -> t
val append : t -> t -> t
    (** [append cis1 cis2] returns the union of [cis1] and [cis2] assuming that all elements of [cis1] are greater than any element of [cis2].
       Takes linear time in the size of [cis1]. Not tail-recursive. *)
val empty : t
    (** [empty] is the empty set. *)
val is_empty : t -> bool
    (** [is_empty cis] returns whether [cis] is the empty set. *)
val cardinal : t -> int
    (** [cardinal cis] returns the cardinal of [cis]. Takes linear time in the size of [cis]. *)
val mem : int -> t -> bool
    (** [mem x cis] returns whether [x] belongs to [cis]. Takes linear time in the size of [cis]. *) 
val choose : t -> int
    (** [choose cis] returns an integer that belongs to [cis] if there is any, and raises [Not_found] otherwise. *)
val singleton : int -> t
    (** [singleton x] returns a singleton set with element [x]. *)
val add : int -> t -> t
    (** [add x cis] adds element [x] to [cis]. Takes linear time in the size of [cis], but constant time when [x] is greater than any element in [cis].
       Not tail-recursive. *)
val remove : int -> t -> t
    (** [remove x cis] removes element [x] from [cis]. Not tail-recursive. *)
val of_list : int list -> t
    (** [of_list l] builds a cis from an integer list. *)
val union : t -> t -> t
    (** The set union. *)
val inter : t -> t -> t
    (** The set intersection. *)
val diff : t -> t -> t
    (** The set difference. *)
val subset : t -> t -> bool
    (** [subset cis1 cis2] returns whether [cis1] is a subset of [cis2]. *)
val equal : t -> t -> bool
    (** [equal cis1 cis2] returns whether [cis1] is equal to [cis2]. *)
val iter : (int -> unit) -> t -> unit
    (** Iteration on the elements of a cis. *)
val fold_left : ('a -> int -> 'a) -> 'a -> t -> 'a
    (** Left folding. Elements are visited in decreasing order. *)
val fold_right : (int -> 'a -> 'a) -> t -> 'a -> 'a
    (** Right folding. Integers are visited in increasing order. *)
val elements : t -> int list
    (** [elements cis] returns the elements of [cis] as list of decreasing integers. *)
val memory_size : t -> int
    (** [memory_size cis] returns the memory size of the set in words. *)
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.