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 | |
---|