Files

589 lines
27 KiB
Lean4
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
/-
Released under Apache 2.0 license as described in the file LICENSE.
-/
import FormalConflictRange.CrossedResidual
/-!
# The crossed reversed truncated residual under the capacity condition
This module closes the remaining branch of the crossed reversed truncated residual:
when `crossedResidualCond` holds, the minimal range is `[end_.key, ⊤)`. The two new
necessity constructions are the gap keys `[end_.key, begin_.key)`, which need a
capacity-filling database with an extra key above the reported head, and the keys above
the reported head, which need a pad of `begin.offset - 1` keys below the reported last.
-/
open FormalConflictRange
namespace FormalConflictRange
/-- Choice of the number of gap keys used in the capacity-branch witness. -/
private theorem exists_gap_choice {D b : ℕ} {capGap capBL : ℕ∞}
(hbD : b < D) (hgap1 : (1 : ℕ∞) ≤ capGap)
(hbBL : (b : ℕ∞) ≤ capBL)
(hcond : (D : ℕ∞) ≤ capGap + capBL) :
∃ g : ℕ, 1 ≤ g ∧ g ≤ D - b ∧ (g : ℕ∞) ≤ capGap ∧
((D - g : ℕ) : ℕ∞) ≤ capBL := by
by_cases hG : capGap = ⊤
· refine ⟨D - b, by omega, le_refl _, hG ▸ le_top, ?_⟩
have hsub : D - (D - b) = b := by omega
rw [hsub]
exact hbBL
· obtain ⟨nG, rfl⟩ := ENat.ne_top_iff_exists.mp hG
have hnG1 : 1 ≤ nG := by exact_mod_cast hgap1
by_cases hGL : nG ≤ D - b
· refine ⟨nG, hnG1, hGL, le_refl _, ?_⟩
by_cases hB : capBL = ⊤
· rw [hB]
exact le_top
· obtain ⟨nBL, rfl⟩ := ENat.ne_top_iff_exists.mp hB
have hcast : (D : ℕ∞) ≤ ((nG + nBL : ℕ) : ℕ∞) := by
simpa [Nat.cast_add] using hcond
have hDle : D ≤ nG + nBL := Nat.cast_le.mp hcast
have hle : D - nG ≤ nBL := by omega
exact_mod_cast hle
· refine ⟨D - b, by omega, le_refl _, ?_, ?_⟩
· have hle : D - b ≤ nG := by omega
exact_mod_cast hle
· have hsub : D - (D - b) = b := by omega
rw [hsub]
exact hbBL
/-- Under the residual, every key above the reported head is necessary. A pad of
`begin.offset - 1` keys in `[begin.key, last reported)` followed by the reversed
reported keys is compatible; inserting a key above the head appends it to the window,
so the reported head is no longer first. -/
theorem necessary_crossedResidual_above_head_residual {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = true)
(hbegin : 2 ≤ r.begin.offset) (hcross : r.end_.key < r.begin.key)
(hend : 1 ≤ r.end_.offset) (hne : res.keys ≠ [])
(hres : res.keys.length + (r.begin.offset - 1).toNat <
(r.end_.offset - 1).toNat)
{k : Key} (hkH : res.keys.head hne < k) :
Necessary r res k := by
obtain ⟨db₀, hcomp₀⟩ := hread
set E : WithTop Key := r.end_.key with hE
set B : WithTop Key := r.begin.key with hB
set e : Nat := (r.end_.offset - 1).toNat with he
set b : Nat := (r.begin.offset - 1).toNat with hb
set L : Key := res.keys.getLast hne with hL
set H : Key := res.keys.head hne with hH
set R : List Key := res.keys.reverse with hR
have hbegin1 : 1 ≤ r.begin.offset := by omega
have hLmem : L ∈ res.keys := by rw [hL]; exact List.getLast_mem hne
have hHmem : H ∈ res.keys := by rw [hH]; exact List.head_mem hne
have hBL : B ≤ ((L : Key) : WithTop Key) := by
simpa [B, L] using
crossed_rev_res_ge_begin_general (db := db₀) (r := r) (res := res) hcomp₀
hbegin1 L hLmem
have hbcard : ((b : ℕ) : ℕ∞) ≤ intervalCard B ((L : Key) : WithTop Key) := by
simpa [B, L, b] using
crossed_rev_b_le_capBL (db := db₀) (r := r) (res := res) hcomp₀ hrev hbegin1
hcross hend hne
obtain ⟨pad, hpadIn, hpadlen⟩ :=
exists_db_keysIn (B := B) (E := ((L : Key) : WithTop Key)) (m := b) hbcard
set P : List Key := pad.keys with hP
have hPsort : P.SortedLT := pad.sorted
have hPmem : ∀ x ∈ P, B ≤ (x : WithTop Key) ∧
((x : Key) : WithTop Key) < ((L : Key) : WithTop Key) := by
intro x hx
simpa only [keysIn, Set.mem_ofPred_eq] using hpadIn x hx
have hPlen : P.length = b := hpadlen
have hsort : res.keys.SortedGT := RangeRead.compatible_sortedGT hcomp₀ hrev
have hLleH : L ≤ H := by
have h := (hsort.pairwise.imp le_of_lt).rel_getLast hHmem
simpa [hL, hH] using h
have hRsort : R.SortedLT := by
rw [hR]
exact hsort.reverse
have hRmem : ∀ y ∈ R, L ≤ y := by
intro y hy
have hyres : y ∈ res.keys := by
rw [hR] at hy
exact List.mem_reverse.mp hy
exact (hsort.pairwise.imp le_of_lt).rel_getLast hyres
have hRleH : ∀ y ∈ R, y ≤ H := by
intro y hy
have hyres : y ∈ res.keys := by
rw [hR] at hy
exact List.mem_reverse.mp hy
simpa [hH] using (hsort.pairwise.imp (fun h => le_of_lt h)).rel_head hyres
have hPR : ∀ x ∈ P, ∀ y ∈ R, x < y := by
intro x hx y hy
exact lt_of_lt_of_le (WithTop.coe_lt_coe.mp (hPmem x hx).2) (hRmem y hy)
have hfullSort : (P ++ R).SortedLT :=
List.sortedLT_append.mpr ⟨hPsort, hRsort, hPR⟩
set dbfull : DB := ⟨P ++ R, hfullSort⟩ with hdbfull
have hfullKeys : dbfull.keys = P ++ R := rfl
have hEB : E ≤ B := le_of_lt (by simpa [E, B] using hcross)
have haboveB : above dbfull B = P ++ R := by
rw [above_eq_filter, hfullKeys, List.filter_eq_self]
intro x hx
rcases List.mem_append.mp hx with hx | hx
· exact decide_eq_true (hPmem x hx).1
· exact decide_eq_true (le_trans hBL (WithTop.coe_le_coe.mpr (hRmem x hx)))
have haboveE : above dbfull E = P ++ R := by
rw [above_eq_filter, hfullKeys, List.filter_eq_self]
intro x hx
rcases List.mem_append.mp hx with hx | hx
· exact decide_eq_true (le_trans hEB (hPmem x hx).1)
· exact decide_eq_true
(le_trans hEB (le_trans hBL (WithTop.coe_le_coe.mpr (hRmem x hx))))
have hckFull : RangeRead.completeKeys dbfull r = res.keys := by
have hle : (above dbfull E).length ≤ e := by
rw [haboveE, List.length_append, hPlen, hR, List.length_reverse]
omega
rw [crossed_rev_window_eq_above_drop (db := dbfull) hrev hbegin1 hcross hend hle,
haboveB, List.drop_append_of_le_length (le_of_eq hPlen.symm),
List.drop_eq_nil_of_le (le_of_eq hPlen), List.nil_append, hR,
List.reverse_reverse]
have hcompFull : RangeRead.Compatible dbfull r res := by
refine ⟨hcomp₀.1, Or.inl ⟨hmore, ?_, hne⟩⟩
simp [hckFull]
have hk_not : k ∉ dbfull.keys := by
rw [hfullKeys]
intro hk
rcases List.mem_append.mp hk with hk | hk
· have hLk : ((L : Key) : WithTop Key) ≤ (k : WithTop Key) :=
le_trans (WithTop.coe_le_coe.mpr hLleH) (le_of_lt (WithTop.coe_lt_coe.mpr hkH))
exact absurd (hPmem k hk).2 (not_lt.mpr hLk)
· exact absurd (hRleH k hk) (not_le.mpr hkH)
have hins : (dbfull.insert k hk_not).keys = dbfull.keys ++ [k] := by
rw [DB.insert_keys]
exact orderedInsert_eq_append_of_forall_lt (l := dbfull.keys) (k := k) (by
intro x hx
rw [hfullKeys] at hx
rcases List.mem_append.mp hx with hx | hx
· exact lt_of_lt_of_le (lt_of_lt_of_le (WithTop.coe_lt_coe.mp (hPmem x hx).2)
hLleH) (le_of_lt hkH)
· exact lt_of_le_of_lt (hRleH x hx) hkH)
have hfiltE : List.filter (fun x : Key => decide (E ≤ (x : WithTop Key)))
(P ++ R) = P ++ R := by
have h := haboveE
rw [above_eq_filter, hfullKeys] at h
exact h
have hfiltEk : List.filter (fun x : Key => decide (E ≤ (x : WithTop Key)))
[k] = [k] := by
rw [List.filter_eq_self]
intro x hx
rw [List.mem_singleton] at hx
subst x
exact decide_eq_true (le_trans hEB (le_trans hBL
(le_trans (WithTop.coe_le_coe.mpr hLleH) (le_of_lt (WithTop.coe_lt_coe.mpr hkH)))))
have haboveIns : above (dbfull.insert k hk_not) E = (P ++ R) ++ [k] := by
rw [above_eq_filter, hins, hfullKeys, List.filter_append, hfiltE, hfiltEk]
have hckIns : RangeRead.completeKeys (dbfull.insert k hk_not) r = [k] ++ res.keys := by
have hle : (above (dbfull.insert k hk_not) E).length ≤ e := by
rw [haboveIns, List.length_append, List.length_append, hPlen, hR,
List.length_reverse, List.length_singleton]
omega
rw [crossed_rev_window_eq_above_drop (db := dbfull.insert k hk_not) hrev hbegin1
hcross hend hle]
have hfiltB : List.filter (fun x : Key => decide (B ≤ (x : WithTop Key)))
(P ++ R) = P ++ R := by
have h := haboveB
rw [above_eq_filter, hfullKeys] at h
exact h
have hfiltBk : List.filter (fun x : Key => decide (B ≤ (x : WithTop Key)))
[k] = [k] := by
rw [List.filter_eq_self]
intro x hx
rw [List.mem_singleton] at hx
subst x
exact decide_eq_true (le_trans hBL
(le_trans (WithTop.coe_le_coe.mpr hLleH) (le_of_lt (WithTop.coe_lt_coe.mpr hkH))))
have haboveB' : above (dbfull.insert k hk_not) B = (P ++ R) ++ [k] := by
rw [above_eq_filter, hins, hfullKeys, List.filter_append, hfiltB, hfiltBk]
rw [haboveB', List.append_assoc, List.drop_append_of_le_length (le_of_eq hPlen.symm),
List.drop_eq_nil_of_le (le_of_eq hPlen), List.nil_append, List.reverse_append,
hR, List.reverse_reverse, List.reverse_singleton]
refine necessary_of_toggle ⟨dbfull, hcompFull, ?_⟩
rw [toggle_eq_insert_of_not_mem hk_not]
intro hcomp'
have htpos : 0 < res.keys.length := List.length_pos_of_ne_nil hne
have hpre' : res.keys <+: [k] ++ res.keys := by
rcases hcomp'.2 with ⟨_, hp, _⟩ | ⟨hm, _⟩
· rw [hckIns] at hp
exact hp
· rw [hmore] at hm
simp at hm
have h0 := hpre'.getElem (i := 0) htpos
have hlhs : res.keys[0] = H := by
simpa [hH] using (List.getElem_zero htpos)
have hrhs : ([k] ++ res.keys)[0] = k := by
simp [List.getElem_cons_zero]
rw [hlhs, hrhs] at h0
exact absurd hkH (not_lt_of_ge (le_of_eq h0.symm))
/-- Under the capacity condition, every key in `[end_.key, begin_.key)` is necessary.
The witness has `g` keys in the gap (including the target), `D - g` pad keys in
`[begin_.key, last reported)`, the reversed reported keys, and one key above the reported
head. Erasing the target lengthens the window by one, so the key above the head enters
the complete keys and breaks compatibility. -/
theorem necessary_crossedResidual_gap_cond {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = true)
(hbegin : 2 ≤ r.begin.offset) (hcross : r.end_.key < r.begin.key)
(hend : 1 ≤ r.end_.offset) (hne : res.keys ≠ [])
(hres : res.keys.length + (r.begin.offset - 1).toNat <
(r.end_.offset - 1).toNat)
(hcond : crossedResidualCond r res hne)
{k : Key} (hEk : r.end_.key ≤ (k : WithTop Key))
(hkB : (k : WithTop Key) < r.begin.key) :
Necessary r res k := by
obtain ⟨db₀, hcomp₀⟩ := hread
set E : WithTop Key := r.end_.key with hE
set B : WithTop Key := r.begin.key with hB
set e : Nat := (r.end_.offset - 1).toNat with he
set b : Nat := (r.begin.offset - 1).toNat with hb
set t : Nat := res.keys.length with ht
set L : Key := res.keys.getLast hne with hL
set H : Key := res.keys.head hne with hH
set D : Nat := e - t with hD
have hbegin1 : 1 ≤ r.begin.offset := by omega
have hres' : t + b < e := by simpa [ht, hb, he] using hres
have hbD : b < D := by rw [hD]; omega
have hLmem : L ∈ res.keys := by rw [hL]; exact List.getLast_mem hne
have hHmem : H ∈ res.keys := by rw [hH]; exact List.head_mem hne
have hEB : E ≤ B := le_of_lt (by simpa [E, B] using hcross)
have hBL : B ≤ ((L : Key) : WithTop Key) := by
simpa [B, L] using
crossed_rev_res_ge_begin_general (db := db₀) (r := r) (res := res) hcomp₀
hbegin1 L hLmem
have hbcard : ((b : ℕ) : ℕ∞) ≤ intervalCard B ((L : Key) : WithTop Key) := by
simpa [B, L, b] using
crossed_rev_b_le_capBL (db := db₀) (r := r) (res := res) hcomp₀ hrev hbegin1
hcross hend hne
have hgap1 : (1 : ℕ∞) ≤ intervalCard E B := by
simpa [E, B] using
one_le_intervalCard_of_le_lt (B := E) (E := B) (k := k)
(by simpa [E] using hEk) (by simpa [B] using hkB)
have hcondEL : ((D : ℕ) : ℕ∞) ≤ intervalCard E ((L : Key) : WithTop Key) := by
rw [crossedResidualCond] at hcond
simpa [E, L, e, t, ht, he, hL, hD] using hcond
have hcond' : ((D : ℕ) : ℕ∞) ≤
intervalCard E B + intervalCard B ((L : Key) : WithTop Key) := by
rw [← intervalCard_add hEB hBL]
exact hcondEL
obtain ⟨g, hg1, hgDb, hgG, hgP⟩ := exists_gap_choice hbD hgap1 hbcard hcond'
set p : Nat := D - g with hp
have hgp : g + p = D := by rw [hp]; omega
have hpb : b ≤ p := by
rw [hp]
omega
obtain ⟨pad, hpadIn, hkpad, hpadlen⟩ :=
exists_db_keysIn_avoid (B := E) (E := B) (k := k) (m := g - 1) (by
have hsub : g - 1 + 1 = g := Nat.sub_add_cancel hg1
have h : (((g - 1 + 1 : ℕ)) : ℕ∞) ≤ intervalCard E B := by
rw [hsub]
exact hgG
simpa only [Nat.cast_add, Nat.cast_one] using h)
set G : List Key := (pad.insert k hkpad).keys with hGdef
have hGmem : ∀ x ∈ G, E ≤ (x : WithTop Key) ∧ (x : WithTop Key) < B := by
intro x hx
have hx' : x ∈ List.orderedInsert (fun x1 x2 => x1 ≤ x2) k pad.keys := by
rw [hGdef, DB.insert_keys] at hx
exact hx
rw [List.mem_orderedInsert] at hx'
rcases hx' with rfl | hx'
· exact ⟨by simpa [E] using hEk, by simpa [B] using hkB⟩
· simpa only [keysIn, Set.mem_ofPred_eq] using hpadIn x hx'
have hGsort : G.SortedLT := by
rw [hGdef]
exact (pad.insert k hkpad).sorted
have hGlen : G.length = g := by
rw [hGdef, DB.insert_keys, List.orderedInsert_length, hpadlen]
omega
obtain ⟨padL, hpadLIn, hpadLlen⟩ :=
exists_db_keysIn (B := B) (E := ((L : Key) : WithTop Key)) (m := p) (by
rw [hp]
exact hgP)
set P : List Key := padL.keys with hPdef
have hPmem : ∀ x ∈ P, B ≤ (x : WithTop Key) ∧
((x : Key) : WithTop Key) < ((L : Key) : WithTop Key) := by
intro x hx
simpa only [keysIn, Set.mem_ofPred_eq] using hpadLIn x hx
have hPsort : P.SortedLT := padL.sorted
have hPlen : P.length = p := hpadLlen
set Q : Key := keyAfter H with hQ
have hHQ : H < Q := by rw [hQ]; exact keyAfter_self_lt H
have hQsort : ([Q] : List Key).SortedLT := sortedLT_singleton Q
set R : List Key := res.keys.reverse with hR
have hsort : res.keys.SortedGT := RangeRead.compatible_sortedGT hcomp₀ hrev
have hLleH : L ≤ H := by
have h := (hsort.pairwise.imp le_of_lt).rel_getLast hHmem
simpa [hL, hH] using h
have hRsort : R.SortedLT := by
rw [hR]
exact hsort.reverse
have hRmem : ∀ y ∈ R, L ≤ y := by
intro y hy
have hyres : y ∈ res.keys := by
rw [hR] at hy
exact List.mem_reverse.mp hy
exact (hsort.pairwise.imp le_of_lt).rel_getLast hyres
have hRleH : ∀ y ∈ R, y ≤ H := by
intro y hy
have hyres : y ∈ res.keys := by
rw [hR] at hy
exact List.mem_reverse.mp hy
simpa [hH] using (hsort.pairwise.imp (fun h => le_of_lt h)).rel_head hyres
have hGP : ∀ x ∈ G, ∀ y ∈ P, x < y := by
intro x hx y hy
exact WithTop.coe_lt_coe.mp
(lt_of_lt_of_le (hGmem x hx).2 (hPmem y hy).1)
have hGPR : ∀ x ∈ G ++ P, ∀ y ∈ R, x < y := by
intro x hx y hy
rcases List.mem_append.mp hx with hx | hx
· exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le (hGmem x hx).2
(le_trans hBL (WithTop.coe_le_coe.mpr (hRmem y hy))))
· exact WithTop.coe_lt_coe.mp
(lt_of_lt_of_le (hPmem x hx).2 (WithTop.coe_le_coe.mpr (hRmem y hy)))
set T : List Key := (G ++ P) ++ R with hT
have hTsort : T.SortedLT := by
rw [hT]
exact List.sortedLT_append.mpr ⟨
List.sortedLT_append.mpr ⟨hGsort, hPsort, hGP⟩, hRsort, hGPR⟩
have hTQ : ∀ x ∈ T, x < Q := by
intro x hx
rw [hT] at hx
rcases List.mem_append.mp hx with hx | hx
· rcases List.mem_append.mp hx with hx | hx
· have hxH : (x : WithTop Key) ≤ (H : WithTop Key) :=
le_trans (le_trans (le_of_lt (hGmem x hx).2) hBL)
(WithTop.coe_le_coe.mpr hLleH)
exact WithTop.coe_lt_coe.mp (lt_of_le_of_lt hxH (WithTop.coe_lt_coe.mpr hHQ))
· have hxH : (x : WithTop Key) ≤ (H : WithTop Key) :=
le_trans (le_of_lt (hPmem x hx).2) (WithTop.coe_le_coe.mpr hLleH)
exact WithTop.coe_lt_coe.mp (lt_of_le_of_lt hxH (WithTop.coe_lt_coe.mpr hHQ))
· exact lt_of_le_of_lt (hRleH x hx) hHQ
have hfullSort : (T ++ [Q]).SortedLT :=
List.sortedLT_append.mpr ⟨hTsort, hQsort, by
intro x hx y hy
rw [List.mem_singleton] at hy
subst y
exact hTQ x hx⟩
set dbfull : DB := ⟨T ++ [Q], hfullSort⟩ with hdbfull
have hfullKeys : dbfull.keys = T ++ [Q] := rfl
have haboveE : above dbfull E = T ++ [Q] := by
rw [above_eq_filter, hfullKeys, List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
rcases List.mem_append.mp hx with hx | hx
· rw [hT] at hx
rcases List.mem_append.mp hx with hx | hx
· rcases List.mem_append.mp hx with hx | hx
· exact (hGmem x hx).1
· exact le_trans hEB (hPmem x hx).1
· exact le_trans hEB (le_trans hBL (WithTop.coe_le_coe.mpr (hRmem x hx)))
· rw [List.mem_singleton] at hx
subst x
exact le_trans hEB (le_trans hBL
(le_trans (WithTop.coe_le_coe.mpr hLleH) (le_of_lt (WithTop.coe_lt_coe.mpr hHQ))))
have haboveB : above dbfull B = (P ++ R) ++ [Q] := by
rw [above_eq_filter, hfullKeys, hT]
rw [List.filter_append, List.filter_append, List.filter_append]
have hGnil : List.filter (fun x : Key => decide (B ≤ (x : WithTop Key))) G = [] := by
rw [List.filter_eq_nil_iff]
intro x hx hge
exact absurd (hGmem x hx).2 (not_lt.mpr (of_decide_eq_true hge))
have hPself : List.filter (fun x : Key => decide (B ≤ (x : WithTop Key))) P = P := by
rw [List.filter_eq_self]
intro x hx
exact decide_eq_true (hPmem x hx).1
have hRself : List.filter (fun x : Key => decide (B ≤ (x : WithTop Key))) R = R := by
rw [List.filter_eq_self]
intro x hx
exact decide_eq_true (hBL.trans (WithTop.coe_le_coe.mpr (hRmem x hx)))
have hQself : List.filter (fun x : Key => decide (B ≤ (x : WithTop Key))) [Q] = [Q] := by
rw [List.filter_eq_self]
intro x hx
rw [List.mem_singleton] at hx
subst x
exact decide_eq_true (le_trans hBL
(le_trans (WithTop.coe_le_coe.mpr hLleH) (le_of_lt (WithTop.coe_lt_coe.mpr hHQ))))
rw [hGnil, hPself, hRself, hQself]
simp
have haboveElen : (above dbfull E).length = g + p + t + 1 := by
rw [haboveE, hT, List.length_append, List.length_append, List.length_append,
hGlen, hPlen, hR, List.length_reverse, List.length_singleton]
have haboveBlen : (above dbfull B).length = p + t + 1 := by
rw [haboveB, List.length_append, List.length_append, hPlen, hR,
List.length_reverse, List.length_singleton]
have hbetweenLen : (between dbfull E B).length = g := by
have h := length_above_eq_between_add_above (db := dbfull) (E := E) (L := B) hEB
rw [haboveElen, haboveBlen] at h
omega
have htle : t ≤ e := by omega
have hTlen : T.length = e := by
rw [hT, List.length_append, List.length_append, hGlen, hPlen, hR,
List.length_reverse]
omega
have htake : (T ++ [Q]).take e = T := by
rw [← hTlen]
exact List.take_left
have hGPdrop : (G ++ P).drop (g + b) = P.drop b := by
rw [← List.drop_drop]
rw [List.drop_append_of_le_length (le_of_eq hGlen.symm)]
rw [List.drop_eq_nil_of_le (le_of_eq hGlen), List.nil_append]
have hdrop : T.drop (g + b) = P.drop b ++ R := by
rw [hT]
rw [List.drop_append_of_le_length (by
rw [List.length_append, hGlen, hPlen]
omega)]
rw [hGPdrop]
have hckFull : RangeRead.completeKeys dbfull r =
res.keys ++ (P.drop b).reverse := by
rw [completeKeys_crossed_rev_eq_general (db := dbfull) hrev hbegin1 hcross hend,
haboveE, hbetweenLen, htake, hdrop, List.reverse_append, hR,
List.reverse_reverse]
have hcompFull : RangeRead.Compatible dbfull r res := by
refine ⟨hcomp₀.1, Or.inl ⟨hmore, ?_, hne⟩⟩
rw [hckFull]
exact List.prefix_append res.keys (P.drop b).reverse
have hkG : k ∈ G := by
rw [hGdef, DB.insert_keys]
rw [List.mem_orderedInsert]
exact Or.inl rfl
have hkGP : k ∈ G ++ P := List.mem_append.mpr (Or.inl hkG)
have hkT : k ∈ T := by
rw [hT]
exact List.mem_append.mpr (Or.inl hkGP)
have hkeysErase : (dbfull.erase k).keys = ((G.erase k ++ P) ++ R) ++ [Q] := by
rw [DB.erase_keys, hfullKeys, hT]
rw [List.erase_append_left (l₁ := (G ++ P) ++ R) [Q]
(List.mem_append.mpr (Or.inl hkGP))]
rw [List.erase_append_left (l₁ := G ++ P) R hkGP]
rw [List.erase_append_left (l₁ := G) P hkG]
have haboveEraseE : above (dbfull.erase k) E = ((G.erase k ++ P) ++ R) ++ [Q] := by
rw [above_eq_filter, hkeysErase, List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
rcases List.mem_append.mp hx with hx | hx
· rcases List.mem_append.mp hx with hx | hx
· rcases List.mem_append.mp hx with hx | hx
· exact (hGmem x (List.mem_of_mem_erase hx)).1
· exact le_trans hEB (hPmem x hx).1
· exact le_trans hEB (le_trans hBL (WithTop.coe_le_coe.mpr (hRmem x hx)))
· rw [List.mem_singleton] at hx
subst x
exact le_trans hEB (le_trans hBL
(le_trans (WithTop.coe_le_coe.mpr hLleH) (le_of_lt (WithTop.coe_lt_coe.mpr hHQ))))
have haboveEraseB : above (dbfull.erase k) B = (P ++ R) ++ [Q] := by
rw [above_eq_filter, hkeysErase]
rw [List.filter_append, List.filter_append, List.filter_append]
have hGnil : List.filter (fun x : Key => decide (B ≤ (x : WithTop Key)))
(G.erase k) = [] := by
rw [List.filter_eq_nil_iff]
intro x hx hge
exact absurd (hGmem x (List.mem_of_mem_erase hx)).2
(not_lt.mpr (of_decide_eq_true hge))
have hPself : List.filter (fun x : Key => decide (B ≤ (x : WithTop Key))) P = P := by
rw [List.filter_eq_self]
intro x hx
exact decide_eq_true (hPmem x hx).1
have hRself : List.filter (fun x : Key => decide (B ≤ (x : WithTop Key))) R = R := by
rw [List.filter_eq_self]
intro x hx
exact decide_eq_true (hBL.trans (WithTop.coe_le_coe.mpr (hRmem x hx)))
have hQself : List.filter (fun x : Key => decide (B ≤ (x : WithTop Key))) [Q] = [Q] := by
rw [List.filter_eq_self]
intro x hx
rw [List.mem_singleton] at hx
subst x
exact decide_eq_true (le_trans hBL
(le_trans (WithTop.coe_le_coe.mpr hLleH) (le_of_lt (WithTop.coe_lt_coe.mpr hHQ))))
rw [hGnil, hPself, hRself, hQself]
simp
have hGeraseLen : (G.erase k).length = g - 1 := by
rw [List.length_erase_of_mem hkG, hGlen]
have hEraseElen : (above (dbfull.erase k) E).length = (g - 1) + p + t + 1 := by
rw [haboveEraseE, List.length_append, List.length_append, List.length_append,
hGeraseLen, hPlen, hR, List.length_reverse, List.length_singleton]
have hEraseBlen : (above (dbfull.erase k) B).length = p + t + 1 := by
rw [haboveEraseB, List.length_append, List.length_append, hPlen, hR,
List.length_reverse, List.length_singleton]
have hbetweenEraseLen : (between (dbfull.erase k) E B).length = g - 1 := by
have h := length_above_eq_between_add_above (db := dbfull.erase k) (E := E)
(L := B) hEB
rw [hEraseElen, hEraseBlen] at h
omega
have hEraseElenE : (above (dbfull.erase k) E).length = e := by
rw [hEraseElen]
omega
have htakeErase : (above (dbfull.erase k) E).take e = above (dbfull.erase k) E := by
rw [← hEraseElenE]
exact List.take_length
have hGPdropErase : (G.erase k ++ P).drop (g - 1 + b) = P.drop b := by
rw [← List.drop_drop]
rw [List.drop_append_of_le_length (le_of_eq hGeraseLen.symm)]
rw [List.drop_eq_nil_of_le (le_of_eq hGeraseLen), List.nil_append]
have hdropErase : (above (dbfull.erase k) E).drop (g - 1 + b) =
P.drop b ++ R ++ [Q] := by
rw [haboveEraseE, List.append_assoc]
rw [List.drop_append_of_le_length (by
rw [List.length_append, hGeraseLen, hPlen]
omega)]
rw [hGPdropErase, List.append_assoc]
have hckErase : RangeRead.completeKeys (dbfull.erase k) r =
[Q] ++ res.keys ++ (P.drop b).reverse := by
rw [completeKeys_crossed_rev_eq_general (db := dbfull.erase k) hrev hbegin1 hcross
hend, hbetweenEraseLen, htakeErase, hdropErase,
List.reverse_append, List.reverse_append, hR, List.reverse_reverse,
List.reverse_singleton, List.append_assoc]
refine necessary_of_toggle ⟨dbfull, hcompFull, ?_⟩
have hkFull : k ∈ dbfull.keys := by
rw [hfullKeys]
exact List.mem_append.mpr (Or.inl hkT)
rw [toggle_eq_erase_of_mem hkFull]
intro hcomp'
have htpos : 0 < res.keys.length := List.length_pos_of_ne_nil hne
have hpre' := RangeRead.compatible_keys_prefix hcomp'
have hpre'' : res.keys <+: [Q] ++ res.keys ++ (P.drop b).reverse := by
simpa [hckErase] using hpre'
have h0 := hpre''.getElem (i := 0) htpos
have hlhs : res.keys[0] = H := by
simpa [hH] using (List.getElem_zero htpos)
have hrhs : ([Q] ++ res.keys ++ (P.drop b).reverse)[0] = Q := by
simp [List.getElem_cons_zero]
rw [hlhs, hrhs] at h0
exact (ne_of_lt hHQ) h0
/-- Under the capacity condition, the crossed reversed truncated residual has minimal
range `[end_.key, ⊤)`. -/
theorem minimal_crossedResidual_cond {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = true)
(hbegin : 2 ≤ r.begin.offset) (hcross : r.end_.key < r.begin.key)
(hend : 1 ≤ r.end_.offset) (hne : res.keys ≠ [])
(hres : res.keys.length + (r.begin.offset - 1).toNat <
(r.end_.offset - 1).toNat)
(hcond : crossedResidualCond r res hne) :
Minimal r res ⟨r.end_.key, ⊤⟩ := by
have hbegin1 : 1 ≤ r.begin.offset := by omega
refine (minimal_iff_sound_and_necessary).mpr ⟨?_, ?_⟩
· simpa using sound_truncatedRevCrossed_top_general (r := r) (res := res)
hrev hbegin1 hcross hend
· intro k hk
rw [ConflictRange.mem_iff] at hk
obtain ⟨hEk, _⟩ := hk
set L : Key := res.keys.getLast hne with hL
set H : Key := res.keys.head hne with hH
by_cases hkB : (k : WithTop Key) < r.begin.key
· exact necessary_crossedResidual_gap_cond hread hmore hrev hbegin hcross hend hne
hres hcond hEk hkB
· have hBk : r.begin.key ≤ (k : WithTop Key) := le_of_not_gt hkB
by_cases hkL : (k : WithTop Key) < ((L : Key) : WithTop Key)
· exact crossed_residual_necessary_below_last_not_cond hread hmore hrev hbegin
hcross hend hne hres hBk hkL
· have hLk : ((L : Key) : WithTop Key) ≤ (k : WithTop Key) := le_of_not_gt hkL
by_cases hkHle : (k : WithTop Key) ≤ ((H : Key) : WithTop Key)
· exact necessary_of_between_result hread
(by rw [hL]; exact List.getLast_mem hne)
(by rw [hH]; exact List.head_mem hne)
(WithTop.coe_le_coe.mp hLk) (WithTop.coe_le_coe.mp hkHle)
· have hHk : ((H : Key) : WithTop Key) < (k : WithTop Key) := lt_of_not_ge hkHle
exact necessary_crossedResidual_above_head_residual hread hmore hrev hbegin
hcross hend hne hres (WithTop.coe_lt_coe.mp hHk)
end FormalConflictRange