1624 lines
81 KiB
Lean4
1624 lines
81 KiB
Lean4
/-
|
||
Released under Apache 2.0 license as described in the file LICENSE.
|
||
-/
|
||
import FormalConflictRange.CrossedTruncated
|
||
|
||
/-!
|
||
# Crossed selectors at positive begin offsets
|
||
|
||
This module extends the crossed-selector closed forms from `begin.offset = 1` to every
|
||
positive begin offset. In the finite complete-result branch the finite condition reads
|
||
`t + (begin.offset - 1) = end.offset - 1`, where `t` is the number of reported keys at or
|
||
above `end_.key`; it forces the selector gap to be empty. The top branch leaves the
|
||
overshoot `e - t - (begin.offset - 1)` to be absorbed by the gap.
|
||
|
||
The main ingredients here are the gap-emptiness lemma, the exact finite window
|
||
`completeKeys = (filter (begin.key ≤ · ∧ · ≤ last)).drop (begin.offset - 1)`, and the
|
||
soundness/necessity results built from them.
|
||
-/
|
||
|
||
open FormalConflictRange
|
||
|
||
namespace FormalConflictRange
|
||
|
||
/-- **Finite branch emptiness of the selector gap.** If the number of reported keys at
|
||
or above `end_.key` plus `begin.offset - 1` equals `end.offset - 1`, then no stored key
|
||
lies in `[end_.key, begin_.key)`. -/
|
||
theorem crossed_gap_empty_of_finite {db : DB} {r : RangeRead} {res : Result}
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 1 ≤ r.end_.offset)
|
||
(hne : res.keys ≠ [])
|
||
(hres : res.keys = RangeRead.completeKeys db r)
|
||
(ht : res.keys.countP
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) +
|
||
(r.begin.offset - 1).toNat = (r.end_.offset - 1).toNat) :
|
||
∀ k ∈ db.keys, ¬ (r.end_.key ≤ (k : WithTop Key) ∧ (k : WithTop Key) < r.begin.key) := by
|
||
set l := db.keys with hl
|
||
have hcounts := crossed_counts_of_t_add_b_eq_e (db := db) (r := r) (res := res)
|
||
hrev hbegin hcross hend hne hres ht
|
||
have hcEp : l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) =
|
||
l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) := by
|
||
simpa [hl] using hcounts.1
|
||
have hpart := countP_lt_add_between (l := l) (E := r.end_.key) (B := r.begin.key)
|
||
(le_of_lt hcross)
|
||
have hzero : l.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key) ∧
|
||
(k : WithTop Key) < r.begin.key)) = 0 := by omega
|
||
intro k hk hkb
|
||
exact (List.countP_eq_zero.mp hzero) k hk (by rw [decide_eq_true_eq]; exact hkb)
|
||
|
||
/-- If no list element lies in `[E, B)`, then filtering at or above `E` agrees with
|
||
filtering at or above `B`. -/
|
||
theorem filter_le_eq_filter_of_no_between {l : List Key} {E B : WithTop Key}
|
||
(hEB : E ≤ B) (hno : ∀ k ∈ l, ¬ (E ≤ (k : WithTop Key) ∧ (k : WithTop Key) < B)) :
|
||
l.filter (fun k : Key => decide (E ≤ (k : WithTop Key))) =
|
||
l.filter (fun k : Key => decide (B ≤ (k : WithTop Key))) := by
|
||
apply List.filter_congr
|
||
intro k hk
|
||
by_cases hEk : E ≤ (k : WithTop Key)
|
||
· have hBk : B ≤ (k : WithTop Key) := by
|
||
by_contra h
|
||
exact hno k hk ⟨hEk, not_le.mp h⟩
|
||
simp [hEk, hBk]
|
||
· have hBk : ¬ B ≤ (k : WithTop Key) := fun h => hEk (le_trans hEB h)
|
||
simp [hEk, hBk]
|
||
|
||
/-- **The finite crossed complete window.** In the finite branch at any positive begin
|
||
offset, the complete keys are the stored keys in `[begin_.key, last]` after dropping the
|
||
first `begin.offset - 1` of them. -/
|
||
theorem completeKeys_eq_filter_drop_of_crossed_finite {db : DB} {r : RangeRead} {res : Result}
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 1 ≤ r.end_.offset)
|
||
(hne : res.keys ≠ [])
|
||
(hres : res.keys = RangeRead.completeKeys db r)
|
||
(ht : res.keys.countP
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) +
|
||
(r.begin.offset - 1).toNat = (r.end_.offset - 1).toNat) :
|
||
RangeRead.completeKeys db r =
|
||
(db.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne))).drop
|
||
(r.begin.offset - 1).toNat := by
|
||
set l := db.keys with hl
|
||
set p := l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) with hp
|
||
set b := (r.begin.offset - 1).toNat with hb
|
||
set e := (r.end_.offset - 1).toNat with he
|
||
set t := res.keys.length with htlen
|
||
have hcounts := crossed_counts_of_t_add_b_eq_e (db := db) (r := r) (res := res)
|
||
hrev hbegin hcross hend hne hres ht
|
||
have hcEp : l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) = p := by
|
||
simpa [hl, hp] using hcounts.1
|
||
have hAele : p + e ≤ l.length := by simpa [hl, hp, he] using hcounts.2
|
||
have hcountlen : res.keys.countP
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) = res.keys.length := by
|
||
rw [hres]
|
||
exact completeKeys_count_ge_eq_length_of_crossed_general (db := db) hrev hbegin hcross hend
|
||
have htb : t + b = e := by
|
||
rw [show t = res.keys.length from rfl]
|
||
omega
|
||
have htpos : 0 < t := List.length_pos_of_ne_nil hne
|
||
have hlist := completeKeys_eq_drop_take_general (db := db) (r := r) hrev hbegin hend
|
||
rw [← hl, ← hp, ← hb, ← he] at hlist
|
||
have hmin : min (l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) + e)
|
||
l.length = p + e := by
|
||
rw [hcEp]
|
||
exact Nat.min_eq_left hAele
|
||
have hlist' : RangeRead.completeKeys db r = (l.drop (p + b)).take t := by
|
||
rw [hlist, hmin]
|
||
congr 1
|
||
omega
|
||
set W := (l.drop (p + b)).take t with hWdef
|
||
have hW : res.keys = W := by rw [hres, hlist']
|
||
have hWne : W ≠ [] := by rw [← hW]; exact hne
|
||
have hWlen : W.length = t := by
|
||
rw [hWdef, List.length_take]
|
||
have : t ≤ (l.drop (p + b)).length := by rw [List.length_drop]; omega
|
||
omega
|
||
have hlast_eq : res.keys.getLast hne = l[p + e - 1] := by
|
||
rw [List.getLast_congr hne hWne hW, List.getLast_eq_getElem]
|
||
rw [List.getElem_take, List.getElem_drop]
|
||
congr 1
|
||
omega
|
||
have hls : l.SortedLT := by rw [hl]; exact db.sorted
|
||
have hAeq : l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) = l.drop p := by
|
||
rw [hp]
|
||
have hdrop := filter_not_lt_eq_drop_countP hls r.begin.key
|
||
rw [← hdrop]
|
||
apply List.filter_congr
|
||
intro k _
|
||
rw [decide_eq_decide]
|
||
exact not_lt.symm
|
||
have hAs : (l.drop p).SortedLT :=
|
||
List.sortedLT_iff_pairwise.mpr (List.Pairwise.drop (i := p) hls.pairwise)
|
||
have hepos : 0 < e := by omega
|
||
have hidx : e - 1 < (l.drop p).length := by rw [List.length_drop]; omega
|
||
have hlastA : (l.drop p)[e - 1]'hidx = res.keys.getLast hne := by
|
||
rw [List.getElem_drop]
|
||
calc l[p + (e - 1)] = l[p + e - 1] := by congr 1; omega
|
||
_ = res.keys.getLast hne := hlast_eq.symm
|
||
have hAle : (l.drop p).filter (fun k : Key => decide (k ≤ res.keys.getLast hne)) =
|
||
(l.drop p).take e := by
|
||
have h := filter_le_eq_take_succ_of_getElem hAs (x := res.keys.getLast hne) (n := e - 1)
|
||
(by rw [List.length_drop]; omega) hlastA
|
||
simpa [Nat.sub_add_cancel hepos] using h
|
||
have hfil : l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne)) =
|
||
(l.drop p).take e := by
|
||
have hsplit : l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne)) =
|
||
(l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).filter
|
||
(fun k : Key => decide (k ≤ res.keys.getLast hne)) := by
|
||
rw [List.filter_filter]
|
||
apply List.filter_congr
|
||
intro k _
|
||
exact (Bool.decide_and (r.begin.key ≤ (k : WithTop Key))
|
||
(k ≤ res.keys.getLast hne)).trans (Bool.and_comm _ _)
|
||
rw [hsplit, hAeq, hAle]
|
||
rw [hlist', hfil]
|
||
rw [List.drop_take, List.drop_drop]
|
||
rw [hWdef]
|
||
congr 1
|
||
omega
|
||
|
||
/-- A conjunction filter is a nested filter. -/
|
||
theorem filter_and_eq_filter_filter {l : List Key} (p q : Key → Prop)
|
||
[DecidablePred p] [DecidablePred q] :
|
||
l.filter (fun k : Key => decide (p k ∧ q k)) =
|
||
(l.filter (fun k : Key => decide (p k))).filter (fun k : Key => decide (q k)) := by
|
||
rw [List.filter_filter]
|
||
apply List.filter_congr
|
||
intro k _
|
||
exact (Bool.decide_and (p k) (q k)).trans (Bool.and_comm _ _)
|
||
|
||
/-- **The finite crossed window from gap emptiness alone.** If the selector gap is
|
||
empty and exactly `end.offset - 1` stored keys lie in `[end_.key, last]`, then the
|
||
complete keys are the stored keys in `[begin_.key, last]` with the first
|
||
`begin.offset - 1` removed. -/
|
||
theorem completeKeys_eq_filter_drop_of_no_gap {db : DB} {r : RangeRead} {last : Key}
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 1 ≤ r.end_.offset)
|
||
(hno : ∀ k ∈ db.keys, ¬ (r.end_.key ≤ (k : WithTop Key) ∧
|
||
(k : WithTop Key) < r.begin.key))
|
||
(hlen : (db.keys.filter (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key) ∧
|
||
k ≤ last))).length = (r.end_.offset - 1).toNat) :
|
||
RangeRead.completeKeys db r =
|
||
(db.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key) ∧
|
||
k ≤ last))).drop (r.begin.offset - 1).toNat := by
|
||
set l := db.keys with hl
|
||
set p := l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) with hp
|
||
set cE := l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) with hcE
|
||
set b := (r.begin.offset - 1).toNat with hb
|
||
set e := (r.end_.offset - 1).toNat with he
|
||
have hls : l.SortedLT := by rw [hl]; exact db.sorted
|
||
have hEeq : l.filter (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) =
|
||
l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) :=
|
||
filter_le_eq_filter_of_no_between (le_of_lt hcross) (by simpa [hl] using hno)
|
||
have hEnotlt : l.filter (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) =
|
||
l.filter (fun k : Key => decide (¬ (k : WithTop Key) < r.end_.key)) := by
|
||
apply List.filter_congr
|
||
intro k _
|
||
rw [decide_eq_decide]
|
||
exact not_lt.symm
|
||
have hBnotlt : l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) =
|
||
l.filter (fun k : Key => decide (¬ (k : WithTop Key) < r.begin.key)) := by
|
||
apply List.filter_congr
|
||
intro k _
|
||
rw [decide_eq_decide]
|
||
exact not_lt.symm
|
||
have hdropE := filter_not_lt_eq_drop_countP hls r.end_.key
|
||
have hdropB := filter_not_lt_eq_drop_countP hls r.begin.key
|
||
have hcEp : cE = p := by
|
||
have hlenEq := congrArg List.length hEeq
|
||
rw [hEnotlt, hdropE, List.length_drop, hBnotlt, hdropB, List.length_drop] at hlenEq
|
||
have hcE_le : cE ≤ l.length := by rw [hcE]; exact List.countP_le_length
|
||
have hp_le : p ≤ l.length := by rw [hp]; exact List.countP_le_length
|
||
omega
|
||
have hAeq : l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) = l.drop p := by
|
||
rw [hBnotlt, hdropB, ← hp]
|
||
have hAs : (l.drop p).SortedLT :=
|
||
List.sortedLT_iff_pairwise.mpr (List.Pairwise.drop (i := p) hls.pairwise)
|
||
have hlenEf : ((l.filter (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key)))).filter
|
||
(fun k : Key => decide (k ≤ last))).length = e := by
|
||
rw [← filter_and_eq_filter_filter (p := fun k : Key => r.end_.key ≤ (k : WithTop Key))
|
||
(q := fun k : Key => k ≤ last)]
|
||
simpa [hl, he] using hlen
|
||
have hlenBf : ((l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).filter
|
||
(fun k : Key => decide (k ≤ last))).length = e := by
|
||
rw [← hEeq]; exact hlenEf
|
||
have hlenBf' : ((l.drop p).filter (fun k : Key => decide (k ≤ last))).length = e := by
|
||
rw [← hAeq]; exact hlenBf
|
||
have hAle : (l.drop p).filter (fun k : Key => decide (k ≤ last)) = (l.drop p).take e := by
|
||
rw [filter_le_eq_take_countP hAs last]
|
||
congr 1
|
||
rw [List.countP_eq_length_filter]
|
||
exact hlenBf'
|
||
have hp_le : p ≤ l.length := by rw [hp]; exact List.countP_le_length
|
||
have hpe_le : p + e ≤ l.length := by
|
||
have he_le : e ≤ (l.drop p).length := by
|
||
have hlen_take : (List.take e (l.drop p)).length = e := by
|
||
rw [← hAle]; exact hlenBf'
|
||
rw [List.length_take] at hlen_take
|
||
omega
|
||
rw [List.length_drop] at he_le
|
||
omega
|
||
have hmain := completeKeys_eq_drop_take_general (db := db) (r := r) hrev hbegin hend
|
||
rw [← hl, ← hp, ← hcE, ← hb, ← he] at hmain
|
||
have hmin : min (cE + e) l.length = p + e := by
|
||
rw [hcEp]
|
||
exact Nat.min_eq_left hpe_le
|
||
have hck : RangeRead.completeKeys db r = (l.drop (p + b)).take (e - b) := by
|
||
rw [hmain, hmin]
|
||
congr 1
|
||
omega
|
||
have hfil : l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key) ∧
|
||
k ≤ last)) = (l.drop p).take e := by
|
||
rw [filter_and_eq_filter_filter (p := fun k : Key => r.begin.key ≤ (k : WithTop Key))
|
||
(q := fun k : Key => k ≤ last)]
|
||
rw [hAeq]
|
||
exact hAle
|
||
rw [hck, hfil, List.drop_take, List.drop_drop]
|
||
|
||
/-- Conjunction filters also agree across an empty selector gap. -/
|
||
theorem filter_le_le_eq_filter_of_no_between {l : List Key} {E B : WithTop Key} {last : Key}
|
||
(hEB : E ≤ B) (hno : ∀ k ∈ l, ¬ (E ≤ (k : WithTop Key) ∧ (k : WithTop Key) < B)) :
|
||
l.filter (fun k : Key => decide (E ≤ (k : WithTop Key) ∧ k ≤ last)) =
|
||
l.filter (fun k : Key => decide (B ≤ (k : WithTop Key) ∧ k ≤ last)) := by
|
||
apply List.filter_congr
|
||
intro k hk
|
||
by_cases hEk : E ≤ (k : WithTop Key)
|
||
· have hBk : B ≤ (k : WithTop Key) := by
|
||
by_contra h
|
||
exact hno k hk ⟨hEk, not_le.mp h⟩
|
||
simp [hEk, hBk]
|
||
· have hBk : ¬ B ≤ (k : WithTop Key) := fun h => hEk (le_trans hEB h)
|
||
simp [hEk, hBk]
|
||
|
||
/-- A crossed complete result's reported keys lie at or above `begin_.key`, for any
|
||
positive begin offset. -/
|
||
theorem crossed_mem_result_ge_begin_general {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false)
|
||
(hbegin : 1 ≤ r.begin.offset) :
|
||
∀ k ∈ res.keys, r.begin.key ≤ (k : WithTop Key) := by
|
||
obtain ⟨db₀, hcomp₀⟩ := hread
|
||
have hres : res.keys = RangeRead.completeKeys db₀ r := by
|
||
rcases hcomp₀.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
|
||
· simp [hmore] at hm
|
||
· exact heq
|
||
intro k hk
|
||
have hk' : k ∈ RangeRead.completeKeys db₀ r := by rw [← hres]; exact hk
|
||
exact le_trans (key_le_resolve_of_one_le (db := db₀) (s := r.begin) hbegin)
|
||
(RangeRead.mem_completeKeys.mp hk').2.1
|
||
|
||
/-- The keys of `[lo, keyAfter last)` are the stored keys in `[lo, last]`. -/
|
||
theorem conflictRange_keys_keyAfter_eq_filter {db : DB} {lo : WithTop Key} {last : Key} :
|
||
(⟨lo, (keyAfter last : Key)⟩ : ConflictRange).keys db =
|
||
(db.keys.filter (fun k : Key => decide (lo ≤ (k : WithTop Key)))).filter
|
||
(fun k : Key => decide (k ≤ last)) := by
|
||
unfold ConflictRange.keys
|
||
rw [show db.keys.filter (fun (k : Key) => decide (lo ≤ (k : WithTop Key) ∧
|
||
(k : WithTop Key) < ((keyAfter last : Key) : WithTop Key))) =
|
||
db.keys.filter (fun (k : Key) =>
|
||
decide ((k : WithTop Key) < ((keyAfter last : Key) : WithTop Key)) &&
|
||
decide (lo ≤ (k : WithTop Key))) from
|
||
List.filter_congr fun k _ => by rw [Bool.decide_and, Bool.and_comm]]
|
||
rw [← List.filter_filter]
|
||
apply List.filter_congr
|
||
intro k _
|
||
rw [decide_eq_decide, WithTop.coe_lt_coe, lt_keyAfter_iff]
|
||
|
||
/-- **Finite-branch soundness for crossed complete results at any positive begin
|
||
offset.** Agreement on `[end_.key, keyAfter (last reported))` fixes the complete keys:
|
||
the finite condition makes the selector gap empty, and the finite window is the stored
|
||
keys in `[begin_.key, last]` with the first `begin.offset - 1` removed. -/
|
||
theorem sound_truncatedRange_of_crossed_finite_general {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
|
||
(ht : res.keys.countP
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) +
|
||
(r.begin.offset - 1).toNat = (r.end_.offset - 1).toNat) :
|
||
Sound r res ⟨r.end_.key, (keyAfter (res.keys.getLastD ([] : Key)) : WithTop Key)⟩ := by
|
||
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by
|
||
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
|
||
rw [hlast]
|
||
let cr : ConflictRange := ⟨r.end_.key, (keyAfter (res.keys.getLast hne) : WithTop Key)⟩
|
||
change Sound r res cr
|
||
have hall_ge : ∀ k ∈ res.keys, r.begin.key ≤ (k : WithTop Key) :=
|
||
crossed_mem_result_ge_begin_general hread hmore hbegin
|
||
have hlast_ge_B : r.begin.key ≤ (res.keys.getLast hne : WithTop Key) :=
|
||
hall_ge _ (List.getLast_mem hne)
|
||
have htb : res.keys.length + (r.begin.offset - 1).toNat =
|
||
(r.end_.offset - 1).toNat := by
|
||
have hcount : res.keys.countP
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) = res.keys.length := by
|
||
rw [List.countP_eq_length]
|
||
intro k hk
|
||
rw [decide_eq_true_eq]
|
||
exact le_trans (le_of_lt hcross) (hall_ge k hk)
|
||
omega
|
||
have htpos : 0 < res.keys.length := List.length_pos_of_ne_nil hne
|
||
have step : ∀ {dA dB : DB}, RangeRead.Compatible dA r res → AgreeOn cr dA dB →
|
||
RangeRead.Compatible dB r res := by
|
||
intro dA dB hcA hag
|
||
have hresA : res.keys = RangeRead.completeKeys dA r := by
|
||
rcases hcA.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
|
||
· simp [hmore] at hm
|
||
· exact heq
|
||
have hgapA := crossed_gap_empty_of_finite (db := dA) hrev hbegin hcross
|
||
(by omega) hne hresA ht
|
||
have hwinA := completeKeys_eq_filter_drop_of_crossed_finite (db := dA) hrev hbegin
|
||
hcross (by omega) hne hresA ht
|
||
have hfilEeqA := filter_le_le_eq_filter_of_no_between (l := dA.keys)
|
||
(last := res.keys.getLast hne) (le_of_lt hcross) hgapA
|
||
have hlenBA : (dA.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne))).length = (r.end_.offset - 1).toNat := by
|
||
have hlenck : (RangeRead.completeKeys dA r).length = res.keys.length := by
|
||
rw [← hresA]
|
||
rw [hwinA, List.length_drop] at hlenck
|
||
omega
|
||
have hlenA : (dA.keys.filter (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne))).length = (r.end_.offset - 1).toNat := by
|
||
rw [hfilEeqA]; exact hlenBA
|
||
have hcrA : cr.keys dA = (dA.keys.filter
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key)))).filter
|
||
(fun k : Key => decide (k ≤ res.keys.getLast hne)) := by
|
||
simpa [cr] using conflictRange_keys_keyAfter_eq_filter (db := dA)
|
||
(lo := r.end_.key) (last := res.keys.getLast hne)
|
||
have hcrA_E : cr.keys dA = dA.keys.filter
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne)) := by
|
||
rw [hcrA, ← filter_and_eq_filter_filter
|
||
(p := fun k : Key => r.end_.key ≤ (k : WithTop Key))
|
||
(q := fun k : Key => k ≤ res.keys.getLast hne)]
|
||
have hcrlenA : (cr.keys dA).length = (r.end_.offset - 1).toNat := by
|
||
rw [hcrA_E, hlenA]
|
||
have hgapB : ∀ k ∈ dB.keys, ¬ (r.end_.key ≤ (k : WithTop Key) ∧
|
||
(k : WithTop Key) < r.begin.key) := by
|
||
intro k hkB hkb
|
||
have hkAfter : (k : WithTop Key) <
|
||
((keyAfter (res.keys.getLast hne) : Key) : WithTop Key) :=
|
||
lt_of_lt_of_le (lt_of_lt_of_le hkb.2 hlast_ge_B)
|
||
(le_of_lt (WithTop.coe_lt_coe.mpr (keyAfter_self_lt _)))
|
||
have hkcrB : k ∈ cr.keys dB := by
|
||
rw [ConflictRange.mem_keys_iff]
|
||
refine ⟨hkB, ?_⟩
|
||
change r.end_.key ≤ (k : WithTop Key) ∧
|
||
(k : WithTop Key) < ((keyAfter (res.keys.getLast hne) : Key) : WithTop Key)
|
||
exact ⟨hkb.1, hkAfter⟩
|
||
have hkcrA : k ∈ cr.keys dA := by
|
||
rw [hag]; exact hkcrB
|
||
have hkA : k ∈ dA.keys := (ConflictRange.mem_keys_iff.mp hkcrA).1
|
||
exact hgapA k hkA ⟨hkb.1, hkb.2⟩
|
||
have hcrB : cr.keys dB = (dB.keys.filter
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key)))).filter
|
||
(fun k : Key => decide (k ≤ res.keys.getLast hne)) := by
|
||
simpa [cr] using conflictRange_keys_keyAfter_eq_filter (db := dB)
|
||
(lo := r.end_.key) (last := res.keys.getLast hne)
|
||
have hcrlenB : (cr.keys dB).length = (r.end_.offset - 1).toNat := by
|
||
rw [← hag]; exact hcrlenA
|
||
have hcrB_E : cr.keys dB = dB.keys.filter
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne)) := by
|
||
rw [hcrB, ← filter_and_eq_filter_filter
|
||
(p := fun k : Key => r.end_.key ≤ (k : WithTop Key))
|
||
(q := fun k : Key => k ≤ res.keys.getLast hne)]
|
||
have hlenB : (dB.keys.filter (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne))).length = (r.end_.offset - 1).toNat := by
|
||
rw [← hcrB_E]; exact hcrlenB
|
||
have hwinB := completeKeys_eq_filter_drop_of_no_gap (db := dB) hrev hbegin
|
||
hcross (by omega) hgapB hlenB
|
||
have hfilEeqB := filter_le_le_eq_filter_of_no_between (l := dB.keys)
|
||
(last := res.keys.getLast hne) (le_of_lt hcross) hgapB
|
||
have hcrA_B : cr.keys dA = (dA.keys.filter
|
||
(fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).filter
|
||
(fun k : Key => decide (k ≤ res.keys.getLast hne)) := by
|
||
rw [hcrA, filter_le_eq_filter_of_no_between (l := dA.keys) (le_of_lt hcross) hgapA]
|
||
have hcrB_B : cr.keys dB = (dB.keys.filter
|
||
(fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).filter
|
||
(fun k : Key => decide (k ≤ res.keys.getLast hne)) := by
|
||
rw [hcrB, filter_le_eq_filter_of_no_between (l := dB.keys) (le_of_lt hcross) hgapB]
|
||
have hfB : (dA.keys.filter
|
||
(fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).filter
|
||
(fun k : Key => decide (k ≤ res.keys.getLast hne)) =
|
||
(dB.keys.filter
|
||
(fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).filter
|
||
(fun k : Key => decide (k ≤ res.keys.getLast hne)) := by
|
||
rw [← hcrA_B, ← hcrB_B]; exact hag
|
||
have hconj : dA.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne)) =
|
||
dB.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne)) := by
|
||
rw [filter_and_eq_filter_filter
|
||
(p := fun k : Key => r.begin.key ≤ (k : WithTop Key))
|
||
(q := fun k : Key => k ≤ res.keys.getLast hne),
|
||
filter_and_eq_filter_filter
|
||
(p := fun k : Key => r.begin.key ≤ (k : WithTop Key))
|
||
(q := fun k : Key => k ≤ res.keys.getLast hne)]
|
||
exact hfB
|
||
refine ⟨hcA.1, Or.inr ⟨hmore, ?_⟩⟩
|
||
calc res.keys = RangeRead.completeKeys dA r := hresA
|
||
_ = (dA.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne))).drop (r.begin.offset - 1).toNat := hwinA
|
||
_ = (dB.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key) ∧
|
||
k ≤ res.keys.getLast hne))).drop (r.begin.offset - 1).toNat := by rw [hconj]
|
||
_ = RangeRead.completeKeys dB r := hwinB.symm
|
||
intro db₁ db₂ hagree
|
||
exact ⟨fun hc₁ => step hc₁ hagree, fun hc₂ => step hc₂ hagree.symm⟩
|
||
|
||
/-- **The end selector's key is necessary in the finite crossed branch, at any
|
||
positive begin offset.** In that branch the selector gap is empty, so `end_.key`
|
||
itself is unstored. Inserting it into a database that a sound range omits it from
|
||
leaves the range's keys unchanged but shifts the finite window down by one reported
|
||
key, so the result is no longer complete. -/
|
||
theorem necessary_end_key_of_crossed_finite_general {r : RangeRead} {res : Result} {v : Key}
|
||
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
|
||
(ht : res.keys.countP
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) +
|
||
(r.begin.offset - 1).toNat = (r.end_.offset - 1).toNat)
|
||
(hE : r.end_.key = (↑v : WithTop Key)) :
|
||
Necessary r res v := by
|
||
obtain ⟨db₀, hcomp₀⟩ := hread
|
||
have hres : res.keys = RangeRead.completeKeys db₀ r := by
|
||
rcases hcomp₀.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
|
||
· simp [hmore] at hm
|
||
· exact heq
|
||
have hgap : ∀ k ∈ db₀.keys, ¬ (r.end_.key ≤ (k : WithTop Key) ∧
|
||
(k : WithTop Key) < r.begin.key) :=
|
||
crossed_gap_empty_of_finite (db := db₀) hrev hbegin hcross (by omega) hne hres ht
|
||
have hv0 : v ∉ db₀.keys := by
|
||
intro hmem
|
||
exact hgap v hmem ⟨le_of_eq hE, hE ▸ hcross⟩
|
||
intro cr hs
|
||
by_contra hvcr
|
||
-- Inserting the (unstored) end key changes the finite window.
|
||
let db₁ : DB := db₀.insert v hv0
|
||
have hagree : AgreeOn cr db₀ db₁ :=
|
||
(ConflictRange.keys_insert_of_not_mem cr db₀ hv0 hvcr).symm
|
||
have hcomp₁ : RangeRead.Compatible db₁ r res := (hs db₀ db₁ hagree).mp hcomp₀
|
||
-- The complete keys of `db₁` drop the last reported key.
|
||
set l := db₀.keys with hl
|
||
set p := l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) with hp
|
||
set b := (r.begin.offset - 1).toNat with hb
|
||
set e := (r.end_.offset - 1).toNat with he
|
||
set t := res.keys.length with htlen
|
||
have hcounts := crossed_counts_of_t_add_b_eq_e (db := db₀) hrev hbegin hcross
|
||
(by omega) hne hres ht
|
||
have hcEp : l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) = p := by
|
||
simpa [hl, hp] using hcounts.1
|
||
have hAele : p + e ≤ l.length := by simpa [hl, hp, he] using hcounts.2
|
||
have hcountlen : res.keys.countP
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) = res.keys.length := by
|
||
rw [hres]
|
||
exact completeKeys_count_ge_eq_length_of_crossed_general (db := db₀) hrev hbegin
|
||
hcross (by omega)
|
||
have htb : t + b = e := by
|
||
rw [show t = res.keys.length from rfl]
|
||
omega
|
||
have htpos : 0 < t := List.length_pos_of_ne_nil hne
|
||
have hwin₀ : RangeRead.completeKeys db₀ r = (l.drop (p + b)).take t := by
|
||
have h := completeKeys_eq_drop_take_general (db := db₀) (r := r) hrev hbegin (by omega)
|
||
rw [← hl, ← hp, ← hb, ← he] at h
|
||
rw [h, show min (l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) + e)
|
||
l.length = p + e from by rw [hcEp]; exact Nat.min_eq_left hAele]
|
||
congr 1
|
||
omega
|
||
have hresW : res.keys = (l.drop (p + b)).take t := by rw [hres, hwin₀]
|
||
-- The rank of `v` in `l` is exactly `p`.
|
||
have hcount_v : l.countP (fun k : Key => decide (k < v)) = p := by
|
||
rw [← countP_lt_coe (l := l) v, ← hE]
|
||
exact hcEp
|
||
have hkeys₁ : db₁.keys = l.insertIdx p v := by
|
||
rw [DB.insert_keys, orderedInsert_eq_insertIdx (by rw [hl]; exact db₀.sorted) hv0,
|
||
hcount_v]
|
||
have hcE₁ : db₁.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) = p := by
|
||
rw [hkeys₁,
|
||
countP_insertIdx (p := fun k : Key => decide ((k : WithTop Key) < r.end_.key)) p v
|
||
(by rw [decide_eq_false_iff_not, hE]; exact not_lt.mpr le_rfl)]
|
||
exact hcEp
|
||
have hcB₁ : db₁.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) =
|
||
p + 1 := by
|
||
rw [hkeys₁, ← hcount_v,
|
||
countP_insertIdx_of_lt (l := l) (hs := by rw [hl]; exact db₀.sorted) (x := v)
|
||
(v := r.begin.key) (by rw [← hE]; exact hcross)]
|
||
have : l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) = p := hp
|
||
omega
|
||
have hp_le : p ≤ l.length := by rw [← hcount_v]; exact List.countP_le_length
|
||
have hlen₁ : db₁.keys.length = l.length + 1 := by
|
||
rw [hkeys₁, insertIdx_eq_take_drop l p v hp_le,
|
||
List.length_append, List.length_cons, List.length_drop, List.length_take,
|
||
Nat.min_eq_left hp_le]
|
||
omega
|
||
have hdrop : (l.insertIdx p v).drop (p + 1 + b) = l.drop (p + b) := by
|
||
rw [insertIdx_eq_take_drop l p v hp_le, List.drop_append,
|
||
List.drop_eq_nil_of_le (by rw [List.length_take]; omega), List.length_take,
|
||
Nat.min_eq_left hp_le]
|
||
have hsub : p + 1 + b - p = b + 1 := by omega
|
||
rw [hsub, List.drop_succ_cons, List.drop_drop]
|
||
rfl
|
||
have hck₁ : RangeRead.completeKeys db₁ r = res.keys.take (t - 1) := by
|
||
have h := completeKeys_eq_drop_take_general (db := db₁) (r := r) hrev hbegin (by omega)
|
||
rw [h, hcB₁, hcE₁, hlen₁, hkeys₁, hdrop, Nat.min_eq_left (by omega)]
|
||
have hidx : p + e - (p + 1 + b) = t - 1 := by omega
|
||
rw [hidx, hresW, List.take_take, Nat.min_eq_left (by omega)]
|
||
have htake_ne : res.keys.take (t - 1) ≠ res.keys := by
|
||
intro heq
|
||
have hlen := congrArg List.length heq
|
||
rw [List.length_take, htlen] at hlen
|
||
omega
|
||
have hnotcomp : ¬ RangeRead.Compatible db₁ r res := by
|
||
intro hc
|
||
have heq : res.keys = RangeRead.completeKeys db₁ r := by
|
||
rcases hc.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
|
||
· simp [hmore] at hm
|
||
· exact heq
|
||
exact htake_ne (by rw [← hck₁, ← heq])
|
||
exact hnotcomp hcomp₁
|
||
|
||
/-- **Finite crossed complete-branch minimality at any positive begin offset.**
|
||
When `t + (begin.offset - 1) = end.offset - 1` the minimal range is
|
||
`[end_.key, keyAfter (last reported))`. Soundness is
|
||
`sound_truncatedRange_of_crossed_finite_general`; every key in the range lies between
|
||
the necessary end key and the necessary last reported key. -/
|
||
theorem minimal_truncatedRange_of_crossed_finite_general {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
|
||
(ht : res.keys.countP
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) +
|
||
(r.begin.offset - 1).toNat = (r.end_.offset - 1).toNat) :
|
||
Minimal r res ⟨r.end_.key, (keyAfter (res.keys.getLastD ([] : Key)) : WithTop Key)⟩ := by
|
||
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by
|
||
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
|
||
rw [minimal_iff_sound_and_necessaryRange]
|
||
refine ⟨sound_truncatedRange_of_crossed_finite_general hread hmore hne hrev hbegin
|
||
hcross hend ht, ?_⟩
|
||
intro k hkE hklt
|
||
have hEne : r.end_.key ≠ (⊤ : WithTop Key) := by
|
||
intro htop
|
||
rw [htop] at hcross
|
||
exact absurd hcross (not_lt.mpr le_top)
|
||
obtain ⟨v, hv⟩ := WithTop.ne_top_iff_exists.mp hEne
|
||
have hEnec : Necessary r res v :=
|
||
necessary_end_key_of_crossed_finite_general hread hmore hne hrev hbegin hcross hend ht
|
||
hv.symm
|
||
have hlastnec : Necessary r res (res.keys.getLastD ([] : Key)) := by
|
||
rw [hlast]
|
||
exact necessary_of_mem_result hread (List.getLast_mem hne)
|
||
have hklast : k ≤ res.keys.getLastD ([] : Key) :=
|
||
(lt_keyAfter_iff k (res.keys.getLastD ([] : Key))).mp (WithTop.coe_lt_coe.mp hklt)
|
||
exact hEnec.of_between hlastnec (WithTop.coe_le_coe.mp (hv.symm ▸ hkE)) hklast
|
||
|
||
/-- A key strictly inside the gap is needed to compute the complete keys; the room
|
||
bound makes the whole window a prefix of the stored keys at or above `begin.key`.
|
||
This is the general-offset form of `completeKeys_eq_iff_filter_ge_begin_of_room`.
|
||
The extra `begin.offset - 1` reflects that the window starts that many keys into
|
||
the `[begin.key, ⊤)` group. -/
|
||
theorem completeKeys_eq_iff_filter_drop_of_room_general {db : DB} {r : RangeRead}
|
||
{res : Result}
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hend : 1 ≤ r.end_.offset) (hEB : r.end_.key ≤ r.begin.key)
|
||
(hne : res.keys ≠ [])
|
||
(hroom : res.keys.length + (r.begin.offset - 1).toNat +
|
||
(db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) -
|
||
db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)))
|
||
< (r.end_.offset - 1).toNat) :
|
||
RangeRead.completeKeys db r = res.keys ↔
|
||
(db.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).drop
|
||
(r.begin.offset - 1).toNat = res.keys := by
|
||
set l := db.keys with hl
|
||
set p := l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) with hp
|
||
set cE := l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) with hcE
|
||
set b := (r.begin.offset - 1).toNat with hb
|
||
set e := (r.end_.offset - 1).toNat with he
|
||
have hls : l.SortedLT := by rw [hl]; exact db.sorted
|
||
have hroom' : res.keys.length + b + (p - cE) < e := by
|
||
simpa [← hl, ← hp, ← hcE, ← hb, ← he] using hroom
|
||
have hcEp : cE ≤ p := by
|
||
rw [hp, hcE]
|
||
apply countP_le_countP_of_imp
|
||
intro k _ hk
|
||
rw [decide_eq_true_eq] at hk ⊢
|
||
exact lt_of_lt_of_le hk hEB
|
||
have hp_le : p ≤ l.length := by rw [hp]; exact List.countP_le_length
|
||
have hlen : (RangeRead.completeKeys db r).length =
|
||
min (cE + e) l.length - (p + b) := by
|
||
have h := completeKeys_length_general (db := db) (r := r) hrev hbegin hend
|
||
simpa [← hl, ← hp, ← hcE, ← hb, ← he] using h
|
||
have hA : l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) =
|
||
l.drop p := by
|
||
have hnot : l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) =
|
||
l.filter (fun k : Key => decide (¬ ((k : WithTop Key) < r.begin.key))) := by
|
||
apply List.filter_congr
|
||
intro k _
|
||
rw [decide_eq_decide]
|
||
exact not_lt.symm
|
||
rw [hnot, filter_not_lt_eq_drop_countP hls r.begin.key, ← hp]
|
||
have hdrop_drop : l.drop (p + b) = (l.drop p).drop b := by
|
||
rw [List.drop_drop]
|
||
constructor
|
||
· intro hck
|
||
have hLres : res.keys.length = min (cE + e) l.length - (p + b) := by
|
||
rw [hck] at hlen
|
||
exact hlen
|
||
have hpos : 0 < min (cE + e) l.length - (p + b) := by
|
||
rw [← hLres]
|
||
exact List.length_pos_of_ne_nil hne
|
||
have hpb_le : p + b ≤ min (cE + e) l.length := by omega
|
||
have hmin : min (cE + e) l.length = l.length := by
|
||
rcases le_total (cE + e) l.length with hle | hle
|
||
· exfalso
|
||
have hMeq : min (cE + e) l.length = cE + e := Nat.min_eq_left hle
|
||
have hlen' : res.keys.length = cE + e - (p + b) := by
|
||
rw [hMeq] at hLres; exact hLres
|
||
have hsum : res.keys.length + (p + b) = cE + e := by omega
|
||
have harith : res.keys.length + b + (p - cE) = e := by omega
|
||
omega
|
||
· exact Nat.min_eq_right hle
|
||
have hfull : RangeRead.completeKeys db r = l.drop (p + b) := by
|
||
rw [completeKeys_eq_drop_take_general (db := db) (r := r) hrev hbegin hend]
|
||
rw [← hl, ← hp, ← hcE, ← hb, ← he, hmin, ← List.length_drop]
|
||
exact List.take_length
|
||
rw [hA, ← hdrop_drop]
|
||
rw [← hfull]
|
||
exact hck
|
||
· intro hfil
|
||
have hA_drop : (l.drop p).drop b = res.keys := by
|
||
rw [← hA]
|
||
exact hfil
|
||
have hq_eq : (l.drop p).length = l.length - p := List.length_drop
|
||
have hb_le_q : b ≤ (l.drop p).length := by
|
||
by_contra hlt
|
||
have hemp : (l.drop p).drop b = [] := List.drop_eq_nil_of_le (by omega)
|
||
rw [hemp] at hA_drop
|
||
exact hne hA_drop.symm
|
||
have hreslen : res.keys.length = (l.drop p).length - b := by
|
||
rw [← hA_drop, List.length_drop]
|
||
have hq_eq' : (l.drop p).length = l.length - p := List.length_drop
|
||
have hlt_len : l.length < cE + e := by
|
||
have hsum : res.keys.length + b + (p - cE) < e := hroom'
|
||
have hlenq : res.keys.length + b = l.length - p := by omega
|
||
omega
|
||
have hmin : min (cE + e) l.length = l.length := Nat.min_eq_right (le_of_lt hlt_len)
|
||
have hfull : RangeRead.completeKeys db r = l.drop (p + b) := by
|
||
rw [completeKeys_eq_drop_take_general (db := db) (r := r) hrev hbegin hend]
|
||
rw [← hl, ← hp, ← hcE, ← hb, ← he, hmin, ← List.length_drop]
|
||
exact List.take_length
|
||
rw [hfull, hdrop_drop, hA_drop]
|
||
|
||
/-- **Small-room crossed compatibility at any positive begin offset.** If the gap
|
||
`[end_.key, begin_.key)` has fewer than the remaining overshoot
|
||
`e - t - (begin.offset - 1)` keys, then the end key may be moved up to the begin key
|
||
without changing compatibility. This is the general-offset form of
|
||
`compatible_crossed_iff_endKeyToBegin_of_room`. -/
|
||
theorem compatible_crossed_iff_endKeyToBegin_of_room_general {r : RangeRead} {res : Result}
|
||
(_hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
|
||
(htb : res.keys.length + (r.begin.offset - 1).toNat <
|
||
(r.end_.offset - 1).toNat)
|
||
(hroom : intervalCard r.end_.key r.begin.key <
|
||
(((r.end_.offset - 1).toNat - res.keys.length -
|
||
(r.begin.offset - 1).toNat : ℕ) : ℕ∞)) :
|
||
∀ db : DB, RangeRead.Compatible db r res ↔
|
||
RangeRead.Compatible db (endKeyToBegin r) res := by
|
||
set b := (r.begin.offset - 1).toNat with hb
|
||
set e := (r.end_.offset - 1).toNat with he
|
||
have htb' : res.keys.length + b < e := by simpa [hb, he] using htb
|
||
intro db
|
||
have hgap_le : ((db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) -
|
||
db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) : ℕ) : ℕ∞) ≤
|
||
intervalCard r.end_.key r.begin.key := by
|
||
simpa [cnt] using cnt_sub_le_intervalCard db (le_of_lt hcross)
|
||
have hgap_lt : (db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) -
|
||
db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key))) <
|
||
e - res.keys.length - b := by
|
||
have h1 : ((db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) -
|
||
db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) :Nat) : ℕ∞) <
|
||
(((e - res.keys.length - b : ℕ)) : ℕ∞) := by
|
||
simpa [hb, he] using lt_of_le_of_lt hgap_le hroom
|
||
exact_mod_cast h1
|
||
have hroom_db : res.keys.length + b +
|
||
(db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) -
|
||
db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key))) < e := by
|
||
omega
|
||
have hA : db.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) =
|
||
db.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) := rfl
|
||
have hbase_r : RangeRead.Compatible db r res ↔
|
||
RangeRead.withinLimit r res.keys ∧
|
||
(db.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).drop b =
|
||
res.keys := by
|
||
constructor
|
||
· rintro ⟨hlim, hdisj | ⟨_, heq⟩⟩
|
||
· simp [hmore] at hdisj
|
||
· exact ⟨hlim, (completeKeys_eq_iff_filter_drop_of_room_general
|
||
(db := db) (r := r) (res := res) hrev hbegin (by omega) (le_of_lt hcross)
|
||
hne hroom_db).mp heq.symm⟩
|
||
· rintro ⟨hlim, hfil⟩
|
||
refine ⟨hlim, Or.inr ⟨hmore, ?_⟩⟩
|
||
exact ((completeKeys_eq_iff_filter_drop_of_room_general
|
||
(db := db) (r := r) (res := res) hrev hbegin (by omega) (le_of_lt hcross)
|
||
hne hroom_db).mpr hfil).symm
|
||
have hbase_r' : RangeRead.Compatible db (endKeyToBegin r) res ↔
|
||
RangeRead.withinLimit r res.keys ∧
|
||
(db.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).drop b =
|
||
res.keys := by
|
||
have hroom_db' : res.keys.length + b +
|
||
(db.keys.countP (fun k : Key => decide ((k : WithTop Key) <
|
||
(endKeyToBegin r).begin.key)) -
|
||
db.keys.countP (fun k : Key => decide ((k : WithTop Key) <
|
||
(endKeyToBegin r).end_.key))) < e := by
|
||
have h1 : (endKeyToBegin r).begin.key = r.begin.key := rfl
|
||
have h2 : (endKeyToBegin r).end_.key = r.begin.key := rfl
|
||
rw [h1, h2]
|
||
have : db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) -
|
||
db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) = 0 :=
|
||
Nat.sub_self _
|
||
rw [this, Nat.add_zero]
|
||
exact htb'
|
||
constructor
|
||
· rintro ⟨hlim, hdisj | ⟨_, heq⟩⟩
|
||
· simp [hmore] at hdisj
|
||
· refine ⟨?_, (completeKeys_eq_iff_filter_drop_of_room_general
|
||
(db := db) (r := endKeyToBegin r) (res := res) (by simpa [endKeyToBegin] using hrev)
|
||
(by simpa [endKeyToBegin] using hbegin) (by simpa [endKeyToBegin] using (by omega : 1 ≤
|
||
r.end_.offset))
|
||
(by simp [endKeyToBegin]) hne hroom_db').mp heq.symm⟩
|
||
simpa [endKeyToBegin, RangeRead.withinLimit] using hlim
|
||
· rintro ⟨hlim, hfil⟩
|
||
refine ⟨?_, Or.inr ⟨hmore, ?_⟩⟩
|
||
· simpa [endKeyToBegin, RangeRead.withinLimit] using hlim
|
||
· exact ((completeKeys_eq_iff_filter_drop_of_room_general
|
||
(db := db) (r := endKeyToBegin r) (res := res) (by simpa [endKeyToBegin] using hrev)
|
||
(by simpa [endKeyToBegin] using hbegin) (by simpa [endKeyToBegin] using (by omega : 1 ≤
|
||
r.end_.offset))
|
||
(by simp [endKeyToBegin]) hne hroom_db').mpr hfil).symm
|
||
rw [hbase_r, hbase_r']
|
||
|
||
/-- **Crossed complete top branch with little room below the begin key, at any
|
||
positive begin offset.** If the gap `[end_.key, begin_.key)` holds fewer than the
|
||
remaining overshoot `e - t - (begin.offset - 1)` keys, the minimal range is
|
||
`[begin.key, ⊤)`: moving the end key up to the begin key gives a key-equal read
|
||
with the same compatible databases, and the key-equal read's top branch is
|
||
`minimal_closedForm_of_key_eq_complete_general`. -/
|
||
theorem minimal_topRange_of_crossed_small_room_general {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
|
||
(htb : res.keys.length + (r.begin.offset - 1).toNat <
|
||
(r.end_.offset - 1).toNat)
|
||
(hroom : intervalCard r.end_.key r.begin.key <
|
||
(((r.end_.offset - 1).toNat - res.keys.length -
|
||
(r.begin.offset - 1).toNat : ℕ) : ℕ∞)) :
|
||
Minimal r res ⟨r.begin.key, ⊤⟩ := by
|
||
let r' := endKeyToBegin r
|
||
have hiff := compatible_crossed_iff_endKeyToBegin_of_room_general hread hmore hne hrev
|
||
hbegin hcross hend htb hroom
|
||
have hall_ge : ∀ k ∈ res.keys, r.begin.key ≤ (k : WithTop Key) :=
|
||
crossed_mem_result_ge_begin_general hread hmore hbegin
|
||
obtain ⟨db₀, hcomp₀⟩ := hread
|
||
have hread' : Readable r' res := ⟨db₀, (hiff db₀).mp hcomp₀⟩
|
||
have hcount : res.keys.countP
|
||
(fun k : Key => decide (r'.end_.key ≤ (k : WithTop Key))) = res.keys.length := by
|
||
rw [List.countP_eq_length]
|
||
intro k hk
|
||
rw [decide_eq_true_eq]
|
||
simpa [r', endKeyToBegin] using hall_ge k hk
|
||
have htne : res.keys.countP
|
||
(fun k : Key => decide (r'.end_.key ≤ (k : WithTop Key))) +
|
||
(r'.begin.offset - 1).toNat ≠ (r'.end_.offset - 1).toNat := by
|
||
rw [hcount]
|
||
simpa [r', endKeyToBegin] using (ne_of_lt htb)
|
||
have hmin' : Minimal r' res (closedFormKeyEqComplete r' res) :=
|
||
minimal_closedForm_of_key_eq_complete_general hread' hmore
|
||
(by simpa [r', endKeyToBegin] using hrev) hne
|
||
(by simpa [r', endKeyToBegin] using hbegin) (by simp [r', endKeyToBegin])
|
||
(by simpa [r', endKeyToBegin] using hend)
|
||
have hform : closedFormKeyEqComplete r' res = ⟨r.begin.key, ⊤⟩ := by
|
||
unfold closedFormKeyEqComplete
|
||
rw [ite_eq_right htne]
|
||
simp [topRange, r', endKeyToBegin]
|
||
rw [hform] at hmin'
|
||
exact minimal_of_compatible_iff hiff hmin'
|
||
|
||
|
||
/-- For a complete crossed result at positive begin offset, the `begin.offset - 1`
|
||
stored keys just above `begin.key` and before the first reported key exist, are
|
||
sorted, lie at or above `begin.key`, and lie strictly below every reported key. -/
|
||
theorem crossed_pad_general {db : DB} {r : RangeRead} {res : Result}
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(_hcross : r.end_.key < r.begin.key) (hend : 1 ≤ r.end_.offset)
|
||
(hne : res.keys ≠ []) (hres : res.keys = RangeRead.completeKeys db r) :
|
||
∃ P : List Key, P.length = (r.begin.offset - 1).toNat ∧ P.SortedLT ∧
|
||
(∀ x ∈ P, r.begin.key ≤ (x : WithTop Key)) ∧
|
||
(∀ x ∈ P, ∀ y ∈ res.keys, x < y) ∧
|
||
(P ++ res.keys).SortedLT := by
|
||
set l := db.keys with hl
|
||
set p := l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) with hp
|
||
set b := (r.begin.offset - 1).toNat with hb
|
||
set A := l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) with hAdef
|
||
have hls : l.SortedLT := by rw [hl]; exact db.sorted
|
||
have hA : A = l.drop p := by
|
||
rw [hAdef]
|
||
have hnot : l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) =
|
||
l.filter (fun k : Key => decide (¬ ((k : WithTop Key) < r.begin.key))) := by
|
||
apply List.filter_congr
|
||
intro k _
|
||
rw [decide_eq_decide]
|
||
exact not_lt.symm
|
||
rw [hnot, filter_not_lt_eq_drop_countP hls r.begin.key, ← hp]
|
||
have hAs : A.SortedLT := by
|
||
rw [hA]
|
||
exact List.sortedLT_iff_pairwise.mpr (List.Pairwise.drop (i := p) hls.pairwise)
|
||
have hAge : ∀ x ∈ A, r.begin.key ≤ (x : WithTop Key) := by
|
||
intro x hx
|
||
rw [hAdef] at hx
|
||
exact of_decide_eq_true (List.mem_filter.mp hx).2
|
||
-- The complete window is a truncated tail of `A.drop b`.
|
||
set K := min (l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) +
|
||
(r.end_.offset - 1).toNat) l.length - (p + b) with hK
|
||
have hck : RangeRead.completeKeys db r = (A.drop b).take K := by
|
||
rw [completeKeys_eq_drop_take_general (db := db) (r := r) hrev hbegin hend]
|
||
rw [← hl, ← hp, ← hb, hA, List.drop_drop, hK]
|
||
have hresK : res.keys = (A.drop b).take K := by rw [hres, hck]
|
||
have htake_ne : (A.drop b).take K ≠ [] := by rw [← hresK]; exact hne
|
||
have hdrop_ne : A.drop b ≠ [] := fun hnil => htake_ne (by rw [hnil]; simp)
|
||
have hb_lt_A : b < A.length := by
|
||
have := List.length_pos_of_ne_nil hdrop_ne
|
||
rw [List.length_drop] at this
|
||
omega
|
||
have hKpos : 0 < K := by
|
||
have := List.length_pos_of_ne_nil htake_ne
|
||
rw [List.length_take] at this
|
||
omega
|
||
let P := A.take b
|
||
have hPdef : P = A.take b := rfl
|
||
have hPlen : P.length = b := by
|
||
rw [hPdef, List.length_take, Nat.min_eq_left (le_of_lt hb_lt_A)]
|
||
have hPs : P.SortedLT := by
|
||
rw [hPdef]
|
||
exact List.sortedLT_iff_pairwise.mpr (List.Pairwise.take (i := b)
|
||
(List.sortedLT_iff_pairwise.mp hAs))
|
||
have hPge : ∀ x ∈ P, r.begin.key ≤ (x : WithTop Key) := by
|
||
intro x hx
|
||
exact hAge x (List.take_subset _ _ (by rw [← hPdef]; exact hx))
|
||
have happend : A = P ++ A.drop b := by rw [hPdef, List.take_append_drop]
|
||
have hcross : ∀ x ∈ P, ∀ y ∈ A.drop b, x < y := by
|
||
have := List.sortedLT_append.mp (by rw [← happend]; exact hAs)
|
||
exact this.2.2
|
||
have hP_lt_res : ∀ x ∈ P, ∀ y ∈ res.keys, x < y := by
|
||
intro x hx y hy
|
||
have hy' : y ∈ A.drop b := by
|
||
rw [hresK] at hy
|
||
exact List.mem_of_mem_take hy
|
||
exact hcross x hx y hy'
|
||
have hdropS : (A.drop b).SortedLT :=
|
||
List.sortedLT_iff_pairwise.mpr (List.Pairwise.drop (i := b)
|
||
(List.sortedLT_iff_pairwise.mp hAs))
|
||
have hresS : res.keys.SortedLT := by
|
||
rw [hresK]
|
||
exact List.sortedLT_iff_pairwise.mpr (List.Pairwise.take (i := K)
|
||
(List.sortedLT_iff_pairwise.mp hdropS))
|
||
refine ⟨P, ?_, hPs, hPge, hP_lt_res, ?_⟩
|
||
· rw [hPlen, hb]
|
||
· exact List.sortedLT_append.mpr ⟨hPs, hresS, hP_lt_res⟩
|
||
|
||
|
||
/-- Generic complete-window computation for a database of the form `P ++ res` with
|
||
`P` padding of length `b`, all at or above the begin key and below the reported keys. -/
|
||
theorem completeKeys_pad_eq_general {r : RangeRead} {res : Result} {P : List Key}
|
||
(_hPs : P.SortedLT) (_hresS : res.keys.SortedLT)
|
||
(hPlen : P.length = (r.begin.offset - 1).toNat)
|
||
(hPge : ∀ x ∈ P, r.begin.key ≤ (x : WithTop Key))
|
||
(hresge : ∀ y ∈ res.keys, r.begin.key ≤ (y : WithTop Key))
|
||
(_hPlt : ∀ x ∈ P, ∀ y ∈ res.keys, x < y)
|
||
(hsort : (P ++ res.keys).SortedLT)
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 1 ≤ r.end_.offset)
|
||
(ht : res.keys.length + (r.begin.offset - 1).toNat < (r.end_.offset - 1).toNat) :
|
||
RangeRead.completeKeys (⟨P ++ res.keys, hsort⟩ : DB) r = res.keys := by
|
||
set b := (r.begin.offset - 1).toNat with hb
|
||
set e := (r.end_.offset - 1).toNat with he
|
||
let db : DB := ⟨P ++ res.keys, hsort⟩
|
||
have hkeys : db.keys = P ++ res.keys := rfl
|
||
have hp0 : db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) = 0 := by
|
||
change cnt db r.begin.key = 0
|
||
apply cnt_eq_zero_of_forall_ge
|
||
intro x hx
|
||
rw [hkeys] at hx
|
||
rcases List.mem_append.mp hx with hxP | hxR
|
||
· exact hPge x hxP
|
||
· exact hresge x hxR
|
||
have hcE0 : db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) = 0 := by
|
||
change cnt db r.end_.key = 0
|
||
apply cnt_eq_zero_of_forall_ge
|
||
intro x hx
|
||
rw [hkeys] at hx
|
||
rcases List.mem_append.mp hx with hxP | hxR
|
||
· exact le_trans (le_of_lt hcross) (hPge x hxP)
|
||
· exact le_trans (le_of_lt hcross) (hresge x hxR)
|
||
have hlen : db.keys.length = b + res.keys.length := by
|
||
rw [hkeys, List.length_append, hPlen]
|
||
have hmin : min (db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) + e)
|
||
db.keys.length = b + res.keys.length := by
|
||
rw [hcE0, Nat.zero_add, hlen]
|
||
exact Nat.min_eq_right (le_of_lt (by omega))
|
||
rw [completeKeys_eq_drop_take_general (db := db) (r := r) hrev hbegin hend]
|
||
rw [hp0, Nat.zero_add]
|
||
rw [hcE0, Nat.zero_add, hlen, Nat.min_eq_right (le_of_lt (by omega))]
|
||
have hsub : b + res.keys.length - b = res.keys.length := by omega
|
||
rw [hsub, hkeys, ← hb, ← hPlen, List.drop_append_of_le_length le_rfl]
|
||
simp
|
||
|
||
|
||
theorem completeKeys_length_pad_general {r : RangeRead} {res : Result} {Q : List Key}
|
||
(_hQs : Q.SortedLT) (hsort : (Q ++ res.keys).SortedLT)
|
||
(hQge : ∀ x ∈ Q, r.begin.key ≤ (x : WithTop Key))
|
||
(hresge : ∀ y ∈ res.keys, r.begin.key ≤ (y : WithTop Key))
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 1 ≤ r.end_.offset) :
|
||
(RangeRead.completeKeys (⟨Q ++ res.keys, hsort⟩ : DB) r).length =
|
||
min ((r.end_.offset - 1).toNat) (Q.length + res.keys.length) -
|
||
(r.begin.offset - 1).toNat := by
|
||
let db : DB := ⟨Q ++ res.keys, hsort⟩
|
||
have hkeys : db.keys = Q ++ res.keys := rfl
|
||
have hp0 : db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) = 0 := by
|
||
change cnt db r.begin.key = 0
|
||
apply cnt_eq_zero_of_forall_ge
|
||
intro x hx
|
||
rw [hkeys] at hx
|
||
rcases List.mem_append.mp hx with hxQ | hxR
|
||
· exact hQge x hxQ
|
||
· exact hresge x hxR
|
||
have hcE0 : db.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) = 0 := by
|
||
change cnt db r.end_.key = 0
|
||
apply cnt_eq_zero_of_forall_ge
|
||
intro x hx
|
||
rw [hkeys] at hx
|
||
rcases List.mem_append.mp hx with hxQ | hxR
|
||
· exact le_trans (le_of_lt hcross) (hQge x hxQ)
|
||
· exact le_trans (le_of_lt hcross) (hresge x hxR)
|
||
have hlen : db.keys.length = Q.length + res.keys.length := by
|
||
rw [hkeys, List.length_append]
|
||
rw [completeKeys_length_general (db := db) (r := r) hrev hbegin hend]
|
||
rw [hp0, hcE0, Nat.zero_add, Nat.zero_add, hlen]
|
||
|
||
|
||
theorem necessary_of_begin_le_crossed_top_general {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = false)
|
||
(hne : res.keys ≠ []) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
|
||
(ht : res.keys.length + (r.begin.offset - 1).toNat < (r.end_.offset - 1).toNat)
|
||
{x : Key} (hx : r.begin.key ≤ (x : WithTop Key)) : Necessary r res x := by
|
||
set b := (r.begin.offset - 1).toNat with hb
|
||
set e := (r.end_.offset - 1).toNat with he
|
||
obtain ⟨db₀, hcomp₀⟩ := hread
|
||
have hres : res.keys = RangeRead.completeKeys db₀ r := by
|
||
rcases hcomp₀.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
|
||
· simp [hmore] at hm
|
||
· exact heq
|
||
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
|
||
have hall_ge : ∀ y ∈ res.keys, r.begin.key ≤ (y : WithTop Key) :=
|
||
crossed_mem_result_ge_begin_general ⟨db₀, hcomp₀⟩ hmore hbegin
|
||
by_cases hxmem : x ∈ res.keys
|
||
· exact necessary_of_mem_result ⟨db₀, hcomp₀⟩ hxmem
|
||
obtain ⟨P, hPlen, hPs, hPge, hPlt, hPsort⟩ :=
|
||
crossed_pad_general (db := db₀) hrev hbegin hcross (by omega) hne hres
|
||
have hPlen' : P.length = b := by simpa [hb] using hPlen
|
||
have hPge' : ∀ y ∈ P, r.begin.key ≤ (y : WithTop Key) := by
|
||
intro y hy; simpa using hPge y hy
|
||
have hhall : ∀ y ∈ res.keys, r.begin.key ≤ (y : WithTop Key) := hall_ge
|
||
by_cases hxP : x ∈ P
|
||
· -- `x` is already one of the padding keys: erase it to obtain the base.
|
||
let dT : DB := ⟨P ++ res.keys, hPsort⟩
|
||
have hcompT : RangeRead.Compatible dT r res := by
|
||
refine ⟨hcomp₀.1, Or.inr ⟨hmore, ?_⟩⟩
|
||
exact (completeKeys_pad_eq_general (r := r) (res := res) (P := P) hPs hsort
|
||
hPlen' hPge' hhall hPlt hPsort hrev hbegin hcross (by omega) (by omega)).symm
|
||
let dB : DB := dT.erase x
|
||
have hdBkeys : dB.keys = P.erase x ++ res.keys := by
|
||
simp only [dB, dT, DB.erase_keys]
|
||
rw [List.erase_append, ite_eq_left hxP]
|
||
have hQlen : (P.erase x).length = b - 1 := by
|
||
rw [List.length_erase_of_mem hxP, hPlen']
|
||
have hQs : (P.erase x).SortedLT :=
|
||
List.sortedLT_iff_pairwise.mpr (List.Pairwise.erase x (List.sortedLT_iff_pairwise.mp hPs))
|
||
have hQge : ∀ y ∈ P.erase x, r.begin.key ≤ (y : WithTop Key) :=
|
||
fun y hy => hPge' y (List.mem_of_mem_erase hy)
|
||
have hQsort : (P.erase x ++ res.keys).SortedLT := by
|
||
rw [← hdBkeys]
|
||
exact dB.sorted
|
||
have hdB : dB = ⟨P.erase x ++ res.keys, hQsort⟩ := by
|
||
change dT.erase x = ⟨P.erase x ++ res.keys, hQsort⟩
|
||
have hk : (dT.erase x).keys = P.erase x ++ res.keys := hdBkeys
|
||
generalize hd : dT.erase x = d at hk ⊢
|
||
cases d with
|
||
| mk ks hs =>
|
||
simp only [DB.mk.injEq] at hk ⊢
|
||
exact hk
|
||
have hlenB : (RangeRead.completeKeys dB r).length = res.keys.length - 1 := by
|
||
have h := completeKeys_length_pad_general (r := r) (res := res) (Q := P.erase x)
|
||
hQs hQsort hQge hhall hrev hbegin hcross (by omega)
|
||
rw [hdB, h, hQlen, ← he, ← hb]
|
||
have hlt : b - 1 + res.keys.length < e := by omega
|
||
rw [Nat.min_eq_right (le_of_lt hlt)]
|
||
have htpos : 0 < res.keys.length := List.length_pos_of_ne_nil hne
|
||
have hbpos : 0 < b := by
|
||
rw [← hPlen']
|
||
exact List.length_pos_of_ne_nil (fun h => by simp [h] at hxP)
|
||
omega
|
||
have hnotB : ¬ RangeRead.Compatible dB r res := by
|
||
intro hc
|
||
have heq : res.keys = RangeRead.completeKeys dB r := by
|
||
rcases hc.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
|
||
· simp [hmore] at hm
|
||
· exact heq
|
||
have hlen := congrArg List.length heq
|
||
rw [hlenB] at hlen
|
||
have htpos : 0 < res.keys.length := List.length_pos_of_ne_nil hne
|
||
omega
|
||
intro cr hs
|
||
by_contra hxcr
|
||
have hagree : AgreeOn cr dT dB :=
|
||
(ConflictRange.keys_erase_of_not_mem cr dT hxcr).symm
|
||
exact hnotB ((hs dT dB hagree).mp hcompT)
|
||
· -- `x` is not padding: use `P ++ res` as base and insert `x`.
|
||
let dB : DB := ⟨P ++ res.keys, hPsort⟩
|
||
have hxdb : x ∉ dB.keys := by
|
||
simp only [dB, List.mem_append]
|
||
rintro (hxp | hxr)
|
||
· exact hxP hxp
|
||
· exact hxmem hxr
|
||
have hcompB : RangeRead.Compatible dB r res := by
|
||
refine ⟨hcomp₀.1, Or.inr ⟨hmore, ?_⟩⟩
|
||
exact (completeKeys_pad_eq_general (r := r) (res := res) (P := P) hPs hsort
|
||
hPlen' hPge' hhall hPlt hPsort hrev hbegin hcross (by omega) (by omega)).symm
|
||
let dT : DB := dB.insert x hxdb
|
||
have hxT : ∀ y ∈ dT.keys, r.begin.key ≤ (y : WithTop Key) := by
|
||
intro y hy
|
||
rw [show dT = dB.insert x hxdb from rfl, DB.mem_insert_iff hxdb] at hy
|
||
rcases hy with rfl | hy
|
||
· exact hx
|
||
· rw [show dB = ⟨P ++ res.keys, hPsort⟩ from rfl, List.mem_append] at hy
|
||
rcases hy with hP | hR
|
||
· exact hPge' y hP
|
||
· exact hhall y hR
|
||
have hpT : dT.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) = 0 := by
|
||
change cnt dT r.begin.key = 0
|
||
apply cnt_eq_zero_of_forall_ge
|
||
exact fun y hy => hxT y hy
|
||
have hcET : dT.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) = 0 := by
|
||
change cnt dT r.end_.key = 0
|
||
apply cnt_eq_zero_of_forall_ge
|
||
intro y hy
|
||
exact le_trans (le_of_lt hcross) (hxT y hy)
|
||
have hlenT : (RangeRead.completeKeys dT r).length = res.keys.length + 1 := by
|
||
have h := completeKeys_length_general (db := dT) (r := r) hrev hbegin (by omega)
|
||
rw [h, hpT, hcET, Nat.zero_add, Nat.zero_add]
|
||
have hlen : dT.keys.length = P.length + res.keys.length + 1 := by
|
||
rw [show dT = dB.insert x hxdb from rfl, DB.insert_keys, List.orderedInsert_length]
|
||
simp only [dB, List.length_append, hPlen']
|
||
rw [hlen, hPlen', ← hb, ← he]
|
||
have hlt : b + res.keys.length + 1 ≤ e := by omega
|
||
rw [Nat.min_eq_right hlt]
|
||
omega
|
||
have hnotT : ¬ RangeRead.Compatible dT r res := by
|
||
intro hc
|
||
have heq : res.keys = RangeRead.completeKeys dT r := by
|
||
rcases hc.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
|
||
· simp [hmore] at hm
|
||
· exact heq
|
||
have hlen := congrArg List.length heq
|
||
rw [hlenT] at hlen
|
||
omega
|
||
intro cr hs
|
||
by_contra hxcr
|
||
have hagree : AgreeOn cr dB dT :=
|
||
(ConflictRange.keys_insert_of_not_mem cr dB hxdb hxcr).symm
|
||
exact hnotT ((hs dB dT hagree).mp hcompB)
|
||
|
||
|
||
|
||
theorem orderedInsert_append_of_forall_lt {l r : List Key} {k : Key}
|
||
(h : ∀ x ∈ r, k < x) :
|
||
(l ++ r).orderedInsert (· ≤ ·) k = l.orderedInsert (· ≤ ·) k ++ r := by
|
||
induction l with
|
||
| nil =>
|
||
have hr : r.orderedInsert (· ≤ ·) k = k :: r := by
|
||
induction r with
|
||
| nil => simp
|
||
| cons a t ih =>
|
||
have hka : k ≤ a := le_of_lt (h a (by simp))
|
||
rw [List.orderedInsert_cons, ite_eq_left hka]
|
||
simp [hr]
|
||
| cons a l ih =>
|
||
by_cases hka : k ≤ a
|
||
· rw [List.cons_append, List.orderedInsert_cons, ite_eq_left hka,
|
||
List.orderedInsert_cons, ite_eq_left hka]
|
||
simp
|
||
· rw [List.cons_append, List.orderedInsert_cons, ite_eq_right hka,
|
||
List.orderedInsert_cons, ite_eq_right hka, ih]
|
||
simp
|
||
|
||
/-- **Necessity of every key in `[end_.key, begin_.key)` in the crossed top branch at
|
||
any positive begin offset.** -/
|
||
theorem necessary_of_mem_interval_crossed_top_general {r : RangeRead} {res : Result} {k : Key}
|
||
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = false)
|
||
(hne : res.keys ≠ []) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
|
||
(ht : res.keys.length + (r.begin.offset - 1).toNat < (r.end_.offset - 1).toNat)
|
||
(hroom : (((r.end_.offset - 1).toNat - res.keys.length -
|
||
(r.begin.offset - 1).toNat : ℕ) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key)
|
||
(hkE : r.end_.key ≤ (k : WithTop Key))
|
||
(hkB : (k : WithTop Key) < r.begin.key) :
|
||
Necessary r res k := by
|
||
set t : ℕ := res.keys.length with htdef
|
||
set eo : ℕ := (r.end_.offset - 1).toNat with heodef
|
||
set b : ℕ := (r.begin.offset - 1).toNat with hbdef
|
||
set s : ℕ := eo - t - b with hsdef
|
||
have htb : t + b < eo := by simpa [t, eo, b, htdef, heodef, hbdef] using ht
|
||
have hs : 0 < s := by omega
|
||
have hsub : s - 1 + 1 = s := Nat.sub_add_cancel (by omega : 1 ≤ s)
|
||
have hroom' : ((s : ℕ) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key := by
|
||
simpa [s, eo, t, b, htdef, heodef, hbdef] using hroom
|
||
have hcard : (((s - 1) + 1 : ℕ) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key := by
|
||
rw [hsub]; exact hroom'
|
||
obtain ⟨dbH, hHrange, hkH, hHlen⟩ :=
|
||
exists_db_keysIn_avoid (B := r.end_.key) (E := r.begin.key) (k := k) (m := s - 1) hcard
|
||
have hHgeE : ∀ x ∈ dbH.keys, r.end_.key ≤ (x : WithTop Key) :=
|
||
fun x hx => (hHrange x hx).1
|
||
have hHltB : ∀ x ∈ dbH.keys, (x : WithTop Key) < r.begin.key :=
|
||
fun x hx => (hHrange x hx).2
|
||
obtain ⟨db₀, hcomp₀⟩ := hread
|
||
have hres : res.keys = RangeRead.completeKeys db₀ r := by
|
||
rcases hcomp₀.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
|
||
· simp [hmore] at hm
|
||
· exact heq
|
||
have hall_ge : ∀ x ∈ res.keys, r.begin.key ≤ (x : WithTop Key) :=
|
||
crossed_mem_result_ge_begin_general ⟨db₀, hcomp₀⟩ hmore hbegin
|
||
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
|
||
obtain ⟨P, hPlen₀, hPs, hPge, hPlt, hPsort⟩ :=
|
||
crossed_pad_general (db := db₀) hrev hbegin hcross (by omega) hne hres
|
||
have hPlen : P.length = b := by simpa [b, hbdef] using hPlen₀
|
||
obtain ⟨C, hCge, hCnotin⟩ :=
|
||
exists_le_not_mem (res.keys ++ dbH.keys) (res.keys.getLast hne)
|
||
have hCnotres : C ∉ res.keys := fun h => hCnotin (List.mem_append_left _ h)
|
||
have hCnotH : C ∉ dbH.keys := fun h => hCnotin (List.mem_append_right _ h)
|
||
have hCgtRes : ∀ a ∈ res.keys, a < C := by
|
||
intro a ha
|
||
have hle : a ≤ res.keys.getLast hne :=
|
||
(hsort.pairwise.imp le_of_lt).rel_getLast ha
|
||
exact lt_of_le_of_ne (le_trans hle hCge) (fun h => hCnotres (h ▸ ha))
|
||
have hlast_ge_B : r.begin.key ≤ (res.keys.getLast hne : WithTop Key) :=
|
||
hall_ge _ (List.getLast_mem hne)
|
||
have hHltC : ∀ a ∈ dbH.keys, a < C := by
|
||
intro a ha
|
||
have h1 : (a : WithTop Key) < (C : WithTop Key) :=
|
||
lt_of_lt_of_le (hHltB a ha)
|
||
(le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge))
|
||
exact WithTop.coe_lt_coe.mp h1
|
||
have hHltP : ∀ a ∈ dbH.keys, ∀ p ∈ P, a < p := by
|
||
intro a ha p hp
|
||
have h1 : (a : WithTop Key) < (p : WithTop Key) :=
|
||
lt_of_lt_of_le (hHltB a ha) (hPge p hp)
|
||
exact WithTop.coe_lt_coe.mp h1
|
||
have hPltC : ∀ p ∈ P, p < C := by
|
||
intro p hp
|
||
exact lt_of_lt_of_le (hPlt p hp (res.keys.getLast hne) (List.getLast_mem hne)) hCge
|
||
have hHres_lt : ∀ a ∈ dbH.keys, ∀ c ∈ res.keys, a < c :=
|
||
fun a ha c hc =>
|
||
WithTop.coe_lt_coe.mp (lt_of_lt_of_le (hHltB a ha) (hall_ge c hc))
|
||
have hdbH_P : (dbH.keys ++ P).SortedLT :=
|
||
List.sortedLT_append.mpr ⟨dbH.sorted, hPs, hHltP⟩
|
||
have hdbH_P_res : (dbH.keys ++ P ++ res.keys).SortedLT :=
|
||
List.sortedLT_append.mpr ⟨hdbH_P, hsort, by
|
||
intro a ha c hc
|
||
rcases List.mem_append.mp ha with haH | haP
|
||
· exact hHres_lt a haH c hc
|
||
· exact hPlt a haP c hc⟩
|
||
have hsingle : ([C] : List Key).SortedLT := by
|
||
rw [List.sortedLT_cons]
|
||
exact ⟨by simp, List.sortedLT_nil⟩
|
||
have hcrossList : ∀ a ∈ (dbH.keys ++ P ++ res.keys), ∀ b ∈ ([C] : List Key), a < b := by
|
||
intro a ha b hb
|
||
rw [List.mem_singleton] at hb
|
||
subst hb
|
||
rcases List.mem_append.mp ha with ha' | haR
|
||
· rcases List.mem_append.mp ha' with haH | haP
|
||
· exact hHltC a haH
|
||
· exact hPltC a haP
|
||
· exact hCgtRes a haR
|
||
have hlst_sorted : (dbH.keys ++ P ++ res.keys ++ [C]).SortedLT :=
|
||
List.sortedLT_append.mpr ⟨hdbH_P_res, hsingle, hcrossList⟩
|
||
let db₂ : DB := ⟨dbH.keys ++ P ++ res.keys ++ [C], hlst_sorted⟩
|
||
have hkeys₂ : db₂.keys = dbH.keys ++ (P ++ (res.keys ++ [C])) := by
|
||
simp [db₂, List.append_assoc]
|
||
-- counts for `db₂`
|
||
have hcE₂ : cnt db₂ r.end_.key = 0 := by
|
||
apply cnt_eq_zero_of_forall_ge
|
||
intro x hx
|
||
rw [hkeys₂] at hx
|
||
rcases List.mem_append.mp hx with hxH | hx'
|
||
· exact hHgeE x hxH
|
||
rcases List.mem_append.mp hx' with hxP | hx''
|
||
· exact le_trans (le_of_lt hcross) (hPge x hxP)
|
||
rcases List.mem_append.mp hx'' with hxR | hxC
|
||
· exact le_trans (le_of_lt hcross) (hall_ge x hxR)
|
||
· rw [List.mem_singleton] at hxC
|
||
subst hxC
|
||
exact le_trans (le_of_lt hcross)
|
||
(le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge))
|
||
have hp₂ : cnt db₂ r.begin.key = s - 1 := by
|
||
change db₂.keys.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = s - 1
|
||
rw [hkeys₂, List.countP_append, List.countP_append, List.countP_append]
|
||
have hHc : dbH.keys.countP
|
||
(fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = dbH.keys.length :=
|
||
cnt_eq_length_of_forall_lt dbH hHltB
|
||
have hPc : P.countP
|
||
(fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = 0 := by
|
||
rw [List.countP_eq_zero]
|
||
intro x hx
|
||
rw [decide_eq_true_eq]
|
||
exact not_lt.mpr (hPge x hx)
|
||
have hresc : res.keys.countP
|
||
(fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = 0 := by
|
||
rw [List.countP_eq_zero]
|
||
intro x hx
|
||
rw [decide_eq_true_eq]
|
||
exact not_lt.mpr (hall_ge x hx)
|
||
have hCc : ([C] : List Key).countP
|
||
(fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = 0 := by
|
||
rw [List.countP_eq_zero]
|
||
intro x hx
|
||
rw [decide_eq_true_eq]
|
||
rw [List.mem_singleton] at hx
|
||
subst hx
|
||
exact not_lt.mpr (le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge))
|
||
rw [hHc, hPc, hresc, hCc, hHlen]
|
||
omega
|
||
have hn₂ : db₂.keys.length = eo := by
|
||
rw [hkeys₂, List.length_append, List.length_append, List.length_append, hPlen, hHlen]
|
||
have htres : res.keys.length = t := rfl
|
||
rw [htres, List.length_singleton]
|
||
omega
|
||
have hk_db₂ : k ∉ db₂.keys := by
|
||
rw [hkeys₂]
|
||
intro hmem
|
||
rcases List.mem_append.mp hmem with hmemH | hmem'
|
||
· exact hkH hmemH
|
||
rcases List.mem_append.mp hmem' with hmemP | hmem''
|
||
· exact absurd (hPge k hmemP) (not_le.mpr hkB)
|
||
rcases List.mem_append.mp hmem'' with hmemR | hmemC
|
||
· exact absurd (hall_ge k hmemR) (not_le.mpr hkB)
|
||
· rw [List.mem_singleton] at hmemC
|
||
have h1 : (k : WithTop Key) < (C : WithTop Key) :=
|
||
lt_of_lt_of_le hkB (le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge))
|
||
rw [hmemC] at h1
|
||
exact (lt_irrefl (C : WithTop Key)) h1
|
||
-- counts for the inserted database
|
||
have hcE₁ : cnt (db₂.insert k hk_db₂) r.end_.key = 0 := by
|
||
rw [cnt_insert_not_lt db₂ k hk_db₂ (v := r.end_.key) (not_lt.mpr hkE)]
|
||
exact hcE₂
|
||
have hp₁ : cnt (db₂.insert k hk_db₂) r.begin.key = s := by
|
||
rw [cnt_insert_lt db₂ k hk_db₂ (v := r.begin.key) hkB, hp₂]
|
||
omega
|
||
have hn₁ : (db₂.insert k hk_db₂).keys.length = eo + 1 := by
|
||
rw [DB.insert_keys, List.orderedInsert_length, hn₂]
|
||
let dbHi : DB := dbH.insert k hkH
|
||
have hdbHi_len : dbHi.keys.length = s := by
|
||
rw [show dbHi = dbH.insert k hkH from rfl, DB.insert_keys, List.orderedInsert_length, hHlen]
|
||
omega
|
||
have hkeys_ins : (db₂.insert k hk_db₂).keys = dbHi.keys ++ P ++ res.keys ++ [C] := by
|
||
rw [DB.insert_keys, hkeys₂]
|
||
rw [show dbH.keys ++ (P ++ (res.keys ++ [C])) =
|
||
dbH.keys ++ (P ++ res.keys ++ [C]) by simp [List.append_assoc]]
|
||
rw [orderedInsert_append_of_forall_lt]
|
||
· simp [dbHi, DB.insert_keys, List.append_assoc]
|
||
· intro x hx
|
||
rcases List.mem_append.mp hx with hxPR | hxC
|
||
· rcases List.mem_append.mp hxPR with hxP | hxR
|
||
· exact WithTop.coe_lt_coe.mp
|
||
(lt_of_lt_of_le hkB (hPge x hxP))
|
||
· exact WithTop.coe_lt_coe.mp
|
||
(lt_of_lt_of_le hkB (hall_ge x hxR))
|
||
· rw [List.mem_singleton] at hxC
|
||
rw [hxC]
|
||
have h1 : (k : WithTop Key) < (C : WithTop Key) :=
|
||
lt_of_lt_of_le hkB (le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge))
|
||
exact WithTop.coe_lt_coe.mp h1
|
||
have hdrop : (dbHi.keys ++ P ++ res.keys ++ [C]).drop (s + b) = res.keys ++ [C] := by
|
||
rw [show dbHi.keys ++ P ++ res.keys ++ [C] =
|
||
dbHi.keys ++ (P ++ (res.keys ++ [C])) by simp [List.append_assoc]]
|
||
rw [List.drop_append]
|
||
rw [show s + b - dbHi.keys.length = b by rw [hdbHi_len]; omega]
|
||
rw [List.drop_eq_nil_of_le (by rw [hdbHi_len]; omega), List.nil_append]
|
||
rw [List.drop_append_of_le_length (by omega)]
|
||
rw [show P.drop b = [] by rw [← hPlen, List.drop_length], List.nil_append]
|
||
-- compatibility of the inserted database
|
||
have hck₁ : RangeRead.completeKeys (db₂.insert k hk_db₂) r = res.keys := by
|
||
have htres : res.keys.length = t := rfl
|
||
have hp₁' : (db₂.insert k hk_db₂).keys.countP
|
||
(fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = s := by
|
||
simpa [cnt] using hp₁
|
||
have hcE₁' : (db₂.insert k hk_db₂).keys.countP
|
||
(fun x : Key => decide ((x : WithTop Key) < r.end_.key)) = 0 := by
|
||
simpa [cnt] using hcE₁
|
||
have hidx : eo - (s + b) = t := by omega
|
||
have htake : (res.keys ++ [C]).take t = res.keys := by
|
||
rw [List.take_append_of_le_length (by rw [htres])]
|
||
exact List.take_length
|
||
rw [completeKeys_eq_drop_take_general (db := db₂.insert k hk_db₂) (r := r) hrev
|
||
hbegin (by omega)]
|
||
rw [hp₁', hcE₁', Nat.zero_add, hkeys_ins]
|
||
have hlenList : (dbHi.keys ++ P ++ res.keys ++ [C]).length = eo + 1 := by
|
||
rw [List.length_append, List.length_append, List.length_append, hdbHi_len, hPlen,
|
||
List.length_singleton]
|
||
have htres : res.keys.length = t := rfl
|
||
rw [htres]
|
||
omega
|
||
rw [hlenList]
|
||
rw [Nat.min_eq_left (by omega : eo ≤ eo + 1)]
|
||
rw [hdrop, hidx, htake]
|
||
have hcomp₁ : RangeRead.Compatible (db₂.insert k hk_db₂) r res :=
|
||
⟨hcomp₀.1, Or.inr ⟨hmore, hck₁.symm⟩⟩
|
||
-- `db₂` itself is not compatible
|
||
have hlen₂ : (RangeRead.completeKeys db₂ r).length = t + 1 := by
|
||
rw [completeKeys_length_general (db := db₂) (r := r) hrev hbegin (by omega)]
|
||
have hp₂' : db₂.keys.countP
|
||
(fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = s - 1 := by
|
||
simpa [cnt] using hp₂
|
||
have hcE₂' : db₂.keys.countP
|
||
(fun x : Key => decide ((x : WithTop Key) < r.end_.key)) = 0 := by
|
||
simpa [cnt] using hcE₂
|
||
rw [hp₂', hcE₂', Nat.zero_add, hn₂]
|
||
have hidx : min eo eo - (s - 1 + b) = t + 1 := by omega
|
||
simpa [heodef, hbdef] using hidx
|
||
have hnot₂ : ¬ RangeRead.Compatible db₂ r res := by
|
||
intro hc
|
||
have ht_eq : res.keys.length = t := rfl
|
||
rcases hc.2 with ⟨hm, _, _⟩ | ⟨hm, heq⟩
|
||
· rw [hmore] at hm
|
||
exact Bool.false_ne_true hm
|
||
· rw [← heq] at hlen₂
|
||
rw [ht_eq] at hlen₂
|
||
omega
|
||
intro cr hs
|
||
by_contra hkcr
|
||
have hagree : AgreeOn cr db₂ (db₂.insert k hk_db₂) :=
|
||
(ConflictRange.keys_insert_of_not_mem cr db₂ hk_db₂ hkcr).symm
|
||
exact hnot₂ ((hs db₂ (db₂.insert k hk_db₂) hagree).mpr hcomp₁)
|
||
|
||
end FormalConflictRange
|
||
|
||
namespace FormalConflictRange
|
||
|
||
/-- **Crossed complete top branch with enough room below the begin key, at any positive
|
||
begin offset.** If the gap `[end_.key, begin_.key)` holds at least the overshoot
|
||
`e - t - (begin.offset - 1)` keys, the minimal range is `[end_.key, ⊤)`. -/
|
||
theorem minimal_topRange_of_crossed_large_room_general {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = false)
|
||
(hne : res.keys ≠ []) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
|
||
(ht : res.keys.length + (r.begin.offset - 1).toNat < (r.end_.offset - 1).toNat)
|
||
(hroom : (((r.end_.offset - 1).toNat - res.keys.length -
|
||
(r.begin.offset - 1).toNat : ℕ) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key) :
|
||
Minimal r res ⟨r.end_.key, ⊤⟩ := by
|
||
rw [minimal_iff_sound_and_necessaryRange]
|
||
refine ⟨sound_topRange_of_lo_le (by omega) (by omega) (le_of_lt hcross) (le_refl _), ?_⟩
|
||
intro k hkE _
|
||
by_cases hkB : (k : WithTop Key) < r.begin.key
|
||
· exact necessary_of_mem_interval_crossed_top_general hread hmore hrev hne hbegin hcross
|
||
hend ht hroom hkE hkB
|
||
· exact necessary_of_begin_le_crossed_top_general hread hmore hrev hne hbegin hcross
|
||
hend ht (not_lt.mp hkB)
|
||
|
||
|
||
|
||
/-- In a readable crossed complete result with positive end offset at any positive
|
||
begin offset, the number of reported keys at or above `end_.key`, plus
|
||
`begin.offset - 1`, is at most `end.offset - 1`. -/
|
||
theorem crossed_complete_t_le_e_general {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = false)
|
||
(hne : res.keys ≠ []) (hbegin : 1 ≤ r.begin.offset) (hcross : r.end_.key < r.begin.key)
|
||
(hend : 1 ≤ r.end_.offset) :
|
||
res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) +
|
||
(r.begin.offset - 1).toNat ≤ (r.end_.offset - 1).toNat := by
|
||
obtain ⟨db₀, hcomp₀⟩ := hread
|
||
have hres : res.keys = RangeRead.completeKeys db₀ r := by
|
||
rcases hcomp₀.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
|
||
· simp [hmore] at hm
|
||
· exact heq
|
||
have hcount : res.keys.countP
|
||
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) = res.keys.length := by
|
||
rw [hres]
|
||
exact completeKeys_count_ge_eq_length_of_crossed_general (db := db₀) hrev hbegin hcross hend
|
||
have hlen := completeKeys_length_general (db := db₀) (r := r) hrev hbegin hend
|
||
rw [← hres] at hlen
|
||
set p := db₀.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) with hp
|
||
set cE := db₀.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) with hcE
|
||
set b := (r.begin.offset - 1).toNat with hb
|
||
set e := (r.end_.offset - 1).toNat with he
|
||
have hcEp : cE ≤ p := by
|
||
rw [hp, hcE]
|
||
apply countP_le_countP_of_imp
|
||
intro k _ hk
|
||
rw [decide_eq_true_eq] at hk ⊢
|
||
exact lt_of_lt_of_le hk (le_of_lt hcross)
|
||
have htpos : 0 < res.keys.length := List.length_pos_of_ne_nil hne
|
||
rw [hcount]
|
||
omega
|
||
|
||
|
||
|
||
/-- The remaining overshoot `s = e - t - (begin.offset - 1)` in the crossed complete
|
||
top branch. -/
|
||
def crossedOvershootGeneral (r : RangeRead) (res : Result) : ℕ :=
|
||
endOvershoot r - reportedAtEnd r res - (r.begin.offset - 1).toNat
|
||
|
||
/-- The unified forward complete rule at any positive begin offset on crossed selectors.
|
||
The lower endpoint is `end_.key` when the gap has room for the remaining overshoot
|
||
`e - t - (begin.offset - 1)`, and `begin.key` otherwise. The upper endpoint is
|
||
`keyAfter (last reported)` in the finite branch `t + (begin.offset - 1) = e`, and `⊤`
|
||
otherwise. -/
|
||
def completeForwardCrossedGeneral (r : RangeRead) (res : Result) : ConflictRange :=
|
||
if r.end_.offset ≤ 1 then canonicalRange r
|
||
else if reportedAtEnd r res + (r.begin.offset - 1).toNat = endOvershoot r then
|
||
⟨r.end_.key, (keyAfter (res.keys.getLastD ([] : Key)) : WithTop Key)⟩
|
||
else
|
||
⟨if (crossedOvershootGeneral r res : ℕ∞) ≤ intervalCard r.end_.key r.begin.key
|
||
then r.end_.key else r.begin.key, ⊤⟩
|
||
|
||
/-- **Crossed complete forward minimality at any positive begin offset.** -/
|
||
theorem minimal_completeForwardCrossedGeneral {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
|
||
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) :
|
||
Minimal r res (completeForwardCrossedGeneral r res) := by
|
||
have hend2 : 2 ≤ r.end_.offset :=
|
||
crossed_end_offset_ge_two hread hmore hne hbegin hcross
|
||
have htle : reportedAtEnd r res + (r.begin.offset - 1).toNat ≤ endOvershoot r := by
|
||
have h := crossed_complete_t_le_e_general hread hmore hrev hne hbegin hcross (by omega)
|
||
simpa [reportedAtEnd, endOvershoot] using h
|
||
have hcount : reportedAtEnd r res = res.keys.length := by
|
||
obtain ⟨db₀, hcomp₀⟩ := hread
|
||
have hres : res.keys = RangeRead.completeKeys db₀ r := by
|
||
rcases hcomp₀.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
|
||
· simp [hmore] at hm
|
||
· exact heq
|
||
rw [reportedAtEnd, hres]
|
||
exact completeKeys_count_ge_eq_length_of_crossed_general (db := db₀) hrev hbegin hcross
|
||
(by omega)
|
||
by_cases hte : reportedAtEnd r res + (r.begin.offset - 1).toNat = endOvershoot r
|
||
· have hmin : Minimal r res
|
||
⟨r.end_.key, (keyAfter (res.keys.getLastD ([] : Key)) : WithTop Key)⟩ :=
|
||
minimal_truncatedRange_of_crossed_finite_general hread hmore hne hrev hbegin hcross
|
||
hend2 (by simpa [reportedAtEnd, endOvershoot] using hte)
|
||
rw [completeForwardCrossedGeneral, ite_eq_right (by omega : ¬ r.end_.offset ≤ 1), ite_eq_left
|
||
hte]
|
||
exact hmin
|
||
· have htlt : reportedAtEnd r res + (r.begin.offset - 1).toNat < endOvershoot r :=
|
||
lt_of_le_of_ne htle hte
|
||
have htb : res.keys.length + (r.begin.offset - 1).toNat <
|
||
(r.end_.offset - 1).toNat := by
|
||
rw [← hcount]
|
||
simpa [endOvershoot] using htlt
|
||
by_cases hroom : (crossedOvershootGeneral r res : ℕ∞) ≤
|
||
intervalCard r.end_.key r.begin.key
|
||
· have hroom' : (((r.end_.offset - 1).toNat - res.keys.length -
|
||
(r.begin.offset - 1).toNat : ℕ) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key := by
|
||
simpa [crossedOvershootGeneral, endOvershoot, hcount] using hroom
|
||
have hmin : Minimal r res ⟨r.end_.key, ⊤⟩ :=
|
||
minimal_topRange_of_crossed_large_room_general hread hmore hrev hne hbegin hcross
|
||
hend2 htb hroom'
|
||
rw [completeForwardCrossedGeneral, ite_eq_right (by omega : ¬ r.end_.offset ≤ 1),
|
||
ite_eq_right hte, ite_eq_left hroom]
|
||
exact hmin
|
||
· have hroom' : intervalCard r.end_.key r.begin.key <
|
||
(((r.end_.offset - 1).toNat - res.keys.length -
|
||
(r.begin.offset - 1).toNat : ℕ) : ℕ∞) := by
|
||
simpa [crossedOvershootGeneral, endOvershoot, hcount] using lt_of_not_ge hroom
|
||
have hmin : Minimal r res ⟨r.begin.key, ⊤⟩ :=
|
||
minimal_topRange_of_crossed_small_room_general hread hmore hne hrev hbegin hcross
|
||
hend2 htb hroom'
|
||
rw [completeForwardCrossedGeneral, ite_eq_right (by omega : ¬ r.end_.offset ≤ 1),
|
||
ite_eq_right hte, ite_eq_right hroom]
|
||
exact hmin
|
||
|
||
end FormalConflictRange
|
||
|
||
namespace FormalConflictRange
|
||
|
||
/-- The reversed-traversal analogue of `completeForwardCrossedGeneral`. -/
|
||
def completeReversedCrossedGeneral (r : RangeRead) (res : Result) : ConflictRange :=
|
||
if r.end_.offset ≤ 1 then canonicalRange r
|
||
else if reportedAtEnd r res + (r.begin.offset - 1).toNat = endOvershoot r then
|
||
⟨r.end_.key, (keyAfter (res.keys.headD ([] : Key)) : WithTop Key)⟩
|
||
else
|
||
⟨if (crossedOvershootGeneral r res : ℕ∞) ≤ intervalCard r.end_.key r.begin.key
|
||
then r.end_.key else r.begin.key, ⊤⟩
|
||
|
||
/-- **Crossed complete reversed minimality at any positive begin offset**, by flipping
|
||
to the forward theorem. -/
|
||
theorem minimal_completeReversedCrossedGeneral {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
|
||
(hrev : r.reverse = true) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) :
|
||
Minimal r res (completeReversedCrossedGeneral r res) := by
|
||
let r' : RangeRead := { r with reverse := false }
|
||
let res' : Result := { keys := res.keys.reverse, more := false }
|
||
have hread' : Readable r' res' := by
|
||
obtain ⟨db, hcomp⟩ := hread
|
||
exact ⟨db, (compatible_flip (b := true) hrev hmore).mpr hcomp⟩
|
||
have hne' : res'.keys ≠ [] := by simpa [res'] using hne
|
||
have hbegin' : 1 ≤ r'.begin.offset := by simpa [r'] using hbegin
|
||
have hmin' : Minimal r' res' (completeForwardCrossedGeneral r' res') :=
|
||
minimal_completeForwardCrossedGeneral hread' rfl hne' rfl hbegin' hcross
|
||
have hflip := (minimal_flip (r := r) (res := res)
|
||
(cr := completeForwardCrossedGeneral r' res') (b := true) hrev hmore)
|
||
have hformula : completeForwardCrossedGeneral r' res' = completeReversedCrossedGeneral r res := by
|
||
unfold completeForwardCrossedGeneral completeReversedCrossedGeneral
|
||
dsimp only [r', res']
|
||
simp only [endOvershoot, crossedOvershootGeneral, reportedAtEnd, List.countP_reverse,
|
||
getLastD_reverse]
|
||
rfl
|
||
have hflip' : Minimal r res (completeForwardCrossedGeneral r' res') := hflip.mp hmin'
|
||
rw [hformula] at hflip'
|
||
exact hflip'
|
||
|
||
/-- The forward crossed complete general rule denotes the general conflict range. -/
|
||
theorem completeForwardCrossedGeneral_toSet_eq_general {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = false)
|
||
(hne : res.keys ≠ []) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) :
|
||
(completeForwardCrossedGeneral r res).toSet = (conflictRangeGeneral r res).toSet :=
|
||
(minimal_completeForwardCrossedGeneral hread hmore hne hrev hbegin hcross).toSet_eq
|
||
(conflictRangeGeneral_minimal hread)
|
||
|
||
/-- The same identification with the executable algorithm. -/
|
||
theorem completeForwardCrossedGeneral_toSet_eq_simple {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = false)
|
||
(hne : res.keys ≠ []) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) :
|
||
(completeForwardCrossedGeneral r res).toSet = (simpleConflictRange r res).toSet :=
|
||
(minimal_completeForwardCrossedGeneral hread hmore hne hrev hbegin hcross).toSet_eq
|
||
(simpleConflictRange_minimal hread)
|
||
|
||
/-- The reversed crossed complete general rule denotes the general conflict range. -/
|
||
theorem completeReversedCrossedGeneral_toSet_eq_general {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = true)
|
||
(hne : res.keys ≠ []) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) :
|
||
(completeReversedCrossedGeneral r res).toSet = (conflictRangeGeneral r res).toSet :=
|
||
(minimal_completeReversedCrossedGeneral hread hmore hne hrev hbegin hcross).toSet_eq
|
||
(conflictRangeGeneral_minimal hread)
|
||
|
||
/-- The same identification with the executable algorithm. -/
|
||
theorem completeReversedCrossedGeneral_toSet_eq_simple {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = true)
|
||
(hne : res.keys ≠ []) (hbegin : 1 ≤ r.begin.offset)
|
||
(hcross : r.end_.key < r.begin.key) :
|
||
(completeReversedCrossedGeneral r res).toSet = (simpleConflictRange r res).toSet :=
|
||
(minimal_completeReversedCrossedGeneral hread hmore hne hrev hbegin hcross).toSet_eq
|
||
(simpleConflictRange_minimal hread)
|
||
|
||
/-- The result-aware crossed complete rule at any positive begin offset: dispatch on the
|
||
traversal order. -/
|
||
noncomputable def completeCrossedGeneral (r : RangeRead) (res : Result) : ConflictRange :=
|
||
if r.reverse then completeReversedCrossedGeneral r res
|
||
else completeForwardCrossedGeneral r res
|
||
|
||
/-- **Total crossed complete closed form at every positive begin offset.** -/
|
||
theorem minimal_completeCrossedGeneral {r : RangeRead} {res : Result}
|
||
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
|
||
(hbegin : 1 ≤ r.begin.offset) (hcross : r.end_.key < r.begin.key) :
|
||
Minimal r res (completeCrossedGeneral r res) := by
|
||
unfold completeCrossedGeneral
|
||
by_cases hrev : r.reverse = true
|
||
· rw [ite_eq_left hrev]
|
||
exact minimal_completeReversedCrossedGeneral hread hmore hne hrev hbegin hcross
|
||
· rw [ite_eq_right hrev]
|
||
have hrevf : r.reverse = false := by
|
||
cases hr : r.reverse <;> simp_all
|
||
exact minimal_completeForwardCrossedGeneral hread hmore hne hrevf hbegin hcross
|
||
|
||
end FormalConflictRange
|