~/bend-docscommunity

proofs/containers/binary_heap/steps.bend checks

raw source on the hub · import bend-collections-laws-containers@1.0.0.0/proofs/containers/binary_heap/steps.bend as Steps

21 imports
import Base
import ../../lib/logic.bend as L
import ../../lib/nat.bend as N
import ../../lib/list.bend as LL
import ../../lib/order.bend as O
import ../../lib/u32.bend as U
import ../../lib/array.bend as AR
import ../../../spec/lib/common.bend as SC
import ../../../spec/containers/binary_heap.bend as S
import ../../../src/containers/binary_heap.bend as H
import ../../../src/containers/types/binary_heap.bend as E
import ./idx.bend as IX
import ./u32idx.bend as UX
import ./slots.bend as SL
import ./vals.bend as V
import ./root.bend as RT
import ./state.bend as ST
import ./push.bend as PU
import ./pop.bend as PO
import ./sorted.bend as SO
import ./budget.bend as BG

Definitions

def le_same source · line 53 · raw

@+d:Nat -> {Nat.is_le(d, Nat.add(d, 0n)) == True{} : Bool}

def le_succ_add source · line 57 · raw

@+d:Nat -> {Nat.is_le(1n+d, Nat.add(d, 1n)) == True{} : Bool}

def empty_bridge source · line 63 · raw

@+size:Nat -> @+depth:Nat -> @+hd:{Nat.is_le(depth, 31n) == True{} : Bool} -> @+hs:{Nat.is_le(size, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(depth)) == True{} : Bool} -> {U32.is_eq(U32.from_nat(size), U32.from_nat(0n)) == Nat.is_eq(size, 0n) : Bool}

the empty/nonempty decision the implementation makes, in Nat

def or_true source · line 105 · raw

@b:Bool -> {Bool.or(b, True{}) == True{} : Bool}

def add_le_r source · line 155 · raw

@+a:Nat -> @+b:Nat -> @+c:Nat -> @+h:{Nat.is_le(a, b) == True{} : Bool} -> {Nat.is_le(Nat.add(a, c), Nat.add(b, c)) == True{} : Bool}

def add_succ_l source · line 160 · raw

@+d:Nat -> @+l:Nat -> {Nat.add(1n+d, l) == 1n+Nat.add(d, l) : Nat}

def add_shift source · line 167 · raw

@+d:Nat -> @+l:Nat -> {Nat.add(d, 1n+l) == Nat.add(1n+d, l) : Nat}

def budget_shift source · line 177 · raw

@+d:Nat -> @+l:Nat -> {Nat.is_le(Nat.add(1n+d, l), Nat.add(d, 1n+l)) == True{} : Bool}

def le_add_zero source · line 223 · raw

@+l:Nat -> @+d:Nat -> {Nat.is_le(Nat.add(0n, l), Nat.add(d, l)) == True{} : Bool}

Templates

template pushcost source · line 32 · raw

@-A:Data -> @op:0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Op<A> -> Nat

template StepOK source · line 47 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @sh:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @op:0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Op<A> -> Type

template mk source · line 50 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @-sh:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @-op:0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Op<A> -> @sh2:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @o:0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Obs<A> -> @e1:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/binary_heap.step(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.real(A, sh), op) == (0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.real(A, sh2), o) : Pair(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/binary_heap.Heap<A>, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Obs<A>)} -> @e2:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, sh2) == True{} : Bool} -> @e3:{(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.model(A, cmp, sh2), o) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/containers/binary_heap.step(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.model(A, cmp, sh), op) : Pair(List<&2, A>, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Obs<A>)} -> @e4:{Nat.is_le(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_depth(A, sh2), Nat.add(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_depth(A, sh), pushcost(A, op))) == True{} : Bool} -> StepOK(A, cmp, sh, op)

template length_ok source · line 70 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @+size:Nat -> @+depth:Nat -> @+t:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<Maybe<&2, A>> -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}) == True{} : Bool} -> StepOK(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Length{})

template peek_at source · line 78 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @-o:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/order.Order(A, cmp) -> @+m:Nat -> @+depth:Nat -> @+t:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<Maybe<&2, A>> -> @+root:A -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{1n+m, depth, t}) == True{} : Bool} -> @+h0:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/slots.slot(A, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(Maybe<&2, A>, t), 0n) == Some{root} : Maybe<&2, A>} -> StepOK(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{1n+m, depth, t}, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Peek{})

template peek_some source · line 92 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @-o:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/order.Order(A, cmp) -> @+m:Nat -> @+depth:Nat -> @+t:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<Maybe<&2, A>> -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{1n+m, depth, t}) == True{} : Bool} -> @sig:Sigma<&1, &1, A, v => {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/slots.slot(A, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(Maybe<&2, A>, t), 0n) == Some{v} : Maybe<&2, A>}> -> StepOK(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{1n+m, depth, t}, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Peek{})

template peek_ok source · line 97 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @-o:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/order.Order(A, cmp) -> @size:Nat -> @+depth:Nat -> @+t:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<Maybe<&2, A>> -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}) == True{} : Bool} -> StepOK(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Peek{})

template push_step source · line 114 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @+size:Nat -> @+depth:Nat -> @+t:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<Maybe<&2, A>> -> @+x:A -> @r:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/push.PushOK(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}, x) -> StepOK(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Push{x})

