Files

107 lines
4.7 KiB
Lean4

/-
Released under Apache 2.0 license as described in the file LICENSE.
-/
import FormalConflictRange.CrossedRev
/-!
# The total closed form at begin offset one
This module assembles the complete, forward-truncated and reversed-truncated rules
into a single result-aware closed form that is minimal for *every* readable result at
`begin.offset = 1`, crossed or cross-free, in either traversal order.
The cross-free region is delegated to `closedFormOffsetOneUniversal`; on a crossed
selector pair `end_.key < begin_.key` it uses the crossed complete rule
`completeClosed`, the crossed forward-truncated rule `truncatedForwardClosed`, or the
corrected reversed-truncated rule `closedFormOffsetOneTruncatedRevFullC`.
-/
open FormalConflictRange
namespace FormalConflictRange
/-- On a crossed readable truncated result, `end.offset ≥ 2`. A nonpositive end
overshoot would make the complete window empty, contradicting a nonempty truncated
result. -/
theorem crossed_end_offset_ge_two_truncated {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true)
(hbegin : 1 ≤ r.begin.offset) (hcross : r.end_.key < r.begin.key) :
2 ≤ r.end_.offset := by
by_contra h
have hend : r.end_.offset ≤ 1 := by omega
obtain ⟨db₀, hcomp₀⟩ := hread
have hne : res.keys ≠ [] := RangeRead.compatible_ne_nil_of_more hcomp₀ hmore
have hemp : RangeRead.completeKeys db₀ r = [] :=
alwaysEmpty_of_begin_gt_end hbegin hend hcross db₀
have hpre : res.keys <+: RangeRead.completeKeys db₀ r :=
RangeRead.compatible_keys_prefix hcomp₀
rw [hemp] at hpre
exact hne (List.eq_nil_of_prefix_nil hpre)
/-- **The total closed form at begin offset one.** Cross-free reads use the compact
universal rule; crossed reads use the traversal-aware crossed complete and truncated
rules. -/
noncomputable def closedFormOffsetOneTotal (r : RangeRead) (res : Result) : ConflictRange :=
if r.end_.key < r.begin.key then
if res.more = true then
if r.reverse = true then closedFormOffsetOneTruncatedRevFullC r res
else truncatedForwardClosed r res
else completeClosed r res
else closedFormOffsetOneUniversal r res
/-- **The total closed form is minimal for every readable result at begin offset
one.** No crossed or cross-free cell is left open. -/
theorem minimal_closedForm_of_offset_one_total {r : RangeRead} {res : Result}
(hread : Readable r res) (hne : res.keys ≠ [])
(hbegin : r.begin.offset = 1) :
Minimal r res (closedFormOffsetOneTotal r res) := by
unfold closedFormOffsetOneTotal
by_cases hcross : r.end_.key < r.begin.key
· rw [ite_eq_left hcross]
by_cases hmore : res.more = true
· rw [ite_eq_left hmore]
have hend := crossed_end_offset_ge_two_truncated hread hmore (by omega) hcross
by_cases hrev : r.reverse = true
· rw [ite_eq_left hrev]
exact minimal_closedForm_of_offset_one_truncated_rev_fullC_crossed hread hmore
hrev hbegin hcross hend
· rw [ite_eq_right hrev]
have hrevf : r.reverse = false := by
cases hr : r.reverse <;> simp_all
exact minimal_truncatedForwardClosed_of_crossed hread hmore hrevf hne hbegin
hcross hend
· rw [ite_eq_right hmore]
have hfalse : res.more = false := by
cases hm : res.more <;> simp_all
exact minimal_completeClosed hread hfalse hne hbegin
· rw [ite_eq_right hcross]
have hcf : r.begin.key ≤ r.end_.key := not_lt.mp hcross
exact minimal_closedForm_of_offset_one_universal hread hne hbegin hcf
/-- The total closed form denotes the general conflict range for every readable
result at begin offset one. -/
theorem closedFormOffsetOneTotal_toSet_eq_general {r : RangeRead} {res : Result}
(hread : Readable r res) (hne : res.keys ≠ [])
(hbegin : r.begin.offset = 1) :
(closedFormOffsetOneTotal r res).toSet = (conflictRangeGeneral r res).toSet :=
(minimal_closedForm_of_offset_one_total hread hne hbegin).toSet_eq
(conflictRangeGeneral_minimal hread)
/-- The total closed form denotes the same key set as the executable algorithm. -/
theorem closedFormOffsetOneTotal_toSet_eq_simple {r : RangeRead} {res : Result}
(hread : Readable r res) (hne : res.keys ≠ [])
(hbegin : r.begin.offset = 1) :
(closedFormOffsetOneTotal r res).toSet = (simpleConflictRange r res).toSet :=
(minimal_closedForm_of_offset_one_total hread hne hbegin).toSet_eq
(simpleConflictRange_minimal hread)
/-- On the cross-free region the total rule agrees with the compact universal rule. -/
theorem closedFormOffsetOneTotal_eq_universal {r : RangeRead} {res : Result}
(hcross : r.begin.key ≤ r.end_.key) :
closedFormOffsetOneTotal r res = closedFormOffsetOneUniversal r res := by
unfold closedFormOffsetOneTotal
rw [ite_eq_right (not_lt.mpr hcross)]
end FormalConflictRange