Previous  Up  Next

Module Cis

module Cis: sig .. end
Cis : compact integer sets (Sébastien Ferré)

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.

License: LGPL
Author(s): : Sébastien Ferré <ferre@irisa.fr>
See also Home page

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 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 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.