1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
module type S = sig
type elt
module Set : MySet.S with type elt = elt
module Rel : InnerRel.S with type elt0 = elt and module Elts = Set
type t = { input : Set.t; rel : Rel.t; output : Set.t }
val empty : t
val is_empty : t -> bool
val from_nodes : Set.t -> t
val map_nodes : (elt -> elt) -> t -> t
val seq : t -> t -> t
val union : t -> t -> t
val union3 : t -> t -> t -> t
val union4 : t -> t -> t -> t -> t
val union5 : t -> t -> t -> t -> t -> t
val union6 : t -> t -> t -> t -> t -> t -> t
val unions : t list -> t
val to_implicitely_transitive_rel : t -> Rel.t
end
module Make (O : MySet.OrderedType) :
S
with type elt = O.t
and module Set = MySet.Make(O)
and module Rel = InnerRel.Make(O) = struct
module Set = MySet.Make (O)
module Rel = InnerRel.Make (O)
type elt = O.t
type t = { input : Set.t; rel : Rel.t; output : Set.t }
let empty = { input = Set.empty; rel = Rel.empty; output = Set.empty }
let is_empty {input; rel; output; } =
Set.is_empty input && Rel.is_empty rel && Set.is_empty output
let from_nodes events = { input = events; rel = Rel.empty; output = events }
let map_nodes f { input; rel; output } =
{
input = Set.map f input;
rel = Rel.map_nodes f rel;
output = Set.map f output;
}
let seq t1 t2 =
assert (not (Set.is_empty t1.output));
assert (not (Set.is_empty t2.input));
{
input = t1.input;
rel = Rel.union3 t1.rel t2.rel (Rel.cartesian t1.output t2.input);
output = t2.output;
}
let union t1 t2 =
{
input = Set.union t1.input t2.input;
rel = Rel.union t1.rel t2.rel;
output = Set.union t1.output t2.output;
}
let union3 t1 t2 t3 =
{
input = Set.union3 t1.input t2.input t3.input;
rel = Rel.union3 t1.rel t2.rel t3.rel;
output = Set.union3 t1.output t2.output t3.output;
}
let union4 t1 t2 t3 t4 =
{
input = Set.union4 t1.input t2.input t3.input t4.input;
rel = Rel.union4 t1.rel t2.rel t3.rel t4.rel;
output = Set.union4 t1.output t2.output t3.output t4.output;
}
let union5 t1 t2 t3 t4 t5 =
{
input = Set.union5 t1.input t2.input t3.input t4.input t5.input;
rel = Rel.union5 t1.rel t2.rel t3.rel t4.rel t5.rel;
output = Set.union5 t1.output t2.output t3.output t4.output t5.output;
}
let union6 t1 t2 t3 t4 t5 t6 =
{
input = Set.union6 t1.input t2.input t3.input t4.input t5.input t6.input;
rel = Rel.union6 t1.rel t2.rel t3.rel t4.rel t5.rel t6.rel;
output =
Set.union6 t1.output t2.output t3.output t4.output t5.output t6.output;
}
(* Dichotomic implementation of iterated union. *)
(* [unions2 acc [l1; l2; ...; l2n]] is the list
[[union l1 l2; union l3 l4; ... union l2n-1 l2n]]. *)
let rec unions2 acc = function
| [] -> acc
| [ h ] -> h :: acc
| h1 :: h2 :: t -> unions2 (union h1 h2 :: acc) t
(* [unions li] calls [unions2] on [li] until it only has one element. *)
let rec unions = function
| [] -> empty
| [ h ] -> h
| li -> unions2 [] li |> unions
let to_implicitely_transitive_rel t = t.rel
end
|
