Previous  Up  Next

Module Fcl_domain

module Fcl_domain: sig .. end

Domain Operations

This module provides functions to create and handle domains, which are useful to build variables and perform propagation (i.e. domain filtering).

type elt = int

Type of element of domains (for generic interface, ).

type t

Type of finite domains of integers (functional: no in-place modifications, domains can be shared). Standard equality and comparison can be used on domains.

val empty : t

The empty domain.

val create : elt list -> t

create l builds a new domain containing the values of l. Removes duplicates and sorts values. Returns empty if l is empty.

val unsafe_create : elt list -> t

unsafe_create l builds a new domain containing the values of l. l must be sorted and must not contain duplicate values, otherwise the behaviour is unspecified. Returns empty if l is empty. It is a more efficient variant of create.

val interval : elt -> elt -> t

interval inf sup returns the domain of all integers in the closed interval [inf..sup]. Raise Invalid_argument if inf > sup.

val int : t

The largest representable domain. Handy to create variables for which bounds cannot be previously known. It is actually much smaller than interval min_int max_int (which really is the biggest one) to try to prevent overflows while computing bounds of expressions involving such variables.

val boolean : t

The domain containing 0 and 1.

val is_empty : t -> bool

is_empty d tests whether the domain d is empty or not.

val size : t -> elt

size d returns the number of integers in d.

val min : t -> elt
val max : t -> elt

min d (resp. max d) returns the lower (resp. upper) bound of d. If d is empty, the behaviour is unspecified (incorrect return value or exception raised).

val min_max : t -> elt * elt

min_max d returns both the lower and upper bound of d. If d is empty, the behaviour is unspecified (incorrect return value or exception raised).

val iter : (elt -> unit) -> t -> unit

iter f d successively applies function f to all element of d in increasing order.

val interval_iter : (elt -> elt -> unit) -> t -> unit

interval_iter f d successively applies function f to the bounds of all the disjoint intervals of d in increasing order. E.g. a suitable function f to print a domain can be defined as fun mini maxi -> Printf.printf "%d..%d " mini maxi.

val mem : elt -> t -> bool
val member : elt -> t -> bool

member n d tests if n belongs to d.

val values : t -> elt list

value d returns the list of values of the domain d

val fprint_elt : Stdlib.out_channel -> elt -> unit
val fprint : Stdlib.out_channel -> t -> unit

Pretty printing of elements and domains.

val sprint : t -> string

sprint d returns a string representation of d.

val included : t -> t -> bool

included d1 d2 tests whether domain d1 is included in domain d2.

val smallest_geq : t -> elt -> elt
val greatest_leq : t -> elt -> elt

smallest_geq dom val (resp. greatest_leq dom val) returns the smallest (resp. greatest) value in dom greater (resp. smaller) than or equal to val. Raises Not_found if max dom < val (resp. min dom > val).

val largest_hole_around : t -> elt -> elt * elt

largest_hole_around dom val returns the largest hole (interval) in dom centred around val. Returns (val, val) if val belongs to dom and raises Not_found if val is outside dom bounds. Equivalent to (greatest_leq dom val, smallest_geq dom val) but faster.

val choose : (elt -> elt -> bool) -> t -> elt

choose ord d returns the mininum value of d for order ord. Raises Not_found if d is empty.

val add : elt -> t -> t

add n d returns d {n}.

val remove : elt -> t -> t

remove n d returns d {n}. Returns d if n is not in d.

val remove_up : elt -> t -> t
val remove_low : elt -> t -> t

remove_up n d (resp. remove_low n d) returns d [n+1..max_int] (resp. d [min_int..n-1]), i.e. removes values stricly greater (resp. less) than n.

val remove_low_up : elt -> elt -> t -> t

remove_low_up low up d is a shortcut for remove_up up (remove_low low d).

val remove_closed_inter : elt -> elt -> t -> t

remove_closed_inter inf sup d returns d [inf..sup], i.e. removes values greater than or equal to inf and less or equal to sup in d. Returns d if inf > sup.

val remove_min : t -> t
val remove_max : t -> t

remove_min d (resp. remove_max d) returns d without its lower (resp. upper) bound. Raises Invalid_argument if d is empty.

val intersection : t -> t -> t
val union : t -> t -> t

Intersection (resp. union) on domains.

val difference : t -> t -> t

difference big small returns big small. small must be included in big, otherwise the behaviour is unspecified (incorrect return value or exception raised).

val diff : t -> t -> t

diff d1 d2 returns d1 d2, i.e. domain of elements in d1 which are not in d2.

val minus : t -> t

minus d returns the domain of opposite values of d.

val plus : t -> elt -> t

plus d n translates a domain by n.

val times : t -> elt -> t

times d k expands a domain by factor k.

val compare : t -> t -> elt

compare d1 d2 is a comparison function working first on the cardinal, then (if d1 and d2 have the same size) on the lexicographic order of the domains (expressed in extension).

val compare_elt : elt -> elt -> elt

compare_elt e1 e2 is a comparison function on elements of domains. Convenient to use the Domain module as a functor argument as in module Var.

val disjoint : t -> t -> bool

disjoint d1 d2 tests whether d1 and d2 are disjoint.