source: Deliverables/D2.2/8051/src/utilities/setMap.mli @ 486

Last change on this file since 486 was 486, checked in by ayache, 9 years ago

Deliverable D2.2

File size: 4.2 KB
RevLine 
[486]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
11module 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
63end
64
65(* This functor offers an implementation of [Heterogeneous] out of
66   standard implementations of sets and maps. *)
67
68module 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
97module 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
118end
119
120module 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
Note: See TracBrowser for help on using the repository browser.