internlm/Lean-Github huggingface dataset:
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.to_eq
Proof state before:
case node_odd_next
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 ≥ Subarray.size x
hx : lt x[i] x[2 * i + 1] = true
⊢ Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl } =
    let lhs := 2 * i + 1;
    let rhs := lhs + 1;
    if hr : rhs < Subarray.size x then
      let_fun hi := (_ : i < Subarray.size x);
      let_fun hl := (_ : lhs < Subarray.size x);
      let j := if lt x[rhs] x[lhs] = true then lhs else rhs;
      let_fun hj := (_ : i < j ∧ j < Subarray.size x);
      if lt x[i] x[j] = true then
        let_fun this := (_ : Subarray.size x - j < Subarray.size x - i);
        heapifyDownAux lt (Subarray.swap x { val := i, isLt := hi } { val := j, isLt := (_ : j < Subarray.size x) }) j
      else x
    else
      if hl : lhs < Subarray.size x then
        let_fun hi := (_ : i < Subarray.size x);
        if lt x[i] x[lhs] = true then Subarray.swap x { val := i, isLt := hi } { val := lhs, isLt := hl } else x
      else x
Tactic:
simp only [dif_neg (Nat.not_lt_of_le hr), dif_pos hl, if_pos hx]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.to_eq
Proof state before:
case node_odd_end
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 ≥ Subarray.size x
hx : lt x[i] x[2 * i + 1] = false
⊢ x = heapifyDown lt x i
Tactic:
unfold heapifyDown heapifyDownAux
Proof state after:
case node_odd_end
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 ≥ Subarray.size x
hx : lt x[i] x[2 * i + 1] = false
⊢ x =
    let lhs := 2 * i + 1;
    let rhs := lhs + 1;
    if hr : rhs < Subarray.size x then
      let_fun hi := (_ : i < Subarray.size x);
      let_fun hl := (_ : lhs < Subarray.size x);
      let j := if lt x[rhs] x[lhs] = true then lhs else rhs;
      let_fun hj := (_ : i < j ∧ j < Subarray.size x);
      if lt x[i] x[j] = true then
        let_fun this := (_ : Subarray.size x - j < Subarray.size x - i);
        heapifyDownAux lt (Subarray.swap x { val := i, isLt := hi } { val := j, isLt := (_ : j < Subarray.size x) }) j
      else x
    else
      if hl : lhs < Subarray.size x then
        let_fun hi := (_ : i < Subarray.size x);
        if lt x[i] x[lhs] = true then Subarray.swap x { val := i, isLt := hi } { val := lhs, isLt := hl } else x
      else x
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.to_eq
Proof state before:
case node_odd_end
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 ≥ Subarray.size x
hx : lt x[i] x[2 * i + 1] = false
⊢ x =
    let lhs := 2 * i + 1;
    let rhs := lhs + 1;
    if hr : rhs < Subarray.size x then
      let_fun hi := (_ : i < Subarray.size x);
      let_fun hl := (_ : lhs < Subarray.size x);
      let j := if lt x[rhs] x[lhs] = true then lhs else rhs;
      let_fun hj := (_ : i < j ∧ j < Subarray.size x);
      if lt x[i] x[j] = true then
        let_fun this := (_ : Subarray.size x - j < Subarray.size x - i);
        heapifyDownAux lt (Subarray.swap x { val := i, isLt := hi } { val := j, isLt := (_ : j < Subarray.size x) }) j
      else x
    else
      if hl : lhs < Subarray.size x then
        let_fun hi := (_ : i < Subarray.size x);
        if lt x[i] x[lhs] = true then Subarray.swap x { val := i, isLt := hi } { val := lhs, isLt := hl } else x
      else x
