1 (* Pasted from Pottier's PP compiler *)
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].
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. *)
11 module type Heterogeneous = sig
13 (* These are the types of keys, items, and sets of items. *)
19 (* This is the type of maps of keys to sets of items. *)
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. *)
26 val find: key -> t -> itemset
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
32 val add: key -> itemset -> t -> t
34 (* [update x f m] is [add x (f (find x m)) m]. *)
36 val update: key -> (itemset -> itemset) -> t -> t
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]. *)
43 val mkedge: key -> item -> t -> t
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]
51 val rmedge: key -> item -> t -> t
53 (* [iter] and [fold] iterate over all edges in the graph. *)
55 val iter: (key * item -> unit) -> t -> unit
56 val fold: (key * item -> 'a -> 'a) -> t -> 'a -> 'a
58 (* [pick m p] returns an arbitrary edge that satisfies predicate
59 [p], if the graph contains one. *)
61 val pick: t -> (key * item -> bool) -> (key * item) option
65 (* This functor offers an implementation of [Heterogeneous] out of
66 standard implementations of sets and maps. *)
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
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
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
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].
95 These maps can be used to represent general directed graphs. *)
97 module type Homogeneous = sig
99 include Heterogeneous (* [key] and [item] intended to be equal *)
101 (* [mkbiedge x1 x2 m] is [mkedge x1 x2 (mkedge x2 x1 m)]. *)
103 val mkbiedge: key -> key -> t -> t
105 (* [rmbiedge x1 x2 m] is [rmedge x1 x2 (rmedge x2 x1 m)]. *)
107 val rmbiedge: key -> key -> t -> t
109 (* [reverse m] is the reverse of graph [m]. *)
113 (* [restrict m] is the graph obtained by keeping only the vertices
114 that satisfy predicate [p]. *)
116 val restrict: (key -> bool) -> t -> 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
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
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