Files

894 lines
42 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.Empty
import FormalConflictRange.ClosedForm
/-!
# Crossed selectors at begin offset one
This module closes the crossed cell `end_.key < begin_.key` of the compact closed form
at `begin.offset = 1`. The complete window starts at the first stored key at or above
`begin_.key`, while the end resolution counts stored keys from `end_.key`; the two
selector keys therefore cut the database at different points.
The main results are:
* `minimal_topRange_of_crossed_large_room` and
`minimal_topRange_of_crossed_small_room`: the top branch `t < e`, split by whether the
gap `[end_.key, begin_.key)` has room for the overshoot `e - t`;
* `minimal_truncatedRange_of_finite_crossed` (from `FormalConflictRange.Sound`): the
finite branch `t = e`;
* `minimal_completeForward_of_crossed`: the unified crossed forward-complete rule,
implemented by `completeForwardClosed`.
-/
open FormalConflictRange
namespace FormalConflictRange
/-- In a readable crossed complete result at begin offset one, every reported key lies
at or above `begin.key`. -/
theorem crossed_mem_result_ge_begin {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = false) (hbegin : r.begin.offset = 1) :
∀ 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) (by omega))
(RangeRead.mem_completeKeys.mp hk').2.1
/-- In a crossed complete result at begin offset one, the reported keys at or above
`end_.key` are all reported keys, so the count equals the length. -/
theorem crossed_complete_t_eq_length {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = false)
(hbegin : r.begin.offset = 1) (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))) =
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
have h := completeKeys_count_ge_eq_length_of_crossed (db := db₀) (r := r)
hrev hbegin hcross hend
rw [← hres] at h
exact h
/-- In a readable crossed complete result at begin offset one with positive end offset,
the number of reported keys at or above `end_.key` is at most `end_.offset - 1`. -/
theorem crossed_complete_t_le_e {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = false)
(hbegin : r.begin.offset = 1) (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.end_.offset - 1).toNat := by
have htlen := crossed_complete_t_eq_length hread hmore hrev hbegin hcross (by omega)
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 hlen := completeKeys_length_of_offset_one (db := db₀) (r := r) hrev hbegin hend
rw [← hres] at hlen
rw [htlen]
have hcEp : db₀.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) ≤
db₀.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) := by
apply countP_le_countP_of_imp
intro k _ hk
rw [decide_eq_true_eq] at hk ⊢
exact lt_trans hk hcross
calc res.keys.length
= min (db₀.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key))
+ (r.end_.offset - 1).toNat) db₀.keys.length
- db₀.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) := hlen
_ ≤ (db₀.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key))
+ (r.end_.offset - 1).toNat)
- db₀.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) :=
Nat.sub_le_sub_right (Nat.min_le_left _ _) _
_ ≤ (r.end_.offset - 1).toNat := by omega
end FormalConflictRange
namespace FormalConflictRange
/-- When there is enough room below `begin.key` (in the sense that the actual gap count
plus the reported length is below `end.offset - 1`), a crossed complete result is
determined exactly by the stored keys at or above `begin.key`. -/
theorem completeKeys_eq_iff_filter_ge_begin_of_room {db : DB} {r : RangeRead}
{res : Result} (hrev : r.reverse = false) (hbegin : r.begin.offset = 1)
(hend : 1 ≤ r.end_.offset) (hcross : r.end_.key ≤ r.begin.key)
(hne : res.keys ≠ [])
(hroom : res.keys.length +
(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))) =
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 e := (r.end_.offset - 1).toNat with he
set t := res.keys.length with ht
set A := l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) with hAdef
set q := l.length - p with hq
have hls : l.SortedLT := by rw [hl]; exact db.sorted
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 hcross
have hp_le_n : p ≤ l.length := by rw [hp]; exact List.countP_le_length
have hroom' : t + (p - cE) < e := by simpa [hp, hcE, he, ht] using hroom
have htpos : 0 < t := List.length_pos_of_ne_nil hne
have hA : A = l.drop p := by
have hdrop : l.filter (fun k : Key => decide (¬ ((k : WithTop Key) < r.begin.key))) =
l.drop p := by
rw [hp]
exact filter_not_lt_eq_drop_countP hls r.begin.key
rw [hAdef, ← hdrop]
apply List.filter_congr
intro k _
rw [decide_eq_decide]
exact not_lt.symm
have hAlen : A.length = q := by rw [hA, List.length_drop, hq]
have hsplit : l.length = cE + (p - cE) + q := by
rw [hq]
omega
have hlen : RangeRead.completeKeys db r =
A.take (min (cE + e) l.length - p) := by
rw [completeKeys_eq_filter_take_of_offset_one hrev hbegin hend]
constructor
· intro hck
have hcklen : (RangeRead.completeKeys db r).length = t := by rw [hck, ht]
have hLt : min (cE + e) l.length - p = t := by
rw [hlen, List.length_take] at hcklen
have hAq : A.length = q := hAlen
omega
-- Suppose q > t; then both arguments of min exceed p + t.
have hqle : q ≤ t := by
by_contra hqt
have hq_gt : t < q := lt_of_not_ge hqt
have h1 : p + t < cE + e := by omega
have h2 : p + t < l.length := by omega
have hmin : p + t < min (cE + e) l.length := lt_min h1 h2
omega
have hqge : t ≤ q := by
have := hLt
have hle : min (cE + e) l.length - p ≤ l.length - p :=
Nat.sub_le_sub_right (Nat.min_le_right _ _) _
omega
have hqt : q = t := le_antisymm hqle hqge
-- hence `take` keeps all of `A`
have hLge : A.length ≤ min (cE + e) l.length - p := by
rw [hAlen, hqt]
omega
have htake : A.take (min (cE + e) l.length - p) = A :=
List.take_of_length_le hLge
exact htake.symm.trans (hlen.symm.trans hck)
· intro hfil
have hAres : A = res.keys := by rw [hAdef]; exact hfil
have hqt : q = t := by rw [← hAlen, hAres, ht]
have hL : min (cE + e) l.length - p = t := by
have hn : l.length = p + t := by omega
have h1 : l.length < cE + e := by omega
rw [Nat.min_eq_right (le_of_lt h1), hn]
omega
rw [hlen, hL, hfil, ht, List.take_length]
end FormalConflictRange
namespace FormalConflictRange
/-- Move the end selector's key up to the begin key, keeping its offset. In the crossed
complete case with little room below the begin key, this read has the same compatible
databases as the original. -/
def endKeyToBegin (r : RangeRead) : RangeRead :=
{ r with end_ := { r.end_ with key := r.begin.key } }
theorem compatible_crossed_iff_endKeyToBegin_of_room {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
(hrev : r.reverse = false) (hbegin : r.begin.offset = 1)
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
(hroom : intervalCard r.end_.key r.begin.key <
(((r.end_.offset - 1).toNat -
res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) : ℕ) : ℕ∞)) :
∀ db : DB, RangeRead.Compatible db r res ↔
RangeRead.Compatible db (endKeyToBegin r) res := by
have htlen := crossed_complete_t_eq_length hread hmore hrev hbegin hcross (by omega)
have htle := crossed_complete_t_le_e hread hmore hrev hbegin hcross (by omega)
have hresne := hne
intro db
have hbase : ∀ (r' : RangeRead),
r'.reverse = false ∧ r'.begin.offset = 1 ∧ 1 ≤ r'.end_.offset ∧
r'.end_.key ≤ r'.begin.key →
(res.keys.length +
(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.Compatible db r' res ↔
(RangeRead.withinLimit r' res.keys ∧
db.keys.filter (fun k : Key => decide (r'.begin.key ≤ (k : WithTop Key))) =
res.keys)) := by
intro r' hprops hroom'
obtain ⟨hrev', hbegin', hend', hcross'⟩ := hprops
constructor
· rintro ⟨hlim, hdisj | ⟨_, heq⟩⟩
· simp [hmore] at hdisj
· exact ⟨hlim, (completeKeys_eq_iff_filter_ge_begin_of_room
(db := db) (r := r') (res := res) hrev' hbegin' hend' hcross' hresne hroom').mp
heq.symm⟩
· rintro ⟨hlim, hfil⟩
refine ⟨hlim, Or.inr ⟨hmore, ?_⟩⟩
exact ((completeKeys_eq_iff_filter_ge_begin_of_room
(db := db) (r := r') (res := res) hrev' hbegin' hend' hcross' hresne hroom').mpr
hfil).symm
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 := db) (w₁ := r.end_.key) (w₂ := r.begin.key)
(le_of_lt hcross)
-- gap plus reported length stays below the end offset budget
rw [htlen] at hroom
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))) <
(r.end_.offset - 1).toNat - res.keys.length := 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)) : ℕ) : ℕ∞) <
(((r.end_.offset - 1).toNat - res.keys.length : ℕ) : ℕ∞) :=
lt_of_le_of_lt hgap_le hroom
exact_mod_cast h1
have hroom_db : res.keys.length +
(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 := by omega
have hbase_r := hbase r ⟨hrev, hbegin, by omega, le_of_lt hcross⟩ hroom_db
-- the modified read
have hbase_r' := hbase (endKeyToBegin r)
⟨by simp [endKeyToBegin, hrev], by simp [endKeyToBegin, hbegin],
by simp [endKeyToBegin]; omega, by simp [endKeyToBegin]⟩
(by
have htlt : res.keys.length < (r.end_.offset - 1).toNat := by omega
change res.keys.length +
(List.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) db.keys -
List.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) db.keys) <
(r.end_.offset - 1).toNat
rw [Nat.sub_self, Nat.add_zero]
exact htlt)
rw [hbase_r, hbase_r']
rfl
end FormalConflictRange
namespace FormalConflictRange
/-- **Crossed complete top branch with little room below the begin key.** If the interval
between the two selector keys holds fewer keys than the overshoot `e - t`, then no key in
that gap can be necessary, and the minimal range is `[begin.key, ⊤)`. Moving the end key
up to the begin key makes the read cross-free with the same compatible databases. -/
theorem minimal_topRange_of_crossed_small_room {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
(hrev : r.reverse = false) (hbegin : r.begin.offset = 1)
(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.end_.offset - 1).toNat)
(hroom : intervalCard r.end_.key r.begin.key <
(((r.end_.offset - 1).toNat -
res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) : ℕ) : ℕ∞)) :
Minimal r res ⟨r.begin.key, ⊤⟩ := by
let r' := endKeyToBegin r
have hiff := compatible_crossed_iff_endKeyToBegin_of_room hread hmore hne hrev hbegin
hcross hend hroom
have hall_ge : ∀ k ∈ res.keys, r.begin.key ≤ (k : WithTop Key) :=
crossed_mem_result_ge_begin hread hmore hbegin
have htlen := crossed_complete_t_eq_length hread hmore hrev hbegin hcross (by omega)
obtain ⟨db₀, hcomp₀⟩ := hread
have hread' : Readable r' res := ⟨db₀, (hiff db₀).mp hcomp₀⟩
have ht' : res.keys.countP
(fun k : Key => decide (r'.end_.key ≤ (k : WithTop Key))) <
(r'.end_.offset - 1).toNat := by
have hcnt : 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
rw [hcnt, ← htlen]
simpa [r', endKeyToBegin] using ht
have hmin' : Minimal r' res (topRange r') :=
minimal_topRange_of_top_branch hread' hmore (by simp [r', endKeyToBegin, hrev])
hne (by simp [r', endKeyToBegin, hbegin]) (by simp [r', endKeyToBegin]) hend ht'
have hmin'' : Minimal r' res ⟨r.begin.key, ⊤⟩ := by
simpa [r', endKeyToBegin, topRange] using hmin'
exact minimal_of_compatible_iff hiff hmin''
end FormalConflictRange
namespace FormalConflictRange
/-- In the crossed complete top branch, every key at or above `begin.key` is necessary. -/
theorem necessary_of_begin_le_crossed_top {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = false)
(hne : res.keys ≠ []) (hbegin : r.begin.offset = 1)
(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.end_.offset - 1).toNat)
{x : Key} (hx : r.begin.key ≤ (x : WithTop Key)) :
Necessary r res x := by
have hread₀ := hread
obtain ⟨db₀, hcomp₀⟩ := hread
have hall_ge : ∀ k ∈ res.keys, r.begin.key ≤ (k : WithTop Key) :=
crossed_mem_result_ge_begin hread₀ hmore hbegin
by_cases hxmem : x ∈ res.keys
· exact necessary_of_mem_result ⟨db₀, hcomp₀⟩ hxmem
· have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
let d₀ : DB := ⟨res.keys, hsort⟩
have hfil₀ : res.keys.filter
(fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) = res.keys := by
rw [List.filter_eq_self]
intro k hk
rw [decide_eq_true_eq]
exact hall_ge k hk
have hp₀ : res.keys.countP
(fun k : Key => decide ((k : WithTop Key) < r.begin.key)) = 0 := by
rw [List.countP_eq_zero]
intro k hk
have hle := hall_ge k hk
rw [decide_eq_true_eq]
exact not_lt.mpr hle
have hcE₀ : res.keys.countP
(fun k : Key => decide ((k : WithTop Key) < r.end_.key)) = 0 := by
rw [List.countP_eq_zero]
intro k hk
have hle := le_trans (le_of_lt hcross) (hall_ge k hk)
rw [decide_eq_true_eq]
exact not_lt.mpr hle
have hroom₀ : res.keys.length +
(res.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) -
res.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)))
< (r.end_.offset - 1).toNat := by
rw [hp₀, hcE₀]
have htlen := crossed_complete_t_eq_length hread₀ hmore hrev hbegin hcross (by omega)
simpa [htlen] using ht
have hcompD₀ : RangeRead.Compatible d₀ r res := by
have hkey := (completeKeys_eq_iff_filter_ge_begin_of_room
(db := d₀) (r := r) (res := res) hrev hbegin (by omega) (le_of_lt hcross)
hne hroom₀).mpr hfil₀
refine ⟨hcomp₀.1, Or.inr ⟨hmore, hkey.symm⟩⟩
intro cr hs
by_contra hxcr
have hknot : x ∉ d₀.keys := hxmem
let d₁ : DB := d₀.insert x hknot
have hall₁ : ∀ k ∈ d₁.keys, r.begin.key ≤ (k : WithTop Key) := by
intro k hk
rw [show d₁ = d₀.insert x hknot from rfl, DB.mem_insert_iff hknot] at hk
rcases hk with rfl | hk
· exact hx
· exact hall_ge k hk
have hfil₁ : d₁.keys.filter
(fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) = d₁.keys := by
rw [List.filter_eq_self]
intro k hk
rw [decide_eq_true_eq]
exact hall₁ k hk
have hp₁ : d₁.keys.countP
(fun k : Key => decide ((k : WithTop Key) < r.begin.key)) = 0 := by
rw [List.countP_eq_zero]
intro k hk
have hle := hall₁ k hk
rw [decide_eq_true_eq]
exact not_lt.mpr hle
have hcE₁ : d₁.keys.countP
(fun k : Key => decide ((k : WithTop Key) < r.end_.key)) = 0 := by
rw [List.countP_eq_zero]
intro k hk
have hle := le_trans (le_of_lt hcross) (hall₁ k hk)
rw [decide_eq_true_eq]
exact not_lt.mpr hle
have hroom₁ : res.keys.length +
(d₁.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) -
d₁.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)))
< (r.end_.offset - 1).toNat := by
rw [hp₁, hcE₁]
have htlen := crossed_complete_t_eq_length hread₀ hmore hrev hbegin hcross (by omega)
simpa [htlen] using ht
have hcomplen : d₁.keys.length = res.keys.length + 1 := by
rw [show d₁ = d₀.insert x hknot from rfl, DB.insert_keys, List.orderedInsert_length]
have hfilne : d₁.keys.filter
(fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) ≠ res.keys := by
intro heq
have hlen : (d₁.keys.filter
(fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).length =
res.keys.length + 1 := by rw [hfil₁, hcomplen]
rw [heq] at hlen
omega
-- compatibility transfer along the sound range
have hagree : AgreeOn cr d₀ d₁ :=
(ConflictRange.keys_insert_of_not_mem cr d₀ hknot hxcr).symm
have hcompD₁ : RangeRead.Compatible d₁ r res := (hs d₀ d₁ hagree).mp hcompD₀
have hkey₁ : d₁.keys.filter
(fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) = res.keys := by
rcases hcompD₁.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
· simp [hmore] at hm
· exact (completeKeys_eq_iff_filter_ge_begin_of_room
(db := d₁) (r := r) (res := res) hrev hbegin (by omega) (le_of_lt hcross)
hne hroom₁).mp heq.symm
exact hfilne hkey₁
end FormalConflictRange
namespace FormalConflictRange
/-- **Necessity of every key in `[end_.key, begin_.key)` in the crossed top branch.** With
enough room in the gap, a key `k` with `E ≤ k < B` can be toggled: a database of `s - 1`
gap keys, the reported keys, and one extra key above the reported last has complete
window of length `t + 1`, while inserting `k` restores the reported keys. -/
theorem necessary_of_mem_interval_crossed_top {r : RangeRead} {res : Result} {k : Key}
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = false)
(hne : res.keys ≠ []) (hbegin : r.begin.offset = 1)
(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.end_.offset - 1).toNat)
(hroom : (((r.end_.offset - 1).toNat -
res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) : ℕ) : ℕ∞) ≤
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
have hte : t < eo := by
have hcount := crossed_complete_t_eq_length hread hmore hrev hbegin hcross (by omega)
rw [hcount] at ht
simpa [t, eo, htdef, heodef] using ht
set s : ℕ := eo - t with hsdef
have hs : 0 < s := by omega
have hsub : s - 1 + 1 = s := Nat.sub_add_cancel (by omega : 1 ≤ s)
have htlen := crossed_complete_t_eq_length hread hmore hrev hbegin hcross (by omega)
have hcard : (((s - 1) + 1 : ℕ) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key := by
rw [hsub]
have hroom' : ((eo - t : ℕ) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key := by
simpa [eo, t, htdef, heodef, htlen] using hroom
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
have hall_ge : ∀ x ∈ res.keys, r.begin.key ≤ (x : WithTop Key) :=
crossed_mem_result_ge_begin hread hmore hbegin
obtain ⟨db₀, hcomp₀⟩ := hread
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
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 hHres_lt : ∀ a ∈ dbH.keys, ∀ b ∈ res.keys, a < b :=
fun a ha b hb =>
WithTop.coe_lt_coe.mp (lt_of_lt_of_le (hHltB a ha) (hall_ge b hb))
have hHres_sorted : (dbH.keys ++ res.keys).SortedLT :=
List.sortedLT_append.mpr ⟨dbH.sorted, hsort, hHres_lt⟩
have hsingle : ([C] : List Key).SortedLT := by
rw [List.sortedLT_cons]
exact ⟨by simp, List.sortedLT_nil⟩
have hcrossList : ∀ a ∈ (dbH.keys ++ 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 haH | haR
· exact hHltC a haH
· exact hCgtRes a haR
have hlst_sorted : (dbH.keys ++ res.keys ++ [C]).SortedLT :=
List.sortedLT_append.mpr ⟨hHres_sorted, hsingle, hcrossList⟩
let db₂ : DB := ⟨dbH.keys ++ res.keys ++ [C], hlst_sorted⟩
have hdb₂ : db₂.keys = dbH.keys ++ res.keys ++ [C] := rfl
-- the filter at or above `begin.key`
have hfil₂ : db₂.keys.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) = res.keys ++ [C] := by
rw [hdb₂, List.filter_append, List.filter_append]
have hHf : dbH.keys.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) = [] := by
rw [List.filter_eq_nil_iff]
intro x hx
rw [decide_eq_true_eq]
exact not_le.mpr (hHltB x hx)
have hresf : res.keys.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) = res.keys := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
exact hall_ge x hx
have hCf : ([C] : List Key).filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) = [C] := by
rw [List.filter_eq_self]
intro x hx
rw [List.mem_singleton] at hx
subst hx
rw [decide_eq_true_eq]
exact le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge)
rw [hHf, hresf, hCf]
simp
-- counts for `db₂`
have hcE₂ : cnt db₂ r.end_.key = 0 := by
apply cnt_eq_zero_of_forall_ge
intro x hx
rw [hdb₂] at hx
rcases List.mem_append.mp hx with hx' | hxC
· rcases List.mem_append.mp hx' with hxH | hxR
· exact hHgeE x hxH
· 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 [hdb₂, 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 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 [List.mem_singleton] at hx
subst hx
rw [decide_eq_true_eq]
exact not_lt.mpr (le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge))
rw [hHc, hresc, hCc, hHlen]
omega
have hn₂ : db₂.keys.length = eo := by
rw [hdb₂, List.length_append, List.length_append, hHlen]
have htres : res.keys.length = t := rfl
rw [htres, List.length_singleton]
omega
have hk_db₂ : k ∉ db₂.keys := by
rw [hdb₂]
intro hmem
rcases List.mem_append.mp hmem with hmem' | hmemC
· rcases List.mem_append.mp hmem' with hmemH | hmemR
· exact hkH hmemH
· exact absurd (hall_ge k hmemR) (not_le.mpr hkB)
· rw [List.mem_singleton] at hmemC
have hkC : k = C := 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 [hkC] 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₂]
have hfil₁ : (db₂.insert k hk_db₂).keys.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) = res.keys ++ [C] := by
have hsingle_filter : List.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) (k :: db₂.keys) =
db₂.keys.filter (fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) := by
rw [List.filter_cons]
have hkf : decide (r.begin.key ≤ (k : WithTop Key)) = false := by
rw [decide_eq_false_iff_not]
exact not_le.mpr hkB
rw [hkf]
rfl
have hperm : List.Perm ((List.orderedInsert (· ≤ ·) k db₂.keys).filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))))
(db₂.keys.filter (fun x : Key => decide (r.begin.key ≤ (x : WithTop Key)))) := by
have h := (List.perm_orderedInsert (· ≤ ·) k db₂.keys).filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key)))
rwa [hsingle_filter] at h
have hs₁ : ((List.orderedInsert (· ≤ ·) k db₂.keys).filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key)))).SortedLT :=
List.sortedLT_iff_pairwise.mpr ((db₂.insert k hk_db₂).sorted.pairwise.filter _)
have hs₂ : (db₂.keys.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key)))).SortedLT :=
List.sortedLT_iff_pairwise.mpr (db₂.sorted.pairwise.filter _)
rw [DB.insert_keys]
exact (List.SortedLT.eq_of_mem_iff hs₁ hs₂ (fun x => hperm.mem_iff)).trans hfil₂
-- 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 hidx : min (cnt (db₂.insert k hk_db₂) r.end_.key + eo)
(db₂.insert k hk_db₂).keys.length -
cnt (db₂.insert k hk_db₂) r.begin.key = t := by
rw [hcE₁, hn₁, hp₁]
omega
have htake : (res.keys ++ [C]).take t = res.keys := by
rw [List.take_append_of_le_length (le_of_eq htres.symm)]
exact List.take_length
have hidx' : min (List.countP (fun x : Key => decide ((x : WithTop Key) < r.end_.key))
(db₂.insert k hk_db₂).keys + (r.end_.offset - 1).toNat)
(db₂.insert k hk_db₂).keys.length -
List.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key))
(db₂.insert k hk_db₂).keys = t := by
simpa [cnt, eo] using hidx
rw [completeKeys_eq_filter_take_of_offset_one hrev hbegin (by omega), hfil₁, 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 hlenComplete₂ : (RangeRead.completeKeys db₂ r).length = t + 1 := by
rw [completeKeys_length_of_offset_one hrev hbegin (by omega)]
change min (cnt db₂ r.end_.key + eo) db₂.keys.length - cnt db₂ r.begin.key = t + 1
rw [hcE₂, hn₂, hp₂]
omega
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 hlenComplete₂
rw [ht_eq] at hlenComplete₂
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.** If the gap
`[end_.key, begin_.key)` holds at least the overshoot `e - t` keys, the minimal range is
`[end_.key, ⊤)`. Soundness is general; keys in the gap are necessary by
`necessary_of_mem_interval_crossed_top`, and keys at or above `begin.key` by
`necessary_of_begin_le_crossed_top`. -/
theorem minimal_topRange_of_crossed_large_room {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = false) (hrev : r.reverse = false)
(hne : res.keys ≠ []) (hbegin : r.begin.offset = 1)
(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.end_.offset - 1).toNat)
(hroom : (((r.end_.offset - 1).toNat -
res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) : ℕ) : ℕ∞) ≤
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 hread hmore hrev hne hbegin hcross hend
ht hroom hkE hkB
· exact necessary_of_begin_le_crossed_top hread hmore hrev hne hbegin hcross hend ht
(not_lt.mp hkB)
end FormalConflictRange
namespace FormalConflictRange
/-- A readable crossed complete result with begin offset one has end offset at least
two: if `end_.offset ≤ 1`, `alwaysEmpty_of_begin_gt_end` makes the complete keys empty. -/
theorem crossed_end_offset_ge_two {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) :
2 ≤ r.end_.offset := by
by_contra h
have hend : r.end_.offset ≤ 1 := by omega
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 hemp := alwaysEmpty_of_begin_gt_end (r := r) hbegin hend hcross db₀
rw [← hres] at hemp
exact hne hemp
end FormalConflictRange
namespace FormalConflictRange
/-- The number of reported keys at or above `end_.key`. -/
def reportedAtEnd (r : RangeRead) (res : Result) : ℕ :=
res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key)))
/-- The overshoot `e = (end_.offset - 1).toNat`. -/
def endOvershoot (r : RangeRead) : ℕ := (r.end_.offset - 1).toNat
/-- The remaining overshoot `s = e - t` in the crossed complete top branch. -/
def gapOvershoot (r : RangeRead) (res : Result) : ℕ :=
endOvershoot r - reportedAtEnd r res
/-- A unified forward complete rule at begin offset one, valid on crossed selectors:
the lower endpoint moves down to `end_.key` exactly when the gap has room for the
overshoot `e - t`; the upper endpoint is `keyAfter (last reported)` in the finite branch
`t = e` and `⊤` otherwise. -/
def completeForwardClosed (r : RangeRead) (res : Result) : ConflictRange :=
if r.end_.offset ≤ 1 then canonicalRange r
else if reportedAtEnd r res = endOvershoot r then
⟨if r.end_.key < r.begin.key ∧
(gapOvershoot r res : ℕ∞) ≤ intervalCard r.end_.key r.begin.key
then r.end_.key else r.begin.key,
(keyAfter (res.keys.getLastD ([] : Key)) : WithTop Key)⟩
else
⟨if r.end_.key < r.begin.key ∧
(gapOvershoot r res : ℕ∞) ≤ intervalCard r.end_.key r.begin.key
then r.end_.key else r.begin.key,
⊤⟩
/-- Crossed complete forward minimality for the unified rule. -/
theorem minimal_completeForward_of_crossed {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
(hrev : r.reverse = false) (hbegin : r.begin.offset = 1)
(hcross : r.end_.key < r.begin.key) :
Minimal r res (completeForwardClosed r res) := by
have hend2 : 2 ≤ r.end_.offset :=
crossed_end_offset_ge_two hread hmore hne (by omega) hcross
have htle : reportedAtEnd r res ≤ endOvershoot r := by
have h := crossed_complete_t_le_e hread hmore hrev hbegin hcross (by omega)
simpa [reportedAtEnd, endOvershoot] using h
by_cases hte : reportedAtEnd r res = endOvershoot r
· have hmin : Minimal r res
⟨r.end_.key, (keyAfter (res.keys.getLastD ([] : Key)) : WithTop Key)⟩ :=
minimal_truncatedRange_of_finite_crossed hread hmore hne hrev hbegin hcross
hend2 (by simpa [reportedAtEnd, endOvershoot] using hte)
have hs0 : gapOvershoot r res = 0 := by
simp [gapOvershoot, hte]
rw [completeForwardClosed, ite_eq_right (by omega : ¬ r.end_.offset ≤ 1), ite_eq_left hte]
rw [ite_eq_left (by refine ⟨hcross, ?_⟩; rw [hs0]; simp)]
exact hmin
· have htlt : reportedAtEnd r res < endOvershoot r := lt_of_le_of_ne htle hte
have htlt' : res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) <
(r.end_.offset - 1).toNat := by
simpa [reportedAtEnd, endOvershoot] using htlt
by_cases hroom : (gapOvershoot r res : ℕ∞) ≤ intervalCard r.end_.key r.begin.key
· have hroom' : ((((r.end_.offset - 1).toNat -
res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) : ℕ) : ℕ∞)) ≤
intervalCard r.end_.key r.begin.key := by
simpa [gapOvershoot, endOvershoot, reportedAtEnd] using hroom
have hmin : Minimal r res ⟨r.end_.key, ⊤⟩ :=
minimal_topRange_of_crossed_large_room hread hmore hrev hne hbegin hcross hend2
htlt' hroom'
rw [completeForwardClosed, ite_eq_right (by omega : ¬ r.end_.offset ≤ 1), ite_eq_right hte]
rw [ite_eq_left (by refine ⟨hcross, ?_⟩; exact hroom)]
exact hmin
· have hroom' : intervalCard r.end_.key r.begin.key <
((((r.end_.offset - 1).toNat -
res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) : ℕ) : ℕ∞))
:= by
simpa [gapOvershoot, endOvershoot, reportedAtEnd] using lt_of_not_ge hroom
have hmin : Minimal r res ⟨r.begin.key, ⊤⟩ :=
minimal_topRange_of_crossed_small_room hread hmore hne hrev hbegin hcross hend2
htlt' hroom'
rw [completeForwardClosed, ite_eq_right (by omega : ¬ r.end_.offset ≤ 1), ite_eq_right hte]
rw [ite_eq_right (by intro h; exact hroom h.2)]
exact hmin
/-- The reversed-traversal analogue of `completeForwardClosed`: the upper endpoint is
`keyAfter (head reported)` in the finite branch, and the lower endpoint is chosen by the
same crossed-room test. -/
def completeReversedClosed (r : RangeRead) (res : Result) : ConflictRange :=
if r.end_.offset ≤ 1 then canonicalRange r
else if reportedAtEnd r res = endOvershoot r then
⟨if r.end_.key < r.begin.key ∧
(gapOvershoot r res : ℕ∞) ≤ intervalCard r.end_.key r.begin.key
then r.end_.key else r.begin.key,
(keyAfter (res.keys.headD ([] : Key)) : WithTop Key)⟩
else
⟨if r.end_.key < r.begin.key ∧
(gapOvershoot r res : ℕ∞) ≤ intervalCard r.end_.key r.begin.key
then r.end_.key else r.begin.key,
⊤⟩
/-- Crossed complete reversed minimality, by flipping the traversal to the forward
crossed theorem. -/
theorem minimal_completeReversed_of_crossed {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
(hrev : r.reverse = true) (hbegin : r.begin.offset = 1)
(hcross : r.end_.key < r.begin.key) :
Minimal r res (completeReversedClosed 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 hmin' : Minimal r' res' (completeForwardClosed r' res') :=
minimal_completeForward_of_crossed hread' rfl hne' rfl hbegin hcross
have hflip := (minimal_flip (r := r) (res := res)
(cr := completeForwardClosed r' res') (b := true) hrev hmore)
have hformula : completeForwardClosed r' res' = completeReversedClosed r res := by
unfold completeForwardClosed completeReversedClosed
dsimp only [r', res']
simp only [endOvershoot, gapOvershoot, reportedAtEnd, List.countP_reverse,
getLastD_reverse]
rfl
have hflip' : Minimal r res (completeForwardClosed r' res') := hflip.mp hmin'
rw [hformula] at hflip'
exact hflip'
end FormalConflictRange
namespace FormalConflictRange
/-- On cross-free selectors the unified forward rule is the existing compact
`closedFormOffsetOne`. -/
theorem completeForwardClosed_eq_closedFormOffsetOne {r : RangeRead} {res : Result}
(hcross : r.begin.key ≤ r.end_.key) :
completeForwardClosed r res = closedFormOffsetOne r res := by
unfold completeForwardClosed closedFormOffsetOne
by_cases h : r.end_.offset ≤ 1
· rw [ite_eq_left h, ite_eq_left h]
· rw [ite_eq_right h, ite_eq_right h]
have hnc : ¬ r.end_.key < r.begin.key := not_lt.mpr hcross
simp only [hnc, false_and, ite_false]
rfl
/-- On cross-free selectors the unified reversed rule is the existing compact
`closedFormOffsetOneRev`. -/
theorem completeReversedClosed_eq_closedFormOffsetOneRev {r : RangeRead} {res : Result}
(hcross : r.begin.key ≤ r.end_.key) :
completeReversedClosed r res = closedFormOffsetOneRev r res := by
unfold completeReversedClosed closedFormOffsetOneRev
by_cases h : r.end_.offset ≤ 1
· rw [ite_eq_left h, ite_eq_left h]
· rw [ite_eq_right h, ite_eq_right h]
have hnc : ¬ r.end_.key < r.begin.key := not_lt.mpr hcross
simp only [hnc, false_and, ite_false]
rfl
/-- The complete closed-form rule at begin offset one, dispatching on traversal order. -/
def completeClosed (r : RangeRead) (res : Result) : ConflictRange :=
if r.reverse then completeReversedClosed r res else completeForwardClosed r res
/-- **Total complete closed form at begin offset one.** The rule is minimal for every
readable complete result, crossed or cross-free, in either traversal order. -/
theorem minimal_completeClosed {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = false) (hne : res.keys ≠ [])
(hbegin : r.begin.offset = 1) :
Minimal r res (completeClosed r res) := by
unfold completeClosed
by_cases hrev : r.reverse = true
· rw [ite_eq_left hrev]
by_cases hcross : r.end_.key < r.begin.key
· exact minimal_completeReversed_of_crossed hread hmore hne hrev hbegin hcross
· have hcf : r.begin.key ≤ r.end_.key := not_lt.mp hcross
rw [completeReversedClosed_eq_closedFormOffsetOneRev hcf]
exact minimal_closedForm_of_offset_one_rev hread hmore hne hrev hbegin hcf
· rw [ite_eq_right hrev]
have hrevf : r.reverse = false := by
cases hr : r.reverse <;> simp_all
by_cases hcross : r.end_.key < r.begin.key
· exact minimal_completeForward_of_crossed hread hmore hne hrevf hbegin hcross
· have hcf : r.begin.key ≤ r.end_.key := not_lt.mp hcross
rw [completeForwardClosed_eq_closedFormOffsetOne hcf]
exact minimal_closedForm_of_offset_one hread hmore hne hrevf hbegin hcf
end FormalConflictRange