Common — library colibrilib.product — module PT

The maps of colibri2 (Node.PT, Patricia trees) from the atoms to the exponents. Trusted: the specification of polynome.PT with other values, given by the sorted list of the bindings

477
module PT
478
use int.Int
479
use list.List
480
use mach.int.Int63
481
use list.Length
482
use option.Option
483
use colibrilib.ring.Atom
484
use colibrilib.stdq.StdQ as Q
485
use QAssoc
486
487
type
t
488
489
function
bindings
(m:t) : list binding
490
491
axiom
bindings_sorted
: forall m. sorted (bindings m)
492
493
function
get
(k:Atom.t) (m:t) : option Q.t = assoc k (bindings m)
494
495
val
empty
() : t
496
ensures { bindings result = Nil }
497
498
val
is_empty
(m:t) : bool
499
ensures { result <-> bindings m = Nil }
500
501
val
singleton
(k:Atom.t) (v:Q.t) : t
502
ensures { bindings result = Cons (k, v) Nil }
503
504
val
find_opt
(k:Atom.t) (m:t) : option Q.t
505
ensures { result = get k m }
506
507
val
remove
(k:Atom.t) (m:t) : t
508
ensures { forall k'. get k' result = if k' = k then None else get k' m }
509
510
val partial
cardinal
(m:t) : int63
511
ensures { to_int result = length (bindings m) }

a binding of m, chosen at random (Shuffle.chooseb)

514
val
choose
(m:t) : (Atom.t, Q.t)
515
requires { bindings m <> Nil }
516
returns { (k, v) -> get k m = Some v }

Node.PT.slow_merge

519
val
merge
(f: Atom.t -> option Q.t -> option Q.t -> option Q.t) (m1 m2:t) : t
520
requires { forall k. f k None None = None }
521
ensures { forall k. get k result = f k (get k m1) (get k m2) }
522
523
val
map
(f: Q.t -> Q.t) (m:t) : t
524
ensures { forall k. get k result = match get k m with
525
| None -> None | Some v -> Some (f v) end }
526
527
val
filter
(f: Atom.t -> bool) (m:t) : t
528
ensures { forall k. get k result = if f k then get k m else None }

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

532
val
to_list
(m:t) : list binding
533
ensures { result = bindings m }
534
end