def bs.none

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

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

1200def bs.none(xs: List<&2, U32>, +key: U32, i: Nat, +x: U32, s: {S.bsearch.sorted(xs) == True{} : Bool}, e: {S.bsearch.find(xs, key) == None{} : Maybe<&2, Nat>}, g: {List.get(&2, U32, xs, i) == Some{x} : Maybe<&2, U32>}) -> {U32.is_eq(x, key) == False{} : Bool}:
1201  match xs i:
1202    case Nil{} _:
1203      Empty.absurd({U32.is_eq(x, key) == False{} : Bool}, absurd.ns32(x, g))
1204    case Con{+x0, +t} 0n:
1205      %some_inj32(x0, x, g) : {U32.is_eq(_, key) == False{} : Bool}
1206      bs.none0(U32.is_lt(x0, key), x0, key, {==}, t, S.bsearch.lower_bound(t, key), e)
1207    case Con{+x0, +t} 1n+ +ip:
1208      +s2 = s
1209      +g2 = g
1210      bs.none1(U32.is_lt(x0, key), x0, x, key, {==}, t, S.bsearch.lower_bound(t, key), e, h => bs.none(t, key, ip, x, bs.sorted_tail(t, x0, s2), h, g2), bs.head_le(t, x0, s2, ip, x, g2))