src/sigs.ml

   1 (***********************************************************************)
   2 (*                                                                     *)
   3 (*                               TAToo                                 *)
   4 (*                                                                     *)
   5 (*                     Kim Nguyen, LRI UMR8623                         *)
   6 (*                   Université Paris-Sud & CNRS                       *)
   7 (*                                                                     *)
   8 (*  Copyright 2010-2012 Université Paris-Sud and Centre National de la *)
   9 (*  Recherche Scientifique. All rights reserved.  This file is         *)
  10 (*  distributed under the terms of the GNU Lesser General Public       *)
  11 (*  License, with the special exception on linking described in file   *)
  12 (*  ../LICENSE.                                                        *)
  13 (*                                                                     *)
  14 (***********************************************************************)
  15
  16 (** Various generic signatures *)
  17
  18 module type HashedType =
  19 sig
  20   type t
  21   val hash : t -> int
  22     (** [hash v] returns an integer in the range
  23         [ 0 - 2^30-1 ]
  24     *)
  25   val equal : t -> t -> bool
  26     (** Equality *)
  27 end
  28 (** Type equipped with an equality and hash function.
  29     If [equal a b] then [(hash a) = (hash b)]
  30 *)
  31
  32
  33 module type OrderedType =
  34 sig
  35   type t
  36   val compare : t -> t -> int
  37     (** Total ordering on values of type [t].
  38         [compare a b] returns a negative number if [a] is strictly
  39         smaller than [b], a positive number if [a] is strictly greater
  40         than [b] and 0 if [a] is equal to [b].
  41     *)
  42 end
  43 (** Type equiped with a total ordering *)
  44
  45 module type Printable =
  46 sig
  47   type t
  48   val print : Format.formatter -> t -> unit
  49 end
  50   (** Type equiped with a pretty-printer *)
  51
  52
  53 module type Type =
  54 sig
  55   type t
  56   include HashedType with type t := t
  57   include OrderedType with type t := t
  58 end
  59   (** Type with both total ordering and hashing functions.
  60       All modules of that type must enforce than:
  61       [equal a b] if and only if [compare a b = 0]
  62   *)
  63
  64 module type HashSet =
  65 sig
  66   type data
  67   type t
  68   val create : int -> t
  69   val add : t -> data -> unit
  70   val remove : t -> data -> unit
  71   val find : t -> data -> data
  72   val find_all : t -> data -> data list
  73   val clear : t -> unit
  74   val mem : t -> data -> bool
  75 end
  76 (** Signature of a simple HashSet module *)
  77 module type Set =
  78 sig
  79   type elt
  80   type t
  81   val empty : t
  82   val is_empty : t -> bool
  83   val mem : elt -> t -> bool
  84   val add : elt -> t -> t
  85   val singleton : elt -> t
  86   val remove : elt -> t -> t
  87   val union : t -> t -> t
  88   val inter : t -> t -> t
  89   val diff : t -> t -> t
  90   val compare : t -> t -> int
  91   val equal : t -> t -> bool
  92   val subset : t -> t -> bool
  93   val iter : (elt -> unit) -> t -> unit
  94   val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
  95   val for_all : (elt -> bool) -> t -> bool
  96   val exists : (elt -> bool) -> t -> bool
  97   val filter : (elt -> bool) -> t -> t
  98   val partition : (elt -> bool) -> t -> t * t
  99   val cardinal : t -> int
 100   val elements : t -> elt list
 101   val min_elt : t -> elt
 102   val max_elt : t -> elt
 103   val choose : t -> elt
 104   val split : elt -> t -> t * bool * t
 105   val intersect : t -> t -> bool
 106   val is_singleton : t -> bool
 107   val from_list : elt list -> t
 108 end
 109
 110 exception InfiniteSet
 111
 112 module type FiniteCofiniteSet =
 113 sig
 114   include Set
 115   type set
 116   val any : t
 117   val is_any : t -> bool
 118   val is_finite : t -> bool
 119   val kind : t -> [ `Finite | `Cofinite ]
 120   val complement : t -> t
 121   val kind_split : t list -> t * t
 122   val positive : t -> set
 123   val negative : t -> set
 124   val inj_positive : set -> t
 125   val inj_negative : set -> t
 126 end