Common — library colibrilib.polynome — module PT

The maps of colibri2 (Node.PT, Patricia trees) from the atoms to the coefficients. Trusted: a map is modelled by the sorted list of its bindings (for the order lt of the atoms, whatever the order of the tree), and each operation by its effect on the bindings.

254
module PT
255
use int.Int
256
use list.List
257
use list.Length
258
use option.Option
259
use colibrilib.ring.Atom
260
use colibrilib.stda.StdA as A
261
use Assoc
262
263
type
t
264
265
function
bindings
(m:t) : list binding
266
267
axiom
bindings_sorted
: forall m. sorted (bindings m)
268
269
function
get
(k:Atom.t) (m:t) : option A.t = assoc k (bindings m)
270
271
val
empty
() : t
272
ensures { bindings result = Nil }
273
274
val
is_empty
(m:t) : bool
275
ensures { result <-> bindings m = Nil }
276
277
val
singleton
(k:Atom.t) (v:A.t) : t
278
ensures { bindings result = Cons (k, v) Nil }
279
280
val
find_opt
(k:Atom.t) (m:t) : option A.t
281
ensures { result = get k m }
282
283
val
remove
(k:Atom.t) (m:t) : t
284
ensures { forall k'. get k' result = if k' = k then None else get k' m }
285
286
val
cardinal
(m:t) : int
287
ensures { result = length (bindings m) }

Node.PT.to_list: in the increasing unsigned order of the tags, which is Node.compare since the tags are not negative (bindings_sorted)

291
val
to_list
(m:t) : list binding
292
ensures { result = bindings m }

a binding of m: the pivot, chosen by the solver (in Colibri2 the greatest atom, the product nodes being above the other nodes)

296
val
pivot_binding
(m:t) : (Atom.t, A.t)
297
requires { bindings m <> Nil }
298
returns { (k, v) -> get k m = Some v }

a binding of m (the first one of the tree)

301
val
min_binding
(m:t) : (Atom.t, A.t)
302
requires { bindings m <> Nil }
303
returns { (k, v) -> get k m = Some v }

Node.PT.slow_merge

306
val
merge
(f: Atom.t -> option A.t -> option A.t -> option A.t) (m1 m2:t) : t
307
requires { forall k. f k None None = None }
308
ensures { forall k. get k result = f k (get k m1) (get k m2) }

Node.PT.update

311
val
update
(k:Atom.t) (f: option A.t -> option A.t) (m:t) : t
312
ensures { forall k'. get k' result = if k' = k then f (get k m) else get k' m }
313
314
val
map
(f: A.t -> A.t) (m:t) : t
315
ensures { forall k. get k result = match get k m with
316
| None -> None | Some v -> Some (f v) end }
317
end