Common — library colibrilib.models — module NodeHModel

bdd.NodeH: maps with finitely many non–empty lists

1154
module NodeHModel
1155
use int.Int
1156
use set.Set
1157
use set.Cardinal
1158
use map.Map
1159
use list.List
1160
use list.Length
1161
use option.Option
1162
use mach.int.Int63
1163
use colibrilib.bdd.Node
1164
clone SetFacts as SF {… begin (* cloned colibrilib.models.SetFacts *) let ghost
SF.inter_union
(t -> bool) (t -> bool) (t -> bool) (t -> bool) (t -> bool) : unit let ghost
SF.card_remove
t (t -> bool) : unit end
}
with type a = Node.t
1165
Valid (23ms) (colibri2)
1166
type
t
'a = {
1167
ghost mutable
contents
: Node.t -> list 'a;
1168
ghost mutable
keys
: set Node.t;
1169
mutable
adds
: int; (* a concrete effect for add_cons *)
1170
} invariant { is_finite keys }
1171
invariant { forall k. contents k <> Nil -> mem k keys }
1172
by { contents = (fun _ -> Nil); keys = Set.empty; adds = 0 }
1173
Valid (29ms) (colibri2)
1174
let
create
(_n: int63) : t 'a
1175
ensures { forall k. result.contents k = Nil }
1176
= { contents = (fun _ -> Nil); keys = Set.empty; adds = 0 }
1177
Valid (97ms) (cvc5)
1178
let
add_cons
(h: t 'a) (n: Node.t) (x: 'a) : unit
1179
writes { h }
1180
ensures { h.contents = Map.set (old h.contents) n (Cons x (old h.contents n)) }
1181
= h.contents <- pure { Map.set h.contents n (Cons x (h.contents n)) };
1182
h.keys <- pure { Set.add n h.keys };
1183
h.adds <- h.adds + 1

A key of s with the shortest non–empty list

  Valid (1.3s) (colibri2)
1186
let rec ghost
argmin
(h: t 'a) (s: set Node.t) : option Node.t
1187
requires { is_finite s }
1188
ensures { match result with
1189
| None -> forall k. mem k s -> h.contents k = Nil
1190
| Some n -> mem n s /\ h.contents n <> Nil /\
1191
(forall k. mem k s -> h.contents k <> Nil ->
1192
length (h.contents n) <= length (h.contents k))
1193
end }
1194
variant { cardinal s }
1195
= if pure { is_empty s } then None
1196
else begin
1197
let k = pick s in
1198
assert { mem k s };
1199
SF.card_remove k s;
1200
let r = argmin h (remove k s) in
1201
match r with
1202
| None -> if pure { h.contents k = Nil } then None else Some k
1203
| Some n ->
1204
if pure { h.contents k <> Nil /\ length (h.contents k) < length (h.contents n) }
1205
then Some k else Some n
1206
end
1207
end
1208
Valid (397ms) (cvc5)
1209
let
fold_min
(h: t 'a) : option (Node.t, int, list 'a)
1210
ensures { match result with
1211
| None -> forall k. h.contents k = Nil
1212
| Some (n, len, l) -> l = h.contents n /\ l <> Nil /\ len = length l /\
1213
(forall k. h.contents k <> Nil -> len <= length (h.contents k))
1214
end }
1215
= let ghost w = match argmin h h.keys with
1216
| None -> None
1217
| Some n -> Some (n, length (h.contents n), h.contents n)
1218
end in
1219
any option (Node.t, int, list 'a) ensures { result = w }
1220
1221
clone colibrilib.bdd.NodeH {… begin (* cloned colibrilib.bdd.NodeH *) end } with
1222
type t'a = t 'a, val create = create, val add_cons = add_cons,
1223
val fold_min = fold_min
1224
end