library colibrilib.polynome — module PTThe 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.
module PT254use int.Int255use list.List256use list.Length257use option.Option258use colibrilib.ring.Atom259use colibrilib.stda.StdA as A260use Assoc261262type t263264function bindings (m:t) : list binding265266axiom bindings_sorted: forall m. sorted (bindings m)267268function get (k:Atom.t) (m:t) : option A.t = assoc k (bindings m)269270val empty () : t271ensures { bindings result = Nil }272273val is_empty (m:t) : bool274ensures { result <-> bindings m = Nil }275276val singleton (k:Atom.t) (v:A.t) : t277ensures { bindings result = Cons (k, v) Nil }278279val find_opt (k:Atom.t) (m:t) : option A.t280ensures { result = get k m }281282val remove (k:Atom.t) (m:t) : t283ensures { forall k'. get k' result = if k' = k then None else get k' m }284285val cardinal (m:t) : int286ensures { result = length (bindings m) }287
Node.PT.to_list: in the increasing unsigned order of the tags, which is Node.compare since the tags are not negative (bindings_sorted)
val to_list (m:t) : list binding291ensures { result = bindings m }292
a binding of m: the pivot, chosen by the solver (in Colibri2 the greatest atom, the product nodes being above the other nodes)
val pivot_binding (m:t) : (Atom.t, A.t)296requires { bindings m <> Nil }297returns { (k, v) -> get k m = Some v }298
a binding of m (the first one of the tree)
val min_binding (m:t) : (Atom.t, A.t)301requires { bindings m <> Nil }302returns { (k, v) -> get k m = Some v }303
Node.PT.slow_merge
val merge (f: Atom.t -> option A.t -> option A.t -> option A.t) (m1 m2:t) : t306requires { forall k. f k None None = None }307ensures { forall k. get k result = f k (get k m1) (get k m2) }308
Node.PT.update
val update (k:Atom.t) (f: option A.t -> option A.t) (m:t) : t311ensures { forall k'. get k' result = if k' = k then f (get k m) else get k' m }312313val map (f: A.t -> A.t) (m:t) : t314ensures { forall k. get k result = match get k m with315| None -> None | Some v -> Some (f v) end }316end317