library colibrilib.product — module PTThe 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
module PT477use int.Int478use list.List479use mach.int.Int63480use list.Length481use option.Option482use colibrilib.ring.Atom483use colibrilib.stdq.StdQ as Q484use QAssoc485486type t487488function bindings (m:t) : list binding489490axiom bindings_sorted: forall m. sorted (bindings m)491492function get (k:Atom.t) (m:t) : option Q.t = assoc k (bindings m)493494val empty () : t495ensures { bindings result = Nil }496497val is_empty (m:t) : bool498ensures { result <-> bindings m = Nil }499500val singleton (k:Atom.t) (v:Q.t) : t501ensures { bindings result = Cons (k, v) Nil }502503val find_opt (k:Atom.t) (m:t) : option Q.t504ensures { result = get k m }505506val remove (k:Atom.t) (m:t) : t507ensures { forall k'. get k' result = if k' = k then None else get k' m }508509val partial cardinal (m:t) : int63510ensures { to_int result = length (bindings m) }511
a binding of m, chosen at random (Shuffle.chooseb)
val choose (m:t) : (Atom.t, Q.t)514requires { bindings m <> Nil }515returns { (k, v) -> get k m = Some v }516
Node.PT.slow_merge
val merge (f: Atom.t -> option Q.t -> option Q.t -> option Q.t) (m1 m2:t) : t519requires { forall k. f k None None = None }520ensures { forall k. get k result = f k (get k m1) (get k m2) }521522val map (f: Q.t -> Q.t) (m:t) : t523ensures { forall k. get k result = match get k m with524| None -> None | Some v -> Some (f v) end }525526val filter (f: Atom.t -> bool) (m:t) : t527ensures { forall k. get k result = if f k then get k m else None }528
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 binding532ensures { result = bindings m }533end534