def bs.above

bend-osdev-algo@0.1.0.0 · PROOF.bend:1135

import Base
import bend-osdev-algo@0.1.0.0/bsearch.bend as S

1135def bs.above(xs: List<&2, U32>, +key: U32, i: Nat, +x: U32, s: {S.bsearch.sorted(xs) == True{} : Bool}, e: {List.get(&2, U32, xs, i) == Some{x} : Maybe<&2, U32>}, l: {Nat.is_le(S.bsearch.lower_bound(xs, key), i) == True{} : Bool}) -> {U32.is_lt(x, key) == False{} : Bool}:
1136  match xs i:
1137    case Nil{} _:
1138      Empty.absurd({U32.is_lt(x, key) == False{} : Bool}, absurd.ns32(x, e))
1139    case Con{+x0, t} 0n:
1140      %some_inj32(x0, x, e) : {U32.is_lt(_, key) == False{} : Bool}
1141      bs.above0(U32.is_lt(x0, key), S.bsearch.lower_bound(t, key), l)
1142    case Con{+x0, +t} 1n+ +ip:
1143      +s2 = s
1144      +e2 = e
1145      bs.above1(U32.is_lt(x0, key), x0, x, key, {==}, S.bsearch.lower_bound(t, key), ip, l, h => bs.above(t, key, ip, x, bs.sorted_tail(t, x0, s2), e2, h), bs.head_le(t, x0, s2, ip, x, e2))