/- Released under Apache 2.0 license as described in the file LICENSE. -/ import FormalConflictRange.CrossedTruncatedGeneral import FormalConflictRange.CrossedRevGeneral import FormalConflictRange.CrossedResidual import FormalConflictRange.CrossedResidualCond import FormalConflictRange.Residual import FormalConflictRange.CrossFreeResidual import FormalConflictRange.ClosedFormTotal import FormalConflictRange.NonposClosedForm import FormalConflictRange.NonposRevClosedForm import FormalConflictRange.NegCrossClosedForm import FormalConflictRange.NegCrossComplete import FormalConflictRange.NegCrossBottom import FormalConflictRange.NegCrossClampNonpos import FormalConflictRange.NegCrossClampLongNonpos import FormalConflictRange.NegCrossCompleteResidual import FormalConflictRange.NegCrossCompleteHigh import FormalConflictRange.NegCrossHighClamp import FormalConflictRange.NegCrossResidual import FormalConflictRange.NegCrossLongNonpos import FormalConflictRange.NegCrossTruncNonclamp import FormalConflictRange.NegCrossTruncClamp import FormalConflictRange.NegCrossTruncRevTop import FormalConflictRange.NegCrossTruncRevFinite import FormalConflictRange.NegCrossTruncRevBeginTop import FormalConflictRange.NegCrossTruncRevBeginTopGeTwo import FormalConflictRange.NegCrossTruncRevBelowEnd import FormalConflictRange.NegCrossTruncRevNonpos import FormalConflictRange.NegCrossTruncRevCrossedSmall import FormalConflictRange.NegCrossTruncRevCrossedLarge import FormalConflictRange.NegCrossTruncRevCrossedNonpos import FormalConflictRange.NegCrossTruncRevResidual import FormalConflictRange.NegCrossTruncRevResidualLargeTop import FormalConflictRange.NegCrossTruncRevResidualLargeSentinel import FormalConflictRange.NegCrossTruncRevResidualFinite import FormalConflictRange.NegCrossTruncRevResidualFiniteOver import FormalConflictRange.ZeroCrossLong import FormalConflictRange.ZeroCrossTrunc import FormalConflictRange.ComputableAlgorithm /-! # A total result-aware closed form This module assembles the compact closed forms proved in the preceding modules into a single total rule, `conflictRangeClosedForm`. At positive begin offsets it covers * complete results in either traversal: the cross-free rule `closedFormCompleteCrossFree` (forward) and its flip `closedFormCompleteCrossFreeRev` (reversed), and the crossed rule `completeCrossedGeneral`; * forward truncated results: the cross-free rule `closedFormTruncatedGeneral` and the crossed rule `truncatedForwardCrossedGeneral`. Beyond begin offset one, the crossed reversed truncated finite branch `t + (begin.offset - 1) = (end.offset - 1)` is inlined as the compact rule `[end_.key, keyAfter (head reported))`, and the complementary crossed residual uses `closedFormCrossedResidual`: it is `[begin.key, ⊤)` when the capacity condition `crossedResidualCond` fails (`minimal_crossedResidual_not_cond`) and `[end_.key, ⊤)` when it holds (`minimal_crossedResidual_cond`). The cross-free residual at `begin.offset ≥ 2` with a reported key at or above `end.key` is `closedFormCrossFreeResidual`, which is the compact truncated range on the finite branch and the top range otherwise. No nonempty positive-offset cell falls back to the exact executable algorithm. At nonpositive begin offsets it uses the cross-free complete rule `closedFormCompleteNonposCrossFree`, the forward truncated rules `closedFormNonposFwdTrunc` (`end.offset ≥ 1`) and `closedFormNonposFwdTruncNonpos` (`end.offset ≤ 0`), the reversed truncated rule `closedFormNonposRevTrunc`, and the crossed complete rules at begin offset zero `closedFormZeroCrossOvershoot`, `closedFormZeroCrossEndOne`, and `closedFormZeroCrossEndOneLong`, and the crossed complete overshoot at negative begin offsets `closedFormNegCrossOvershoot` (full range when the reported keys below `begin.key` fit the begin slack, the top range from the reported head otherwise). The residual nonpositive crossed cells delegate to the exact executable `simpleConflictRange`. The resulting definition is total and minimal on every `Readable` pair (`minimal_conflictRangeClosedForm_total`), and denotes the same key set as both `conflictRangeGeneral` and the executable algorithm. -/ open FormalConflictRange namespace FormalConflictRange /-- The reversed-traversal cross-free complete-result closed form, obtained by flipping to the forward rule. -/ noncomputable def closedFormCompleteCrossFreeRev (r : RangeRead) (res : Result) : ConflictRange := closedFormCompleteCrossFree { r with reverse := false } { keys := res.keys.reverse, more := false } /-- The reversed cross-free complete rule is minimal at every positive begin offset. -/ theorem minimal_closedForm_of_complete_crossFree_rev {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.begin.key ≤ r.end_.key) : Minimal r res (closedFormCompleteCrossFreeRev 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' (closedFormCompleteCrossFree r' res') := minimal_closedForm_of_complete_crossFree hread' rfl rfl hne' hbegin hcross have hflip := (minimal_flip (r := r) (res := res) (cr := closedFormCompleteCrossFree r' res') (b := true) hrev hmore) exact hflip.mp hmin' /-- The reversed cross-free complete rule denotes the general conflict range. -/ theorem closedFormCompleteCrossFreeRev_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.begin.key ≤ r.end_.key) : (closedFormCompleteCrossFreeRev r res).toSet = (conflictRangeGeneral r res).toSet := (minimal_closedForm_of_complete_crossFree_rev hread hmore hrev hne hbegin hcross).toSet_eq (conflictRangeGeneral_minimal hread) /-- The same identification with the executable algorithm. -/ theorem closedFormCompleteCrossFreeRev_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.begin.key ≤ r.end_.key) : (closedFormCompleteCrossFreeRev r res).toSet = (simpleConflictRange r res).toSet := (minimal_closedForm_of_complete_crossFree_rev hread hmore hrev hne hbegin hcross).toSet_eq (simpleConflictRange_minimal hread) /-- The crossed reversed truncated residual: when the capacity condition fails, the minimal range is `[begin.key, ⊤)`; when it holds, the minimal range is `[end_.key, ⊤)`. -/ noncomputable def closedFormCrossedResidual (r : RangeRead) (res : Result) : ConflictRange := by classical exact if h : res.keys = [] then emptyValue r else if crossedResidualCond r res h then ⟨r.end_.key, ⊤⟩ else ⟨r.begin.key, ⊤⟩ /-- The crossed nonpositive-begin complete overshoot closed form at begin offset zero. -/ noncomputable def closedFormZeroCrossOvershoot (r : RangeRead) (res : Result) : ConflictRange := topOfLast (leastReported r res) /-- The crossed nonpositive-begin complete under-end closed form at begin offset zero, `end.offset = 1` and `begin.key ≤ end_.key`. -/ noncomputable def closedFormZeroCrossEndOne (r : RangeRead) (res : Result) : ConflictRange := ⟨((leastReported r res : Key) : WithTop Key), r.end_.key⟩ /-- The crossed nonpositive-begin complete long under-end closed form at begin offset zero, `end.offset = 1` and `end_.key < begin.key`. -/ noncomputable def closedFormZeroCrossEndOneLong (r : RangeRead) (res : Result) : ConflictRange := ⟨((leastReported r res : Key) : WithTop Key), r.begin.key⟩ /-- The crossed nonpositive-begin complete under-end closed form at begin offset zero and `end.offset ≤ 0`. -/ noncomputable def closedFormZeroCrossEndNonpos (r : RangeRead) (res : Result) : ConflictRange := ⟨((leastReported r res : Key) : WithTop Key), r.end_.key⟩ /-- The crossed complete begin-zero under-end closed form at `end.offset ≥ 2` and `begin.key ≤ end.key`, via the offset-one anchor at the reported head. -/ noncomputable def closedFormZeroCrossUnderEnd (r : RangeRead) (res : Result) : ConflictRange := closedFormOffsetOneTotal (zeroBeginAnchor r res) res /-- **The crossed complete begin-zero under-end rule with `end.offset ≥ 2` and `begin.key ≤ end.key` is minimal.** The crossed read and its offset-one anchor have the same compatible databases, so the offset-one closed form answers it. -/ theorem minimal_closedForm_of_zeroCross_underEnd {r : RangeRead} {res : Result} (hread : Readable r res) (h : zeroCrossUnderEnd r res) : Minimal r res (closedFormZeroCrossUnderEnd r res) := by obtain ⟨hbegin, hmore, hrev, hend2, hne, hcrossD, hBE⟩ := h have hleast : leastReported r res = res.keys.head hne := by simp only [leastReported, hrev] rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl have hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key := by rw [← hleast]; exact hcrossD let r' := zeroBeginAnchor r res have hiff := compatible_zero_crossed_iff_anchor hread hrev hmore hne hbegin hcross hBE (by omega) have hread' : Readable r' res := by obtain ⟨db, hcomp⟩ := hread exact ⟨db, (hiff db).mp hcomp⟩ have hmin' : Minimal r' res (closedFormOffsetOneTotal r' res) := minimal_closedForm_of_offset_one_total hread' hne (by simp [r', zeroBeginAnchor]) exact minimal_of_compatible_iff hiff hmin' /-- **The crossed complete begin-zero long-cell rule with `begin.key = ⊤` is minimal.** -/ theorem minimal_closedForm_of_zeroCross_longTop {r : RangeRead} {res : Result} (hread : Readable r res) (h : zeroCrossLongTop r res) : Minimal r res (closedFormZeroCrossLong r res) := by obtain ⟨hbegin, hmore, hrev, hend, hne, htop⟩ := h exact minimal_closedForm_of_zero_cross_long_top hread hrev hmore hne hbegin htop hend /-- **The crossed complete begin-zero long-cell rule at finite `begin.key` is minimal.** -/ theorem minimal_closedForm_of_zeroCross_longFinite {r : RangeRead} {res : Result} (hread : Readable r res) (h : zeroCrossLongFinite r res) : Minimal r res (closedFormZeroCrossLong r res) := by obtain ⟨hbegin, hmore, hrev, hend, hne, hB, hlong, hleast⟩ := h have hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key := by have hleast' : leastReported r res = res.keys.head hne := by simp only [leastReported, hrev] rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl rw [← hleast']; exact hleast exact minimal_closedForm_of_zero_cross_long_finite hread hrev hmore hne hbegin hcross hend hlong hB /-- **The crossed nonpositive-begin complete overshoot rule is minimal.** -/ theorem minimal_closedForm_of_zeroCross_overshoot {r : RangeRead} {res : Result} (hread : Readable r res) (h : zeroCrossOvershootComplete r res) : Minimal r res (closedFormZeroCrossOvershoot r res) := by obtain ⟨hbegin, hmore, hrev, hov, hcrossD⟩ := h obtain ⟨hend, hne, hhi⟩ := hov have hleast : leastReported r res = res.keys.head hne := by simp only [leastReported, hrev] rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl have hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key := by rw [← hleast]; exact hcrossD unfold closedFormZeroCrossOvershoot rw [hleast] exact minimal_topOfHead_of_zero_begin_crossed_overshoot hread hrev hmore hne hbegin hcross hend hhi /-- **The crossed nonpositive-begin complete under-end rule at `end.offset = 1` is minimal.** -/ theorem minimal_closedForm_of_zeroCross_endOne {r : RangeRead} {res : Result} (hread : Readable r res) (h : zeroCrossEndOne r res) : Minimal r res (closedFormZeroCrossEndOne r res) := by obtain ⟨hbegin, hmore, hrev, hend, hne, hcrossD, hkeyle⟩ := h have hleast : leastReported r res = res.keys.head hne := by simp only [leastReported, hrev] rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl have hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key := by rw [← hleast]; exact hcrossD unfold closedFormZeroCrossEndOne rw [hleast] exact minimal_headToEnd_of_zero_begin_crossed_endOne hread hrev hmore hne hbegin hcross hend hkeyle /-- **The crossed nonpositive-begin complete long under-end rule at `end.offset = 1` is minimal.** -/ theorem minimal_closedForm_of_zeroCross_endOne_long {r : RangeRead} {res : Result} (hread : Readable r res) (h : zeroCrossEndOneLong r res) : Minimal r res (closedFormZeroCrossEndOneLong r res) := by obtain ⟨hbegin, hmore, hrev, hend, hne, hcrossD, hlong⟩ := h have hleast : leastReported r res = res.keys.head hne := by simp only [leastReported, hrev] rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl have hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key := by rw [← hleast]; exact hcrossD unfold closedFormZeroCrossEndOneLong rw [hleast] exact minimal_headToBeginKey_of_zero_begin_crossed_endOne_long hread hrev hmore hne hbegin hcross hend hlong /-- **The crossed nonpositive-begin complete under-end rule with `end.offset ≤ 0` is minimal.** -/ theorem minimal_closedForm_of_zeroCross_endNonpos {r : RangeRead} {res : Result} (hread : Readable r res) (h : zeroCrossEndNonpos r res) : Minimal r res (closedFormZeroCrossEndNonpos r res) := by obtain ⟨hbegin, hmore, hrev, hend, hne, hcrossD⟩ := h have hleast : leastReported r res = res.keys.head hne := by simp only [leastReported, hrev] rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl have hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key := by rw [← hleast]; exact hcrossD unfold closedFormZeroCrossEndNonpos rw [hleast] exact minimal_headToEnd_of_zero_begin_crossed_endNonpos hread hrev hmore hne hbegin hcross hend /-- The crossed complete begin-zero closed form in a single dispatch, used for the reversed reduction. -/ noncomputable def closedFormZeroCrossComplete (r : RangeRead) (res : Result) : ConflictRange := if r.end_.offset ≤ 0 then closedFormZeroCrossEndNonpos r res else if r.end_.offset = 1 then if r.end_.key < r.begin.key then closedFormZeroCrossEndOneLong r res else closedFormZeroCrossEndOne r res else if r.begin.key = (⊤ : WithTop Key) then closedFormZeroCrossLong r res else if r.end_.key < r.begin.key then closedFormZeroCrossLong r res else closedFormZeroCrossUnderEnd r res /-- **The crossed complete begin-zero forward rule is minimal.** Every crossed complete forward result at begin offset zero falls into one of the end-offset / selector-order cells closed above. -/ theorem minimal_closedForm_of_zeroCross_complete {r : RangeRead} {res : Result} (hread : Readable r res) (hrev : r.reverse = false) (hbegin : r.begin.offset = 0) (hmore : res.more = false) (hne : res.keys ≠ []) (hcross : ((leastReported r res : Key) : WithTop Key) < r.begin.key) : Minimal r res (closedFormZeroCrossComplete r res) := by unfold closedFormZeroCrossComplete by_cases hE0 : r.end_.offset ≤ 0 · rw [ite_eq_left hE0] exact minimal_closedForm_of_zeroCross_endNonpos hread ⟨hbegin, hmore, hrev, hE0, hne, hcross⟩ · rw [ite_eq_right hE0] by_cases hE1 : r.end_.offset = 1 · rw [ite_eq_left hE1] by_cases hlong : r.end_.key < r.begin.key · rw [ite_eq_left hlong] exact minimal_closedForm_of_zeroCross_endOne_long hread ⟨hbegin, hmore, hrev, hE1, hne, hcross, hlong⟩ · rw [ite_eq_right hlong] exact minimal_closedForm_of_zeroCross_endOne hread ⟨hbegin, hmore, hrev, hE1, hne, hcross, not_lt.mp hlong⟩ · rw [ite_eq_right hE1] have hE2 : 2 ≤ r.end_.offset := by omega by_cases htop : r.begin.key = (⊤ : WithTop Key) · rw [ite_eq_left htop] exact minimal_closedForm_of_zeroCross_longTop hread ⟨hbegin, hmore, hrev, hE2, hne, htop⟩ · rw [ite_eq_right htop] by_cases hlong : r.end_.key < r.begin.key · rw [ite_eq_left hlong] exact minimal_closedForm_of_zeroCross_longFinite hread ⟨hbegin, hmore, hrev, hE2, hne, htop, hlong, hcross⟩ · rw [ite_eq_right hlong] exact minimal_closedForm_of_zeroCross_underEnd hread ⟨hbegin, hmore, hrev, hE2, hne, hcross, not_lt.mp hlong⟩ /-- The reversed-traversal crossed complete begin-zero closed form, obtained by flipping to the forward rule. -/ noncomputable def closedFormZeroCrossCompleteRev (r : RangeRead) (res : Result) : ConflictRange := closedFormZeroCrossComplete { r with reverse := false } { keys := res.keys.reverse, more := false } /-- **The reversed crossed complete begin-zero rule is minimal.** -/ theorem minimal_closedForm_of_zeroCross_complete_rev {r : RangeRead} {res : Result} (hread : Readable r res) (hrev : r.reverse = true) (hbegin : r.begin.offset = 0) (hmore : res.more = false) (hne : res.keys ≠ []) (hcross : ((leastReported r res : Key) : WithTop Key) < r.begin.key) : Minimal r res (closedFormZeroCrossCompleteRev 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 hleast : leastReported r' res' = leastReported r res := by have h1 : leastReported r' res' = res'.keys.headD ([] : Key) := by simp [leastReported, r'] have h2 : leastReported r res = res.keys.getLastD ([] : Key) := by simp [leastReported, hrev] rw [h1, h2] simp only [res'] rw [List.headD_eq_head?, List.getLastD_eq_getLast?, List.head?_reverse] have hcross' : ((leastReported r' res' : Key) : WithTop Key) < r'.begin.key := by rw [hleast] exact hcross have hmin' : Minimal r' res' (closedFormZeroCrossComplete r' res') := minimal_closedForm_of_zeroCross_complete hread' rfl hbegin rfl hne' hcross' have hflip := (minimal_flip (r := r) (res := res) (cr := closedFormZeroCrossComplete r' res') (b := true) hrev hmore) exact hflip.mp hmin' /-- Minimality is invariant under a change of the result that preserves the compatible databases. -/ theorem minimal_congr_of_compatible_res {r : RangeRead} {res res' : Result} {cr : ConflictRange} (h : ∀ db, RangeRead.Compatible db r res ↔ RangeRead.Compatible db r res') : Minimal r res cr ↔ Minimal r res' cr := by have hS : ∀ cr, Sound r res cr ↔ Sound r res' cr := by intro cr unfold Sound constructor <;> intro hs db₁ db₂ hagree · exact (h db₁).symm.trans ((hs db₁ db₂ hagree).trans (h db₂)) · exact (h db₁).trans ((hs db₁ db₂ hagree).trans (h db₂).symm) have hN : ∀ k, Necessary r res k ↔ Necessary r res' k := by intro k unfold Necessary exact ⟨fun hk cr hs => hk cr ((hS cr).mpr hs), fun hk cr hs => hk cr ((hS cr).mp hs)⟩ rw [minimal_iff_sound_and_necessary, minimal_iff_sound_and_necessary] constructor · rintro ⟨hs, hnec⟩ exact ⟨(hS cr).mp hs, fun k hk => (hN k).mp (hnec k hk)⟩ · rintro ⟨hs, hnec⟩ exact ⟨(hS cr).mpr hs, fun k hk => (hN k).mpr (hnec k hk)⟩ /-- A nonempty *truncated reversed* result at begin offset zero that is crossed (the reported last lies strictly below `begin.key`). On this cell the reported keys are already the whole window: the reversed complete keys all lie at or above the reported last, so the `≥ last` filter of the truncated bridge is the identity. The compatible databases are therefore the same as those of the complete result. -/ abbrev zeroCrossTruncRevCrossed (r : RangeRead) (res : Result) : Prop := r.begin.offset = 0 ∧ r.reverse = true ∧ res.more = true ∧ res.keys ≠ [] ∧ ((leastReported r res : Key) : WithTop Key) < r.begin.key /-- The begin-zero crossed reversed truncated closed form, by dropping the `more` flag and using the crossed complete begin-zero rule. -/ noncomputable def closedFormZeroCrossTruncRevCrossed (r : RangeRead) (res : Result) : ConflictRange := closedFormZeroCrossCompleteRev r { keys := res.keys, more := false } /-- Under the begin-zero crossed reversed truncated hypotheses, the truncated and complete results have the same compatible databases: the reported keys contain the reported last, so the reversed truncated bridge forces the whole window to be reported. -/ theorem compatible_zeroCrossTruncRevCrossed_iff_complete {r : RangeRead} {res : Result} (hrev : r.reverse = true) (hbegin : r.begin.offset = 0) (hmore : res.more = true) (hne : res.keys ≠ []) (hcross : ((res.keys.getLastD ([] : Key) : Key) : WithTop Key) < r.begin.key) : ∀ db, RangeRead.Compatible db r res ↔ RangeRead.Compatible db r { keys := res.keys, more := false } := by intro db have hlastD : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl have hB : ((res.keys.getLast hne : Key) : WithTop Key) < r.begin.key := by rw [← hlastD]; exact hcross constructor · intro hcomp obtain ⟨hlim, heq⟩ := (compatible_iff_truncated_keys_rev hrev hmore hne).mp hcomp have hlastmem_res : res.keys.getLast hne ∈ res.keys := List.getLast_mem hne have hlastmem_filter : res.keys.getLast hne ∈ (RangeRead.completeKeys db r).filter (fun k : Key => decide (res.keys.getLast hne ≤ k)) := by rw [heq]; exact hlastmem_res have hlastmem_ck : res.keys.getLast hne ∈ RangeRead.completeKeys db r := List.mem_of_mem_filter hlastmem_filter obtain ⟨hlastdb, hreslo, -⟩ := RangeRead.mem_completeKeys.mp hlastmem_ck have hres_ge : ((res.keys.getLast hne : Key) : WithTop Key) ≤ resolve db r.begin := resolve_zero_begin_le_of_mem_below hbegin hlastdb hB (res.keys.getLast hne) hlastdb hB have hres_eq : resolve db r.begin = ((res.keys.getLast hne : Key) : WithTop Key) := le_antisymm hreslo hres_ge have hfilter_id : (RangeRead.completeKeys db r).filter (fun k : Key => decide (res.keys.getLast hne ≤ k)) = RangeRead.completeKeys db r := by apply List.filter_eq_self.mpr intro k hk rw [decide_eq_true_eq] have hkge := (RangeRead.mem_completeKeys.mp hk).2.1 rw [hres_eq] at hkge exact WithTop.coe_le_coe.mp hkge have hck_eq : res.keys = RangeRead.completeKeys db r := by rw [hfilter_id] at heq; exact heq.symm exact ⟨hlim, Or.inr ⟨rfl, hck_eq⟩⟩ · intro hcomp rcases hcomp.2 with ⟨hm, -, -⟩ | ⟨-, heq⟩ · simp at hm · refine ⟨hcomp.1, Or.inl ⟨hmore, ?_, hne⟩⟩ exact heq ▸ List.prefix_refl (res.keys) /-- **The crossed begin-zero reversed truncated closed form is minimal.** The truncated result has the same compatible databases as its complete version, so the crossed complete begin-zero rule answers it. -/ theorem minimal_closedForm_of_zeroCross_trunc_revCrossed {r : RangeRead} {res : Result} (hread : Readable r res) (h : zeroCrossTruncRevCrossed r res) : Minimal r res (closedFormZeroCrossTruncRevCrossed r res) := by obtain ⟨hbegin, hrev, hmore, hne, hcrossD⟩ := h have hlastD : leastReported r res = res.keys.getLastD ([] : Key) := by simp [leastReported, hrev] have hcrossLast : ((res.keys.getLastD ([] : Key) : Key) : WithTop Key) < r.begin.key := by rw [← hlastD]; exact hcrossD have hcrossD' : ((leastReported r { keys := res.keys, more := false } : Key) : WithTop Key) < r.begin.key := by have hleast' : leastReported r { keys := res.keys, more := false } = res.keys.getLastD ([] : Key) := by simp [leastReported, hrev] rw [hleast']; exact hcrossLast have hread' : Readable r { keys := res.keys, more := false } := by obtain ⟨db, hcomp⟩ := hread exact ⟨db, (compatible_zeroCrossTruncRevCrossed_iff_complete hrev hbegin hmore hne hcrossLast db).mp hcomp⟩ have hmin' : Minimal r { keys := res.keys, more := false } (closedFormZeroCrossCompleteRev r { keys := res.keys, more := false }) := minimal_closedForm_of_zeroCross_complete_rev hread' hrev hbegin rfl hne hcrossD' exact (minimal_congr_of_compatible_res (compatible_zeroCrossTruncRevCrossed_iff_complete hrev hbegin hmore hne hcrossLast)).mpr hmin' /-- **The total result-aware closed form at every positive begin offset.** Empty results use the empty-result value `emptyValue`; every nonempty cell uses a compact closed form. -/ noncomputable def conflictRangeClosedForm (r : RangeRead) (res : Result) : ConflictRange := if res.keys = [] then emptyValue r else if nonposCompleteCrossFree r res then closedFormCompleteNonposCrossFree r res else if nonposFwdTrunc r res then closedFormNonposFwdTrunc r res else if nonposFwdTruncNonpos r res then closedFormNonposFwdTruncNonpos r res else if nonposRevTrunc r res then closedFormNonposRevTrunc r res else if zeroCrossOvershootComplete r res then closedFormZeroCrossOvershoot r res else if zeroCrossEndOne r res then closedFormZeroCrossEndOne r res else if zeroCrossEndOneLong r res then closedFormZeroCrossEndOneLong r res else if zeroCrossEndNonpos r res then closedFormZeroCrossEndNonpos r res else if zeroCrossUnderEnd r res then closedFormZeroCrossUnderEnd r res else if zeroCrossLongTop r res then closedFormZeroCrossLong r res else if zeroCrossLongFinite r res then closedFormZeroCrossLong r res else if zeroCrossCompleteRev r res then closedFormZeroCrossCompleteRev r res else if negCrossOvershoot r res then closedFormNegCrossOvershoot r res else if negCrossOvershootRev r res then closedFormNegCrossOvershootRev r res else if negCrossLowFwd r res then closedFormNegCrossLowFwd r res else if negCrossLowFwdRev r res then closedFormNegCrossLowFwdRev r res else if negCrossEndOne r res then closedFormNegCrossEndOne r res else if negCrossEndOneRev r res then closedFormNegCrossEndOneRev r res else if negCrossEndOneLong r res then closedFormNegCrossEndOneLong r res else if negCrossEndOneLongRev r res then closedFormNegCrossEndOneLongRev r res else if negCrossClampEndOne r res then closedFormNegCrossClampEndOne r res else if negCrossClampEndOneRev r res then closedFormNegCrossClampEndOneRev r res else if negCrossHeadBottom r res then closedFormNegCrossHeadBottom r res else if negCrossHeadBottomRev r res then closedFormNegCrossHeadBottomRev r res else if negCrossClampNonposInfinite r res then closedFormNegCrossClampNonposInfinite r res else if negCrossClampNonposInfiniteRev r res then closedFormNegCrossClampNonposInfiniteRev r res else if r.begin.offset ≤ 0 then if zeroCrossTruncRevCrossed r res then closedFormZeroCrossTruncRevCrossed r res else if zeroCrossTruncReadAllEnd r res then closedFormZeroCrossTrunc r res else if zeroCrossTruncBelowEnd r res then closedFormZeroCrossTrunc r res else if zeroCrossTruncEndGeHead r res then closedFormZeroCrossTrunc r res else if zeroCrossTruncLowEndSmall r res then closedFormZeroCrossTrunc r res else if zeroCrossTruncLowEndBig r res then closedFormZeroCrossTruncLowEnd r res else if zeroCrossTruncNonposEnd r res then closedFormZeroCrossTruncNonposEnd r res else if negCrossClampNonposLastGe r res then closedFormNegCrossClampNonposLastGe r res else if negCrossClampNonposLastGeRev r res then closedFormNegCrossClampNonposLastGeRev r res else if negCrossClampNonposBottom r res then closedFormNegCrossClampNonposBottom r res else if negCrossClampNonposBottomRev r res then closedFormNegCrossClampNonposBottomRev r res else if negCrossNonclampNonpos r res then closedFormNegCrossNonclampNonpos r res else if negCrossNonclampNonposRev r res then closedFormNegCrossNonclampNonposRev r res else if negCrossNonclampLongNonpos r res then closedFormNegCrossNonclampLongNonpos r res else if negCrossNonclampLongNonposRev r res then closedFormNegCrossNonclampLongNonposRev r res else if negCrossClampLongNonpos r res then closedFormNegCrossClampLongNonpos r res else if negCrossClampLongNonposRev r res then closedFormNegCrossClampLongNonposRev r res else if negCrossCompleteHighSmall r res then closedFormNegCrossCompleteHigh r res else if negCrossCompleteHighClampFinite r res then closedFormNegCrossCompleteHigh r res else if negCrossCompleteHighRev r res then closedFormNegCrossCompleteHighRev r res else if negCrossCompleteResidual r res then closedFormNegCrossCompleteResidual r res else if negCrossCompleteResidualRev r res then closedFormNegCrossCompleteResidualRev r res else if negCrossTruncNonclampBelowEnd r res then closedFormNegCrossTruncNonclampBelowEnd r res else if negCrossTruncNonclampEndGeHead r res then closedFormNegCrossTruncNonclampTop r res else if negCrossTruncNonclampEndOne r res then closedFormNegCrossTruncNonclampEndOne r res else if negCrossTruncNonclampTop r res then closedFormNegCrossTruncNonclampTop r res else if negCrossTruncNonclampLowEndSmall r res then closedFormNegCrossTruncNonclampTop r res else if negCrossTruncNonclampLowEndBig r res then closedFormNegCrossTruncNonclampLowEnd r res else if negCrossTruncClampGapLow r res then closedFormNegCrossTruncClampGapLow r res else if negCrossTruncClampGapBotMid r res then closedFormNegCrossTruncClampGapBotMid r res else if negCrossTruncClampGapHighBot r res then closedFormNegCrossTruncClampGapHighBot r res else if negCrossTruncClampGapHigh r res then closedFormNegCrossTruncClampGapHigh r res else if negCrossTruncClampNoGap r res then closedFormNegCrossTruncClampNoGap r res else if negCrossTruncRevBelowEnd r res then closedFormNegCrossTruncRevBelowEnd r res else if negCrossTruncRevNonposOvershoot r res then closedFormNegCrossTruncRevNonposOvershoot r res else if negCrossTruncRevNonposUnder r res then closedFormNegCrossTruncRevNonposUnder r res else if negCrossTruncRevCrossedSmall r res then closedFormNegCrossTruncRevCrossedSmall r res else if negCrossTruncRevCrossedLarge r res then closedFormNegCrossTruncRevCrossedLarge r res else if negCrossTruncRevUnder r res then closedFormNegCrossTruncRevUnder r res else if negCrossTruncRevBeginTop r res then closedFormNegCrossTruncRevBeginTop r res else if negCrossTruncRevBeginTopGeTwo r res then closedFormNegCrossTruncRevBeginTopGeTwo r res else if negCrossTruncRevTop r res then closedFormNegCrossTruncRevTop r res else if negCrossTruncRevCrossedNonposSmall r res then closedFormNegCrossTruncRevCrossedNonposSmall r res else if negCrossTruncRevCrossedNonposLarge r res then closedFormNegCrossTruncRevCrossedNonposLarge r res else if negCrossTruncRevResidualRoom r res then closedFormNegCrossTruncRevResidualRoom r res else if negCrossTruncRevResidualTopCrossedSmallGap r res then closedFormNegCrossTruncRevResidualTopCrossedSmallGap r res else if negCrossTruncRevResidualTopCrossed r res then closedFormNegCrossTruncRevResidualTopCrossed r res else if negCrossTruncRevResidualTopLargeCrossed r res then closedFormNegCrossTruncRevResidualTopLargeCrossed r res else if negCrossTruncRevResidualTopLargeSentinel r res then closedFormNegCrossTruncRevResidualTopLargeSentinel r res else if negCrossTruncRevResidualFiniteUnderCrossed r res then closedFormNegCrossTruncRevResidualFiniteUnder r res else if negCrossTruncRevResidualFiniteUnderNotCrossed r res then closedFormNegCrossTruncRevResidualFiniteUnder r res else if negCrossTruncRevResidualFiniteOver r res then closedFormNegCrossTruncRevResidualFiniteOver r res else simpleConflictRange r res else if r.begin.offset = 1 then closedFormOffsetOneTotal r res else if res.more = false then if r.end_.key < r.begin.key then completeCrossedGeneral r res else if r.reverse = true then closedFormCompleteCrossFreeRev r res else closedFormCompleteCrossFree r res else if r.reverse = true then if r.end_.offset ≤ 1 then canonicalRange r else if ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key then topRange r else if r.end_.key < r.begin.key ∧ res.keys.length + (r.begin.offset - 1).toNat = (r.end_.offset - 1).toNat then ⟨r.end_.key, (keyAfter (res.keys.headD ([] : Key)) : WithTop Key)⟩ else if r.end_.key < r.begin.key then closedFormCrossedResidual r res else closedFormCrossFreeResidual r res else if r.end_.key < r.begin.key then truncatedForwardCrossedGeneral r res else closedFormTruncatedGeneral r res /-- **The total closed form is minimal for every readable result at every positive begin offset.** -/ theorem minimal_conflictRangeClosedForm {r : RangeRead} {res : Result} (hread : Readable r res) (hbegin : 1 ≤ r.begin.offset) : Minimal r res (conflictRangeClosedForm r res) := by classical unfold conflictRangeClosedForm by_cases hempty : res.keys = [] · rw [ite_eq_left hempty] exact minimal_emptyValue_of_emptyInference emptyInference hread hempty · rw [ite_eq_right hempty] by_cases hnp : nonposCompleteCrossFree r res · exact absurd hnp.2.2.1 (by omega) · rw [ite_eq_right hnp] by_cases hft : nonposFwdTrunc r res · exact absurd hft.2.2.1 (by omega) · rw [ite_eq_right hft] by_cases hftn : nonposFwdTruncNonpos r res · exact absurd hftn.2.2.1 (by omega) · rw [ite_eq_right hftn] by_cases hrt : nonposRevTrunc r res · exact absurd hrt.2.2.1 (by omega) · rw [ite_eq_right hrt] by_cases hzc : zeroCrossOvershootComplete r res · exact absurd hzc.1 (by omega) · rw [ite_eq_right hzc] by_cases hze : zeroCrossEndOne r res · exact absurd hze.1 (by omega) · rw [ite_eq_right hze] by_cases hzel : zeroCrossEndOneLong r res · exact absurd hzel.1 (by omega) · rw [ite_eq_right hzel] have hzn_false : ¬ zeroCrossEndNonpos r res := by intro hzn exact absurd hzn.1 (by omega) rw [ite_eq_right hzn_false] have hzu_false : ¬ zeroCrossUnderEnd r res := by intro hzu exact absurd hzu.1 (by omega) rw [ite_eq_right hzu_false] have hzl_false : ¬ zeroCrossLongTop r res := by intro hzl exact absurd hzl.1 (by omega) rw [ite_eq_right hzl_false] have hzlf_false : ¬ zeroCrossLongFinite r res := by intro hzlf exact absurd hzlf.1 (by omega) rw [ite_eq_right hzlf_false] have hzcr_false : ¬ zeroCrossCompleteRev r res := by intro hzcr exact absurd hzcr.1 (by omega) rw [ite_eq_right hzcr_false] have hnc_false : ¬ negCrossOvershoot r res := by intro hnc exact absurd hnc.2.1 (by omega) rw [ite_eq_right hnc_false] have hncr_false : ¬ negCrossOvershootRev r res := by intro hncr exact absurd hncr.2.1 (by omega) rw [ite_eq_right hncr_false] have hncl_false : ¬ negCrossLowFwd r res := by intro hncl exact absurd hncl.2.1 (by omega) rw [ite_eq_right hncl_false] have hnclr_false : ¬ negCrossLowFwdRev r res := by intro hnclr exact absurd hnclr.2.1 (by omega) rw [ite_eq_right hnclr_false] have hnce_false : ¬ negCrossEndOne r res := by intro hnce exact absurd hnce.2.1 (by omega) rw [ite_eq_right hnce_false] have hncer_false : ¬ negCrossEndOneRev r res := by intro hncer exact absurd hncer.2.1 (by omega) rw [ite_eq_right hncer_false] have hncel_false : ¬ negCrossEndOneLong r res := by intro h exact absurd h.2.1 (by omega) rw [ite_eq_right hncel_false] have hncelr_false : ¬ negCrossEndOneLongRev r res := by intro h exact absurd h.2.1 (by omega) rw [ite_eq_right hncelr_false] have hncc_false : ¬ negCrossClampEndOne r res := by intro hncc exact absurd hncc.2.1 (by omega) rw [ite_eq_right hncc_false] have hnccr_false : ¬ negCrossClampEndOneRev r res := by intro hnccr exact absurd hnccr.2.1 (by omega) rw [ite_eq_right hnccr_false] have hnb_false : ¬ negCrossHeadBottom r res := by intro h exact absurd h.2.1 (by omega) rw [ite_eq_right hnb_false] have hnbr_false : ¬ negCrossHeadBottomRev r res := by intro h exact absurd h.2.1 (by omega) rw [ite_eq_right hnbr_false] have hnci_false : ¬ negCrossClampNonposInfinite r res := by intro h exact absurd h.2.1 (by omega) rw [ite_eq_right hnci_false] have hncir_false : ¬ negCrossClampNonposInfiniteRev r res := by intro h exact absurd h.2.1 (by omega) rw [ite_eq_right hncir_false] have hnonpos : ¬ (r.begin.offset ≤ 0) := by omega rw [ite_eq_right hnonpos] by_cases hone : r.begin.offset = 1 · rw [ite_eq_left hone] exact minimal_closedForm_of_offset_one_total hread hempty hone · rw [ite_eq_right hone] by_cases hmore : res.more = false · rw [ite_eq_left hmore] by_cases hcross : r.end_.key < r.begin.key · rw [ite_eq_left hcross] exact minimal_completeCrossedGeneral hread hmore hempty hbegin hcross · rw [ite_eq_right hcross] have hcf : r.begin.key ≤ r.end_.key := not_lt.mp hcross by_cases hrev : r.reverse = true · rw [ite_eq_left hrev] exact minimal_closedForm_of_complete_crossFree_rev hread hmore hrev hempty hbegin hcf · rw [ite_eq_right hrev] have hrevf : r.reverse = false := by cases hr : r.reverse <;> simp_all exact minimal_closedForm_of_complete_crossFree hread hmore hrevf hempty hbegin hcf · rw [ite_eq_right hmore] have hm : res.more = true := by cases hm : res.more <;> simp_all by_cases hrev : r.reverse = true · rw [ite_eq_left hrev] by_cases hle : r.end_.offset ≤ 1 · rw [ite_eq_left hle] exact minimal_canonicalRange_of_end_offset_le_one_rev_more hread hm hrev hempty (by omega) hle · rw [ite_eq_right hle] have hend2 : 2 ≤ r.end_.offset := by omega by_cases hhi : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key · rw [ite_eq_left hhi] exact minimal_topRange_of_end_offset_ge_two_rev_more hread hm hrev (by omega) hend2 hhi · rw [ite_eq_right hhi] by_cases hfin : r.end_.key < r.begin.key ∧ res.keys.length + (r.begin.offset - 1).toNat = (r.end_.offset - 1).toNat · rw [ite_eq_left hfin] exact minimal_truncatedRevCrossed_finite_general hread hm hrev hbegin hfin.1 (by omega) hempty hfin.2 · rw [ite_eq_right hfin] by_cases hcross : r.end_.key < r.begin.key · rw [ite_eq_left hcross] unfold closedFormCrossedResidual rw [dite_eq_right hempty] obtain ⟨db, hcomp⟩ := hread have hread' : Readable r res := ⟨db, hcomp⟩ have hle := crossed_rev_res_length_add_le_end (db := db) hcomp hrev (by omega) hcross (by omega) hempty have hne_eq : res.keys.length + (r.begin.offset - 1).toNat ≠ (r.end_.offset - 1).toNat := by intro heq exact hfin ⟨hcross, heq⟩ have hlt : res.keys.length + (r.begin.offset - 1).toNat < (r.end_.offset - 1).toNat := by omega by_cases hcond : crossedResidualCond r res hempty · rw [ite_eq_left hcond] exact minimal_crossedResidual_cond hread' hm hrev (by omega) hcross (by omega) hempty hlt hcond · rw [ite_eq_right hcond] exact minimal_crossedResidual_not_cond hread' hm hrev (by omega) hcross (by omega) hempty hlt hcond · rw [ite_eq_right hcross] have htpos : 0 < residualT r res := by simp only [not_forall, not_lt] at hhi obtain ⟨k, hk, hkge⟩ := hhi exact countP_pos_of_mem hk (by rw [decide_eq_true_eq]; exact hkge) have hcf : r.begin.key ≤ r.end_.key := not_lt.mp hcross exact minimal_closedForm_of_crossfree_residual hread hm hrev (by omega) hcf hend2 hempty htpos · 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 · rw [ite_eq_left hcross] have hend := crossed_end_offset_ge_two_truncated hread hm hbegin hcross exact minimal_truncatedForwardCrossedGeneral hread hm hrevf hempty hbegin hcross hend · rw [ite_eq_right hcross] have hcf : r.begin.key ≤ r.end_.key := not_lt.mp hcross exact minimal_closedForm_of_truncated_general hread hm hrevf hbegin hcf /-- **The closed form is minimal on the cross-free nonpositive-begin complete cell.** -/ theorem minimal_conflictRangeClosedForm_nonpos {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposCompleteCrossFree r res) : Minimal r res (conflictRangeClosedForm r res) := by classical unfold conflictRangeClosedForm have hne : res.keys ≠ [] := h.2.1 rw [ite_eq_right hne, ite_eq_left h] exact minimal_closedForm_of_complete_nonpos_crossFree hread h /-- On the cross-free nonpositive-begin complete cell, the closed form denotes the general conflict range. -/ theorem conflictRangeClosedForm_nonpos_toSet_eq_general {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposCompleteCrossFree r res) : (conflictRangeClosedForm r res).toSet = (conflictRangeGeneral r res).toSet := (minimal_conflictRangeClosedForm_nonpos hread h).toSet_eq (conflictRangeGeneral_minimal hread) /-- On the cross-free nonpositive-begin complete cell, the closed form denotes the executable algorithm. -/ theorem conflictRangeClosedForm_nonpos_toSet_eq_simple {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposCompleteCrossFree r res) : (conflictRangeClosedForm r res).toSet = (simpleConflictRange r res).toSet := (minimal_conflictRangeClosedForm_nonpos hread h).toSet_eq (simpleConflictRange_minimal hread) /-- **The closed form is minimal on the cross-free nonpositive-begin forward truncated cell.** -/ theorem minimal_conflictRangeClosedForm_nonpos_trunc {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposFwdTrunc r res) : Minimal r res (conflictRangeClosedForm r res) := by classical unfold conflictRangeClosedForm have hne : res.keys ≠ [] := by obtain ⟨db, hcomp⟩ := hread exact RangeRead.compatible_ne_nil_of_more hcomp h.1 have hnp : ¬ nonposCompleteCrossFree r res := by intro hc unfold nonposCompleteCrossFree at hc rw [h.1] at hc exact Bool.noConfusion hc.1 rw [ite_eq_right hne, ite_eq_right hnp, ite_eq_left h] exact minimal_closedForm_of_nonpos_fwdTrunc hread h /-- On the cross-free nonpositive-begin forward truncated cell, the closed form denotes the general conflict range. -/ theorem conflictRangeClosedForm_nonpos_trunc_toSet_eq_general {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposFwdTrunc r res) : (conflictRangeClosedForm r res).toSet = (conflictRangeGeneral r res).toSet := (minimal_conflictRangeClosedForm_nonpos_trunc hread h).toSet_eq (conflictRangeGeneral_minimal hread) /-- On the cross-free nonpositive-begin forward truncated cell, the closed form denotes the executable algorithm. -/ theorem conflictRangeClosedForm_nonpos_trunc_toSet_eq_simple {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposFwdTrunc r res) : (conflictRangeClosedForm r res).toSet = (simpleConflictRange r res).toSet := (minimal_conflictRangeClosedForm_nonpos_trunc hread h).toSet_eq (simpleConflictRange_minimal hread) /-- **The closed form is minimal on the cross-free nonpositive-begin forward truncated nonpositive-end cell.** -/ theorem minimal_conflictRangeClosedForm_nonpos_trunc_nonpos {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposFwdTruncNonpos r res) : Minimal r res (conflictRangeClosedForm r res) := by classical unfold conflictRangeClosedForm have hne : res.keys ≠ [] := by obtain ⟨db, hcomp⟩ := hread exact RangeRead.compatible_ne_nil_of_more hcomp h.1 have hnp : ¬ nonposCompleteCrossFree r res := by intro hc unfold nonposCompleteCrossFree at hc rw [h.1] at hc exact Bool.noConfusion hc.1 have hft : ¬ nonposFwdTrunc r res := by intro hf have hge : 1 ≤ r.end_.offset := hf.2.2.2.2 have hle : r.end_.offset ≤ 0 := h.2.2.2.2 omega rw [ite_eq_right hne, ite_eq_right hnp, ite_eq_right hft, ite_eq_left h] exact minimal_closedForm_of_nonpos_fwdTruncNonpos hread h /-- On the cross-free nonpositive-begin forward truncated nonpositive-end cell, the closed form denotes the general conflict range. -/ theorem conflictRangeClosedForm_nonpos_trunc_nonpos_toSet_eq_general {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposFwdTruncNonpos r res) : (conflictRangeClosedForm r res).toSet = (conflictRangeGeneral r res).toSet := (minimal_conflictRangeClosedForm_nonpos_trunc_nonpos hread h).toSet_eq (conflictRangeGeneral_minimal hread) /-- On the cross-free nonpositive-begin forward truncated nonpositive-end cell, the closed form denotes the executable algorithm. -/ theorem conflictRangeClosedForm_nonpos_trunc_nonpos_toSet_eq_simple {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposFwdTruncNonpos r res) : (conflictRangeClosedForm r res).toSet = (simpleConflictRange r res).toSet := (minimal_conflictRangeClosedForm_nonpos_trunc_nonpos hread h).toSet_eq (simpleConflictRange_minimal hread) /-- **The closed form is minimal on the cross-free nonpositive-begin reversed truncated cell.** -/ theorem minimal_conflictRangeClosedForm_nonpos_revtrunc {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposRevTrunc r res) : Minimal r res (conflictRangeClosedForm r res) := by classical unfold conflictRangeClosedForm have hne : res.keys ≠ [] := by obtain ⟨db, hcomp⟩ := hread exact RangeRead.compatible_ne_nil_of_more hcomp h.1 have hnp : ¬ nonposCompleteCrossFree r res := by intro hc have hmc : res.more = false := hc.1 rw [h.1] at hmc exact Bool.noConfusion hmc have hft : ¬ nonposFwdTrunc r res := by intro hf have hrevf : r.reverse = false := hf.2.1 rw [h.2.1] at hrevf exact Bool.noConfusion hrevf have hftn : ¬ nonposFwdTruncNonpos r res := by intro hf have hrevf : r.reverse = false := hf.2.1 rw [h.2.1] at hrevf exact Bool.noConfusion hrevf rw [ite_eq_right hne, ite_eq_right hnp, ite_eq_right hft, ite_eq_right hftn, ite_eq_left h] exact minimal_closedForm_of_nonpos_revTrunc hread h /-- On the cross-free nonpositive-begin reversed truncated cell, the closed form denotes the general conflict range. -/ theorem conflictRangeClosedForm_nonpos_revtrunc_toSet_eq_general {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposRevTrunc r res) : (conflictRangeClosedForm r res).toSet = (conflictRangeGeneral r res).toSet := (minimal_conflictRangeClosedForm_nonpos_revtrunc hread h).toSet_eq (conflictRangeGeneral_minimal hread) /-- On the cross-free nonpositive-begin reversed truncated cell, the closed form denotes the executable algorithm. -/ theorem conflictRangeClosedForm_nonpos_revtrunc_toSet_eq_simple {r : RangeRead} {res : Result} (hread : Readable r res) (h : nonposRevTrunc r res) : (conflictRangeClosedForm r res).toSet = (simpleConflictRange r res).toSet := (minimal_conflictRangeClosedForm_nonpos_revtrunc hread h).toSet_eq (simpleConflictRange_minimal hread) /-- The total closed form denotes the general conflict range for every readable result at every positive begin offset. -/ theorem conflictRangeClosedForm_toSet_eq_general {r : RangeRead} {res : Result} (hread : Readable r res) (hbegin : 1 ≤ r.begin.offset) : (conflictRangeClosedForm r res).toSet = (conflictRangeGeneral r res).toSet := (minimal_conflictRangeClosedForm hread hbegin).toSet_eq (conflictRangeGeneral_minimal hread) /-- The total closed form denotes the executable algorithm for every readable result at every positive begin offset. -/ theorem conflictRangeClosedForm_toSet_eq_simple {r : RangeRead} {res : Result} (hread : Readable r res) (hbegin : 1 ≤ r.begin.offset) : (conflictRangeClosedForm r res).toSet = (simpleConflictRange r res).toSet := (minimal_conflictRangeClosedForm hread hbegin).toSet_eq (simpleConflictRange_minimal hread) /-- **The total closed form is minimal for every readable result, at every begin offset.** Positive begin offsets use the compact closed forms, and the nonpositive cells use the cross-free and crossed closed forms where they exist; the residual nonpositive crossed cells delegate to the exact executable `simpleConflictRange`. -/ theorem minimal_conflictRangeClosedForm_total {r : RangeRead} {res : Result} (hread : Readable r res) : Minimal r res (conflictRangeClosedForm r res) := by classical by_cases hpos : 1 ≤ r.begin.offset · exact minimal_conflictRangeClosedForm hread hpos unfold conflictRangeClosedForm by_cases hempty : res.keys = [] · rw [ite_eq_left hempty] exact minimal_emptyValue_of_emptyInference emptyInference hread hempty rw [ite_eq_right hempty] by_cases hnp : nonposCompleteCrossFree r res · rw [ite_eq_left hnp] exact minimal_closedForm_of_complete_nonpos_crossFree hread hnp rw [ite_eq_right hnp] by_cases hft : nonposFwdTrunc r res · rw [ite_eq_left hft] exact minimal_closedForm_of_nonpos_fwdTrunc hread hft rw [ite_eq_right hft] by_cases hftn : nonposFwdTruncNonpos r res · rw [ite_eq_left hftn] exact minimal_closedForm_of_nonpos_fwdTruncNonpos hread hftn rw [ite_eq_right hftn] by_cases hrt : nonposRevTrunc r res · rw [ite_eq_left hrt] exact minimal_closedForm_of_nonpos_revTrunc hread hrt rw [ite_eq_right hrt] by_cases hzc : zeroCrossOvershootComplete r res · rw [ite_eq_left hzc] exact minimal_closedForm_of_zeroCross_overshoot hread hzc rw [ite_eq_right hzc] by_cases hze : zeroCrossEndOne r res · rw [ite_eq_left hze] exact minimal_closedForm_of_zeroCross_endOne hread hze rw [ite_eq_right hze] by_cases hzel : zeroCrossEndOneLong r res · rw [ite_eq_left hzel] exact minimal_closedForm_of_zeroCross_endOne_long hread hzel rw [ite_eq_right hzel] by_cases hzn : zeroCrossEndNonpos r res · rw [ite_eq_left hzn] exact minimal_closedForm_of_zeroCross_endNonpos hread hzn rw [ite_eq_right hzn] by_cases hzu : zeroCrossUnderEnd r res · rw [ite_eq_left hzu] exact minimal_closedForm_of_zeroCross_underEnd hread hzu rw [ite_eq_right hzu] by_cases hzl : zeroCrossLongTop r res · rw [ite_eq_left hzl] exact minimal_closedForm_of_zeroCross_longTop hread hzl rw [ite_eq_right hzl] by_cases hzlf : zeroCrossLongFinite r res · rw [ite_eq_left hzlf] exact minimal_closedForm_of_zeroCross_longFinite hread hzlf rw [ite_eq_right hzlf] by_cases hzcr : zeroCrossCompleteRev r res · rw [ite_eq_left hzcr] exact minimal_closedForm_of_zeroCross_complete_rev hread hzcr.2.2.1 hzcr.1 hzcr.2.1 hzcr.2.2.2.1 hzcr.2.2.2.2 rw [ite_eq_right hzcr] by_cases hnc : negCrossOvershoot r res · rw [ite_eq_left hnc] have hcross' : ((res.keys.head hnc.2.2.2.1 : Key) : WithTop Key) < r.begin.key := by have h := hnc.2.2.2.2.2.2 rwa [headD_eq_head_of_ne hnc.2.2.2.1] at h exact minimal_closedForm_of_negCross_overshoot hread hnc.1 hnc.2.1 hnc.2.2.1 hnc.2.2.2.1 hnc.2.2.2.2.1 hnc.2.2.2.2.2.1 hcross' rw [ite_eq_right hnc] by_cases hncr : negCrossOvershootRev r res · rw [ite_eq_left hncr] exact minimal_closedForm_of_negCross_overshoot_rev hread hncr rw [ite_eq_right hncr] by_cases hncl : negCrossLowFwd r res · rw [ite_eq_left hncl] exact minimal_closedForm_of_negCross_lowFwd hread hncl rw [ite_eq_right hncl] by_cases hnclr : negCrossLowFwdRev r res · rw [ite_eq_left hnclr] exact minimal_closedForm_of_negCross_lowFwd_rev hread hnclr rw [ite_eq_right hnclr] by_cases hnce : negCrossEndOne r res · rw [ite_eq_left hnce] exact minimal_closedForm_of_negCross_endOne hread hnce rw [ite_eq_right hnce] by_cases hncer : negCrossEndOneRev r res · rw [ite_eq_left hncer] exact minimal_closedForm_of_negCross_endOne_rev hread hncer rw [ite_eq_right hncer] by_cases hncel : negCrossEndOneLong r res · rw [ite_eq_left hncel] exact minimal_closedForm_of_negCross_endOne_long hread hncel rw [ite_eq_right hncel] by_cases hncelr : negCrossEndOneLongRev r res · rw [ite_eq_left hncelr] exact minimal_closedForm_of_negCross_endOne_long_rev hread hncelr rw [ite_eq_right hncelr] by_cases hncc : negCrossClampEndOne r res · rw [ite_eq_left hncc] exact minimal_closedForm_of_negCross_clampEndOne hread hncc rw [ite_eq_right hncc] by_cases hnccr : negCrossClampEndOneRev r res · rw [ite_eq_left hnccr] exact minimal_closedForm_of_negCross_clampEndOne_rev hread hnccr rw [ite_eq_right hnccr] by_cases hnb : negCrossHeadBottom r res · rw [ite_eq_left hnb] exact minimal_closedForm_of_negCross_headBottom hread hnb rw [ite_eq_right hnb] by_cases hnbr : negCrossHeadBottomRev r res · rw [ite_eq_left hnbr] exact minimal_closedForm_of_negCross_headBottom_rev hread hnbr rw [ite_eq_right hnbr] by_cases hnci : negCrossClampNonposInfinite r res · rw [ite_eq_left hnci] exact minimal_closedForm_of_negCross_clampNonpos_infinite hread hnci rw [ite_eq_right hnci] by_cases hncir : negCrossClampNonposInfiniteRev r res · rw [ite_eq_left hncir] exact minimal_closedForm_of_negCross_clampNonpos_infinite_rev hread hncir rw [ite_eq_right hncir] rw [ite_eq_left (by omega : r.begin.offset ≤ 0)] by_cases hzcrv : zeroCrossTruncRevCrossed r res · rw [ite_eq_left hzcrv] exact minimal_closedForm_of_zeroCross_trunc_revCrossed hread hzcrv rw [ite_eq_right hzcrv] by_cases hzct : zeroCrossTruncReadAllEnd r res · rw [ite_eq_left hzct] exact minimal_closedForm_of_zeroCross_trunc_readAllEnd hread hzct rw [ite_eq_right hzct] by_cases hzcb : zeroCrossTruncBelowEnd r res · rw [ite_eq_left hzcb] exact minimal_closedForm_of_zeroCross_trunc_belowEnd hread hzcb rw [ite_eq_right hzcb] by_cases hzce : zeroCrossTruncEndGeHead r res · rw [ite_eq_left hzce] exact minimal_closedForm_of_zeroCross_trunc_endGeHead hread hzce rw [ite_eq_right hzce] by_cases hzcl : zeroCrossTruncLowEndSmall r res · rw [ite_eq_left hzcl] exact minimal_closedForm_of_zeroCross_trunc_lowEndSmall hread hzcl rw [ite_eq_right hzcl] by_cases hzcbg : zeroCrossTruncLowEndBig r res · rw [ite_eq_left hzcbg] exact minimal_closedForm_of_zeroCross_trunc_lowEndBig hread hzcbg rw [ite_eq_right hzcbg] by_cases hzcn : zeroCrossTruncNonposEnd r res · rw [ite_eq_left hzcn] exact minimal_closedForm_of_zeroCross_trunc_nonposEnd hread hzcn rw [ite_eq_right hzcn] by_cases hnlg : negCrossClampNonposLastGe r res · rw [ite_eq_left hnlg] exact minimal_closedForm_of_negCross_clampNonpos_lastGe hread hnlg rw [ite_eq_right hnlg] by_cases hnlgrev : negCrossClampNonposLastGeRev r res · rw [ite_eq_left hnlgrev] exact minimal_closedForm_of_negCross_clampNonpos_lastGe_rev hread hnlgrev rw [ite_eq_right hnlgrev] by_cases hncbn : negCrossClampNonposBottom r res · rw [ite_eq_left hncbn] exact minimal_closedForm_of_negCross_clampNonpos_bottom hread hncbn rw [ite_eq_right hncbn] by_cases hncbnr : negCrossClampNonposBottomRev r res · rw [ite_eq_left hncbnr] exact minimal_closedForm_of_negCross_clampNonpos_bottom_rev hread hncbnr rw [ite_eq_right hncbnr] by_cases hnc : negCrossNonclampNonpos r res · rw [ite_eq_left hnc] exact minimal_closedForm_of_negCross_nonclamp_nonpos hread hnc rw [ite_eq_right hnc] by_cases hncr : negCrossNonclampNonposRev r res · rw [ite_eq_left hncr] exact minimal_closedForm_of_negCross_nonclamp_nonpos_rev hread hncr rw [ite_eq_right hncr] by_cases hncl : negCrossNonclampLongNonpos r res · rw [ite_eq_left hncl] exact minimal_closedForm_of_negCross_nonclamp_long_nonpos hread hncl rw [ite_eq_right hncl] by_cases hnclr : negCrossNonclampLongNonposRev r res · rw [ite_eq_left hnclr] exact minimal_closedForm_of_negCross_nonclamp_long_nonpos_rev hread hnclr rw [ite_eq_right hnclr] by_cases hnclc : negCrossClampLongNonpos r res · rw [ite_eq_left hnclc] exact minimal_closedForm_of_negCross_clamp_long_nonpos hread hnclc rw [ite_eq_right hnclc] by_cases hnclcr : negCrossClampLongNonposRev r res · rw [ite_eq_left hnclcr] exact minimal_closedForm_of_negCross_clamp_long_nonpos_rev hread hnclcr rw [ite_eq_right hnclcr] by_cases hhigh : negCrossCompleteHighSmall r res · rw [ite_eq_left hhigh] exact minimal_closedForm_of_negCrossCompleteHigh_small hread hhigh rw [ite_eq_right hhigh] by_cases hclampfin : negCrossCompleteHighClampFinite r res · rw [ite_eq_left hclampfin] exact minimal_closedForm_of_negCrossCompleteHigh_clampFinite hread hclampfin rw [ite_eq_right hclampfin] by_cases hhighrev : negCrossCompleteHighRev r res · rw [ite_eq_left hhighrev] exact minimal_closedForm_of_negCrossCompleteHigh_rev hread hhighrev rw [ite_eq_right hhighrev] by_cases hncres : negCrossCompleteResidual r res · rw [ite_eq_left hncres] exact minimal_closedForm_of_negCross_complete_residual hread hncres rw [ite_eq_right hncres] by_cases hncresr : negCrossCompleteResidualRev r res · rw [ite_eq_left hncresr] exact minimal_closedForm_of_negCross_complete_residual_rev hread hncresr rw [ite_eq_right hncresr] by_cases hnb : negCrossTruncNonclampBelowEnd r res · rw [ite_eq_left hnb] exact minimal_closedForm_of_negCross_trunc_nonclamp_below hread hnb rw [ite_eq_right hnb] by_cases heg : negCrossTruncNonclampEndGeHead r res · rw [ite_eq_left heg] exact minimal_closedForm_of_negCross_trunc_nonclamp_endGeHead hread heg rw [ite_eq_right heg] by_cases hne1 : negCrossTruncNonclampEndOne r res · rw [ite_eq_left hne1] exact minimal_closedForm_of_negCross_trunc_nonclamp_endOne hread hne1 rw [ite_eq_right hne1] by_cases hnt : negCrossTruncNonclampTop r res · rw [ite_eq_left hnt] exact minimal_closedForm_of_negCross_trunc_nonclamp_top hread hnt rw [ite_eq_right hnt] by_cases hlows : negCrossTruncNonclampLowEndSmall r res · rw [ite_eq_left hlows] exact minimal_closedForm_of_negCross_trunc_nonclamp_lowEndSmall hread hlows rw [ite_eq_right hlows] by_cases hlowb : negCrossTruncNonclampLowEndBig r res · rw [ite_eq_left hlowb] exact minimal_closedForm_of_negCross_trunc_nonclamp_lowEndBig hread hlowb rw [ite_eq_right hlowb] by_cases hgaplow : negCrossTruncClampGapLow r res · rw [ite_eq_left hgaplow] exact minimal_closedForm_of_negCross_trunc_clamp_gapLow hread hgaplow rw [ite_eq_right hgaplow] by_cases hgapbotmid : negCrossTruncClampGapBotMid r res · rw [ite_eq_left hgapbotmid] exact minimal_closedForm_of_negCross_trunc_clamp_gapBotMid hread hgapbotmid rw [ite_eq_right hgapbotmid] by_cases hgaphigh : negCrossTruncClampGapHighBot r res · rw [ite_eq_left hgaphigh] exact minimal_closedForm_of_negCross_trunc_clamp_gapHighBot hread hgaphigh rw [ite_eq_right hgaphigh] by_cases hgaphighgen : negCrossTruncClampGapHigh r res · rw [ite_eq_left hgaphighgen] exact minimal_closedForm_of_negCross_trunc_clamp_gapHigh hread hgaphighgen rw [ite_eq_right hgaphighgen] by_cases hclampgen : negCrossTruncClampNoGap r res · rw [ite_eq_left hclampgen] exact minimal_closedForm_of_negCross_trunc_clamp_noGap hread hclampgen rw [ite_eq_right hclampgen] by_cases hrevbelowend : negCrossTruncRevBelowEnd r res · rw [ite_eq_left hrevbelowend] exact minimal_closedForm_of_negCross_trunc_rev_belowEnd hread hrevbelowend rw [ite_eq_right hrevbelowend] by_cases hrevnonposover : negCrossTruncRevNonposOvershoot r res · rw [ite_eq_left hrevnonposover] exact minimal_closedForm_of_negCross_trunc_rev_nonposOvershoot hread hrevnonposover rw [ite_eq_right hrevnonposover] by_cases hrevnonposunder : negCrossTruncRevNonposUnder r res · rw [ite_eq_left hrevnonposunder] exact minimal_closedForm_of_negCross_trunc_rev_nonposUnder hread hrevnonposunder rw [ite_eq_right hrevnonposunder] by_cases hrevcrosssmall : negCrossTruncRevCrossedSmall r res · rw [ite_eq_left hrevcrosssmall] exact minimal_closedForm_of_negCross_trunc_rev_crossedSmall hread hrevcrosssmall rw [ite_eq_right hrevcrosssmall] by_cases hrevcrosslarge : negCrossTruncRevCrossedLarge r res · rw [ite_eq_left hrevcrosslarge] exact minimal_closedForm_of_negCross_trunc_rev_crossedLarge hread hrevcrosslarge rw [ite_eq_right hrevcrosslarge] by_cases hrevunder : negCrossTruncRevUnder r res · rw [ite_eq_left hrevunder] exact minimal_closedForm_of_negCross_trunc_rev_under hread hrevunder rw [ite_eq_right hrevunder] by_cases hrevbegtop : negCrossTruncRevBeginTop r res · rw [ite_eq_left hrevbegtop] exact minimal_closedForm_of_negCross_trunc_rev_beginTop hread hrevbegtop rw [ite_eq_right hrevbegtop] by_cases hrevbegtoptwo : negCrossTruncRevBeginTopGeTwo r res · rw [ite_eq_left hrevbegtoptwo] exact minimal_closedForm_of_negCross_trunc_rev_beginTop_ge_two hread hrevbegtoptwo rw [ite_eq_right hrevbegtoptwo] by_cases hrevtop : negCrossTruncRevTop r res · rw [ite_eq_left hrevtop] exact minimal_closedForm_of_negCross_trunc_rev_top hread hrevtop rw [ite_eq_right hrevtop] by_cases hrevcrossnonpossmall : negCrossTruncRevCrossedNonposSmall r res · rw [ite_eq_left hrevcrossnonpossmall] exact minimal_closedForm_of_negCross_trunc_rev_crossedNonpos_small hread hrevcrossnonpossmall rw [ite_eq_right hrevcrossnonpossmall] by_cases hrevcrossnonposlarge : negCrossTruncRevCrossedNonposLarge r res · rw [ite_eq_left hrevcrossnonposlarge] exact minimal_closedForm_of_negCross_trunc_rev_crossedNonpos_large hread hrevcrossnonposlarge rw [ite_eq_right hrevcrossnonposlarge] by_cases hrevresroom : negCrossTruncRevResidualRoom r res · rw [ite_eq_left hrevresroom] exact minimal_closedForm_of_negCross_trunc_rev_residual_room hread hrevresroom rw [ite_eq_right hrevresroom] by_cases hrevrestopsmall : negCrossTruncRevResidualTopCrossedSmallGap r res · rw [ite_eq_left hrevrestopsmall] exact minimal_closedForm_of_negCross_trunc_rev_residual_top_crossed_smallGap hread hrevrestopsmall rw [ite_eq_right hrevrestopsmall] by_cases hrevrestopcrossed : negCrossTruncRevResidualTopCrossed r res · rw [ite_eq_left hrevrestopcrossed] exact minimal_closedForm_of_negCross_trunc_rev_residual_top_crossed hread hrevrestopcrossed rw [ite_eq_right hrevrestopcrossed] by_cases hrevrestoplarge : negCrossTruncRevResidualTopLargeCrossed r res · rw [ite_eq_left hrevrestoplarge] exact minimal_closedForm_of_negCross_trunc_rev_residual_top_large_crossed hread hrevrestoplarge rw [ite_eq_right hrevrestoplarge] by_cases hrevrestopsentinel : negCrossTruncRevResidualTopLargeSentinel r res · rw [ite_eq_left hrevrestopsentinel] exact minimal_closedForm_of_negCross_trunc_rev_residual_top_large_sentinel hread hrevrestopsentinel rw [ite_eq_right hrevrestopsentinel] by_cases hrevfinunder : negCrossTruncRevResidualFiniteUnderCrossed r res · rw [ite_eq_left hrevfinunder] exact minimal_closedForm_of_negCross_trunc_rev_residualFinite_under_crossed hread hrevfinunder rw [ite_eq_right hrevfinunder] by_cases hrevfinundernc : negCrossTruncRevResidualFiniteUnderNotCrossed r res · rw [ite_eq_left hrevfinundernc] exact minimal_closedForm_of_negCross_trunc_rev_residualFinite_under_notCrossed hread hrevfinundernc rw [ite_eq_right hrevfinundernc] by_cases hrevfinover : negCrossTruncRevResidualFiniteOver r res · rw [ite_eq_left hrevfinover] exact minimal_closedForm_of_negCross_trunc_rev_residualFinite_over hread hrevfinover rw [ite_eq_right hrevfinover] exact simpleConflictRange_minimal hread /-- The total closed form denotes the general conflict range for every readable result. -/ theorem conflictRangeClosedForm_toSet_eq_general_total {r : RangeRead} {res : Result} (hread : Readable r res) : (conflictRangeClosedForm r res).toSet = (conflictRangeGeneral r res).toSet := (minimal_conflictRangeClosedForm_total hread).toSet_eq (conflictRangeGeneral_minimal hread) /-- The total closed form denotes the executable algorithm for every readable result. -/ theorem conflictRangeClosedForm_toSet_eq_simple_total {r : RangeRead} {res : Result} (hread : Readable r res) : (conflictRangeClosedForm r res).toSet = (simpleConflictRange r res).toSet := (minimal_conflictRangeClosedForm_total hread).toSet_eq (simpleConflictRange_minimal hread) end FormalConflictRange