Files

1687 lines
78 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 Mathlib
/-!
# Keys and databases
This file defines the basic data model: `Byte`, `Key` (lexicographically
ordered byte strings) and `DB` (a sorted, duplicate-free list of keys).
## Design note: keys and `WithTop`
`Key` is ordered lexicographically, so it has a least element, the empty key,
and no greatest element. Wherever a key-shaped value may need to name a
position outside the stored keys of an arbitrary database — a selector's
anchor, a resolved selector target, an endpoint of a conflict range — the
library uses `WithTop Key`, whose `⊥` is the empty key and whose `⊤` is a
genuine sentinel above every key. The bottom needs no sentinel of its own: the
empty key is the least key, so "the start of the key space" is expressed by the
empty key itself, which keeps acting as an ordinary key throughout the
development (indeed, as `FormalConflictRange.Sound` shows, the empty key can
itself be necessary). The top is different: no fixed key lies above every
stored key of an arbitrary database, so only `⊤` can serve as an unbounded
upper end or anchor a selector past the end of the database — which is what
makes a database-independent "read all keys" read (`RangeRead.readAll`)
expressible.
-/
namespace FormalConflictRange
/-- A byte is an 8-bit value, represented as an element of `Fin 256`. -/
abbrev Byte := Fin 256
/-- A key is a list of bytes, ordered lexicographically. -/
abbrev Key := List Byte
/-- A database is a sorted, duplicate-free list of keys.
The strict sortedness condition subsumes the no-duplicates condition. -/
structure DB where
keys : List Key
sorted : keys.SortedLT
namespace DB
/-- A database contains no duplicate keys. -/
theorem nodup (db : DB) : db.keys.Nodup :=
db.sorted.pairwise.nodup
/-- A `List.Pairwise (· ≤ ·)` list with no duplicates is `List.Pairwise (· < ·)`. -/
theorem pairwise_lt_of_le_of_nodup {l : List Key} (h : l.Pairwise (· ≤ ·)) (hnd : l.Nodup) :
l.Pairwise (· < ·) := by
rw [List.pairwise_iff_getElem] at h ⊢
intro i j hi hj hij
have hle := h i j hi hj hij
have hne : l[i] ≠ l[j] := fun heq => (Nat.ne_of_lt hij) ((hnd.getElem_inj_iff).mp heq)
exact lt_of_le_of_ne hle hne
/-- Remove a key from a database, preserving sortedness. -/
def erase (db : DB) (k : Key) : DB where
keys := db.keys.erase k
sorted := List.sortedLT_iff_pairwise.mpr (db.sorted.pairwise.erase k)
/-- Insert a key not already stored into a database at its sorted position,
preserving sortedness. -/
def insert (db : DB) (k : Key) (hk : k ∉ db.keys) : DB where
keys := db.keys.orderedInsert (· ≤ ·) k
sorted := List.sortedLT_iff_pairwise.mpr <|
pairwise_lt_of_le_of_nodup
((db.sorted.pairwise.imp fun h => le_of_lt h).orderedInsert k)
((List.perm_orderedInsert (· ≤ ·) k db.keys).nodup_iff.mpr
(List.nodup_cons.mpr ⟨hk, db.nodup⟩))
/-- The keys of an erased database are the erased keys of the database. -/
@[simp] theorem erase_keys (db : DB) (k : Key) : (db.erase k).keys = db.keys.erase k := rfl
/-- The keys of an inserted database are the ordered insert of the keys. -/
@[simp] theorem insert_keys (db : DB) (k : Key) (hk : k ∉ db.keys) :
(db.insert k hk).keys = db.keys.orderedInsert (· ≤ ·) k := rfl
/-- A key is stored in an erased database exactly when it is stored in the
original and differs from the erased key. -/
theorem mem_erase_iff {db : DB} {k x : Key} : x ∈ (db.erase k).keys ↔ x ≠ k ∧ x ∈ db.keys := by
rw [erase_keys]
exact List.Nodup.mem_erase_iff db.nodup
/-- The erased key is no longer stored. -/
theorem not_mem_erase_self (db : DB) (k : Key) : k ∉ (db.erase k).keys := by
rw [erase_keys]
exact List.Nodup.not_mem_erase db.nodup
/-- A key is stored in an inserted database exactly when it is the inserted key
or was already stored. -/
theorem mem_insert_iff {db : DB} {k x : Key} (hk : k ∉ db.keys) :
x ∈ (db.insert k hk).keys ↔ x = k ∨ x ∈ db.keys := by
rw [insert_keys]
exact List.mem_orderedInsert (· ≤ ·)
/-- The inserted key is stored. -/
theorem mem_insert_self (db : DB) (k : Key) (hk : k ∉ db.keys) :
k ∈ (db.insert k hk).keys :=
(mem_insert_iff hk).mpr (Or.inl rfl)
/-- Erasing the key just inserted restores the database's keys. This is
`List.erase_orderedInsert` for `Key`; it is stated here because the `List.erase`
`BEq` instance is not definitionally the decidable-equality one, so the library
lemma does not apply directly. -/
theorem erase_insert_keys (db : DB) (k : Key) (hk : k ∉ db.keys) :
((db.insert k hk).erase k).keys = db.keys := by
rw [erase_keys, insert_keys]
induction db.keys with
| nil => simp
| cons a t ih =>
rw [List.orderedInsert_cons]
by_cases h : k ≤ a
· rw [ite_eq_left h, List.erase_cons_head]
· rw [ite_eq_right h]
have h' : ¬(a == k) := by
intro hk'; rw [beq_iff_eq] at hk'; exact h (le_of_eq hk'.symm)
rw [List.erase_cons_tail h', ih]
/-- Erase every stored key in the half-open interval `[a, b)`, preserving
sortedness. This is the interval analogue of `erase`, removing a whole interval
of keys at once rather than a single key. -/
def eraseInterval (db : DB) (a b : WithTop Key) : DB where
keys := db.keys.filter
(fun (x : Key) => decide (¬ (a ≤ (x : WithTop Key) ∧ (x : WithTop Key) < b)))
sorted := List.sortedLT_iff_pairwise.mpr (db.sorted.pairwise.filter _)
/-- The keys of an interval-erased database are the interval-filtered keys. -/
@[simp] theorem eraseInterval_keys (db : DB) (a b : WithTop Key) :
(db.eraseInterval a b).keys = db.keys.filter
(fun (x : Key) => decide (¬ (a ≤ (x : WithTop Key) ∧ (x : WithTop Key) < b))) := rfl
/-- A key is stored in an interval-erased database exactly when it is stored in
the original and does not lie in the erased interval. -/
theorem mem_eraseInterval_iff {db : DB} {a b : WithTop Key} {x : Key} :
x ∈ (db.eraseInterval a b).keys ↔
x ∈ db.keys ∧ ¬(a ≤ (x : WithTop Key) ∧ (x : WithTop Key) < b) := by
rw [eraseInterval_keys, List.mem_filter]
simp only [decide_eq_true_eq]
end DB
/-- In a strictly increasing list, exactly the keys at indices below `n` are
strictly below the `n`-th key. Hence the number of keys strictly below that key
is `n`. -/
theorem countP_lt_eq_of_getElem {l : List Key} (hs : l.SortedLT) {x : Key} {n : Nat}
(hn : n < l.length) (hnx : l[n] = x) :
l.countP (fun k => decide (k < x)) = n := by
have hdecomp : l = l.take n ++ l[n] :: l.drop (n + 1) := by
have h1 := List.take_append_drop (n + 1) l
rw [List.take_succ_eq_append_getElem hn, List.append_assoc, List.singleton_append] at h1
exact h1.symm
rw [hdecomp, List.countP_append]
rw [List.countP_cons_of_neg]
· have htake : (l.take n).countP (fun k => decide (k < x)) = (l.take n).length := by
rw [List.countP_eq_length]
intro k hk
rw [List.mem_take_iff_getElem] at hk
obtain ⟨j, hj, rfl⟩ := hk
rw [decide_eq_true_eq, ← hnx, hs.getElem_lt_getElem_iff]
omega
rw [htake, List.length_take, Nat.min_eq_left (le_of_lt hn)]
have hdrop : (l.drop (n + 1)).countP (fun k => decide (k < x)) = 0 := by
rw [List.countP_eq_zero]
intro k hk
rw [List.mem_drop_iff_getElem] at hk
obtain ⟨j, hj, rfl⟩ := hk
simp only [decide_eq_true_eq]
rw [← hnx]
exact not_lt.mpr ((hs.getElem_le_getElem_iff).mpr (by omega))
rw [hdrop, Nat.add_zero]
· rw [hnx]; simp
/-- A list containing a key its predicate accepts has a positive count. -/
theorem countP_pos_of_mem {l : List Key} {p : Key → Bool} {a : Key} (h : a ∈ l)
(hp : p a = true) : 0 < l.countP p := by
by_contra h0
have hz : l.countP p = 0 := by omega
exact (List.countP_eq_zero.mp hz) a h hp
/-- A key below `x` at index `i` of a strictly increasing list forces more than
`i` keys below `x`. -/
theorem lt_countP_of_getElem_lt {l : List Key} (hs : l.SortedLT) {x : Key} {i : Nat}
(hi : i < l.length) (hlt : l[i] < x) : i < l.countP (fun k => decide (k < x)) := by
have h1 : (l.take (i + 1)).countP (fun k => decide (k < x)) = (l.take (i + 1)).length := by
rw [List.countP_eq_length]
intro k hk
rw [List.mem_take_iff_getElem] at hk
obtain ⟨j, hj, rfl⟩ := hk
rw [decide_eq_true_eq]
exact lt_of_le_of_lt ((hs.getElem_le_getElem_iff).mpr (by omega)) hlt
have h3 : (l.take (i + 1)).countP (fun k => decide (k < x)) ≤
l.countP (fun k => decide (k < x)) :=
List.Sublist.countP_le (List.take_prefix (i + 1) l).sublist
rw [h1, List.length_take, Nat.min_eq_left (by omega)] at h3
omega
/-- In a strictly increasing list, the key at an index below the count of keys
below `x` is itself below `x`. -/
theorem getElem_lt_of_lt_countP {l : List Key} (hs : l.SortedLT) {x : Key} {i : Nat}
(hi : i < l.length) (hic : i < l.countP (fun k => decide (k < x))) : l[i] < x := by
by_contra h
have hle : x ≤ l[i] := le_of_not_gt h
have hzero : (l.drop i).countP (fun k => decide (k < x)) = 0 := by
rw [List.countP_eq_zero]
intro k hk
rw [List.mem_drop_iff_getElem] at hk
obtain ⟨j, hj, rfl⟩ := hk
simp only [decide_eq_true_eq]
exact not_lt.mpr (le_trans hle ((hs.getElem_le_getElem_iff).mpr (by omega)))
have hsplit : l.countP (fun k => decide (k < x)) =
(l.take i).countP (fun k => decide (k < x)) +
(l.drop i).countP (fun k => decide (k < x)) := by
conv_lhs => rw [← List.take_append_drop i l]
rw [List.countP_append]
rw [hzero, Nat.add_zero] at hsplit
have hle' : (l.take i).countP (fun k => decide (k < x)) ≤ (l.take i).length :=
List.countP_le_length
rw [List.length_take, Nat.min_eq_left (le_of_lt hi)] at hle'
omega
/-- Erasing the `n`-th key does not change the count of keys strictly below it. -/
theorem eraseIdx_countP {l : List Key} (hs : l.SortedLT) {x : Key} {n : Nat}
(hn : n < l.length) (hnx : l[n] = x) :
(l.eraseIdx n).countP (fun k => decide (k < x)) = n := by
rw [List.eraseIdx_eq_take_drop_succ, List.countP_append]
have htake : (l.take n).countP (fun k => decide (k < x)) = (l.take n).length := by
rw [List.countP_eq_length]
intro k hk
rw [List.mem_take_iff_getElem] at hk
obtain ⟨j, hj, rfl⟩ := hk
rw [decide_eq_true_eq, ← hnx, hs.getElem_lt_getElem_iff]
omega
have hdrop : (l.drop (n + 1)).countP (fun k => decide (k < x)) = 0 := by
rw [List.countP_eq_zero]
intro k hk
rw [List.mem_drop_iff_getElem] at hk
obtain ⟨j, hj, rfl⟩ := hk
simp only [decide_eq_true_eq]
rw [← hnx]
exact not_lt.mpr ((hs.getElem_le_getElem_iff).mpr (by omega))
rw [htake, List.length_take, Nat.min_eq_left (le_of_lt hn), hdrop, Nat.add_zero]
/-- Erasing the key at index `n` brings the successor of that key to index `n`. -/
theorem eraseIdx_getElem_succ {l : List Key} (n : Nat) (hn : n + 1 < l.length) :
(l.eraseIdx n)[n]'(by rw [List.length_eraseIdx]; split <;> omega) = l[n + 1] := by
rw [List.getElem_eraseIdx_of_ge (by rw [List.length_eraseIdx]; split <;> omega) (le_refl n)]
/-- Insert at rank `m`, decomposed into a prefix, the element, and a suffix. -/
theorem insertIdx_eq_take_drop : ∀ (l : List Key) (i : Nat) (k : Key), i ≤ l.length →
l.insertIdx i k = l.take i ++ k :: l.drop i := by
intro l
induction l with
| nil => intro i k hi; simp only [List.length_nil, nonpos_iff_eq_zero] at hi; subst hi; rfl
| cons a t ih =>
intro i k hi
cases i with
| zero => rfl
| succ i =>
change a :: t.insertIdx i k = a :: (t.take i ++ k :: t.drop i)
rw [ih i k (by simpa using hi)]
/-- Filtering is invariant under inserting a key the predicate rejects. -/
theorem filter_insertIdx_of_not {l : List Key} (p : Key → Bool) (m : Nat) (k : Key)
(hk : p k = false) : (l.insertIdx m k).filter p = l.filter p := by
by_cases hm : m ≤ l.length
· rw [insertIdx_eq_take_drop l m k hm, List.filter_append,
List.filter_cons_of_neg (by simpa using hk)]
rw [← List.filter_append, List.take_append_drop m l]
· rw [List.insertIdx_of_length_lt (by omega)]
/-- In a strictly increasing list not containing `v`, the prefix of keys below `v`
is taken by `takeWhile (¬ v ≤ ·)`. -/
theorem takeWhile_not_le_eq_take {l : List Key} (hs : l.SortedLT) {v : Key} (hv : v ∉ l) :
l.takeWhile (fun b => ¬ v ≤ b) =
l.take (l.countP (fun k => decide (k < v))) := by
induction l with
| nil => rfl
| cons a t ih =>
have ht : t.SortedLT := List.sortedLT_iff_pairwise.mpr (List.pairwise_cons.mp hs.pairwise).2
have hvt : v ∉ t := fun h => hv (List.mem_cons_of_mem a h)
by_cases hva : v ≤ a
· rw [List.takeWhile_cons_of_neg (by simp [hva])]
have hcount : (a :: t).countP (fun k => decide (k < v)) = 0 := by
rw [List.countP_eq_zero]
intro x hx
rw [List.mem_cons] at hx
rcases hx with rfl | hx
· simp [hva]
· have hax : a ≤ x := le_of_lt ((List.pairwise_cons.mp hs.pairwise).1 x hx)
simp [not_lt.mpr (le_trans hva hax)]
rw [hcount]; rfl
· have hlt : a < v := lt_of_not_ge hva
rw [List.takeWhile_cons_of_pos (by simp [hva]), ih ht hvt]
have hcount : (a :: t).countP (fun k => decide (k < v)) =
t.countP (fun k => decide (k < v)) + 1 := by
rw [List.countP_cons]; simp [hlt]
rw [hcount, List.take_succ_cons]
/-- In a strictly increasing list not containing `v`, the suffix of keys at or
above `v` is taken by `dropWhile (¬ v ≤ ·)`. -/
theorem dropWhile_not_le_eq_drop {l : List Key} (hs : l.SortedLT) {v : Key} (hv : v ∉ l) :
l.dropWhile (fun b => ¬ v ≤ b) =
l.drop (l.countP (fun k => decide (k < v))) := by
induction l with
| nil => rfl
| cons a t ih =>
have ht : t.SortedLT := List.sortedLT_iff_pairwise.mpr (List.pairwise_cons.mp hs.pairwise).2
have hvt : v ∉ t := fun h => hv (List.mem_cons_of_mem a h)
by_cases hva : v ≤ a
· rw [List.dropWhile_cons_of_neg (by simp [hva])]
have hcount : (a :: t).countP (fun k => decide (k < v)) = 0 := by
rw [List.countP_eq_zero]
intro x hx
rw [List.mem_cons] at hx
rcases hx with rfl | hx
· simp [hva]
· have hax : a ≤ x := le_of_lt ((List.pairwise_cons.mp hs.pairwise).1 x hx)
simp [not_lt.mpr (le_trans hva hax)]
rw [hcount]
rfl
· have hlt : a < v := lt_of_not_ge hva
rw [List.dropWhile_cons_of_pos (by simp [hva]), ih ht hvt]
have hcount : (a :: t).countP (fun k => decide (k < v)) =
t.countP (fun k => decide (k < v)) + 1 := by
rw [List.countP_cons]; simp [hlt]
rw [hcount, List.drop_succ_cons]
/-- Inserting an absent key into a sorted list is an `insertIdx` at the count of
keys strictly below it. -/
theorem orderedInsert_eq_insertIdx {l : List Key} (hs : l.SortedLT) {v : Key}
(hv : v ∉ l) :
l.orderedInsert (· ≤ ·) v =
l.insertIdx (l.countP (fun k => decide (k < v))) v := by
rw [List.orderedInsert_eq_take_drop, takeWhile_not_le_eq_take hs hv,
dropWhile_not_le_eq_drop hs hv]
exact (insertIdx_eq_take_drop l (l.countP (fun k => decide (k < v))) v
List.countP_le_length).symm
/-- A key's rank equals the number of stored keys strictly below it. -/
theorem getElem_countP_lt {l : List Key} (hs : l.SortedLT) {x : Key} (hx : x ∈ l) :
l[l.countP (fun k => decide (k < x))]'(by
obtain ⟨i, hi, hix⟩ := List.mem_iff_getElem.mp hx
rw [countP_lt_eq_of_getElem hs hi hix]
exact hi) = x := by
obtain ⟨i, hi, hix⟩ := List.mem_iff_getElem.mp hx
have hcount := countP_lt_eq_of_getElem hs hi hix
subst hcount
exact hix
/-- Inserting a key the predicate rejects preserves the count of accepted keys. -/
theorem countP_insertIdx {l : List Key} (p : Key → Bool) (i : Nat) (v : Key)
(hv : p v = false) : (l.insertIdx i v).countP p = l.countP p := by
rw [List.countP_eq_length_filter, List.countP_eq_length_filter,
filter_insertIdx_of_not p i v hv]
/-- Inserting a key strictly between the insertion rank and `v` increments the
count of keys strictly below `v`, where `v` may be past every key. -/
theorem countP_insertIdx_of_lt {l : List Key} (hs : l.SortedLT) {x : Key} {v : WithTop Key}
(hxv : (x : WithTop Key) < v) :
(l.insertIdx (l.countP (fun k => decide (k < x))) x).countP
(fun (k : Key) => decide ((↑k : WithTop Key) < v)) =
l.countP (fun (k : Key) => decide ((↑k : WithTop Key) < v)) + 1 := by
set c := l.countP (fun k => decide (k < x)) with hc
have hclen : c ≤ l.length := by rw [hc]; exact List.countP_le_length
rw [insertIdx_eq_take_drop l c x hclen, List.countP_append,
List.countP_cons_of_pos (by rw [decide_eq_true_eq]; exact hxv)]
have htake : (l.take c).countP (fun (k : Key) => decide ((↑k : WithTop Key) < v)) = c := by
have h1 : (l.take c).countP (fun (k : Key) => decide ((↑k : WithTop Key) < v)) =
(l.take c).length := by
rw [List.countP_eq_length]
intro k hk
rw [List.mem_take_iff_getElem] at hk
obtain ⟨i, hi, rfl⟩ := hk
rw [decide_eq_true_eq]
exact lt_trans (WithTop.coe_lt_coe.mpr
(getElem_lt_of_lt_countP hs (by omega) (by rw [← hc]; omega))) hxv
rw [h1, List.length_take, Nat.min_eq_left hclen]
have hsplit : l.countP (fun (k : Key) => decide ((↑k : WithTop Key) < v)) =
(l.take c).countP (fun (k : Key) => decide ((↑k : WithTop Key) < v)) +
(l.drop c).countP (fun (k : Key) => decide ((↑k : WithTop Key) < v)) := by
conv_lhs => rw [← List.take_append_drop c l]
rw [List.countP_append]
rw [htake] at hsplit
omega
/-- The count of keys strictly below a coerced key `↑v` equals the count of keys
strictly below `v`. -/
theorem countP_lt_coe {l : List Key} (v : Key) :
l.countP (fun (k : Key) => decide ((↑k : WithTop Key) < (↑v : WithTop Key))) =
l.countP (fun k => decide (k < v)) := by
simp [WithTop.coe_lt_coe]
/-- No key lies strictly below the empty key, so nothing is counted below it. -/
theorem countP_lt_nil {l : List Key} :
l.countP (fun (k : Key) => decide ((↑k : WithTop Key) < (([] : Key) : WithTop Key))) = 0 := by
rw [List.countP_eq_zero]
intro k _
simp only [decide_eq_true_eq, WithTop.coe_lt_coe]
exact List.not_lt_nil k
/-- Every key lies strictly below `⊤`, so all of `l` is counted below it. -/
theorem countP_lt_top {l : List Key} :
l.countP (fun (k : Key) => decide ((↑k : WithTop Key) < (⊤ : WithTop Key))) = l.length := by
rw [List.countP_eq_length]
intro k _
rw [decide_eq_true_eq]
exact WithTop.coe_lt_top k
/-!
## The least key above a key
`keyAfter k = k ++ [0]` is the immediate successor of `k` in the lexicographic
order on keys: it lies strictly above `k`, and every key strictly below it is at
most `k`. This is what lets a range end just past a reported key while still
naming a genuine half-open upper bound.
-/
/-- A key strictly above `k`: append a zero byte. By `lt_keyAfter_iff` it is the
least such key. -/
def keyAfter (k : Key) : Key := k ++ [0]
/-- `keyAfter` commutes with `cons`, by definition. -/
theorem keyAfter_cons (a : Byte) (t : Key) : keyAfter (a :: t) = a :: keyAfter t := rfl
/-- A key lies strictly below its successor. -/
theorem keyAfter_self_lt (l : Key) : l < keyAfter l := by
rw [keyAfter]
simpa using List.Lex.append_left (· < ·)
(List.Lex.nil (a := (0 : Byte)) (l := ([] : Key))) l
/-- Lexicographic `≤` on keys, in the `LinearOrder` instance this library uses,
splits on the head byte. The core `List.cons_le_cons_iff` names a different `LE`
instance and so does not apply directly. -/
private theorem cons_le_cons_iff {c a : Byte} {u t : Key} :
(c :: u ≤ a :: t) ↔ c < a ∨ c = a ∧ u ≤ t := by
rw [le_iff_lt_or_eq, List.cons_lt_cons_iff]
constructor
· rintro (h | h)
· rcases h with hca | ⟨hca, hut⟩
· exact Or.inl hca
· exact Or.inr ⟨hca, le_of_lt hut⟩
· rw [List.cons.injEq] at h
obtain ⟨rfl, rfl⟩ := h
exact Or.inr ⟨rfl, le_refl u⟩
· rintro (hca | ⟨rfl, hut⟩)
· exact Or.inl (Or.inl hca)
· rw [le_iff_lt_or_eq] at hut
rcases hut with hut | hut
· exact Or.inl (Or.inr ⟨rfl, hut⟩)
· exact Or.inr (by rw [hut])
/-- A key is strictly below `keyAfter l` exactly when it is at or below `l`. -/
theorem lt_keyAfter_iff (k l : Key) : k < keyAfter l ↔ k ≤ l := by
constructor
· intro h
induction l generalizing k with
| nil =>
cases k with
| nil => exact le_refl []
| cons c u =>
simp only [keyAfter, List.nil_append] at h
rw [List.cons_lt_cons_iff] at h
rcases h with hc | ⟨_, h⟩
· exact absurd hc (not_lt.mpr (by simp))
· exact absurd h (List.not_lt_nil u)
| cons a t ih =>
cases k with
| nil => exact (le_iff_lt_or_eq).mpr (Or.inl (List.nil_lt_cons a t))
| cons c u =>
rw [keyAfter_cons, List.cons_lt_cons_iff] at h
rcases h with hca | ⟨hca, hut⟩
· exact cons_le_cons_iff.mpr (Or.inl hca)
· exact cons_le_cons_iff.mpr (Or.inr ⟨hca, ih u hut⟩)
· intro h
rcases (le_iff_lt_or_eq).mp h with hlt | heq
· exact List.lt_trans hlt (keyAfter_self_lt l)
· rw [heq]; exact keyAfter_self_lt l
/-- `keyAfter l` is at most any `WithTop Key` bound lying strictly above `l`. -/
theorem keyAfter_le_of_lt {l : Key} {E : WithTop Key} (h : (l : WithTop Key) < E) :
(keyAfter l : WithTop Key) ≤ E := by
cases E with
| top => exact le_top
| coe e =>
refine WithTop.coe_le_coe.mpr ?_
by_contra hcon
have hel : e < keyAfter l := not_le.mp hcon
exact absurd (WithTop.coe_lt_coe.mp h) (not_lt.mpr ((lt_keyAfter_iff e l).mp hel))
/-- In a strictly increasing list, the key at an index below the count of keys
below `w` is itself below `w` in `WithTop Key`. -/
theorem getElem_lt_of_lt_countP_top {l : List Key} (hs : l.SortedLT) {w : WithTop Key}
{i : Nat} (hi : i < l.length)
(hic : i < l.countP (fun (k : Key) => decide ((↑k : WithTop Key) < w))) :
(l[i] : WithTop Key) < w := by
by_contra h
have hle : w ≤ (l[i] : WithTop Key) := le_of_not_gt h
have hzero : (l.drop i).countP (fun (k : Key) => decide ((↑k : WithTop Key) < w)) = 0 := by
rw [List.countP_eq_zero]
intro k hk
rw [List.mem_drop_iff_getElem] at hk
obtain ⟨j, hj, rfl⟩ := hk
simp only [decide_eq_true_eq]
exact not_lt.mpr (le_trans hle
(WithTop.coe_le_coe.mpr ((hs.getElem_le_getElem_iff).mpr (by omega))))
have hsplit : l.countP (fun (k : Key) => decide ((↑k : WithTop Key) < w)) =
(l.take i).countP (fun (k : Key) => decide ((↑k : WithTop Key) < w)) +
(l.drop i).countP (fun (k : Key) => decide ((↑k : WithTop Key) < w)) := by
conv_lhs => rw [← List.take_append_drop i l]
rw [List.countP_append]
rw [hzero, Nat.add_zero] at hsplit
have hle' : (l.take i).countP (fun (k : Key) => decide ((↑k : WithTop Key) < w)) ≤
(l.take i).length := List.countP_le_length
rw [List.length_take, Nat.min_eq_left (le_of_lt hi)] at hle'
omega
/-!
## The cardinality of a key interval
`intervalCard b e` is the number of keys in the half-open interval `[b, e)` as an
extended natural. The key space is discrete but unbounded above, so the count is
`⊤` unless the interval is either empty or a finite run of the immediate successors
of its lower end: `[b, b ++ [0]⁰)` is empty, and `[b, b ++ [0]ⁿ)` contains exactly
the `n` keys `b ++ [0]⁰, …, b ++ [0]ⁿ⁻¹`. Every other interval is infinite.
`[b, e)` is empty when `e ≤ b` and, since `⊤` is above every key, `[b, ⊤)` is
infinite for any genuine `b` while `[⊤, e)` is empty. The successor chain is exactly
the notation the truncated conflict ranges use: `keyAfter b = b ++ [0]`, so
`[b, keyAfterⁿ b)` has `n` keys.
-/
/-- The number of keys in the half-open interval `[b, e)`, as an extended natural.
It is `0` when the interval is empty (`e ≤ b`), the length `n` when `e` is `b`
followed by `n` zero bytes, and `⊤` otherwise. -/
def intervalCard (b e : WithTop Key) : ℕ∞ :=
match b, e with
| ⊤, _ => 0
| _, ⊤ => ⊤
| (b : Key), (e : Key) =>
if e ≤ b then 0
else if b <+: e ∧ (e.drop b.length).all (fun c => c == (0 : Byte)) then
(e.length - b.length : ℕ)
else ⊤
/-- No key lies at or above `⊤`. -/
theorem intervalCard_top_left (e : WithTop Key) : intervalCard ⊤ e = 0 := by
cases e <;> simp only [intervalCard]
/-- The interval from a genuine key to `⊤` is infinite. -/
theorem intervalCard_top_right {b : WithTop Key} (hb : b ≠ ⊤) :
intervalCard b ⊤ = ⊤ := by
cases b with
| top => exact absurd rfl hb
| coe b => simp only [intervalCard]
/-- For genuine keys, `intervalCard b ⊤` is `⊤`: spelled with both ends coerced to
`WithTop Key`, this is the `intervalCard_top_right` shape the guard uses. -/
theorem intervalCard_coe_top (b : Key) :
intervalCard (↑b : WithTop Key) (⊤ : WithTop Key) = ⊤ :=
intervalCard_top_right (by simp)
/-- An empty interval has cardinality zero. -/
theorem intervalCard_eq_zero_of_le {b e : WithTop Key} (h : e ≤ b) :
intervalCard b e = 0 := by
cases b with
| top => exact intervalCard_top_left e
| coe b =>
cases e with
| top => exact absurd h (not_le.mpr (WithTop.coe_lt_top b))
| coe e =>
simp only [intervalCard]
rw [ite_eq_left (WithTop.coe_le_coe.mp h)]
/-- The interval from `b` to `b` followed by `n` zero bytes has exactly `n` keys. -/
theorem intervalCard_succChain (b : Key) (n : ℕ) :
intervalCard (↑b) (↑(b ++ List.replicate n (0 : Byte))) = (n : ℕ) := by
induction n with
| zero => simpa using intervalCard_eq_zero_of_le (le_refl (↑b : WithTop Key))
| succ k ih =>
rw [List.replicate_succ]
simp only [intervalCard]
have hb_lt : b < b ++ (0 : Byte) :: List.replicate k 0 := by
simpa using List.append_left_lt (l₁ := b) (l₂ := ([] : Key))
(l₃ := (0 : Byte) :: List.replicate k 0) (List.nil_lt_cons 0 _)
have hlt : ¬ (b ++ (0 : Byte) :: List.replicate k 0) ≤ b :=
fun h => absurd (lt_of_lt_of_le hb_lt h) (lt_irrefl b)
rw [ite_eq_right hlt]
have hpre : b <+: b ++ (0 : Byte) :: List.replicate k 0 := List.prefix_append b _
have hdrop : (b ++ (0 : Byte) :: List.replicate k 0).drop b.length =
(0 : Byte) :: List.replicate k 0 := List.drop_left
have hall : ((b ++ (0 : Byte) :: List.replicate k 0).drop b.length).all
(fun c => c == (0 : Byte)) = true := by
rw [hdrop]; simp
rw [ite_eq_left ⟨hpre, hall⟩]
have hlen : (b ++ (0 : Byte) :: List.replicate k 0).length = b.length + (k + 1) := by
simp [List.length_append, Nat.add_assoc, Nat.add_comm]
rw [hlen, Nat.add_sub_cancel_left]
/-- For genuine keys, a finite cardinality exactly characterizes the successor
chains: `[b, e)` has `n` keys precisely when `e ≤ b` (and `n = 0`) or `e` is `b`
followed by `n` zero bytes. This says the finite intervals are exactly the
iterated `keyAfter` chains. -/
theorem intervalCard_eq_coe_iff {b e : Key} {n : ℕ} :
intervalCard (↑b) (↑e) = (n : ℕ) ↔
(n = 0 ∧ e ≤ b) ∨ e = b ++ List.replicate n (0 : Byte) := by
constructor
· intro h
simp only [intervalCard] at h
by_cases hle : e ≤ b
· rw [ite_eq_left hle] at h
exact Or.inl ⟨(WithTop.coe_eq_coe.mp h).symm, hle⟩
· rw [ite_eq_right hle] at h
by_cases hc : b <+: e ∧ (e.drop b.length).all (fun c => c == (0 : Byte))
· rw [ite_eq_left hc] at h
right
have heq : e = b ++ (e.drop b.length) := (List.prefix_iff_eq_append.mp hc.1).symm
have hall : e.drop b.length = List.replicate (e.drop b.length).length (0 : Byte) :=
List.eq_replicate_length.mpr fun x hx =>
eq_of_beq ((List.all_eq_true.mp hc.2) x hx)
rw [heq, hall]
have hnd : n = (e.drop b.length).length := by
rw [← WithTop.coe_eq_coe.mp h, List.length_drop]
rw [hnd]
· rw [ite_eq_right hc] at h
exact absurd h (by simp)
· rintro (⟨rfl, hle⟩ | heq)
· exact intervalCard_eq_zero_of_le (WithTop.coe_le_coe.mpr hle)
· subst heq
exact intervalCard_succChain b n
/-- A genuine-coerced interval has cardinality zero exactly when it is empty. -/
theorem intervalCard_eq_zero_iff {b e : WithTop Key} :
intervalCard b e = 0 ↔ e ≤ b := by
constructor
· intro h
cases b with
| top => exact le_top
| coe b =>
cases e with
| top => rw [intervalCard_top_right (by simp)] at h; exact absurd h (by simp)
| coe e =>
by_contra hle
rcases (intervalCard_eq_coe_iff (b := b) (e := e) (n := 0)).mp h with
⟨_, hle'⟩ | heq
· exact hle (WithTop.coe_le_coe.mpr hle')
· rw [List.replicate_zero, List.append_nil] at heq
exact hle (WithTop.coe_le_coe.mpr heq.le)
· exact intervalCard_eq_zero_of_le
/-- A genuine-coerced interval is infinite exactly when `e` is neither at or below
`b` nor a run of zero bytes appended to `b`. -/
theorem intervalCard_eq_top_iff {b e : Key} :
intervalCard (↑b) (↑e) = ⊤ ↔
¬ e ≤ b ∧ ¬ (b <+: e ∧ (e.drop b.length).all (fun c => c == (0 : Byte))) := by
constructor
· intro h
simp only [intervalCard] at h
by_cases hle : e ≤ b
· rw [ite_eq_left hle] at h; exact absurd h (by simp)
· rw [ite_eq_right hle] at h
by_cases hc : b <+: e ∧ (e.drop b.length).all (fun c => c == (0 : Byte))
· rw [ite_eq_left hc] at h; exact absurd h (by simp)
· rw [ite_eq_right hc] at h; exact ⟨hle, hc⟩
· rintro ⟨hle, hc⟩
simp only [intervalCard]
rw [ite_eq_right hle, ite_eq_right hc]
/-!
### `intervalCard` counts the keys in the interval
The three computational cases of `intervalCard` are exactly the cardinalities of the
set `keysIn b e` of genuine keys lying in `[b, e)`. The finite case is the heart of
the argument: the keys of `[b, b ++ [0]ⁿ)` are precisely the iterated successors
`b, keyAfter b, …, keyAfterⁿ⁻¹ b` (`eq_chain_of_lt_chain`), a set of `n` elements.
When the interval is nonempty but its upper end is not such a chain, an injection
`n ↦ b ++ [0]ⁿ` into the interval makes it infinite (`keysIn_coe_coe_infinite`).
-/
/-- The iterated successor chain `b, keyAfter b, keyAfter² b, …`. -/
def chain (b : Key) (n : ℕ) : Key := b ++ List.replicate n (0 : Byte)
/-- The chain starts at `b`. -/
theorem chain_zero (b : Key) : chain b 0 = b := by simp [chain]
/-- Each chain element is the successor of the previous one. -/
theorem chain_succ (b : Key) (n : ℕ) : chain b (n + 1) = keyAfter (chain b n) := by
simp only [chain, keyAfter, List.replicate_succ']
rw [← List.append_assoc]
/-- The chain is injective in its index. -/
theorem chain_injective (b : Key) : Function.Injective (chain b) := by
intro i j h
have h' : List.replicate i (0 : Byte) = List.replicate j (0 : Byte) :=
List.append_cancel_left h
simpa using congrArg List.length h'
/-- Every chain element is at or above its base. -/
theorem chain_le (b : Key) (n : ℕ) : b ≤ chain b n := by
rcases n with _ | m
· simp [chain]
· rw [chain]
have h := List.append_left_lt (l₁ := b) (l₂ := ([] : Key))
(l₃ := List.replicate (m + 1) (0 : Byte)) (by
rw [List.replicate_succ]; exact List.nil_lt_cons _ _)
simpa using le_of_lt h
/-- The chain is strictly increasing in its index. -/
theorem chain_lt_mono {b : Key} {i n : ℕ} (h : i < n) : chain b i < chain b n := by
have hle : i ≤ n := le_of_lt h
have hsplit : chain b n = chain b i ++ List.replicate (n - i) (0 : Byte) := by
simp only [chain]
rw [List.append_assoc, List.replicate_append_replicate, Nat.add_sub_of_le hle]
rw [hsplit]
have hlt : ([] : Key) < List.replicate (n - i) (0 : Byte) := by
obtain ⟨m, hm⟩ : ∃ m, n - i = m + 1 := ⟨n - i - 1, by omega⟩
rw [hm, List.replicate_succ]
exact List.nil_lt_cons _ _
have h := List.append_left_lt (l₁ := chain b i) (l₂ := ([] : Key))
(l₃ := List.replicate (n - i) (0 : Byte)) hlt
simpa using h
/-- Nothing lies strictly between `b` and its successor `keyAfter b`. -/
theorem eq_of_le_of_lt_keyAfter {b k : Key} (h₁ : b ≤ k) (h₂ : k < keyAfter b) : k = b :=
le_antisymm ((lt_keyAfter_iff k b).mp h₂) h₁
/-- A key in `(b, chain b n]` is some `chain b m` with `m ≤ n`: the chain absorbs
every key up to its last element. -/
theorem eq_chain_of_le_chain {b e : Key} (hb : b < e) :
∀ n, e ≤ chain b n → ∃ m ≤ n, e = chain b m := by
intro n
induction n with
| zero =>
intro h
rw [chain_zero] at h
exact absurd (lt_of_lt_of_le hb h) (lt_irrefl b)
| succ k ih =>
intro h
rw [chain_succ] at h
rcases le_or_gt e (chain b k) with hle | hgt
· obtain ⟨m, hm, rfl⟩ := ih hle
exact ⟨m, Nat.le_succ_of_le hm, rfl⟩
· have heq : e = keyAfter (chain b k) := by
rcases lt_or_eq_of_le h with hlt | heq
· exact absurd (eq_of_le_of_lt_keyAfter (le_of_lt hgt) hlt) (ne_of_gt hgt)
· exact heq
exact ⟨k + 1, le_refl _, by rw [chain_succ]; exact heq⟩
/-- A key strictly below `chain b n` and above `b` is some `chain b m` with `m < n`. -/
theorem eq_chain_of_lt_chain {b e : Key} (hb : b < e) :
∀ n, e < chain b n → ∃ m < n, e = chain b m := by
intro n h
obtain ⟨m, hm, hmk⟩ := eq_chain_of_le_chain hb n (le_of_lt h)
refine ⟨m, lt_of_le_of_ne hm ?_, hmk⟩
intro hmn
subst hmn
exact absurd hmk (ne_of_lt h)
/-- If `e` is above `b` and is not any chain element, every chain element is below it. -/
theorem chain_lt_of_not_chain {b e : Key} (hb : b < e) (hne : ∀ n, e ≠ chain b n) :
∀ n, chain b n < e := by
intro n
by_contra h
have hle : e ≤ chain b n := le_of_not_gt h
obtain ⟨m, _, hm⟩ := eq_chain_of_le_chain hb n hle
exact hne m hm
/-- The set of genuine keys lying in the half-open interval `[b, e)`. -/
def keysIn (b e : WithTop Key) : Set Key :=
{k : Key | b ≤ (↑k : WithTop Key) ∧ (↑k : WithTop Key) < e}
/-- The first `n` elements of the chain from `b`. -/
def chainSet (b : Key) (n : ℕ) : Set Key :=
{k : Key | ∃ i, i < n ∧ k = chain b i}
/-- In the coerced case, `[b, e)` is the set of keys between `b` and `e`. -/
theorem keysIn_coe_coe (b e : Key) :
keysIn (↑b : WithTop Key) (↑e : WithTop Key) = {k : Key | b ≤ k ∧ k < e} := by
ext k; simp only [keysIn, Set.mem_ofPred_eq, WithTop.coe_le_coe, WithTop.coe_lt_coe]
/-- `[⊤, e)` is empty: no key lies at or above `⊤`. -/
theorem keysIn_top_left (e : WithTop Key) : keysIn ⊤ e = ∅ := by
ext k
simp only [keysIn, Set.mem_ofPred_eq, Set.mem_empty_iff_false, iff_false, not_and]
intro h
exact absurd h (not_le.mpr (WithTop.coe_lt_top k))
/-- `[b, ⊤)` is the set of keys at or above `b`. -/
theorem keysIn_coe_top (b : Key) :
keysIn (↑b : WithTop Key) (⊤ : WithTop Key) = {k : Key | b ≤ k} := by
ext k
simp only [keysIn, Set.mem_ofPred_eq, WithTop.coe_le_coe, WithTop.coe_lt_top, and_true]
/-- The interval up to a chain element is exactly the chain's first `n` elements. -/
theorem keysIn_chain (b : Key) (n : ℕ) :
keysIn (↑b) (↑(chain b n)) = chainSet b n := by
ext k
simp only [keysIn, chainSet, Set.mem_ofPred_eq, WithTop.coe_le_coe, WithTop.coe_lt_coe]
constructor
· rintro ⟨hbk, hke⟩
by_cases hbk' : b = k
· subst hbk'
refine ⟨0, ?_, (chain_zero b).symm⟩
rcases n with _ | m
· rw [chain_zero] at hke; exact absurd hke (lt_irrefl b)
· exact Nat.succ_pos m
· have hb_lt_k : b < k := lt_of_le_of_ne hbk hbk'
obtain ⟨m, hm, hmk⟩ := eq_chain_of_lt_chain hb_lt_k n hke
exact ⟨m, hm, hmk⟩
· rintro ⟨i, hi, rfl⟩
exact ⟨chain_le b i, chain_lt_mono hi⟩
/-- A chain of `n` keys has exactly `n` elements. -/
theorem chainSet_encard (b : Key) (n : ℕ) : (chainSet b n).encard = (n : ℕ∞) := by
have hset : chainSet b n = chain b '' {i : ℕ | i < n} := by
ext k
simp only [chainSet, Set.mem_ofPred_eq, Set.mem_image]
constructor
· rintro ⟨i, hi, rfl⟩; exact ⟨i, hi, rfl⟩
· rintro ⟨i, hi, rfl⟩; exact ⟨i, hi, rfl⟩
rw [hset, (chain_injective b).encard_image, Set.Nat.encard_range]
/-- `[b, ⊤)` is infinite: the chain from `b` injects into it. -/
theorem keysIn_coe_top_infinite (b : Key) : (keysIn (↑b : WithTop Key) ⊤).Infinite := by
rw [keysIn_coe_top]
exact Set.infinite_of_injective_forall_mem (chain_injective b) (fun n => chain_le b n)
/-- `[b, e)` is infinite when `e` is above `b` but not a chain element: the chain
from `b` injects into it, staying below `e`. -/
theorem keysIn_coe_coe_infinite {b e : Key} (hb : b < e) (hne : ∀ n, e ≠ chain b n) :
(keysIn (↑b : WithTop Key) (↑e : WithTop Key)).Infinite := by
rw [keysIn_coe_coe]
exact Set.infinite_of_injective_forall_mem (chain_injective b)
(fun n => ⟨chain_le b n, chain_lt_of_not_chain hb hne n⟩)
/-- A prefix of zero bytes is exactly a chain endpoint: if `b` is a prefix of `e`
whose remainder is all zeros, then `e` is `chain b n` for `n` the length excess. -/
theorem eq_chain_of_prefix_zeros {b e : Key} (hpre : b <+: e)
(hall : (e.drop b.length).all (· == (0 : Byte)) = true) :
e = chain b (e.length - b.length) := by
have hdrop : e.drop b.length = List.replicate (e.length - b.length) (0 : Byte) := by
have h : e.drop b.length =
List.replicate (e.drop b.length).length (0 : Byte) :=
List.eq_replicate_length.mpr fun x hx =>
eq_of_beq ((List.all_eq_true.mp hall) x hx)
rwa [List.length_drop] at h
have heq : e = b ++ (e.drop b.length) := (List.prefix_iff_eq_append.mp hpre).symm
rw [heq, hdrop]
simp [chain]
/-- A byte list is a run of zero bytes exactly when all its entries are zero. -/
theorem exists_eq_replicate_zero_iff (l : List Byte) :
(∃ m, l = List.replicate m (0 : Byte)) ↔ l.all (· == (0 : Byte)) = true := by
constructor
· rintro ⟨m, rfl⟩; simp
· intro h
exact ⟨l.length, List.eq_replicate_length.mpr fun b hb =>
eq_of_beq ((List.all_eq_true.mp h) b hb)⟩
/-- **Interpretation.** `intervalCard b e` is the cardinality of the set of genuine
keys lying in the half-open interval `[b, e)`. -/
theorem intervalCard_eq_encard_keysIn (b e : WithTop Key) :
intervalCard b e = (keysIn b e).encard := by
cases b with
| top => rw [intervalCard_top_left, keysIn_top_left, Set.encard_empty]
| coe b =>
cases e with
| top => rw [intervalCard_top_right (by simp), (keysIn_coe_top_infinite b).encard_eq]
| coe e =>
by_cases hle : e ≤ b
· simp only [intervalCard]
rw [ite_eq_left hle]
have hempty : keysIn (↑b : WithTop Key) (↑e : WithTop Key) = ∅ := by
ext k
simp only [keysIn, Set.mem_ofPred_eq, Set.mem_empty_iff_false, iff_false,
not_and, WithTop.coe_le_coe, WithTop.coe_lt_coe]
intro hbk
exact not_lt.mpr (le_trans hle hbk)
rw [hempty, Set.encard_empty]
· simp only [intervalCard]
rw [ite_eq_right hle]
by_cases hc : b <+: e ∧ (e.drop b.length).all (fun c => c == (0 : Byte)) = true
· rw [ite_eq_left hc]
have hchain := eq_chain_of_prefix_zeros hc.1 hc.2
have hset : keysIn (↑b : WithTop Key) (↑e : WithTop Key) =
chainSet b (e.length - b.length) := by
rw [hchain]
have hlen : (chain b (e.length - b.length)).length - b.length =
e.length - b.length := by
simp [chain, List.length_append]
rw [hlen]
exact keysIn_chain b _
rw [hset, chainSet_encard]
· rw [ite_eq_right hc]
have hne : ∀ n, e ≠ chain b n := by
intro n hn
apply hc
exact ⟨by rw [hn, chain]; exact List.prefix_append b _, by
rw [hn, chain, List.drop_left]; simp⟩
have hb : b < e := lt_of_not_ge hle
rw [(keysIn_coe_coe_infinite hb hne).encard_eq]
/-- **Additivity over a subrange.** When `m` lies in `[b, e]`, the keys of
`[b, e)` are exactly those of `[b, m)` together with those of `[m, e)`, and the
two subintervals are disjoint, so their cardinalities add:
`intervalCard b e = intervalCard b m + intervalCard m e`. The hypothesis that `m`
sits between `b` and `e` is essential: for `m` above `e` the interval `[b, m)`
already contains keys at or above `e`, which `[b, e)` excludes. -/
theorem intervalCard_add {b m e : WithTop Key} (hb : b ≤ m) (hm : m ≤ e) :
intervalCard b e = intervalCard b m + intervalCard m e := by
rw [intervalCard_eq_encard_keysIn, intervalCard_eq_encard_keysIn,
intervalCard_eq_encard_keysIn]
have hdisj : Disjoint (keysIn b m) (keysIn m e) := by
rw [Set.disjoint_left]
rintro k ⟨-, hk2⟩ ⟨hmk, -⟩
exact absurd hk2 (not_lt.mpr hmk)
have hunion : keysIn b e = keysIn b m ∪ keysIn m e := by
ext k
simp only [keysIn, Set.mem_ofPred_eq, Set.mem_union]
constructor
· rintro ⟨hbk, hke⟩
by_cases hkm : (↑k : WithTop Key) < m
· exact Or.inl ⟨hbk, hkm⟩
· exact Or.inr ⟨le_of_not_gt hkm, hke⟩
· rintro (⟨hbk, hkm⟩ | ⟨hmk, hke⟩)
· exact ⟨hbk, lt_of_lt_of_le hkm hm⟩
· exact ⟨le_trans hb hmk, hke⟩
rw [hunion, Set.encard_union_eq hdisj]
/-!
## Counting and indexing keys
These are the generic sorted-list tools shared by the selector-conflict-range
arguments: counting the keys of a sorted list that lie strictly below a bound,
and bounding the key at an index by the successor chain of the count. They
mention only `List Key` and `Key`, so they live here beside the `chain` API.
-/
/-- A list whose keys all lie at or above `k₀` has nothing counted strictly
below `k₀`. -/
theorem countP_lt_eq_zero_of_forall_ge {l : List Key} {k₀ : Key} (h : ∀ x ∈ l, k₀ ≤ x) :
l.countP (fun k => decide (k < k₀)) = 0 := by
rw [List.countP_eq_zero]
intro x hx
simpa using not_lt.mpr (h x hx)
/-- A list whose keys all lie strictly below `k₀` has all of them counted
strictly below `k₀`. -/
theorem countP_lt_eq_length_of_forall_lt {l : List Key} {k₀ : Key} (h : ∀ x ∈ l, x < k₀) :
l.countP (fun k => decide (k < k₀)) = l.length := by
rw [List.countP_eq_length]
intro x hx
rw [decide_eq_true_eq]
exact h x hx
/-- In a strictly increasing list, every index at or past the count of keys
strictly below `k₀` holds a key at or above `k₀`. -/
theorem le_getElem_of_countP_le {l : List Key} (hs : l.SortedLT) {k₀ : Key} {i : Nat}
(hci : l.countP (fun k => decide (k < k₀)) ≤ i) (hi : i < l.length) : k₀ ≤ l[i] := by
by_contra hcon
exact absurd (lt_countP_of_getElem_lt hs hi (not_le.mp hcon)) (not_lt.mpr hci)
/-- In a strictly increasing list, the `j`-fold successor chain from the key at
`i` stays at or below the key at `i + j`. -/
theorem chain_getElem_le {l : List Key} (hs : l.SortedLT) {i j : Nat} (hi : i < l.length)
(hij : i + j < l.length) : chain l[i] j ≤ l[i + j] := by
induction j with
| zero => simp [chain_zero]
| succ j ih =>
have hij' : i + j < l.length := by omega
have hle : chain l[i] j ≤ l[i + j] := ih hij'
have hstep : l[i + j] < l[i + (j + 1)] :=
(hs.getElem_lt_getElem_iff).mpr (by omega)
have hkey : (keyAfter (chain l[i] j) : WithTop Key) ≤ (↑(l[i + (j + 1)]) : WithTop Key) :=
keyAfter_le_of_lt (WithTop.coe_lt_coe.mpr (lt_of_le_of_lt hle hstep))
rw [chain_succ]
exact WithTop.coe_le_coe.mp hkey
/-- In a strictly increasing list, the key `m` chain steps past the count of keys
strictly below `k₀` is at or above `chain k₀ m`. -/
theorem chain_le_getElem_countP {l : List Key} (hs : l.SortedLT) {k₀ : Key} {m : Nat}
(hm : l.countP (fun k => decide (k < k₀)) + m < l.length) :
chain k₀ m ≤ l[l.countP (fun k => decide (k < k₀)) + m] := by
induction m with
| zero =>
have hm' : l.countP (fun k => decide (k < k₀)) < l.length := by omega
have h := le_getElem_of_countP_le hs (le_refl _) hm'
simpa [chain_zero] using h
| succ m ih =>
have hm' : l.countP (fun k => decide (k < k₀)) + m < l.length := by omega
have hle : chain k₀ m ≤ l[l.countP (fun k => decide (k < k₀)) + m] := ih hm'
have hstep : l[l.countP (fun k => decide (k < k₀)) + m] <
l[l.countP (fun k => decide (k < k₀)) + (m + 1)] :=
(hs.getElem_lt_getElem_iff).mpr (by omega)
have hkey : (keyAfter (chain k₀ m) : WithTop Key) ≤
(↑(l[l.countP (fun k => decide (k < k₀)) + (m + 1)]) : WithTop Key) :=
keyAfter_le_of_lt (WithTop.coe_lt_coe.mpr (lt_of_le_of_lt hle hstep))
rw [chain_succ]
exact WithTop.coe_le_coe.mp hkey
/-- The successor chain is monotone in its index. -/
theorem chain_le_chain {b : Key} {i j : ℕ} (h : i ≤ j) : chain b i ≤ chain b j := by
rcases eq_or_lt_of_le h with rfl | hlt
· exact le_refl _
· exact le_of_lt (chain_lt_mono hlt)
/-- The empty key is at or below every key. -/
theorem nil_le_key (k : Key) : ([] : Key) ≤ k := by
rcases k with - | ⟨a, t⟩
· exact le_refl _
· exact le_of_lt (List.nil_lt_cons a t)
/-!
### Sortedness of the successor-chain lists
The successor chain in index order is strictly increasing, and appending a key
above the whole chain preserves that. These build the witness databases of the
footprint specification.
-/
/-- The successor chain from a base, in index order, is strictly increasing. -/
theorem sortedLT_map_chain (b : Key) (n : ℕ) : ((List.range n).map (chain b)).SortedLT := by
rw [List.sortedLT_iff_pairwise, List.pairwise_iff_getElem]
intro i j hi hj hij
simp only [List.getElem_map, List.getElem_range]
exact chain_lt_mono hij
/-- The successors of a base, in index order, are strictly increasing. -/
theorem sortedLT_map_chain_succ (b : Key) (n : ℕ) :
((List.range n).map (fun i => chain b (i + 1))).SortedLT := by
rw [List.sortedLT_iff_pairwise, List.pairwise_iff_getElem]
intro i j hi hj hij
simp only [List.getElem_map, List.getElem_range]
exact chain_lt_mono (by omega)
/-- A one-key list is strictly increasing. -/
theorem sortedLT_singleton (k : Key) : [k].SortedLT := by
rw [List.sortedLT_cons]
exact ⟨by simp, List.sortedLT_nil⟩
/-- A key followed by its own successors is strictly increasing. -/
theorem sortedLT_cons_map_chain_succ (b : Key) (n : ℕ) :
(b :: (List.range n).map (fun i => chain b (i + 1))).SortedLT := by
rw [List.sortedLT_cons]
refine ⟨?_, sortedLT_map_chain_succ b n⟩
intro x hx
rw [List.mem_map] at hx
obtain ⟨i, -, rfl⟩ := hx
have h : chain b 0 < chain b (i + 1) := chain_lt_mono (Nat.succ_pos i)
simpa [chain_zero] using h
/-- The successors of `k₀` followed by a key strictly above them all is strictly
increasing. -/
theorem sortedLT_map_chain_append {k₀ k : Key} {m : ℕ} (h : ∀ i < m, chain k₀ i < k) :
((List.range m).map (chain k₀) ++ [k]).SortedLT := by
rw [List.sortedLT_append]
refine ⟨sortedLT_map_chain k₀ m, sortedLT_singleton k, ?_⟩
intro a ha b hb
rw [List.mem_map] at ha
obtain ⟨i, hi, rfl⟩ := ha
rw [List.mem_singleton] at hb
subst hb
exact h i (List.mem_range.mp hi)
/-- The successors of `k₀` followed by a key at or above `k₀` has nothing
counted strictly below `k₀`. -/
theorem countP_lt_map_chain_append {k₀ k : Key} {m : ℕ} (h : k₀ ≤ k) :
((List.range m).map (chain k₀) ++ [k]).countP (fun x => decide (x < k₀)) = 0 :=
countP_lt_eq_zero_of_forall_ge (fun x hx => by
rw [List.mem_append, List.mem_singleton] at hx
rcases hx with hx | rfl
· rw [List.mem_map] at hx
obtain ⟨i, -, rfl⟩ := hx
exact chain_le k₀ i
· exact h)
/-- A key below `k₀` followed by successors that all stay below `k₀` has all of
its keys counted strictly below `k₀`. -/
theorem countP_lt_cons_map_chain_succ {k k₀ : Key} {n : ℕ}
(hk : k < k₀) (h : ∀ i < n, chain k (i + 1) < k₀) :
(k :: (List.range n).map (fun i => chain k (i + 1))).countP
(fun x => decide (x < k₀)) =
(k :: (List.range n).map (fun i => chain k (i + 1))).length :=
countP_lt_eq_length_of_forall_lt (fun x hx => by
rw [List.mem_cons, List.mem_map] at hx
rcases hx with rfl | ⟨i, hi, rfl⟩
· exact hk
· exact h i (List.mem_range.mp hi))
/-- Delete every stored key in `[a, b)` and insert the successor chain
`chain a 0, …, chain a (n-1)` in its place, preserving sortedness. This is the
interval analogue of `insert`: it replaces a whole interval of keys by a chosen
run of successors rather than toggling a single key. The keys below `a` and at or
above `b` are kept verbatim, and `hn` certifies that the inserted chain stays
strictly inside `[a, b)`. -/
def DB.insertInterval (db : DB) (a b : Key) (hab : a ≤ b) (n : ℕ)
(hn : ∀ i < n, chain a i < b) : DB where
keys := (db.keys.filter (fun x => decide (x < a)) ++
(List.range n).map (chain a)) ++
db.keys.filter (fun x => decide (b ≤ x))
sorted := by
have hP_sorted : (db.keys.filter (fun x => decide (x < a))).SortedLT :=
List.sortedLT_iff_pairwise.mpr (db.sorted.pairwise.filter _)
have hrest_sorted : ((List.range n).map (chain a)).SortedLT := sortedLT_map_chain a n
have hQ_sorted : (db.keys.filter (fun x => decide (b ≤ x))).SortedLT :=
List.sortedLT_iff_pairwise.mpr (db.sorted.pairwise.filter _)
have hcross : ∀ x ∈ db.keys.filter (fun x => decide (x < a)),
∀ y ∈ (List.range n).map (chain a), x < y := by
intro x hx y hy
have hxa : x < a := of_decide_eq_true (List.mem_filter.mp hx).2
rw [List.mem_map] at hy
obtain ⟨i, -, rfl⟩ := hy
exact lt_of_lt_of_le hxa (chain_le a i)
have hPrest_sorted : ((db.keys.filter (fun x => decide (x < a)) ++
(List.range n).map (chain a))).SortedLT :=
List.sortedLT_append.mpr ⟨hP_sorted, hrest_sorted, hcross⟩
have hcross2 : ∀ x ∈ db.keys.filter (fun x => decide (x < a)) ++
(List.range n).map (chain a),
∀ y ∈ db.keys.filter (fun x => decide (b ≤ x)), x < y := by
intro x hx y hy
have hyb : b ≤ y := of_decide_eq_true (List.mem_filter.mp hy).2
rw [List.mem_append] at hx
rcases hx with hx | hx
· exact lt_of_lt_of_le
(lt_of_lt_of_le (of_decide_eq_true (List.mem_filter.mp hx).2) hab) hyb
· rw [List.mem_map] at hx
obtain ⟨i, hi, rfl⟩ := hx
exact lt_of_lt_of_le (hn i (List.mem_range.mp hi)) hyb
exact List.sortedLT_append.mpr ⟨hPrest_sorted, hQ_sorted, hcross2⟩
/-- The keys of an interval-inserted database: the keys below `a`, the inserted
successor chain, then the keys at or above `b`. -/
@[simp] theorem DB.insertInterval_keys (db : DB) (a b : Key) (hab : a ≤ b) (n : ℕ)
(hn : ∀ i < n, chain a i < b) :
(db.insertInterval a b hab n hn).keys =
(db.keys.filter (fun x => decide (x < a)) ++ (List.range n).map (chain a)) ++
db.keys.filter (fun x => decide (b ≤ x)) := rfl
/-- Inserting the successor chain of `[a, b)` leaves the count of keys strictly
below `a` unchanged: those keys are exactly the stored keys below `a`, and each
precedes the whole chain. This is the interval analogue of `countP_insertIdx`
below `a`. -/
theorem countP_lt_insertInterval_of_lt {db : DB} {a b x : Key} (hab : a ≤ b) (hxa : x ≤ a)
(n : ℕ) (hn : ∀ i < n, chain a i < b) :
(db.insertInterval a b hab n hn).keys.countP (fun k => decide (k < x)) =
db.keys.countP (fun k => decide (k < x)) := by
rw [DB.insertInterval_keys, List.countP_append, List.countP_append]
have hP : (db.keys.filter (fun k => decide (k < a))).countP (fun k => decide (k < x)) =
db.keys.countP (fun k => decide (k < x)) := by
rw [List.countP_eq_length_filter, List.filter_filter, List.countP_eq_length_filter]
congr 1
apply List.filter_congr
intro k _
by_cases hkx : k < x
· have hka : k < a := lt_of_lt_of_le hkx hxa
simp [hkx, hka]
· simp [hkx]
have hrest : ((List.range n).map (chain a)).countP (fun k => decide (k < x)) = 0 :=
countP_lt_eq_zero_of_forall_ge fun k hk => by
rw [List.mem_map] at hk
obtain ⟨i, -, rfl⟩ := hk
exact le_trans hxa (chain_le a i)
have hQ : (db.keys.filter (fun k => decide (b ≤ k))).countP (fun k => decide (k < x)) = 0 :=
countP_lt_eq_zero_of_forall_ge fun k hk =>
le_trans (le_trans hxa hab) (of_decide_eq_true (List.mem_filter.mp hk).2)
rw [hP, hrest, hQ]
omega
/-- Inserting the successor chain of `[a, b)` makes the count of keys strictly
below `b` exactly the stored keys below `a` plus the `n` chain elements: the
erased `[a, b)` keys and the chain are replaced one-for-the-other, and the stored
keys at or above `b` are not counted. This is the interval analogue of
`countP_insertIdx` at the new key. -/
theorem countP_lt_insertInterval_self {db : DB} {a b : Key} (hab : a ≤ b) {n : ℕ}
(hn : ∀ i < n, chain a i < b) :
(db.insertInterval a b hab n hn).keys.countP (fun k => decide (k < b)) =
(db.keys.filter (fun k => decide (k < a))).length + n := by
rw [DB.insertInterval_keys, List.countP_append, List.countP_append]
have hP : (db.keys.filter (fun k => decide (k < a))).countP (fun k => decide (k < b)) =
(db.keys.filter (fun k => decide (k < a))).length :=
countP_lt_eq_length_of_forall_lt fun k hk =>
lt_of_lt_of_le (of_decide_eq_true (List.mem_filter.mp hk).2) hab
have hrest : ((List.range n).map (chain a)).countP (fun k => decide (k < b)) = n := by
rw [countP_lt_eq_length_of_forall_lt (fun k hk => ?_), List.length_map, List.length_range]
rw [List.mem_map] at hk
obtain ⟨i, hi, rfl⟩ := hk
exact hn i (List.mem_range.mp hi)
have hQ : (db.keys.filter (fun k => decide (b ≤ k))).countP (fun k => decide (k < b)) = 0 :=
countP_lt_eq_zero_of_forall_ge fun k hk =>
of_decide_eq_true (List.mem_filter.mp hk).2
rw [hP, hrest, hQ]
omega
/-- Erasing the interval `[a, b)` leaves the count of keys strictly below `a`
unchanged: erased keys all lie at or above `a`, so none is counted. -/
theorem countP_lt_eraseInterval_of_le {db : DB} {a b : Key} {x : Key} (hxa : x ≤ a) :
(db.eraseInterval (↑a) (↑b)).keys.countP (fun k => decide (k < x)) =
db.keys.countP (fun k => decide (k < x)) := by
rw [DB.eraseInterval_keys, List.countP_eq_length_filter, List.countP_eq_length_filter,
List.filter_filter]
congr 1
apply List.filter_congr
intro k _
by_cases hkx : k < x
· have hq : decide (¬ (a ≤ (k : WithTop Key) ∧ (k : WithTop Key) < b)) = true := by
rw [decide_eq_true_eq]
rintro ⟨hak, -⟩
exact absurd (lt_of_lt_of_le hkx hxa) (not_lt.mpr (WithTop.coe_le_coe.mp hak))
rw [hq]
simp [hkx]
· simp [hkx]
/-- Erasing `[a, b)` with `a ≤ b` leaves the count of keys strictly below `b`
at exactly the stored keys below `a`: every erased key lies in `[a, b)`, and the
stored keys at or above `b` are not counted. This is the erase counterpart of
`countP_lt_insertInterval_self`. -/
theorem countP_lt_eraseInterval_self {db : DB} {a b : Key} (hab : a ≤ b) :
(db.eraseInterval (↑a) (↑b)).keys.countP (fun k => decide (k < b)) =
(db.keys.filter (fun k => decide (k < a))).length := by
simp only [DB.eraseInterval_keys, List.countP_eq_length_filter, List.filter_filter]
congr 1
apply List.filter_congr
intro k _
by_cases hka : k < a
· have hkb : k < b := lt_of_lt_of_le hka hab
have hna : ¬ ((a : WithTop Key) ≤ (k : WithTop Key)) :=
fun h => not_le.mpr hka (WithTop.coe_le_coe.mp h)
simp [hka, hkb, hna]
· have hak : (a : WithTop Key) ≤ (k : WithTop Key) := by
rw [WithTop.coe_le_coe]; exact le_of_not_gt hka
by_cases hkb : k < b
· have hkb' : (k : WithTop Key) < (b : WithTop Key) := WithTop.coe_lt_coe.mpr hkb
simp [hka, hkb, hak, hkb']
· simp [hka, hkb]
/-- Inserting the chain of `[a, b)` and then counting below `b` leaves exactly
the stored keys below `a` plus the chain length: the inserted `n` elements are
the only keys of the rebuilt database in `[a, b)`. This is the count form of the
selector-anchor shift under an interval replacement. -/
theorem countP_lt_insertInterval_shift {db : DB} {a b : Key} (hab : a ≤ b) {n : ℕ}
(hn : ∀ i < n, chain a i < b) :
(db.insertInterval a b hab n hn).keys.countP (fun k => decide (k < b)) =
(db.eraseInterval (↑a) (↑b)).keys.countP (fun k => decide (k < b)) + n := by
rw [countP_lt_insertInterval_self hab hn, countP_lt_eraseInterval_self hab]
/-- The `i`-th key of an interval-inserted database, for `i < n`, is exactly the
chain element `chain a i`: it sits at index `i` past the stored keys below `a`.
This pinpoints the inserted chain, the multi-key analogue of a single-key
insertion placing the new key at its rank. -/
theorem getElem?_insertInterval_chain {db : DB} {a b : Key} (hab : a ≤ b) {n i : ℕ}
(hn : ∀ j < n, chain a j < b) (hi : i < n) :
(db.insertInterval a b hab n hn).keys[
(db.keys.filter (fun k => decide (k < a))).length + i]? = some (chain a i) := by
rw [DB.insertInterval_keys]
have hlen : ((db.keys.filter (fun k => decide (k < a))) ++
(List.range n).map (chain a)).length =
(db.keys.filter (fun k => decide (k < a))).length + n := by
rw [List.length_append, List.length_map, List.length_range]
rw [List.getElem?_append_left (by rw [hlen]; omega),
List.getElem?_append_right (by omega), Nat.add_sub_cancel_left,
List.getElem?_map, List.getElem?_range hi]
rfl
/-- Single-key erasure is interval erasure over `[k, keyAfter k)`: the only key
the interval can contain is `k` itself. This makes `DB.erase` a special case of
`DB.eraseInterval`. -/
theorem DB.erase_eq_eraseInterval (db : DB) (k : Key) :
db.erase k = db.eraseInterval (↑k) (↑(keyAfter k)) := by
unfold DB.erase DB.eraseInterval
congr 1
apply List.SortedLT.eq_of_mem_iff
· exact List.sortedLT_iff_pairwise.mpr (db.sorted.pairwise.erase k)
· exact List.sortedLT_iff_pairwise.mpr (db.sorted.pairwise.filter _)
· intro x
rw [List.Nodup.mem_erase_iff db.nodup]
simp only [List.mem_filter, decide_eq_true_eq, WithTop.coe_le_coe, WithTop.coe_lt_coe]
constructor
· rintro ⟨hne, hx⟩
exact ⟨hx, fun hcon => hne (le_antisymm ((lt_keyAfter_iff x k).mp hcon.2) hcon.1)⟩
· rintro ⟨hx, hcon⟩
refine ⟨?_, hx⟩
intro heq
rw [heq] at hcon
exact hcon ⟨le_refl k, keyAfter_self_lt k⟩
/-- Single-key insertion is the interval insertion of the one-element chain at
`[k, keyAfter k)`: it erases nothing but `k` (which is unstored) and inserts `k`.
This makes `DB.insert` a special case of `DB.insertInterval`. -/
theorem DB.insert_eq_insertInterval (db : DB) (k : Key) (hk : k ∉ db.keys) :
db.insert k hk =
db.insertInterval k (keyAfter k) (le_of_lt (keyAfter_self_lt k)) 1
(by intro i _; interval_cases i; simp only [chain, List.replicate_zero, List.append_nil];
exact keyAfter_self_lt k) := by
have hkeyAfter_le : ∀ c z : Key, keyAfter c ≤ z ↔ c < z := by
intro c z
constructor
· intro h; exact lt_of_lt_of_le (keyAfter_self_lt c) h
· intro h
by_contra hcon
exact absurd ((lt_keyAfter_iff z c).mp (not_le.mp hcon)) (not_le.mpr h)
have hordered : db.keys.orderedInsert (· ≤ ·) k =
(db.keys.filter (fun x => decide (x < k)) ++ [k]) ++
db.keys.filter (fun x => decide (keyAfter k ≤ x)) := by
apply List.SortedLT.eq_of_mem_iff
· exact List.sortedLT_iff_pairwise.mpr <|
DB.pairwise_lt_of_le_of_nodup
((db.sorted.pairwise.imp fun h => le_of_lt h).orderedInsert k)
((List.perm_orderedInsert (· ≤ ·) k db.keys).nodup_iff.mpr
(List.nodup_cons.mpr ⟨hk, db.nodup⟩))
· refine List.sortedLT_append.mpr ⟨?_, List.sortedLT_iff_pairwise.mpr
(db.sorted.pairwise.filter _), ?_⟩
· refine List.sortedLT_append.mpr ⟨List.sortedLT_iff_pairwise.mpr
(db.sorted.pairwise.filter _), sortedLT_singleton k, ?_⟩
intro a ha b hb
rw [List.mem_filter] at ha
rw [List.mem_singleton] at hb
rw [hb]
exact (of_decide_eq_true ha.2)
· intro a ha b hb
rw [List.mem_append] at ha
rw [List.mem_filter] at hb
rcases ha with ha | ha
· rw [List.mem_filter] at ha
exact lt_of_lt_of_le (of_decide_eq_true ha.2)
(le_of_lt ((hkeyAfter_le k b).mp (of_decide_eq_true hb.2)))
· rw [List.mem_singleton] at ha
rw [ha]
exact (hkeyAfter_le k b).mp (of_decide_eq_true hb.2)
· intro x
rw [List.mem_orderedInsert (· ≤ ·)]
constructor
· rintro (rfl | hx)
· exact List.mem_append.mpr
(Or.inl (List.mem_append.mpr (Or.inr (List.mem_singleton_self x))))
· rcases lt_trichotomy x k with hlt | heq | hgt
· exact List.mem_append.mpr (Or.inl (List.mem_append.mpr (Or.inl
(List.mem_filter.mpr ⟨hx, by rw [decide_eq_true_eq]; exact hlt⟩))))
· exact absurd (heq ▸ hx) hk
· exact List.mem_append.mpr (Or.inr (List.mem_filter.mpr
⟨hx, by rw [decide_eq_true_eq]; exact (hkeyAfter_le k x).mpr hgt⟩))
· intro hxx
rw [List.mem_append, List.mem_append, List.mem_singleton] at hxx
rcases hxx with (hx | rfl) | hx
· exact Or.inr (List.mem_filter.mp hx).1
· exact Or.inl rfl
· exact Or.inr (List.mem_filter.mp hx).1
unfold DB.insert DB.insertInterval
congr 1
rw [hordered]
simp [chain]
/-!
## How many keys fit below a key
`intervalCard ⊥ k` bounds the number of stored keys a database can place strictly
below a genuine key `k`, and every number up to it is attainable. The bound is
`intervalCard_eq_encard_keysIn` at the lower end: the stored keys below `k` are a
subset of `keysIn ⊥ k`, whose extended cardinality is `intervalCard ⊥ k`. For the
converse, the successor chain `⊥, [0], [0,0], …` enumerates `[⊥, k)` — it lies
below `k` exactly up to index `intervalCard ⊥ k` (`chain_nil_lt_iff`) — so storing
its first `c` elements realizes any `c` below the bound. This is the same-database
tool for reasoning about selector counts: a selector's key alone does not bound how
many keys can lie below it, and `intervalCard ⊥ k` pins that count exactly.
-/
/-- The chain from `b` is strictly increasing in its index, so a larger index means
a larger key. -/
theorem chain_lt_iff_lt (b : Key) (i n : ℕ) : chain b i < chain b n ↔ i < n := by
constructor
· intro h
by_contra hcon
exact absurd h (not_lt.mpr (chain_le_chain (b := b) (by omega)))
· exact chain_lt_mono
/-- Every chain element from `b` is strictly below `e` whenever `intervalCard b e`
is infinite. -/
theorem chain_lt_of_intervalCard_eq_top {b e : Key}
(h : intervalCard (↑b : WithTop Key) (↑e : WithTop Key) = ⊤) (i : ℕ) :
chain b i < e := by
have hbe : b < e := by
by_contra hle
have h0 : intervalCard (↑b : WithTop Key) (↑e : WithTop Key) = 0 :=
intervalCard_eq_zero_of_le (WithTop.coe_le_coe.mpr (le_of_not_gt hle))
rw [h0] at h; exact absurd h (by simp)
have hne : ∀ m, e ≠ chain b m := by
intro m hm
have : intervalCard (↑b : WithTop Key) (↑(chain b m)) = (m : ℕ∞) := by
rw [chain]; exact intervalCard_succChain b m
rw [hm, this] at h
exact absurd h (by simp)
exact chain_lt_of_not_chain hbe hne i
/-- The chain from `b` lies below `e` exactly up to `intervalCard b e`: the
interval `[b, e)` is enumerated by the successor chain. This is the counting bound
at the heart of the same-database analysis, `chain_nil_lt_iff` being the case
`b = ⊥`. -/
theorem chain_lt_iff (b e : Key) (i : ℕ) :
chain b i < e ↔
(i : ℕ∞) < intervalCard (↑b : WithTop Key) (↑e : WithTop Key) := by
by_cases htop : intervalCard (↑b : WithTop Key) (↑e : WithTop Key) = ⊤
· rw [htop]
exact ⟨fun _ => WithTop.coe_lt_top i, fun _ => chain_lt_of_intervalCard_eq_top htop i⟩
· obtain ⟨n, hn⟩ := ENat.ne_top_iff_exists.mp htop
have hcoeeq : intervalCard (↑b : WithTop Key) (↑e : WithTop Key) = (n : ℕ∞) := hn.symm
rw [hcoeeq, ENat.natCast_lt_natCast]
have hiff := (intervalCard_eq_coe_iff (b := b) (e := e) (n := n)).mp hcoeeq
rcases hiff with ⟨rfl, hle⟩ | hk
· refine iff_of_false (fun hc => ?_) (by simp)
exact absurd (lt_of_lt_of_le hc hle) (not_lt.mpr (chain_le b i))
· rw [hk]; exact chain_lt_iff_lt b i n
/-- The successor chain from the empty key is the run of `n` zero bytes. -/
theorem chain_nil_eq_replicate (n : ℕ) :
chain ([] : Key) n = List.replicate n (0 : Byte) := by
simp [chain]
/-- The chain from the empty key lies below `k` exactly up to `intervalCard ⊥ k`:
the interval `[⊥, k)` is enumerated by the successor chain. -/
theorem chain_nil_lt_iff (k : Key) (i : ℕ) :
chain ([] : Key) i < k ↔
(i : ℕ∞) < intervalCard (↑([] : Key) : WithTop Key) (↑k : WithTop Key) := by
simpa only [List.nil_append] using chain_lt_iff ([] : Key) k i
/-- `countP (· < k) = c` says the filtered list has `c` elements. -/
theorem countP_lt_iff_length_filter (l : List Key) (k : Key) (c : ℕ) :
l.countP (fun x => decide (x < k)) = c ↔
(l.filter (fun x => decide (x < k))).length = c := by
rw [List.countP_eq_length_filter]
/-- The possible counts of stored keys strictly below a genuine key `k` are exactly
the natural numbers up to `intervalCard ⊥ k`: a database can store any number of
the keys in `[⊥, k)`, and no database can store more than that interval holds.
`intervalCard ⊥ k` therefore characterizes the possible values of
`countP (· < k)` over all databases. -/
theorem exists_countP_lt_eq_iff (k : Key) (c : ℕ) :
(∃ db : DB, db.keys.countP (fun x => decide (x < k)) = c) ↔
(c : ℕ∞) ≤ intervalCard (↑([] : Key) : WithTop Key) (↑k : WithTop Key) := by
constructor
· rintro ⟨db, hdb⟩
have hlen : (db.keys.filter (fun x => decide (x < k))).length = c :=
(countP_lt_iff_length_filter db.keys k c).mp hdb
have hnodup : (db.keys.filter (fun x => decide (x < k))).Nodup := db.nodup.filter _
have hset : ((db.keys.filter (fun x => decide (x < k))).toFinset : Set Key) ⊆
keysIn (↑([] : Key) : WithTop Key) (↑k : WithTop Key) := by
intro x hx
simp only [Finset.mem_coe, List.mem_toFinset, List.mem_filter] at hx
exact ⟨WithTop.coe_le_coe.mpr (nil_le_key x), WithTop.coe_lt_coe.mpr (by simpa using hx.2)⟩
have h1 := Set.encard_le_encard hset
rw [Set.encard_coe_eq_coe_finsetCard, List.toFinset_card_of_nodup hnodup, hlen] at h1
rw [intervalCard_eq_encard_keysIn]
exact h1
· intro hc
refine ⟨⟨(List.range c).map (chain ([] : Key)), sortedLT_map_chain _ _⟩, ?_⟩
rw [countP_lt_eq_length_of_forall_lt (fun x hx => ?_), List.length_map, List.length_range]
rw [List.mem_map] at hx
obtain ⟨i, hi, rfl⟩ := hx
rw [chain_nil_lt_iff]
exact lt_of_lt_of_le (by exact_mod_cast List.mem_range.mp hi) hc
/-- For a list, the set of keys below `ke` splits at `kb ≤ ke` into the keys below
`kb` and those in `[kb, ke)`. -/
theorem filter_lt_toFinset_union (l : List Key) {kb ke : Key} (h : kb ≤ ke) :
(l.filter (fun x => decide (x < ke))).toFinset =
(l.filter (fun x => decide (x < kb))).toFinset ∪
(l.filter (fun x => decide (kb ≤ x ∧ x < ke))).toFinset := by
ext x
simp only [List.mem_toFinset, List.mem_filter, decide_eq_true_eq, Finset.mem_union]
constructor
· rintro ⟨hx, hxe⟩
by_cases hxb : x < kb
· exact Or.inl ⟨hx, hxb⟩
· exact Or.inr ⟨hx, le_of_not_gt hxb, hxe⟩
· rintro (⟨hx, hxb⟩ | ⟨hx, hxb, hxe⟩)
· exact ⟨hx, lt_of_lt_of_le hxb h⟩
· exact ⟨hx, hxe⟩
/-- The two pieces of the preceding split are disjoint. -/
theorem disjoint_filters (l : List Key) (kb ke : Key) :
Disjoint (l.filter (fun x => decide (x < kb))).toFinset
(l.filter (fun x => decide (kb ≤ x ∧ x < ke))).toFinset := by
rw [Finset.disjoint_left]
intro x hx1 hx2
simp only [List.mem_toFinset, List.mem_filter, decide_eq_true_eq] at hx1 hx2
exact absurd hx1.2 (not_lt.mpr hx2.2.1)
/-- Counting keys below `ke` splits at `kb ≤ ke` into those below `kb` and those in
`[kb, ke)`: the counts of a database in the two adjacent intervals add. -/
theorem countP_lt_eq_add_filter (l : List Key) (hnd : l.Nodup) {kb ke : Key} (h : kb ≤ ke) :
l.countP (fun x => decide (x < ke)) =
l.countP (fun x => decide (x < kb)) +
(l.filter (fun x => decide (kb ≤ x ∧ x < ke))).length := by
simp only [List.countP_eq_length_filter]
rw [← List.toFinset_card_of_nodup (hnd.filter _),
← List.toFinset_card_of_nodup (hnd.filter _),
← List.toFinset_card_of_nodup (hnd.filter _),
filter_lt_toFinset_union l h,
Finset.card_union_of_disjoint (disjoint_filters l kb ke)]
/-- For a key, membership in the coerced interval `[kb, ke)` is exactly
`kb ≤ x ∧ x < ke`. -/
theorem mem_keysIn_coe {kb ke x : Key} :
x ∈ keysIn (↑kb : WithTop Key) (↑ke : WithTop Key) ↔ kb ≤ x ∧ x < ke := by
simp [keysIn]
/-- A database's keys in `[kb, ke)` form a subset of `keysIn kb ke`. -/
theorem filter_toFinset_subset_keysIn (db : DB) (kb ke : Key) :
((db.keys.filter (fun x => decide (kb ≤ x ∧ x < ke))).toFinset : Set Key) ⊆
keysIn (↑kb : WithTop Key) (↑ke : WithTop Key) := by
intro x hx
simp only [Finset.mem_coe, List.mem_toFinset, List.mem_filter, decide_eq_true_eq] at hx
exact mem_keysIn_coe.mpr hx.2
/-- The concatenation of the chain from `⊥` below `kb` with the chain from `kb` is
strictly increasing, provided the first chain stays below `kb`. -/
theorem sortedLT_append_map_chain {c d : ℕ} {kb : Key}
(h1 : ∀ i < c, chain ([] : Key) i < kb) :
((List.range c).map (chain ([] : Key)) ++ (List.range d).map (chain kb)).SortedLT := by
rw [List.sortedLT_append]
refine ⟨sortedLT_map_chain _ _, sortedLT_map_chain _ _, ?_⟩
intro a ha b hb
rw [List.mem_map] at ha hb
obtain ⟨i, hi, rfl⟩ := ha
obtain ⟨j, -, rfl⟩ := hb
exact lt_of_lt_of_le (h1 i (List.mem_range.mp hi)) (chain_le kb j)
/-- The same-database joint count lemma: for genuine `kb ≤ ke`, a database can
realize `c` stored keys below `kb` and `c + d` below `ke` exactly when `c` fits in
`[⊥, kb)` and `d` fits in `[kb, ke)`. The gap `d` is bounded by
`intervalCard kb ke`, so the two counts are coupled in one database — the fact the
separate footprints of `kb` and `ke` cannot see. -/
theorem exists_countP_lt_pair_iff (kb ke : Key) (hkbke : kb ≤ ke) (c d : ℕ) :
(∃ db : DB, db.keys.countP (fun x => decide (x < kb)) = c ∧
db.keys.countP (fun x => decide (x < ke)) = c + d) ↔
(c : ℕ∞) ≤ intervalCard (↑([] : Key) : WithTop Key) (↑kb : WithTop Key) ∧
(d : ℕ∞) ≤ intervalCard (↑kb : WithTop Key) (↑ke : WithTop Key) := by
constructor
· rintro ⟨db, hc, hcd⟩
refine ⟨(exists_countP_lt_eq_iff kb c).mp ⟨db, hc⟩, ?_⟩
have hsplit := countP_lt_eq_add_filter db.keys db.nodup hkbke
have hd : (db.keys.filter (fun x => decide (kb ≤ x ∧ x < ke))).length = d := by
rw [hc] at hsplit; omega
have hnodup : (db.keys.filter (fun x => decide (kb ≤ x ∧ x < ke))).Nodup :=
db.nodup.filter _
have h1 := Set.encard_le_encard (filter_toFinset_subset_keysIn db kb ke)
rw [Set.encard_coe_eq_coe_finsetCard, List.toFinset_card_of_nodup hnodup, hd] at h1
rw [intervalCard_eq_encard_keysIn]
exact h1
· rintro ⟨hc, hd⟩
have hchainc : ∀ i < c, chain ([] : Key) i < kb := fun i hi =>
(chain_nil_lt_iff kb i).mpr (lt_of_lt_of_le (by exact_mod_cast hi) hc)
have hkind : ∀ i < d, chain kb i < ke := fun i hi =>
(chain_lt_iff kb ke i).mpr (lt_of_lt_of_le (by exact_mod_cast hi) hd)
let db : DB := ⟨(List.range c).map (chain ([] : Key)) ++ (List.range d).map (chain kb),
sortedLT_append_map_chain hchainc⟩
refine ⟨db, ?_, ?_⟩
· rw [List.countP_append]
have h1 : ((List.range c).map (chain ([] : Key))).countP
(fun x => decide (x < kb)) = c := by
rw [countP_lt_eq_length_of_forall_lt (fun x hx => ?_), List.length_map, List.length_range]
rw [List.mem_map] at hx
obtain ⟨i, hi, rfl⟩ := hx
exact hchainc i (List.mem_range.mp hi)
have h2 : ((List.range d).map (chain kb)).countP
(fun x => decide (x < kb)) = 0 := by
rw [countP_lt_eq_zero_of_forall_ge]
intro x hx
rw [List.mem_map] at hx
obtain ⟨i, _, rfl⟩ := hx
exact chain_le kb i
rw [h1, h2, Nat.add_zero]
· rw [List.countP_append]
have h1 : ((List.range c).map (chain ([] : Key))).countP
(fun x => decide (x < ke)) = c := by
rw [countP_lt_eq_length_of_forall_lt (fun x hx => ?_), List.length_map, List.length_range]
rw [List.mem_map] at hx
obtain ⟨i, hi, rfl⟩ := hx
exact lt_of_lt_of_le (hchainc i (List.mem_range.mp hi)) hkbke
have h2 : ((List.range d).map (chain kb)).countP
(fun x => decide (x < ke)) = d := by
rw [countP_lt_eq_length_of_forall_lt (fun x hx => ?_), List.length_map, List.length_range]
rw [List.mem_map] at hx
obtain ⟨i, hi, rfl⟩ := hx
exact hkind i (List.mem_range.mp hi)
rw [h1, h2]
/-- Interval perturbation: a database can be rebuilt to agree with a given one
both below `a` and at or above `b` — keeping exactly its stored keys outside
`[a, b)` — while realizing any gap `d` up to `intervalCard a b` in the count of
stored keys below `b`. Only the keys in `[a, b)` are changed, and the realization
is a successor chain from `a`, so the keys below `a` and the keys at or above `b`
are untouched. This is the batch companion of the single-key `erase`/`insert`
perturbations: varying a whole interval by `d` rather than one key, which is what
an agreement on a range disjoint from `[a, b)` permits. The witness is
`DB.insertInterval a b d`, the interval analogue of `DB.insert`.
When `[a, b)` is infinite (`intervalCard a b = ⊤`), `d` is unbounded, so the count
of stored keys below `b` can be shifted arbitrarily far while agreement on
`[⊥, a)` and on `[b, ⊤)` is preserved. -/
theorem exists_db_perturb_interval {db : DB} {a b : Key} (hab : a ≤ b) (d : ℕ)
(hd : (d : ℕ∞) ≤ intervalCard (↑a : WithTop Key) (↑b : WithTop Key)) :
∃ db' : DB,
db'.keys.filter (fun x => decide (x < a)) = db.keys.filter (fun x => decide (x < a)) ∧
db'.keys.filter (fun x => decide (b ≤ x)) = db.keys.filter (fun x => decide (b ≤ x)) ∧
db'.keys.countP (fun x => decide (x < b)) =
(db.keys.filter (fun x => decide (x < a))).length + d := by
have hchain : ∀ i < d, chain a i < b := fun i hi =>
(chain_lt_iff a b i).mpr (lt_of_lt_of_le (by exact_mod_cast hi) hd)
let P : List Key := db.keys.filter (fun x => decide (x < a))
let rest : List Key := (List.range d).map (chain a)
let Q : List Key := db.keys.filter (fun x => decide (b ≤ x))
have hkey : (db.insertInterval a b hab d hchain).keys = (P ++ rest) ++ Q := rfl
refine ⟨db.insertInterval a b hab d hchain, ?_, ?_, ?_⟩
· rw [hkey, List.filter_append, List.filter_append]
have hP' : P.filter (fun x => decide (x < a)) = P :=
List.filter_eq_self.mpr fun x hx => (List.mem_filter.mp hx).2
have hrest' : rest.filter (fun x => decide (x < a)) = [] :=
List.filter_eq_nil_iff.mpr fun x hx hcon => by
rw [List.mem_map] at hx
obtain ⟨i, -, rfl⟩ := hx
rw [decide_eq_true_eq] at hcon
exact absurd hcon (not_lt.mpr (chain_le a i))
have hQ' : Q.filter (fun x => decide (x < a)) = [] :=
List.filter_eq_nil_iff.mpr fun x hx hcon => by
rw [decide_eq_true_eq] at hcon
exact absurd hcon (not_lt.mpr (le_trans hab (of_decide_eq_true (List.mem_filter.mp hx).2)))
rw [hP', hrest', hQ', List.append_nil, List.append_nil]
· rw [hkey, List.filter_append, List.filter_append]
have hQ' : Q.filter (fun x => decide (b ≤ x)) = Q :=
List.filter_eq_self.mpr fun x hx => (List.mem_filter.mp hx).2
have hP' : P.filter (fun x => decide (b ≤ x)) = [] :=
List.filter_eq_nil_iff.mpr fun x hx hcon => by
rw [decide_eq_true_eq] at hcon
exact absurd (le_trans hab hcon)
(not_le.mpr (of_decide_eq_true (List.mem_filter.mp hx).2))
have hrest' : rest.filter (fun x => decide (b ≤ x)) = [] :=
List.filter_eq_nil_iff.mpr fun x hx hcon => by
rw [List.mem_map] at hx
obtain ⟨i, hi, rfl⟩ := hx
rw [decide_eq_true_eq] at hcon
exact absurd hcon (not_le.mpr (hchain i (List.mem_range.mp hi)))
rw [hP', hrest', hQ', List.nil_append, List.nil_append]
· rw [hkey, List.countP_append, List.countP_append]
have hPcount : P.countP (fun x => decide (x < b)) = P.length :=
countP_lt_eq_length_of_forall_lt fun x hx =>
lt_of_lt_of_le (of_decide_eq_true (List.mem_filter.mp hx).2) hab
have hrestcount : rest.countP (fun x => decide (x < b)) = d := by
rw [countP_lt_eq_length_of_forall_lt (fun x hx => ?_), List.length_map,
List.length_range]
rw [List.mem_map] at hx
obtain ⟨i, hi, rfl⟩ := hx
exact hchain i (List.mem_range.mp hi)
have hQcount : Q.countP (fun x => decide (x < b)) = 0 :=
countP_lt_eq_zero_of_forall_ge fun x hx =>
of_decide_eq_true (List.mem_filter.mp hx).2
rw [hPcount, hrestcount, hQcount, Nat.add_zero]
/-- Interval-emptying perturbation: a database can be rebuilt to agree with a
given one both below `a` and at or above `b` while storing nothing in `[a, b)`.
The keys outside `[a, b)` are kept verbatim, so this removes exactly the stored
keys in `[a, b)`; it is the `d = 0` companion of `exists_db_perturb_interval`,
whose rebuilt database agrees on the same two ranges but may fill `[a, b)` with a
successor chain. The witness is `DB.eraseInterval a b`, the interval analogue of
`DB.erase`, so no ordering hypothesis on `a` and `b` is needed. -/
theorem exists_db_empty_interval {db : DB} {a b : Key} :
∃ db' : DB,
db'.keys.filter (fun x => decide (x < a)) = db.keys.filter (fun x => decide (x < a)) ∧
db'.keys.filter (fun x => decide (b ≤ x)) = db.keys.filter (fun x => decide (b ≤ x)) ∧
db'.keys.filter (fun x => decide (a ≤ x ∧ x < b)) = [] := by
refine ⟨db.eraseInterval (↑a) (↑b), ?_, ?_, ?_⟩
· rw [DB.eraseInterval_keys, List.filter_filter]
apply List.filter_congr
intro x _
by_cases h : x < a <;> simp [h]
· rw [DB.eraseInterval_keys, List.filter_filter]
apply List.filter_congr
intro x _
by_cases h : b ≤ x <;> simp [h]
· rw [DB.eraseInterval_keys, List.filter_filter]
rw [List.filter_eq_nil_iff]
intro x _ hcon
simp only [Bool.and_eq_true, decide_eq_true_eq] at hcon
exact hcon.2 ⟨WithTop.coe_le_coe.mpr hcon.1.1, WithTop.coe_lt_coe.mpr hcon.1.2⟩
end FormalConflictRange