Tactic:
simp only [dif_neg (Nat.not_lt_of_le hr), dif_pos hl, if_neg (Bool.eq_false_iff.mp hx)]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.to_eq
Proof state before:
case leaf
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hl : 2 * i + 1 ≥ Subarray.size x
⊢ x = heapifyDown lt x i
Tactic:
have hr : 2*i+2 ≥ x.size := .step hl
Proof state after:
case leaf
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hl : 2 * i + 1 ≥ Subarray.size x
hr : 2 * i + 2 ≥ Subarray.size x
⊢ x = heapifyDown lt x i
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.to_eq
Proof state before:
case leaf
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hl : 2 * i + 1 ≥ Subarray.size x
hr : 2 * i + 2 ≥ Subarray.size x
⊢ x = heapifyDown lt x i
Tactic:
unfold heapifyDown heapifyDownAux
Proof state after:
case leaf
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hl : 2 * i + 1 ≥ Subarray.size x
hr : 2 * i + 2 ≥ Subarray.size x
⊢ x =
    let lhs := 2 * i + 1;
    let rhs := lhs + 1;
    if hr : rhs < Subarray.size x then
      let_fun hi := (_ : i < Subarray.size x);
      let_fun hl := (_ : lhs < Subarray.size x);
      let j := if lt x[rhs] x[lhs] = true then lhs else rhs;
      let_fun hj := (_ : i < j ∧ j < Subarray.size x);
      if lt x[i] x[j] = true then
        let_fun this := (_ : Subarray.size x - j < Subarray.size x - i);
        heapifyDownAux lt (Subarray.swap x { val := i, isLt := hi } { val := j, isLt := (_ : j < Subarray.size x) }) j
      else x
    else
      if hl : lhs < Subarray.size x then
        let_fun hi := (_ : i < Subarray.size x);
        if lt x[i] x[lhs] = true then Subarray.swap x { val := i, isLt := hi } { val := lhs, isLt := hl } else x
      else x
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.to_eq
Proof state before:
case leaf
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hl : 2 * i + 1 ≥ Subarray.size x
hr : 2 * i + 2 ≥ Subarray.size x
⊢ x =
    let lhs := 2 * i + 1;
    let rhs := lhs + 1;
    if hr : rhs < Subarray.size x then
      let_fun hi := (_ : i < Subarray.size x);
      let_fun hl := (_ : lhs < Subarray.size x);
      let j := if lt x[rhs] x[lhs] = true then lhs else rhs;
      let_fun hj := (_ : i < j ∧ j < Subarray.size x);
      if lt x[i] x[j] = true then
        let_fun this := (_ : Subarray.size x - j < Subarray.size x - i);
        heapifyDownAux lt (Subarray.swap x { val := i, isLt := hi } { val := j, isLt := (_ : j < Subarray.size x) }) j
      else x
    else
      if hl : lhs < Subarray.size x then
        let_fun hi := (_ : i < Subarray.size x);
        if lt x[i] x[lhs] = true then Subarray.swap x { val := i, isLt := hi } { val := lhs, isLt := hl } else x
      else x
Tactic:
simp only [dif_neg (Nat.not_lt_of_le hr), dif_neg (Nat.not_lt_of_le hl)]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.size_as_eq
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
h : heapifyDown.OpSpec lt x i y
⊢ Array.size y.as = Array.size x.as
Tactic:
induction h <;> try rfl
Proof state after:
case node_next_left
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = true
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }) (2 * i✝ + 1) y✝
a_ih✝ :
  Array.size y✝.as = Array.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).as
⊢ Array.size y✝.as = Array.size x✝.as

case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ :
  Array.size y✝.as = Array.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).as
⊢ Array.size y✝.as = Array.size x✝.as

case node_odd_next
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
a✝¹ : 2 * i✝ + 2 ≥ Subarray.size x✝
a✝ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
⊢ Array.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).as = Array.size x✝.as
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.size_as_eq
Proof state before:
case node_next_left
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = true
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }) (2 * i✝ + 1) y✝
a_ih✝ :
  Array.size y✝.as = Array.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).as
⊢ Array.size y✝.as = Array.size x✝.as

case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ :
  Array.size y✝.as = Array.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).as
⊢ Array.size y✝.as = Array.size x✝.as

case node_odd_next
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
a✝¹ : 2 * i✝ + 2 ≥ Subarray.size x✝
a✝ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
⊢ Array.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).as = Array.size x✝.as
Tactic:
all_goals simp only [Subarray.size_as_swap] at *
Proof state after:
case node_next_left
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = true
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }) (2 * i✝ + 1) y✝
a_ih✝ : Array.size y✝.as = Array.size x✝.as
⊢ Array.size y✝.as = Array.size x✝.as

