def bal.lo

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

import Base
import bend-mathlib@0.7.4.0/bool.bend as MBool
import bend-kit-collections@0.1.4.1/LAWS.bend as Laws
import bend-kit-collections@0.1.4.1/omap.bend as O
import bend-kit-collections@0.1.4.1/nat_order.bend as Ord

1555# lo became lo2, one lighter or heavier at most: rebalance the node.
1556def bal.lo(
1557  -K: Data, -V: Data, +k: K, +v: V, +lo: O.OMap<K, V>, +lo2: O.OMap<K, V>, +hi: O.OMap<K, V>,
1558  +ok: {Laws.weight_ok(W(K, V, lo), W(K, V, hi)) == True{} : Bool},
1559  wbh: {WB(K, V, hi) == True{} : Bool},
1560  +pw: {PW(K, V, W(K, V, lo), lo2) == True{} : Bool}
1561) -> {PW(K, V, Nat.add(W(K, V, lo), W(K, V, hi)), Laws.g_balance(K, V, k, v, lo2, hi)) == True{} : Bool}:
1562  +a = W(K, V, lo)
1563  +a2 = W(K, V, lo2)
1564  +c = W(K, V, hi)
1565  +nr = MBool.eq_true_of_and_right(WB(K, V, lo2), Ord.near(a, a2), pw)
1566  +n1 = MBool.eq_true_of_and_left(Nat.is_le(a, 1n+a2), Nat.is_le(a2, 1n+a), nr)
1567  +n2 = MBool.eq_true_of_and_right(Nat.is_le(a, 1n+a2), Nat.is_le(a2, 1n+a), nr)
1568  MBool.and_eq_true(WB(K, V, Laws.g_balance(K, V, k, v, lo2, hi)), Ord.near(Nat.add(a, c), W(K, V, Laws.g_balance(K, V, k, v, lo2, hi))), bal.wb(K, V, k, v, lo2, hi, MBool.eq_true_of_and_left(WB(K, V, lo2), Ord.near(a, a2), pw), wbh,
1569      Ord.almlo.w0(a, c, a2, Ord.wok_l(a, c, ok), Ord.wok_r(a, c, ok), n1, n2)), bal.lo.near(K, V, k, v, lo, lo2, hi, n1, n2))