Files

1313 lines
67 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.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