template push_ok source · line 123 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @-o:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/order.Order(A, cmp) -> @+size:Nat -> @+depth:Nat -> @+t:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<Maybe<&2, A>> -> @+x:A -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}) == True{} : Bool} -> @+q:Nat -> @+hq:{Nat.is_le(q, 31n) == True{} : Bool} -> @+hs:{Nat.is_lt(size, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(q)) == True{} : Bool} -> StepOK(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Push{x})

template pop_step source · line 129 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @+size:Nat -> @+depth:Nat -> @+t:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<Maybe<&2, A>> -> @r:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/pop.PopRes(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}) -> StepOK(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Pop{})

template pop_ok source · line 138 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @-o:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/order.Order(A, cmp) -> @+size:Nat -> @+depth:Nat -> @+t:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<Maybe<&2, A>> -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}) == True{} : Bool} -> StepOK(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Pop{})

template sorted_ok source · line 143 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @-o:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/order.Order(A, cmp) -> @+size:Nat -> @+depth:Nat -> @+t:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<Maybe<&2, A>> -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}) == True{} : Bool} -> StepOK(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.ToSortedList{})

template budget_rest source · line 173 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @+y:A -> @+rest:List<&2, A> -> @+sh:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @+sh1:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @+q:Nat -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, sh) == True{} : Bool} -> @+g1:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, sh1) == True{} : Bool} -> @+ems:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.model(A, cmp, sh1) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/containers/binary_heap.ins(A, cmp, y, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.model(A, cmp, sh)) : List<&2, A>} -> @+h:{Nat.is_lt(Nat.add(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_size(A, sh), 1n+0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.length(A, rest)), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(q)) == True{} : Bool} -> {Nat.is_lt(Nat.add(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_size(A, sh1), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.length(A, rest)), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(q)) == True{} : Bool}

the size budget after pushing y onto sh

template FromOK source · line 180 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @ys:List<&2, A> -> @sh:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> Type

template FromRec source · line 183 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @rest:List<&2, A> -> @+q:Nat -> Type

template from_rest source · line 186 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @+y:A -> @+rest:List<&2, A> -> @+sh:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @+sh1:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @+ereal:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/binary_heap.push(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.real(A, sh), y) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.real(A, sh1) : 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/binary_heap.Heap<A>} -> @+ems:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.model(A, cmp, sh1) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/containers/binary_heap.ins(A, cmp, y, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.model(A, cmp, sh)) : List<&2, A>} -> @+edd:{Nat.is_le(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_depth(A, sh1), 1n+0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_depth(A, sh)) == True{} : Bool} -> @r:FromOK(A, cmp, rest, sh1) -> FromOK(A, cmp, y <> rest, sh)

template from_push source · line 203 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @+y:A -> @+rest:List<&2, A> -> @+sh:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, sh) == True{} : Bool} -> @+q:Nat -> @+room:{Nat.is_lt(Nat.add(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_size(A, sh), 1n+0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.length(A, rest)), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(q)) == True{} : Bool} -> @rec:FromRec(A, cmp, rest, q) -> @+sh1:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @+ereal:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/binary_heap.push(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.real(A, sh), y) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.real(A, sh1) : 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/binary_heap.Heap<A>} -> @+g1:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, sh1) == True{} : Bool} -> @+ems:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.model(A, cmp, sh1) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/containers/binary_heap.ins(A, cmp, y, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.model(A, cmp, sh)) : List<&2, A>} -> @+edd:{Nat.is_le(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_depth(A, sh1), 1n+0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_depth(A, sh)) == True{} : Bool} -> FromOK(A, cmp, y <> rest, sh)

template from_cons source · line 207 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @+y:A -> @+rest:List<&2, A> -> @+sh:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, sh) == True{} : Bool} -> @+q:Nat -> @+room:{Nat.is_lt(Nat.add(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_size(A, sh), 1n+0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.length(A, rest)), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(q)) == True{} : Bool} -> @rec:FromRec(A, cmp, rest, q) -> @r:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/push.PushOK(A, cmp, sh, y) -> FromOK(A, cmp, y <> rest, sh)

template from_list_ok source · line 212 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @-o:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/order.Order(A, cmp) -> @ys:List<&2, A> -> @sh:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, sh) == True{} : Bool} -> @+q:Nat -> @+hq:{Nat.is_le(q, 31n) == True{} : Bool} -> @+room:{Nat.is_lt(Nat.add(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_size(A, sh), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.length(A, ys)), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(q)) == True{} : Bool} -> FromOK(A, cmp, ys, sh)

template from_list_step source · line 226 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @+size:Nat -> @+depth:Nat -> @+t:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<Maybe<&2, A>> -> @+ys:List<&2, A> -> @r:FromOK(A, cmp, ys, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.initial(A)) -> StepOK(A, cmp, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Sh{size, depth, t}, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.FromList{ys})

template step_ok source · line 244 · raw

@-A:Data -> @-cmp:(@_:A -> @_:A -> Cmp) -> @-o:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/order.Order(A, cmp) -> @sh:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.Shadow<A> -> @op:0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/types/binary_heap.Op<A> -> @+g:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.good(A, cmp, sh) == True{} : Bool} -> @+q:Nat -> @+hq:{Nat.is_le(q, 31n) == True{} : Bool} -> @+room:{Nat.is_lt(Nat.add(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/binary_heap/state.sh_size(A, sh), pushcost(A, op)), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(q)) == True{} : Bool} -> StepOK(A, cmp, sh, op)