extracted/untrusted/setMap.mli

   1 (* Pasted from Pottier's PP compiler *)
   2
   3 (** This signature defines a few operations over maps of keys to
   4     nonempty sets of items. Keys and items can have distinct types,
   5     hence the name [Heterogeneous].
   6
   7     These maps can be used to represent directed bipartite graphs whose
   8     source vertices are keys and whose target vertices are items. Each
   9     key is mapped to the set of its successors. *)
  10
  11 module type Heterogeneous = sig
  12
  13   (* These are the types of keys, items, and sets of items. *)
  14
  15   type key
  16   type item
  17   type itemset
  18
  19   (* This is the type of maps of keys to sets of items. *)
  20
  21   type t
  22
  23   (* [find x m] is the item set associated with key [x] in map [m], if
  24      such an association is defined; it is the empty set otherwise. *)
  25
  26   val find: key -> t -> itemset
  27
  28   (* [add x is m] extends [m] with a binding of [x] to the item set
  29      [is], if [is] is nonempty. If [is] is empty, it removes [x] from
  30      [m]. *)
  31
  32   val add: key -> itemset -> t -> t
  33
  34   (* [update x f m] is [add x (f (find x m)) m]. *)
  35
  36   val update: key -> (itemset -> itemset) -> t -> t
  37
  38   (* [mkedge x i m] extends [m] with a binding of [x] to the union of
  39      the set [m x] and the singleton [i], where [m x] is taken to be
  40      empty if undefined. In terms of graphs, [mkedge x i m] extends
  41      the graph [m] with an edge of [x] to [i]. *)
  42
  43   val mkedge: key -> item -> t -> t
  44
  45   (* [rmedge x i m] extends [m] with a binding of [x] to the
  46      difference of the set [m x] and the singleton [i], where the
  47      binding is considered undefined if that difference is empty.  In
  48      terms of graphs, [rmedge x i m] removes an edge of [x] to [i]
  49      to the graph [m]. *)
  50
  51   val rmedge: key -> item -> t -> t
  52
  53   (* [iter] and [fold] iterate over all edges in the graph. *)
  54
  55   val iter: (key * item -> unit) -> t -> unit
  56   val fold: (key * item -> 'a -> 'a) -> t -> 'a -> 'a
  57
  58   (* [pick m p] returns an arbitrary edge that satisfies predicate
  59      [p], if the graph contains one. *)
  60
  61   val pick: t -> (key * item -> bool) -> (key * item) option
  62
  63 end
  64
  65 (* This functor offers an implementation of [Heterogeneous] out of
  66    standard implementations of sets and maps. *)
  67
  68 module MakeHetero
  69     (Set : sig
  70       type elt
  71       type t
  72       val empty: t
  73       val is_empty: t -> bool
  74       val add: elt -> t -> t
  75       val remove: elt -> t -> t
  76       val fold: (elt -> 'a -> 'a) -> t -> 'a -> 'a
  77     end)
  78     (Map : sig
  79       type key
  80       type 'a t
  81       val add: key -> 'a -> 'a t -> 'a t
  82       val find: key -> 'a t -> 'a
  83       val remove: key -> 'a t -> 'a t
  84       val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
  85     end)
  86     : Heterogeneous with type key = Map.key
  87                      and type item = Set.elt
  88                      and type itemset = Set.t
  89                      and type t = Set.t Map.t
  90
  91 (* This signature defines a few common operations over maps of keys
  92    to sets of keys -- that is, keys and items have the same type,
  93    hence the name [Homogeneous].
  94
  95    These maps can be used to represent general directed graphs. *)
  96
  97 module type Homogeneous = sig
  98
  99   include Heterogeneous (* [key] and [item] intended to be equal *)
 100
 101   (* [mkbiedge x1 x2 m] is [mkedge x1 x2 (mkedge x2 x1 m)]. *)
 102
 103   val mkbiedge: key -> key -> t -> t
 104
 105   (* [rmbiedge x1 x2 m] is [rmedge x1 x2 (rmedge x2 x1 m)]. *)
 106
 107   val rmbiedge: key -> key -> t -> t
 108
 109   (* [reverse m] is the reverse of graph [m]. *)
 110
 111   val reverse: t -> t
 112
 113   (* [restrict m] is the graph obtained by keeping only the vertices
 114      that satisfy predicate [p]. *)
 115
 116   val restrict: (key -> bool) -> t -> t
 117
 118 end
 119
 120 module MakeHomo
 121     (Set : sig
 122       type elt
 123       type t
 124       val empty: t
 125       val is_empty: t -> bool
 126       val add: elt -> t -> t
 127       val remove: elt -> t -> t
 128       val fold: (elt -> 'a -> 'a) -> t -> 'a -> 'a
 129       val filter: (elt -> bool) -> t -> t
 130     end)
 131     (Map : sig
 132       type key = Set.elt
 133       type 'a t
 134       val empty: 'a t
 135       val add: key -> 'a -> 'a t -> 'a t
 136       val find: key -> 'a t -> 'a
 137       val remove: key -> 'a t -> 'a t
 138       val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
 139     end)
 140     : Homogeneous with type key = Set.elt
 141                    and type item = Set.elt
 142                    and type itemset = Set.t
 143                    and type t = Set.t Map.t
 144