Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_as_eq_of_ge_stop (Algdata/Data/BinaryHeap/Basic.lean)

State before:
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
h : heapifyDown.OpSpec lt x i y
k : Nat
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ y.as[k] = x.as[k]
Tactic:
induction h <;> try rfl
State after:
case node_next_left
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
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✝ :
  ∀ {hk : k < Array.size y✝.as},
    k ≥ (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).stop →
      y✝.as[k] = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).as[k]
hk : k < Array.size y✝.as
hge : k ≥ x✝.stop
⊢ y✝.as[k] = x✝.as[k]

case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
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✝ :
  ∀ {hk : k < Array.size y✝.as},
    k ≥ (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).stop →
      y✝.as[k] = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }).as[k]
hk : k < Array.size y✝.as
hge : k ≥ x✝.stop
⊢ y✝.as[k] = x✝.as[k]

case node_odd_next
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
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
hk : k < Array.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).as
hge : k ≥ x✝.stop
⊢ (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }).as[k] = x✝.as[k]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ y.as[k] = x.as[k]
Tactic:
case node_next_left x i y hi hl hr hx' hx _ IH =>
  rewrite [@IH hk hge]
  apply Array.getElem_swap_ne <;> (dsimp; intro h; cases h)
  all_goals exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ y.as[k] = x.as[k]
Tactic:
case node_next_right x i y hi hl hr hx' hx _ IH =>
  rewrite [@IH hk hge]
  apply Array.getElem_swap_ne <;> (dsimp; intro h; cases h)
  all_goals exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k] = x.as[k]
Tactic:
case node_odd_next x i hi hl _ _ =>
  apply Array.getElem_swap_ne <;> (dsimp; intro h; cases h)
  all_goals exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
State after:
no goals

State before:
case leaf
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
x✝ : Subarray α
i✝ : Nat
a✝ : 2 * i✝ + 1 ≥ Subarray.size x✝
hk : k < Array.size x✝.as
hge : k ≥ x✝.stop
⊢ x✝.as[k] = x✝.as[k]
Tactic:
rfl
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ y.as[k] = x.as[k]
Tactic:
rewrite [@IH hk hge]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k] = x.as[k]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k] = x.as[k]
Tactic:
apply Array.getElem_swap_ne <;> (dsimp; intro h; cases h)
State after:
case hik.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : ↑(Subarray.castIndex x { val := i, isLt := hi }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[↑(Subarray.castIndex x { val := i, isLt := hi })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 1, isLt := hl }).as[↑(Subarray.castIndex x { val := i, isLt := hi })]
hk : ↑(Subarray.castIndex x { val := i, isLt := hi }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥ x.stop
⊢ False

case hjk.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 1, isLt := hl }).as[↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl })]
hk : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False

State before:
case hik.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : ↑(Subarray.castIndex x { val := i, isLt := hi }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[↑(Subarray.castIndex x { val := i, isLt := hi })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 1, isLt := hl }).as[↑(Subarray.castIndex x { val := i, isLt := hi })]
hk : ↑(Subarray.castIndex x { val := i, isLt := hi }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥ x.stop
⊢ False

case hjk.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 1, isLt := hl }).as[↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl })]
hk : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False
Tactic:
all_goals exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
State after:
no goals

State before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≠ k
Tactic:
dsimp
State after:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ ¬↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k

State before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ ¬↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k
Tactic:
intro h
State after:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
h : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k
⊢ False

State before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
h : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k
⊢ False
Tactic:
cases h
State after:
case hjk.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 1, isLt := hl }).as[↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl })]
hk : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False

State before:
case hjk.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : 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
IH :
  ∀ {hk : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).stop →
      y.as[↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 1, isLt := hl }).as[↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl })]
hk : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False
Tactic:
exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ y.as[k] = x.as[k]
Tactic:
rewrite [@IH hk hge]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k] = x.as[k]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k] = x.as[k]
Tactic:
apply Array.getElem_swap_ne <;> (dsimp; intro h; cases h)
State after:
case hik.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : ↑(Subarray.castIndex x { val := i, isLt := hi }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[↑(Subarray.castIndex x { val := i, isLt := hi })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 2, isLt := hr }).as[↑(Subarray.castIndex x { val := i, isLt := hi })]
hk : ↑(Subarray.castIndex x { val := i, isLt := hi }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥ x.stop
⊢ False

case hjk.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 2, isLt := hr }).as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })]
hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥ x.stop
⊢ False

State before:
case hik.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : ↑(Subarray.castIndex x { val := i, isLt := hi }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[↑(Subarray.castIndex x { val := i, isLt := hi })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 2, isLt := hr }).as[↑(Subarray.castIndex x { val := i, isLt := hi })]
hk : ↑(Subarray.castIndex x { val := i, isLt := hi }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥ x.stop
⊢ False

case hjk.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 2, isLt := hr }).as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })]
hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥ x.stop
⊢ False
Tactic:
all_goals exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
State after:
no goals

State before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≠ k
Tactic:
dsimp
State after:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ ¬↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) = k

State before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
⊢ ¬↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) = k
Tactic:
intro h
State after:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
h : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) = k
⊢ False

State before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
h : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) = k
⊢ False
Tactic:
cases h
State after:
case hjk.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 2, isLt := hr }).as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })]
hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥ x.stop
⊢ False

State before:
case hjk.refl
α : 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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : 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 :
  ∀ {hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 2, isLt := hr }).as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })]
hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥ x.stop
⊢ False
Tactic:
exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k] = x.as[k]
Tactic:
apply Array.getElem_swap_ne <;> (dsimp; intro h; cases h)
State after:
case hik.refl
α : 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
hk :
  ↑(Subarray.castIndex x { val := i, isLt := hi }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥ x.stop
⊢ False

case hjk.refl
α : 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
hk :
  ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False

State before:
case hik.refl
α : 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
hk :
  ↑(Subarray.castIndex x { val := i, isLt := hi }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥ x.stop
⊢ False

case hjk.refl
α : 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
hk :
  ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False
Tactic:
all_goals exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
State after:
no goals

State before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
⊢ ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≠ k
Tactic:
dsimp
State after:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
⊢ ¬↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k

State before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
⊢ ¬↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k
Tactic:
intro h
State after:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
h : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k
⊢ False

State before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
h : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k
⊢ False
Tactic:
cases h
State after:
case hjk.refl
α : 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
hk :
  ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False

State before:
case hjk.refl
α : 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
hk :
  ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False
Tactic:
exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
State after:
no goals