Theorem: Algdata.BinaryHeap.heapSort.Intermed.popMax (Algdata/Data/BinaryHeap/Lemmas.lean)

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
⊢ lt (BinaryHeap.popMax lt x).as[i] (BinaryHeap.popMax lt x)[k] = false
Tactic:
have ⟨k',hk',_ ,h⟩ := exists_get_popMax lt x k (size_popMax lt x ▸ hk)
State after:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h✝ : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
h : (BinaryHeap.popMax lt x)[k] = x[k']
⊢ lt (BinaryHeap.popMax lt x).as[i] (BinaryHeap.popMax lt x)[k] = false

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h✝ : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
h : (BinaryHeap.popMax lt x)[k] = x[k']
⊢ lt (BinaryHeap.popMax lt x).as[i] (BinaryHeap.popMax lt x)[k] = false
Tactic:
rewrite [h]
State after:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h✝ : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
h : (BinaryHeap.popMax lt x)[k] = x[k']
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h✝ : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
h : (BinaryHeap.popMax lt x)[k] = x[k']
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false
Tactic:
clear h
State after:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false
Tactic:
have hrng : x.start < x.stop :=
  trans (x.start.le_add_left k') (Nat.add_lt_of_lt_sub hk')
State after:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false
Tactic:
have hi' : x.stop - 1 ≤ i :=
  stop_popMax lt x hrng ▸ hi.1
State after:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi' : x.stop - 1 ≤ i
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi' : x.stop - 1 ≤ i
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false
Tactic:
cases Nat.lt_or_eq_of_le hi' with
| inl hlt =>
  have hi' : x.stop ≤ i :=
    Nat.sub_add_cancel (trans x.start.zero_le hrng :) ▸ hlt
  rewrite [get_as_popMax_of_ge_stop lt x i hi']
  exact h.bound_above i k' ⟨hi',hi.2⟩ hk'
| inr heq =>
  cases heq
  rewrite [get_as_popMax_stop_sub_one lt x hrng]
  exact h.is_heap.not_lt_of_descendant k' (.root k')
State after:
no goals

State before:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi' : x.stop - 1 ≤ i
hlt : x.stop - 1 < i
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false
Tactic:
have hi' : x.stop ≤ i :=
  Nat.sub_add_cancel (trans x.start.zero_le hrng :) ▸ hlt
State after:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi'✝ : x.stop - 1 ≤ i
hlt : x.stop - 1 < i
hi' : x.stop ≤ i
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false

State before:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi'✝ : x.stop - 1 ≤ i
hlt : x.stop - 1 < i
hi' : x.stop ≤ i
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false
Tactic:
rewrite [get_as_popMax_of_ge_stop lt x i hi']
State after:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi'✝ : x.stop - 1 ≤ i
hlt : x.stop - 1 < i
hi' : x.stop ≤ i
⊢ lt x.as[i] x[k'] = false

State before:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi'✝ : x.stop - 1 ≤ i
hlt : x.stop - 1 < i
hi' : x.stop ≤ i
⊢ lt x.as[i] x[k'] = false
Tactic:
exact h.bound_above i k' ⟨hi',hi.2⟩ hk'
State after:
no goals

State before:
case inr
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i k : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i ∧ i < stop
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi' : x.stop - 1 ≤ i
heq : x.stop - 1 = i
⊢ lt (BinaryHeap.popMax lt x).as[i] x[k'] = false
Tactic:
cases heq
State after:
case inr.refl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
k : Nat
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi : (BinaryHeap.popMax lt x).stop ≤ x.stop - 1 ∧ x.stop - 1 < stop
hi' : x.stop - 1 ≤ x.stop - 1
⊢ lt (BinaryHeap.popMax lt x).as[x.stop - 1] x[k'] = false

State before:
case inr.refl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
k : Nat
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi : (BinaryHeap.popMax lt x).stop ≤ x.stop - 1 ∧ x.stop - 1 < stop
hi' : x.stop - 1 ≤ x.stop - 1
⊢ lt (BinaryHeap.popMax lt x).as[x.stop - 1] x[k'] = false
Tactic:
rewrite [get_as_popMax_stop_sub_one lt x hrng]
State after:
case inr.refl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
k : Nat
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi : (BinaryHeap.popMax lt x).stop ≤ x.stop - 1 ∧ x.stop - 1 < stop
hi' : x.stop - 1 ≤ x.stop - 1
⊢ lt x[0] x[k'] = false

State before:
case inr.refl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
k : Nat
hk : k < Subarray.size (BinaryHeap.popMax lt x)
k' : Nat
hk' : k' < Subarray.size x
left✝ : 0 < k'
hrng : x.start < x.stop
hi : (BinaryHeap.popMax lt x).stop ≤ x.stop - 1 ∧ x.stop - 1 < stop
hi' : x.stop - 1 ≤ x.stop - 1
⊢ lt x[0] x[k'] = false
Tactic:
exact h.is_heap.not_lt_of_descendant k' (.root k')
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i
hij : i < j
hj : j < stop
⊢ lt (BinaryHeap.popMax lt x).as[j] (BinaryHeap.popMax lt x).as[i] = false
Tactic:
cases Nat.lt_or_eq_of_le x.h₁ with
| inl hrng =>
  simp only [stop_popMax lt x hrng] at hi
  have stop_pos : 0 < x.stop :=
    Nat.lt_of_le_of_lt x.start.zero_le hrng
  have : x.stop-1+1 = x.stop :=
    Nat.sub_add_cancel stop_pos
  have hj' : x.stop ≤ j :=
    trans this.symm (trans hi hij :)
  rewrite [get_as_popMax_of_ge_stop lt x j hj']
  cases Nat.lt_or_eq_of_le hi with
  | inl hlti =>
    have : x.stop ≤ i :=
      ‹x.stop-1+1=x.stop› ▸ (hlti : x.stop-1+1 ≤ i)
    rewrite [get_as_popMax_of_ge_stop lt x i this]
    exact h.sorted i j this hij hj
  | inr heqi =>
    cases heqi
    rewrite [get_as_popMax_stop_sub_one lt x hrng]
    exact h.bound_above j 0 ⟨hj',hj⟩ _
| inr hz =>
  simp only [popMax_empty lt x hz] at hi ⊢
  exact h.sorted i j hi hij hj
State after:
no goals

State before:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i
hij : i < j
hj : j < stop
hrng : x.start < x.stop
⊢ lt (BinaryHeap.popMax lt x).as[j] (BinaryHeap.popMax lt x).as[i] = false
Tactic:
simp only [stop_popMax lt x hrng] at hi
State after:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
⊢ lt (BinaryHeap.popMax lt x).as[j] (BinaryHeap.popMax lt x).as[i] = false

State before:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
⊢ lt (BinaryHeap.popMax lt x).as[j] (BinaryHeap.popMax lt x).as[i] = false
Tactic:
have stop_pos : 0 < x.stop :=
  Nat.lt_of_le_of_lt x.start.zero_le hrng
State after:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
⊢ lt (BinaryHeap.popMax lt x).as[j] (BinaryHeap.popMax lt x).as[i] = false

State before:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
⊢ lt (BinaryHeap.popMax lt x).as[j] (BinaryHeap.popMax lt x).as[i] = false
Tactic:
have : x.stop-1+1 = x.stop :=
  Nat.sub_add_cancel stop_pos
State after:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
⊢ lt (BinaryHeap.popMax lt x).as[j] (BinaryHeap.popMax lt x).as[i] = false

State before:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
⊢ lt (BinaryHeap.popMax lt x).as[j] (BinaryHeap.popMax lt x).as[i] = false
Tactic:
have hj' : x.stop ≤ j :=
  trans this.symm (trans hi hij :)
State after:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
⊢ lt (BinaryHeap.popMax lt x).as[j] (BinaryHeap.popMax lt x).as[i] = false

State before:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
⊢ lt (BinaryHeap.popMax lt x).as[j] (BinaryHeap.popMax lt x).as[i] = false
Tactic:
rewrite [get_as_popMax_of_ge_stop lt x j hj']
State after:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
⊢ lt x.as[j] (BinaryHeap.popMax lt x).as[i] = false

State before:
case inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
⊢ lt x.as[j] (BinaryHeap.popMax lt x).as[i] = false
Tactic:
cases Nat.lt_or_eq_of_le hi with
| inl hlti =>
  have : x.stop ≤ i :=
    ‹x.stop-1+1=x.stop› ▸ (hlti : x.stop-1+1 ≤ i)
  rewrite [get_as_popMax_of_ge_stop lt x i this]
  exact h.sorted i j this hij hj
| inr heqi =>
  cases heqi
  rewrite [get_as_popMax_stop_sub_one lt x hrng]
  exact h.bound_above j 0 ⟨hj',hj⟩ _
State after:
no goals

State before:
case inl.inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
hlti : x.stop - 1 < i
⊢ lt x.as[j] (BinaryHeap.popMax lt x).as[i] = false
Tactic:
have : x.stop ≤ i :=
  ‹x.stop-1+1=x.stop› ▸ (hlti : x.stop-1+1 ≤ i)
State after:
case inl.inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this✝ : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
hlti : x.stop - 1 < i
this : x.stop ≤ i
⊢ lt x.as[j] (BinaryHeap.popMax lt x).as[i] = false

State before:
case inl.inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this✝ : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
hlti : x.stop - 1 < i
this : x.stop ≤ i
⊢ lt x.as[j] (BinaryHeap.popMax lt x).as[i] = false
Tactic:
rewrite [get_as_popMax_of_ge_stop lt x i this]
State after:
case inl.inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this✝ : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
hlti : x.stop - 1 < i
this : x.stop ≤ i
⊢ lt x.as[j] x.as[i] = false

State before:
case inl.inl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this✝ : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
hlti : x.stop - 1 < i
this : x.stop ≤ i
⊢ lt x.as[j] x.as[i] = false
Tactic:
exact h.sorted i j this hij hj
State after:
no goals

State before:
case inl.inr
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hrng : x.start < x.stop
hi : x.stop - 1 ≤ i
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
heqi : x.stop - 1 = i
⊢ lt x.as[j] (BinaryHeap.popMax lt x).as[i] = false
Tactic:
cases heqi
State after:
case inl.inr.refl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
j : Nat
hj : j < stop
hrng : x.start < x.stop
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
hij : x.stop - 1 < j
hi : x.stop - 1 ≤ x.stop - 1
⊢ lt x.as[j] (BinaryHeap.popMax lt x).as[x.stop - 1] = false

State before:
case inl.inr.refl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
j : Nat
hj : j < stop
hrng : x.start < x.stop
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
hij : x.stop - 1 < j
hi : x.stop - 1 ≤ x.stop - 1
⊢ lt x.as[j] (BinaryHeap.popMax lt x).as[x.stop - 1] = false
Tactic:
rewrite [get_as_popMax_stop_sub_one lt x hrng]
State after:
case inl.inr.refl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
j : Nat
hj : j < stop
hrng : x.start < x.stop
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
hij : x.stop - 1 < j
hi : x.stop - 1 ≤ x.stop - 1
⊢ lt x.as[j] x[0] = false

State before:
case inl.inr.refl
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
j : Nat
hj : j < stop
hrng : x.start < x.stop
stop_pos : 0 < x.stop
this : x.stop - 1 + 1 = x.stop
hj' : x.stop ≤ j
hij : x.stop - 1 < j
hi : x.stop - 1 ≤ x.stop - 1
⊢ lt x.as[j] x[0] = false
Tactic:
exact h.bound_above j 0 ⟨hj',hj⟩ _
State after:
no goals

State before:
case inr
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hi : (BinaryHeap.popMax lt x).stop ≤ i
hij : i < j
hj : j < stop
hz : x.start = x.stop
⊢ lt (BinaryHeap.popMax lt x).as[j] (BinaryHeap.popMax lt x).as[i] = false
Tactic:
simp only [popMax_empty lt x hz] at hi ⊢
State after:
case inr
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hz : x.start = x.stop
hi : x.stop ≤ i
⊢ lt x.as[j] x.as[i] = false

State before:
case inr
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
stop : Nat
h : Algdata.BinaryHeap.heapSort.Intermed lt x stop
i j : Nat
hij : i < j
hj : j < stop
hz : x.start = x.stop
hi : x.stop ≤ i
⊢ lt x.as[j] x.as[i] = false
Tactic:
exact h.sorted i j hi hij hj
State after:
no goals