def balance.bnd

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

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

487def balance.bnd(
488  ~K: Data, ~V: Data, ~cmp: K -> K -> Cmp, ~trans: Trans(~K, ~cmp),
489  +lb: Maybe<&2, K>, +ub: Maybe<&2, K>, +k: K, +v: V, +lo: O.OMap<K, V>,
490  +hi: O.OMap<K, V>,
491  ea: {Laws.above(~K, ~cmp, lb, k) == True{} : Bool},
492  eb: {Laws.below(~K, ~cmp, ub, k) == True{} : Bool},
493  el: {Laws.bounded(~K, ~V, ~cmp, lo, lb, Some{k}) == True{} : Bool},
494  eh: {Laws.bounded(~K, ~V, ~cmp, hi, Some{k}, ub) == True{} : Bool}
495) -> {Laws.bounded(~K, ~V, ~cmp, O.OMap.balance(K, V, k, v, lo, hi), lb, ub) == True{} : Bool}:
496  +wl = (O.OMap.size(K, V, lo) + 1 : U32)
497  +wh = (O.OMap.size(K, V, hi) + 1 : U32)
498  balance.if.bnd(~K, ~V, ~cmp, ~trans, U32.is_gt(wh, (3 * wl : U32)),
499    U32.is_gt(wl, (3 * wh : U32)), lb, ub, k, v, lo, hi, ea, eb, el, eh)