case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ : Array.size y✝.as = Array.size x✝.as
⊢ Array.size y✝.as = Array.size x✝.as
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.size_as_eq
Proof state before:
case node_next_left
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = true
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }) (2 * i✝ + 1) y✝
a_ih✝ : Array.size y✝.as = Array.size x✝.as
⊢ Array.size y✝.as = Array.size x✝.as

case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ : Array.size y✝.as = Array.size x✝.as
⊢ Array.size y✝.as = Array.size x✝.as
Tactic:
all_goals assumption
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.size_as_eq
Proof state before:
case leaf
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
a✝ : 2 * i✝ + 1 ≥ Subarray.size x✝
⊢ Array.size x✝.as = Array.size x✝.as
Tactic:
rfl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.size_as_eq
Proof state before:
case node_odd_next
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
a✝¹ : 2 * i✝ + 2 ≥ Subarray.size x✝
a✝ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
⊢ Array.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).as = Array.size x✝.as
Tactic:
simp only [Subarray.size_as_swap] at *
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.size_as_eq
Proof state before:
case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ : Array.size y✝.as = Array.size x✝.as
⊢ Array.size y✝.as = Array.size x✝.as
Tactic:
assumption
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.start_eq
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
h : heapifyDown.OpSpec lt x i y
⊢ y.start = x.start
Tactic:
induction h <;> try rfl
Proof state after:
case node_next_left
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = true
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }) (2 * i✝ + 1) y✝
a_ih✝ : y✝.start = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).start
⊢ y✝.start = x✝.start

case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ : y✝.start = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).start
⊢ y✝.start = x✝.start
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.start_eq
Proof state before:
case node_next_left
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = true
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }) (2 * i✝ + 1) y✝
a_ih✝ : y✝.start = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).start
⊢ y✝.start = x✝.start

case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ : y✝.start = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).start
⊢ y✝.start = x✝.start
Tactic:
all_goals next IH => simp only [IH, Subarray.start_swap]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.start_eq
Proof state before:
case leaf
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
a✝ : 2 * i✝ + 1 ≥ Subarray.size x✝
⊢ x✝.start = x✝.start
Tactic:
rfl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.start_eq
Proof state before:
case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ : y✝.start = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).start
⊢ y✝.start = x✝.start
Tactic:
next IH => simp only [IH, Subarray.start_swap]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.start_eq
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
IH : y✝.start = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).start
⊢ y✝.start = x✝.start
Tactic:
simp only [IH, Subarray.start_swap]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.stop_eq
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
h : heapifyDown.OpSpec lt x i y
⊢ y.stop = x.stop
Tactic:
induction h <;> try rfl
Proof state after:
case node_next_left
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = true
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }) (2 * i✝ + 1) y✝
a_ih✝ : y✝.stop = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).stop
⊢ y✝.stop = x✝.stop

case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ : y✝.stop = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).stop
⊢ y✝.stop = x✝.stop
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.stop_eq
Proof state before:
case node_next_left
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = true
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }) (2 * i✝ + 1) y✝
a_ih✝ : y✝.stop = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).stop
⊢ y✝.stop = x✝.stop

case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ : y✝.stop = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).stop
⊢ y✝.stop = x✝.stop
Tactic:
all_goals next IH => simp only [IH, Subarray.stop_swap]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.stop_eq
Proof state before:
case leaf
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
a✝ : 2 * i✝ + 1 ≥ Subarray.size x✝
⊢ x✝.stop = x✝.stop
Tactic:
rfl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.stop_eq
Proof state before:
case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ : y✝.stop = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).stop
⊢ y✝.stop = x✝.stop
Tactic:
next IH => simp only [IH, Subarray.stop_swap]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.stop_eq
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
IH : y✝.stop = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).stop
⊢ y✝.stop = x✝.stop
Tactic:
simp only [IH, Subarray.stop_swap]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.size_eq
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
h : heapifyDown.OpSpec lt x i y
⊢ Subarray.size y = Subarray.size x
Tactic:
simp only [Subarray.size, h.stop_eq, h.start_eq]
Proof state after:
no goals