src/common_sig.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 (** Type equipped with an equality and hash function.
  17     If [equal a b] then [(hash a) = (hash b)]
  18 *)
  19 module type HashedType =
  20 sig
  21   type t
  22
  23     (** [hash v] returns an integer in the range [ 0 - 2^30-1 ]
  24     *)
  25   val hash : t -> int
  26
  27     (** Equality *)
  28   val equal : t -> t -> bool
  29
  30 end
  31
  32 (** Type equiped with a total ordering *)
  33 module type OrderedType =
  34 sig
  35   type t
  36
  37     (** Total ordering on values of type [t].  [compare a b] returns a
  38         negative number if [a] is strictly smaller than [b], a positive
  39         number if [a] is strictly greater than [b] and 0 if [a] is equal
  40         to [b].  *)
  41   val compare : t -> t -> int
  42 end
  43
  44 module type Type =
  45 sig
  46   type t
  47   include HashedType with type t := t
  48   include OrderedType with type t := t
  49 end
  50
  51 (** Type equiped with a pretty-printer *)
  52 module type Printable =
  53 sig
  54   type t
  55   val print : Format.formatter -> t -> unit
  56 end
  57
  58 (** Signature of a simple HashSet module *)
  59 module type HashSet =
  60 sig
  61   type data
  62   type t
  63   val create : int -> t
  64   val add : t -> data -> unit
  65   val remove : t -> data -> unit
  66   val find : t -> data -> data
  67   val find_all : t -> data -> data list
  68   val clear : t -> unit
  69   val mem : t -> data -> bool
  70 end
  71
  72   (** Signature of simple Set module *)
  73 module type Set =
  74 sig
  75   type elt
  76   type t
  77   val empty : t
  78   val is_empty : t -> bool
  79   val mem : elt -> t -> bool
  80   val add : elt -> t -> t
  81   val singleton : elt -> t
  82   val remove : elt -> t -> t
  83   val union : t -> t -> t
  84   val inter : t -> t -> t
  85   val diff : t -> t -> t
  86   val compare : t -> t -> int
  87   val equal : t -> t -> bool
  88   val subset : t -> t -> bool
  89   val iter : (elt -> unit) -> t -> unit
  90   val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
  91   val for_all : (elt -> bool) -> t -> bool
  92   val exists : (elt -> bool) -> t -> bool
  93   val filter : (elt -> bool) -> t -> t
  94   val partition : (elt -> bool) -> t -> t * t
  95   val cardinal : t -> int
  96   val elements : t -> elt list
  97   val min_elt : t -> elt
  98   val max_elt : t -> elt
  99   val choose : t -> elt
 100   val split : elt -> t -> t * bool * t
 101   val intersect : t -> t -> bool
 102   val is_singleton : t -> bool
 103   val from_list : elt list -> t
 104 end