def put.bnd

bend-kit-collections@0.1.4.1 · PROOF.bend:517

import Base
import bend-kit-collections@0.1.4.1/LAWS.bend as Laws
import bend-kit-collections@0.1.4.1/omap.bend as O

517def put.bnd(
518  ~K: Data, ~V: Data, ~cmp: K -> K -> Cmp, ~flip: Flip(~K, ~cmp),
519  ~trans: Trans(~K, ~cmp), t: O.OMap<K, V>, +lb: Maybe<&2, K>,
520  +ub: Maybe<&2, K>, +k: K, +v: V,
521  +bt: {Laws.bounded(~K, ~V, ~cmp, t, lb, ub) == True{} : Bool},
522  +ea: {Laws.above(~K, ~cmp, lb, k) == True{} : Bool},
523  +eb: {Laws.below(~K, ~cmp, ub, k) == True{} : Bool}
524) -> {Laws.bounded(~K, ~V, ~cmp, O.OMap.put(~K, ~V, ~cmp, t, k, v), lb, ub) == True{} : Bool}:
525  match t:
526    case O.OTip{}:
527      bn.i(~K, ~V, ~cmp, lb, ub, k, v, O.OTip{}, O.OTip{}, ea, eb, {==}, {==})
528    case O.OBin{+s, +key, +val, +lo, +hi}:
529      +b_a = bn.a(~K, ~V, ~cmp, lb, ub, key, val, lo, hi, bt)
530      +b_b = bn.b(~K, ~V, ~cmp, lb, ub, key, val, lo, hi, bt)
531      +b_l = bn.l(~K, ~V, ~cmp, lb, ub, key, val, lo, hi, bt)
532      +b_h = bn.h(~K, ~V, ~cmp, lb, ub, key, val, lo, hi, bt)
533      cmp.split(O.OMap<K, V>, Bool, x => Laws.bounded(~K, ~V, ~cmp, x, lb, ub), True{},
534        cmp(k, key),
535        u => O.OMap.balance(K, V, key, val, O.OMap.put(~K, ~V, ~cmp, lo, k, v), hi),
536        u => O.OBin{s, key, v, lo, hi},
537        u => O.OMap.balance(K, V, key, val, lo, O.OMap.put(~K, ~V, ~cmp, hi, k, v)),
538        e => balance.bnd(~K, ~V, ~cmp, ~trans, lb, ub, key, val,
539          O.OMap.put(~K, ~V, ~cmp, lo, k, v), hi, b_a, b_b,
540          put.bnd(~K, ~V, ~cmp, ~flip, ~trans, lo, lb, Some{key}, k, v, b_l, ea,
541            lt_true(cmp(k, key), e)),
542          b_h),
543        e => bt,
544        e => balance.bnd(~K, ~V, ~cmp, ~trans, lb, ub, key, val, lo,
545          O.OMap.put(~K, ~V, ~cmp, hi, k, v), b_a, b_b, b_l,
546          put.bnd(~K, ~V, ~cmp, ~flip, ~trans, hi, Some{key}, ub, k, v, b_h,
547            lt_true(cmp(key, k), gt_flip(~K, ~cmp, ~flip, k, key, e)), eb)))