blob: 05428ba66a40bd9283df61ad20c7aae85a137644 [file]
/-
Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Markus Himmel, Paul Reichert
-/
module
prelude
public import Std.Data.DTreeMap.Internal.WF.Defs
public import Std.Data.DTreeMap.Internal.Cell
import Init.Data.Nat.Linear
import Init.Omega
@[expose] public section
/-!
# Model implementations of tree map functions
-/
set_option autoImplicit false
set_option linter.all true
universe u v w
variable {α : Type u} {β : α → Type v} {γ : α → Type w} {δ : Type w}
namespace Std.DTreeMap.Internal
open Std.Internal (IsStrictCut)
namespace Impl
/-!
## General infrastructure
-/
/-- Internal implementation detail of the tree map -/
def contains' [Ord α] (k : α → Ordering) (l : Impl α β) : Bool :=
match l with
| .leaf => false
| .inner _ k' _ l r =>
match k k' with
| .lt => contains' k l
| .gt => contains' k r
| .eq => true
theorem contains'_compare [Ord α] {k : α} {l : Impl α β} :
l.contains' (compare k) = l.contains k := by
induction l <;> simp_all only [contains', contains] <;> rfl
/-- General tree-traversal function. Internal implementation detail of the tree map -/
def applyPartition [Ord α] (k : α → Ordering) (l : Impl α β)
(f : List ((a : α) × β a) → (c : Cell α β k) → (l.contains' k → c.contains) → List ((a : α) × β a) → δ) : δ :=
go [] l id []
where
go (ll : List ((a : α) × β a)) (m : Impl α β) (hm : l.contains' k → m.contains' k) (rr : List ((a : α) × β a)) : δ :=
match m with
| .leaf => f ll .empty (by simp_all [contains']) rr
| .inner _ k' v' l r =>
match h : k k' with
| .lt =>
go ll l (fun hc => have := hm hc; by rw [← this, contains']; simp_all)
(⟨k', v'⟩ :: r.toListModel ++ rr)
| .eq => f (ll ++ l.toListModel) (.ofEq k' v' h) (by simp) (r.toListModel ++ rr)
| .gt =>
go (ll ++ l.toListModel ++ [⟨k', v'⟩]) r
(fun hc => have := hm hc; by rw [← this, contains']; simp_all) rr
/-- Internal implementation detail of the tree map -/
def applyCell [Ord α] (k : α) (l : Impl α β)
(f : (c : Cell α β (compare k)) → (l.contains' (compare k) → c.contains) → δ) : δ :=
match l with
| .leaf => f .empty (by simp [contains'])
| .inner _ k' v' l r =>
match hcmp : compare k k' with
| .lt => applyCell k l (fun c h => f c fun h' => h (by simpa [contains', hcmp] using h'))
| .eq => f (.ofEq k' v' hcmp) (by simp)
| .gt => applyCell k r (fun c h => f c fun h' => h (by simpa [contains', hcmp] using h'))
/-- Internal implementation detail of the tree map -/
theorem applyCell_eq_applyPartition [Ord α] (k : α) (l : Impl α β)
(f : (c : Cell α β (compare k)) → (l.contains' (compare k) → c.contains) → δ) :
applyCell k l f = applyPartition (compare k) l (fun _ c hc _ => f c hc) := by
rw [applyPartition]
suffices ∀ L u v, (hL : l.contains' (compare k) ↔ L.contains' (compare k)) →
applyCell k l f = applyPartition.go (compare k) L (fun _ c hc _ => f c (hc ∘ hL.1)) u l hL.2 v from
this l [] [] Iff.rfl
intro L u v hL
induction l generalizing u v L
· rename_i sz k' v' l r ih₁ ih₂
simp only [applyCell, applyPartition.go]
split <;> rename_i hcmp
· exact ih₁ _ _ _ _ (by simpa [contains', hcmp] using hL)
· rfl
· exact ih₂ _ _ _ _ (by simpa [contains', hcmp] using hL)
· simp [applyCell, applyPartition.go]
variable (α β) in
/--
Data structure used by the general tree-traversal function `explore`.
Internal implementation detail of the tree map
-/
inductive ExplorationStep [Ord α] (k : α → Ordering) where
/-- Needle was less than key at this node: return key-value pair and unexplored right subtree,
recursion will continue in left subtree. -/
| lt : (a : α) → k a = .lt → β a → List ((a : α) × β a) → ExplorationStep k
/-- Needle was equal to key at this node: return key-value pair and both unexplored subtrees,
recursion will terminate. -/
| eq : List ((a : α) × β a) → Cell α β k → List ((a : α) × β a) → ExplorationStep k
/-- Needle was larger than key at this node: return key-value pair and unexplored left subtree,
recursion will continue in right subtree. -/
| gt : List ((a : α) × β a) → (a : α) → k a = .gt → β a → ExplorationStep k
/-- General tree-traversal function. Internal implementation detail of the tree map -/
def explore {γ : Type w} [Ord α] (k : α → Ordering) (init : γ)
(inner : γ → ExplorationStep α β k → γ) (l : Impl α β) : γ :=
match l with
| .leaf => inner init (.eq [] .empty [])
| .inner _ ky y l r =>
match h : k ky with
| .lt => explore k (inner init <| .lt ky h y r.toListModel) inner l
| .eq => inner init <| .eq l.toListModel (Cell.ofEq ky y h) r.toListModel
| .gt => explore k (inner init <| .gt l.toListModel ky h y) inner r
/-
Note: these congruence lemmas are proven manually because `simp` currently can't handle
matches with hypotheses on discriminants properly.
-/
@[congr]
theorem applyPartition.go.match_1.congr {α : Sort u} {o o' : Ordering}
{lt : o = .lt → α} {eq : o = .eq → α} {gt : o = .gt → α}
{lt' : o' = .lt → α} {eq' : o' = .eq → α} {gt' : o' = .gt → α}
(ho : o = o')
(hlt : ∀ h, lt (ho.trans h) = lt' h)
(heq : ∀ h, eq (ho.trans h) = eq' h)
(hgt : ∀ h, gt (ho.trans h) = gt' h) :
(match (generalizing := false) h : o with | .lt => lt h | .eq => eq h | .gt => gt h) =
(match (generalizing := false) h : o' with | .lt => lt' h | .eq => eq' h | .gt => gt' h) := by
induction ho; induction funext hlt; induction funext heq; induction funext hgt
rfl
@[congr]
theorem entryAtIdx.match_1.congr {α : Sort u} {o o' : Ordering}
{lt : o = .lt → α} {eq : o = .eq → α} {gt : o = .gt → α}
{lt' : o' = .lt → α} {eq' : o' = .eq → α} {gt' : o' = .gt → α}
(ho : o = o')
(hlt : ∀ h, lt (ho.trans h) = lt' h)
(heq : ∀ h, eq (ho.trans h) = eq' h)
(hgt : ∀ h, gt (ho.trans h) = gt' h) :
entryAtIdx.match_1 (fun _ => α) o lt eq gt = entryAtIdx.match_1 (fun _ => α) o' lt' eq' gt' := by
induction ho; induction funext hlt; induction funext heq; induction funext hgt
rfl
@[congr]
theorem getEntryLE.match_1.congr {α : Sort u} {o o' : Ordering}
{lt : o = .lt → α} {eq : o = .eq → α} {gt : o = .gt → α}
{lt' : o' = .lt → α} {eq' : o' = .eq → α} {gt' : o' = .gt → α}
(ho : o = o')
(hlt : ∀ h, lt (ho.trans h) = lt' h)
(heq : ∀ h, eq (ho.trans h) = eq' h)
(hgt : ∀ h, gt (ho.trans h) = gt' h) :
getEntryLE.match_1 (fun _ => α) o gt eq lt = getEntryLE.match_1 (fun _ => α) o' gt' eq' lt' := by
induction ho; induction funext hlt; induction funext heq; induction funext hgt
rfl
@[congr]
theorem get?.match_1.congr {α : Sort u} {o o' : Ordering}
{lt : o = .lt → α} {eq : o = .eq → α} {gt : o = .gt → α}
{lt' : o' = .lt → α} {eq' : o' = .eq → α} {gt' : o' = .gt → α}
(ho : o = o')
(hlt : ∀ h, lt (ho.trans h) = lt' h)
(heq : ∀ h, eq (ho.trans h) = eq' h)
(hgt : ∀ h, gt (ho.trans h) = gt' h) :
get?.match_1 (fun _ => α) o lt gt eq = get?.match_1 (fun _ => α) o' lt' gt' eq' := by
induction ho; induction funext hlt; induction funext heq; induction funext hgt
rfl
/--
Induction principle on `Impl` with an additional case split on `k ky` for
`Impl.inner _ ky _ _ _` without generalization.
-/
@[elab_as_elim]
theorem tree_split_ind_no_gen [Ord α] (k : α → Ordering)
{motive : (l : Impl α β) → Prop}
(leaf : motive .leaf)
(lt : ∀ n ky y l r, (h : k ky = .lt) →
motive l → motive (.inner n ky y l r))
(eq : ∀ n ky y l r, (h : k ky = .eq) →
motive l → motive r → motive (.inner n ky y l r))
(gt : ∀ n ky y l r, (h : k ky = .gt) →
motive r → motive (.inner n ky y l r))
(t : Impl α β) : motive t := by
induction t with
| leaf => exact leaf
| inner n ky v l r ih ih' =>
cases h : k ky
· exact lt n ky v l r h ih
· exact eq n ky v l r h ih ih'
· exact gt n ky v l r h ih'
/--
Induction principle on `Impl` with an additional case split on `k ky` for
`Impl.inner _ ky _ _ _` and a generalization built in for convenience.
-/
@[elab_as_elim]
theorem tree_split_ind {γ : Sort w} [Ord α] (k : α → Ordering)
{motive : (l : Impl α β) → γ → Prop}
(leaf : ∀ x, motive .leaf x)
(lt : ∀ n ky y l r, (h : k ky = .lt) →
(∀ x, motive l x) → ∀ x, motive (.inner n ky y l r) x)
(eq : ∀ n ky y l r, (h : k ky = .eq) →
(∀ x, motive l x) → (∀ x, motive r x) → ∀ x, motive (.inner n ky y l r) x)
(gt : ∀ n ky y l r, (h : k ky = .gt) →
(∀ x, motive r x) → ∀ x, motive (.inner n ky y l r) x)
(t : Impl α β) : (x : γ) → motive t x :=
tree_split_ind_no_gen k leaf lt eq gt t
open ExplorationStep
theorem applyPartition_go_step [Ord α] {k : α → Ordering} {init : δ} (l₁ l₂) (l l' : Impl α β) (h)
(f : δ → ExplorationStep α β k → δ) :
applyPartition.go k l' (fun l' c _ r' => f init (.eq l' c r')) l₁ l h l₂ =
applyPartition.go k l' (fun l' c _ r' => f init (.eq (l₁ ++ l') c (r' ++ l₂))) [] l h [] := by
suffices ∀ l₃ l₄,
applyPartition.go k l' (fun l' c _ r' => f init (.eq (l₃ ++ l') c (r' ++ l₄))) l₁ l h l₂ =
applyPartition.go k l' (fun l' c _ r' => f init (.eq (l₃ ++ l₁ ++ l') c (r' ++ l₂ ++ l₄))) [] l h [] by
simpa using this [] []
intro l₃ l₄
induction l generalizing l₁ l₂ l₃ l₄
· rename_i sz k' v' l r ih₁ ih₂
simp only [applyPartition.go]
split
· simp only [List.cons_append, List.append_assoc, List.append_nil]
simp only [ih₁, ← List.append_assoc l₃]
simp
· simp
· simp only [List.append_assoc, List.nil_append]
simp only [ih₂, ← List.append_assoc l₃]
simp
· simp [applyPartition.go]
theorem explore_eq_applyPartition [Ord α] {k : α → Ordering} (init : δ) (l : Impl α β)
(f : δ → ExplorationStep α β k → δ)
(hfr : ∀ {k hk v ll c rr r init}, f (f init (.lt k hk v r)) (.eq ll c rr) = f init (.eq ll c (rr ++ ⟨k, v⟩ :: r)))
(hfl : ∀ {k hk v ll c rr l init}, f (f init (.gt l k hk v)) (.eq ll c rr) = f init (.eq (l ++ ⟨k, v⟩ :: ll) c rr)) :
explore k init f l = applyPartition k l fun l c _ r => f init (.eq l c r) := by
rw [applyPartition]
suffices ∀ L, (h : L.contains' k → l.contains' k) →
explore k init f l = applyPartition.go k L (fun l_1 c x r => f init (eq l_1 c r)) [] l h [] from this l id
intro L hL
induction l generalizing init
· rename_i sz k' v' l r ih₁ ih₂
rw [explore, applyPartition.go]
split <;> rename_i hcmp
· simp only [hcmp, contains'] at hL
rw [ih₁ _ hL]
conv => rhs; rw [applyPartition_go_step]
simp only [List.nil_append, List.append_nil]
congr
ext ll c hc rr
apply hfr
· simp
· simp only [hcmp, contains'] at hL
rw [ih₂ _ hL]
conv => rhs; rw [applyPartition_go_step]
simp only [List.nil_append, List.append_assoc, List.singleton_append, List.append_nil]
congr
ext ll c hc rr
apply hfl
· simp [explore, applyPartition.go]
/--
General "update the mapping for a given key" function.
Internal implementation detail of the tree map
-/
noncomputable def updateCell [Ord α] (k : α) (f : Cell α β (compare k) → Cell α β (compare k))
(l : Impl α β) (hl : Balanced l) : SizedBalancedTree α β (l.size - 1) (l.size + 1) :=
match l with
| leaf => match (f .empty).inner with
| none => ⟨.leaf, ✓, ✓, ✓⟩
| some ⟨k', v'⟩ => ⟨.inner 1 k' v' .leaf .leaf, ✓, ✓, ✓⟩
| inner sz ky y l r =>
match h : compare k ky with
| .lt =>
let ⟨newL, h₁, h₂, h₃⟩ := updateCell k f l ✓
⟨balance ky y newL r ✓ ✓ ✓, ✓, ✓, ✓⟩
| .eq => match (f (.ofEq ky y h)).inner with
| none =>
⟨glue l r ✓ ✓ ✓, ✓, ✓, ✓⟩
| some ⟨ky', y'⟩ => ⟨.inner sz ky' y' l r, ✓, ✓, ✓⟩
| .gt =>
let ⟨newR, h₁, h₂, h₃⟩ := updateCell k f r ✓
⟨balance ky y l newR ✓ ✓ ✓, ✓, ✓, ✓⟩
/-!
## Model functions
-/
/--
Model implementation of the `contains` function.
Internal implementation detail of the tree map
-/
def containsₘ [Ord α] (l : Impl α β) (k : α) : Bool :=
applyCell k l fun c _ => c.contains
/--
Model implementation of the `get?` function.
Internal implementation detail of the tree map
-/
def get?ₘ [Ord α] [OrientedOrd α] [LawfulEqOrd α] (l : Impl α β) (k : α) : Option (β k) :=
applyCell k l fun c _ => c.get?
/--
Model implementation of the `get` function.
Internal implementation detail of the tree map
-/
def getₘ [Ord α] [OrientedOrd α] [LawfulEqOrd α] (l : Impl α β) (k : α) (h : (get?ₘ l k).isSome) :
β k :=
get?ₘ l k |>.get h
/--
Model implementation of the `get!` function.
Internal implementation detail of the tree map
-/
def get!ₘ [Ord α] [OrientedOrd α] [LawfulEqOrd α] (l : Impl α β) (k : α) [Inhabited (β k)] : β k :=
get?ₘ l k |>.get!
/--
Model implementation of the `getD` function.
Internal implementation detail of the tree map
-/
def getDₘ [Ord α] [OrientedOrd α] [LawfulEqOrd α] (k : α) (l : Impl α β) (fallback : β k) : β k :=
get?ₘ l k |>.getD fallback
/--
Model implementation of the `getEntry?` function.
Internal implementation detail of the tree map
-/
def getEntry?ₘ [Ord α] (l : Impl α β) (k : α) : Option ((a : α) × β a) :=
applyCell k l fun c _ => c.getEntry?
/--
Model implementation of the `getEntry` function.
Internal implementation detail of the tree map
-/
def getEntryₘ [Ord α] (l : Impl α β) (k : α) (h : (getEntry?ₘ l k).isSome) :
(a : α) × β a :=
getEntry?ₘ l k |>.get h
/--
Model implementation of the `getEntry!` function.
Internal implementation detail of the tree map
-/
def getEntry!ₘ [Ord α] [Inhabited ((a : α) × β a)] (l : Impl α β) (k : α) : (a : α) × β a :=
getEntry?ₘ l k |>.get!
/--
Model implementation of the `getEntryD` function.
Internal implementation detail of the tree map
-/
def getEntryDₘ [Ord α] (k : α) (l : Impl α β) (fallback : (a : α) × β a) : (a : α) × β a :=
getEntry?ₘ l k |>.getD fallback
/--
Model implementation of the `getKey?` function.
Internal implementation detail of the tree map
-/
def getKey?ₘ [Ord α] (l : Impl α β) (k : α) : Option α :=
applyCell k l fun c _ => c.getKey?
/--
Model implementation of the `getKey` function.
Internal implementation detail of the tree map
-/
def getKeyₘ [Ord α] (l : Impl α β) (k : α) (h : (getKey?ₘ l k).isSome) : α :=
getKey?ₘ l k |>.get h
/--
Model implementation of the `getKey!` function.
Internal implementation detail of the tree map
-/
def getKey!ₘ [Ord α] (l : Impl α β) (k : α) [Inhabited α] : α :=
getKey?ₘ l k |>.get!
/--
Model implementation of the `getKeyD` function.
Internal implementation detail of the tree map
-/
def getKeyDₘ [Ord α] (k : α) (l : Impl α β) (fallback : α) : α :=
getKey?ₘ l k |>.getD fallback
/-- Internal implementation detail of the tree map -/
def minEntry?ₘ' [Ord α] (l : Impl α β) : Option ((a : α) × β a) :=
explore (fun (_ : α) => .lt) none (fun sofar step =>
match step with
| .lt ky _ y _ => some ⟨ky, y⟩
| .eq _ _ r => r.head?.or sofar) l
/-- Internal implementation detail of the tree map -/
def minEntry?ₘ [Ord α] (l : Impl α β) : Option ((a : α) × β a) :=
applyPartition (fun (_ : α) => .lt) l fun _ _ _ r => r.head?
/-- Internal implementation detail of the tree map -/
def reverse : Impl α β → Impl α β
| .leaf => .leaf
| .inner sz k v l r => .inner sz k v (reverse r) (reverse l)
/--
Model implementation of the `insert` function.
Internal implementation detail of the tree map
-/
noncomputable def insertₘ [Ord α] (k : α) (v : β k) (l : Impl α β) (h : l.Balanced) : Impl α β :=
updateCell k (fun _ => .of k v) l h |>.impl
/--
Model implementation of the `erase` function.
Internal implementation detail of the tree map
-/
noncomputable def eraseₘ [Ord α] (k : α) (t : Impl α β) (h : t.Balanced) : Impl α β :=
updateCell k (fun _ => .empty) t h |>.impl
/--
Model implementation of the `insertIfNew` function.
Internal implementation detail of the tree map
-/
noncomputable def insertIfNewₘ [Ord α] (k : α) (v : β k) (l : Impl α β) (h : l.Balanced) : Impl α β :=
updateCell k (fun
| ⟨.none, _⟩ => .of k v
| c => c) l h |>.impl
/--
Model implementation of the `alter` function.
Internal implementation detail of the tree map
-/
noncomputable def alterₘ [Ord α] [OrientedOrd α] [LawfulEqOrd α] (k : α) (f : Option (β k) → Option (β k))
(t : Impl α β) (h : t.Balanced) : Impl α β :=
updateCell k (·.alter f) t h |>.impl
namespace Const
variable {β : Type v}
/--
Model implementation of the `get?` function.
Internal implementation detail of the tree map
-/
def get?ₘ [Ord α] (l : Impl α (fun _ => β)) (k : α) : Option β :=
applyCell k l fun c _ => Cell.Const.get? c
/--
Model implementation of the `get` function.
Internal implementation detail of the tree map
-/
def getₘ [Ord α] (l : Impl α (fun _ => β)) (k : α) (h : (get?ₘ l k).isSome) :
β :=
get?ₘ l k |>.get h
/--
Model implementation of the `get!` function.
Internal implementation detail of the tree map
-/
def get!ₘ [Ord α] (l : Impl α (fun _ => β)) (k : α) [Inhabited β] : β :=
get?ₘ l k |>.get!
/--
Model implementation of the `getD` function.
Internal implementation detail of the tree map
-/
def getDₘ [Ord α] (l : Impl α (fun _ => β)) (k : α) (fallback : β) : β :=
get?ₘ l k |>.getD fallback
/--
Model implementation of the `alter` function.
Internal implementation detail of the tree map
-/
noncomputable def alterₘ [Ord α] [OrientedOrd α] (k : α) (f : Option β → Option β)
(t : Impl α (fun _ => β)) (h : t.Balanced) : Impl α (fun _ => β) :=
updateCell k (Cell.Const.alter f) t h |>.impl
end Const
/-!
## Helper theorems for reasoning with key-value pairs
-/
theorem balanceL!_pair_congr {k : α} {v : β k} {k' : α} {v' : β k'}
(h : (⟨k, v⟩ : (a : α) × β a) = ⟨k', v'⟩) {l l' r r' : Impl α β}
(hl : l = l') (hr : r = r') :
balanceL! k v l r = balanceL! k' v' l' r' := by
cases h; cases hl; cases hr; rfl
theorem balanceR!_pair_congr {k : α} {v : β k} {k' : α} {v' : β k'}
(h : (⟨k, v⟩ : (a : α) × β a) = ⟨k', v'⟩) {l l' r r' : Impl α β}
(hl : l = l') (hr : r = r') :
balanceR! k v l r = balanceR! k' v' l' r' := by
cases h; cases hl; cases hr; rfl
/-!
## Equivalence of function to model functions
-/
theorem contains_eq_containsₘ [Ord α] (k : α) (l : Impl α β) :
l.contains k = l.containsₘ k := by
simp only [containsₘ]
induction l
· simp only [contains, applyCell]
split <;> simp_all
· simp [contains, applyCell]
theorem get?_eq_get?ₘ [Ord α] [OrientedOrd α] [LawfulEqOrd α] (k : α) (l : Impl α β) :
l.get? k = l.get?ₘ k := by
simp only [get?ₘ]
induction l
· simp only [applyCell, get?]
split <;> simp_all [Cell.get?, Cell.ofEq]
· simp [get?, applyCell]
theorem get_eq_get? [Ord α] [OrientedOrd α] [LawfulEqOrd α] (k : α) (l : Impl α β) {h} :
some (l.get k h) = l.get? k := by
induction l
· simp only [get, get?]
split <;> simp_all
· contradiction
theorem get_eq_getₘ [Ord α] [OrientedOrd α] [LawfulEqOrd α] (k : α) (l : Impl α β) {h} (h') :
l.get k h = l.getₘ k h' := by
apply Option.some.inj
simp [get_eq_get?, get?_eq_get?ₘ, getₘ]
theorem get!_eq_get!ₘ [Ord α] [OrientedOrd α] [LawfulEqOrd α] (k : α) [Inhabited (β k)] (l : Impl α β) :
l.get! k = l.get!ₘ k := by
simp only [get!ₘ, get?ₘ]
induction l
· simp only [applyCell, get!]
split <;> simp_all [Cell.get?, Cell.ofEq]
· simp only [get!, applyCell, Cell.get?_empty, Option.get!_none]; rfl
theorem getD_eq_getDₘ [Ord α] [OrientedOrd α] [LawfulEqOrd α] (k : α) (l : Impl α β)
(fallback : β k) : l.getD k fallback = l.getDₘ k fallback := by
simp only [getDₘ, get?ₘ]
induction l
· simp only [applyCell, getD]
split <;> simp_all [Cell.get?, Cell.ofEq]
· simp only [getD, applyCell, Cell.get?_empty, Option.getD_none]
theorem getKey?_eq_getKey?ₘ [Ord α] (k : α) (l : Impl α β) :
l.getKey? k = l.getKey?ₘ k := by
simp only [getKey?ₘ]
induction l
· simp only [applyCell, getKey?]
split <;> simp_all [Cell.getKey?, Cell.ofEq]
· simp [getKey?, applyCell]
theorem getEntry?_eq_getEntry?ₘ [Ord α] (k : α) (l : Impl α β) :
l.getEntry? k = l.getEntry?ₘ k := by
simp only [getEntry?ₘ]
induction l
· simp only [applyCell, getEntry?]
split <;> simp_all [Cell.getEntry?, Cell.ofEq]
· simp only [getEntry?, applyCell]; rfl
theorem getEntry_eq_getEntry? [Ord α] (k : α) (l : Impl α β) {h} :
some (l.getEntry k h) = l.getEntry? k := by
induction l
· simp only [getEntry, getEntry?]
split <;> simp_all
· contradiction
theorem getEntry_eq_getEntryₘ [Ord α] (k : α) (l : Impl α β) {h} (h') :
l.getEntry k h = l.getEntryₘ k h' := by
apply Option.some.inj
simp [getEntry_eq_getEntry?, getEntry?_eq_getEntry?ₘ, getEntryₘ]
theorem getEntry!_eq_getEntry!ₘ [Ord α] [Inhabited ((a : α) × (β a))] (k : α) (l : Impl α β) :
l.getEntry! k = l.getEntry!ₘ k := by
simp only [getEntry!ₘ, getEntry?ₘ]
induction l
· simp only [applyCell, getEntry!]
split <;> simp_all [Cell.getEntry?, Cell.ofEq]
· simp only [getEntry!, applyCell]; rfl
theorem getEntryD_eq_getEntryDₘ [Ord α] (k : α) (l : Impl α β)
(fallback : (a : α) × β a) : l.getEntryD k fallback = l.getEntryDₘ k fallback := by
simp only [getEntryDₘ, getEntry?ₘ]
induction l
· simp only [applyCell, getEntryD]
split <;> simp_all [Cell.getEntry?, Cell.ofEq]
· simp only [getEntryD, applyCell]; rfl
theorem getKey_eq_getKey? [Ord α] (k : α) (l : Impl α β) {h} :
some (l.getKey k h) = l.getKey? k := by
induction l
· simp only [getKey, getKey?]
split <;> simp_all
· contradiction
theorem getKey_eq_getKeyₘ [Ord α] (k : α) (l : Impl α β) {h} (h') :
l.getKey k h = l.getKeyₘ k h' := by
apply Option.some.inj
simp [getKey_eq_getKey?, getKey?_eq_getKey?ₘ, getKeyₘ]
theorem getKey!_eq_getKey!ₘ [Ord α] (k : α) [Inhabited α] (l : Impl α β) :
l.getKey! k = l.getKey!ₘ k := by
simp only [getKey!ₘ, getKey?ₘ]
induction l
· simp only [applyCell, getKey!]
split <;> simp_all [Cell.getKey?, Cell.ofEq]
· simp only [getKey!, applyCell, Cell.getKey?_empty, Option.get!_none]; rfl
theorem getKeyD_eq_getKeyDₘ [Ord α] (k : α) (l : Impl α β)
(fallback : α) : l.getKeyD k fallback = l.getKeyDₘ k fallback := by
simp only [getKeyDₘ, getKey?ₘ]
induction l
· simp only [applyCell, getKeyD]
split <;> simp_all [Cell.getKey?, Cell.ofEq]
· simp only [getKeyD, applyCell, Cell.getKey?_empty, Option.getD_none]
theorem minEntry?_eq_minEntry?ₘ' [Ord α] {l : Impl α β} : l.minEntry? = l.minEntry?ₘ' := by
rw [minEntry?ₘ']
induction l using minEntry?.induct <;> simp_all [minEntry?, explore]
theorem minEntry?ₘ'_eq_minEntry?ₘ [Ord α] {l : Impl α β} : l.minEntry?ₘ' = l.minEntry?ₘ := by
rw [minEntry?ₘ', explore_eq_applyPartition, minEntry?ₘ] <;> simp
theorem minEntry?_eq_minEntry?ₘ [Ord α] {l : Impl α β} : l.minEntry? = l.minEntry?ₘ := by
rw [minEntry?_eq_minEntry?ₘ', minEntry?ₘ'_eq_minEntry?ₘ]
theorem minEntry!_eq_get!_minEntry? [Inhabited ((a : α) × β a)] {l : Impl α β} :
l.minEntry! = l.minEntry?.get! := by
induction l using minEntry?.induct_unfolding <;> simp only [minEntry!] <;> trivial
theorem minEntryD_eq_getD_minEntry? {l : Impl α β} {fallback : (a : α) × β a} :
l.minEntryD fallback = l.minEntry?.getD fallback := by
induction l using minEntry?.induct_unfolding <;> simp only [minEntryD] <;> trivial
theorem some_minEntry_eq_minEntry? {l : Impl α β} {he} :
some (l.minEntry he) = l.minEntry? := by
induction l, he using minEntry.induct_unfolding <;> simp only [minEntry?] <;> assumption
theorem minEntry_eq_get_minEntry? {l : Impl α β} {he} :
l.minEntry he = l.minEntry?.get (by simp [← some_minEntry_eq_minEntry? (he := he)]) := by
simp [← some_minEntry_eq_minEntry? (he := he)]
theorem maxEntry?_eq_minEntry?_reverse {l : Impl α β} : l.maxEntry? = l.reverse.minEntry? := by
induction l using maxEntry?.induct_unfolding <;> simp only [minEntry?, reverse] <;> assumption
theorem maxEntry!_eq_get!_maxEntry? [Inhabited ((a : α) × β a)] {l : Impl α β} :
l.maxEntry! = l.maxEntry?.get! := by
induction l using maxEntry?.induct_unfolding <;> simp only [maxEntry!] <;> trivial
theorem maxEntryD_eq_getD_maxEntry? {l : Impl α β} {fallback : (a : α) × β a} :
l.maxEntryD fallback = l.maxEntry?.getD fallback := by
induction l using maxEntry?.induct_unfolding <;> simp only [maxEntryD] <;> trivial
theorem some_maxEntry_eq_maxEntry? {l : Impl α β} {he} : some (l.maxEntry he) = l.maxEntry? := by
induction l, he using maxEntry.induct_unfolding <;> simp only [maxEntry?] <;> assumption
theorem minKey?_eq_minEntry?_map_fst {l : Impl α β} : l.minKey? = l.minEntry?.map Sigma.fst := by
induction l using minKey?.induct_unfolding <;> simp only [minEntry?] <;> trivial
theorem minKey_eq_minEntry_fst {l : Impl α β} {he} : l.minKey he = (l.minEntry he).fst := by
induction l, he using minKey.induct_unfolding <;> simp only [minEntry] <;> trivial
theorem minKey!_eq_get!_minKey? [Inhabited α] {l : Impl α β} :
l.minKey! = l.minKey?.get! := by
induction l using minKey!.induct_unfolding <;> simp only [minKey?] <;> trivial
theorem minKeyD_eq_getD_minKey? {l : Impl α β} {fallback} :
l.minKeyD fallback = l.minKey?.getD fallback := by
induction l, fallback using minKeyD.induct_unfolding <;> simp only [minKey?] <;> trivial
theorem maxKey?_eq_minKey?_reverse {l : Impl α β} : l.maxKey? = l.reverse.minKey? := by
induction l using maxKey?.induct_unfolding <;> simp only [minKey?, reverse] <;> assumption
theorem some_maxKey_eq_maxKey? {l : Impl α β} {he} : some (l.maxKey he) = l.maxKey? := by
induction l, he using maxKey.induct_unfolding <;> simp only [maxKey?] <;> assumption
theorem maxKey_eq_get_maxKey? {l : Impl α β} {he} :
l.maxKey he = l.maxKey?.get (by simp [← some_maxKey_eq_maxKey? (he := he)]) := by
simp [← some_maxKey_eq_maxKey? (he := he)]
theorem maxKey!_eq_get!_maxKey? [Inhabited α] {l : Impl α β} :
l.maxKey! = l.maxKey?.get! := by
induction l using maxKey!.induct_unfolding <;> simp only [maxKey?] <;> trivial
theorem maxKeyD_eq_getD_maxKey? {l : Impl α β} {fallback} :
l.maxKeyD fallback = l.maxKey?.getD fallback := by
induction l using maxKey?.induct_unfolding <;> simp only [maxKeyD] <;> trivial
namespace Const
variable {β : Type v}
theorem minEntry?_eq_minEntry? [Ord α] {l : Impl α fun _ => β} :
minEntry? l = l.minEntry?.map (fun x => (x.1, x.2)) := by
induction l using minEntry?.induct_unfolding <;> simp only [Impl.minEntry?] <;> trivial
theorem minEntry!_eq_get!_minEntry? [Ord α] {l : Impl α fun _ => β} [Inhabited (α × β)] :
minEntry! l = (minEntry? l).get! := by
induction l using minEntry?.induct_unfolding <;> simp only [minEntry!] <;> trivial
theorem minEntryD_eq_getD_minEntry? [Ord α] {l : Impl α fun _ => β} {fallback : α × β} :
minEntryD l fallback = (minEntry? l).getD fallback := by
induction l using minEntry?.induct_unfolding <;> simp only [minEntryD] <;> trivial
theorem some_minEntry_eq_minEntry? [Ord α] {l : Impl α fun _ => β} {he} :
some (minEntry l he) = minEntry? l := by
induction l, he using minEntry.induct_unfolding <;> simp only [minEntry?] <;> trivial
theorem maxEntry?_eq_maxEntry? [Ord α] {l : Impl α fun _ => β} :
maxEntry? l = l.maxEntry?.map (fun x => (x.1, x.2)) := by
induction l using maxEntry?.induct_unfolding <;> simp only [Impl.maxEntry?] <;> trivial
theorem maxEntry!_eq_get!_maxEntry? [Ord α] {l : Impl α fun _ => β} [Inhabited (α × β)] :
maxEntry! l = (maxEntry? l).get! := by
induction l using maxEntry?.induct_unfolding <;> simp only [maxEntry!] <;> trivial
theorem maxEntryD_eq_getD_maxEntry? [Ord α] {l : Impl α fun _ => β} {fallback : α × β} :
maxEntryD l fallback = (maxEntry? l).getD fallback := by
induction l using maxEntry?.induct_unfolding <;> simp only [maxEntryD] <;> trivial
theorem some_maxEntry_eq_maxEntry? [Ord α] {l : Impl α fun _ => β} {he} :
some (maxEntry l he) = maxEntry? l := by
induction l, he using maxEntry.induct_unfolding <;> simp only [maxEntry?] <;> trivial
end Const
theorem balanceL_eq_balance {k : α} {v : β k} {l r : Impl α β} {hlb hrb hlr} :
balanceL k v l r hlb hrb hlr = balance k v l r hlb hrb (Or.inl hlr.erase) := by
rw [balanceL_eq_balanceLErase, balanceLErase_eq_balanceL!,
balanceL!_eq_balance! hlb hrb hlr.erase, balance_eq_balance!]
theorem balanceR_eq_balance {k : α} {v : β k} {l r : Impl α β} {hlb hrb hlr} :
balanceR k v l r hlb hrb hlr = balance k v l r hlb hrb (Or.inr hlr.erase) := by
rw [balanceR_eq_balanceRErase, balanceRErase_eq_balanceR!,
balanceR!_eq_balance! hlb hrb hlr.erase, balance_eq_balance!]
theorem balanceLErase_eq_balance {k : α} {v : β k} {l r : Impl α β} {hlb hrb hlr} :
balanceLErase k v l r hlb hrb hlr = balance k v l r hlb hrb (Or.inl hlr) := by
rw [balanceLErase_eq_balanceL!,
balanceL!_eq_balance! hlb hrb hlr, balance_eq_balance!]
theorem balanceRErase_eq_balance {k : α} {v : β k} {l r : Impl α β} {hlb hrb hlr} :
balanceRErase k v l r hlb hrb hlr = balance k v l r hlb hrb (Or.inr hlr) := by
rw [balanceRErase_eq_balanceR!,
balanceR!_eq_balance! hlb hrb hlr, balance_eq_balance!]
theorem balanceL_eq_balanceL! {k : α} {v : β k} {l r : Impl α β} {hlb hrb hlr} :
balanceL k v l r hlb hrb hlr = balanceL! k v l r := by
rw [balanceL_eq_balanceLErase, balanceLErase_eq_balanceL!]
theorem balanceR_eq_balanceR! {k : α} {v : β k} {l r : Impl α β} {hlb hrb hlr} :
balanceR k v l r hlb hrb hlr = balanceR! k v l r := by
rw [balanceR_eq_balanceRErase, balanceRErase_eq_balanceR!]
theorem minView_k_eq_minView! {k : α} {v : β k} {l r : Impl α β} {hl hr hlr} :
(minView k v l r hl hr hlr).k = (minView! k v l r).k := by
induction k, v, l, r, hl, hr, hlr using minView.induct <;> simp_all [minView, minView!]
theorem minView_kv_eq_minView! {k : α} {v : β k} {l r : Impl α β} {hl hr hlr} :
(⟨(minView k v l r hl hr hlr).k, (minView k v l r hl hr hlr).v⟩ : (a : α) × β a) =
⟨(minView! k v l r).k, (minView! k v l r).v⟩ := by
induction k, v, l, r, hl, hr, hlr using minView.induct <;>
simp_all [minView, minView!]
theorem minView_tree_impl_eq_minView! {k : α} {v : β k} {l r : Impl α β} {hl hr hlr} :
(minView k v l r hl hr hlr).tree.impl = (minView! k v l r).tree := by
induction k, v, l, r, hl, hr, hlr using minView.induct <;>
simp_all [minView, minView!, balanceRErase_eq_balanceR!]
theorem maxView_k_eq_maxView! {k : α} {v : β k} {l r : Impl α β} {hl hr hlr} :
(maxView k v l r hl hr hlr).k = (maxView! k v l r).k := by
induction k, v, l, r, hl, hr, hlr using maxView.induct <;> simp_all [maxView, maxView!]
theorem maxView_kv_eq_maxView! {k : α} {v : β k} {l r : Impl α β} {hl hr hlr} :
(⟨(maxView k v l r hl hr hlr).k, (maxView k v l r hl hr hlr).v⟩ : (a : α) × β a) =
⟨(maxView! k v l r).k, (maxView! k v l r).v⟩ := by
induction k, v, l, r, hl, hr, hlr using maxView.induct <;>
simp_all [maxView, maxView!]
theorem maxView_tree_impl_eq_maxView! {k : α} {v : β k} {l r : Impl α β} {hl hr hlr} :
(maxView k v l r hl hr hlr).tree.impl = (maxView! k v l r).tree := by
induction k, v, l, r, hl, hr, hlr using maxView.induct <;>
simp_all [maxView, maxView!, balanceLErase_eq_balanceL!]
theorem glue_eq_glue! {l r : Impl α β} {hl hr hlr} :
glue l r hl hr hlr = glue! l r := by
rw [glue.eq_def, glue!.eq_def]
split
· simp
split
· simp
split
· simpa [*, balanceLErase_eq_balanceL!] using balanceL!_pair_congr
minView_kv_eq_minView! rfl minView_tree_impl_eq_minView!
· simpa [*, balanceRErase_eq_balanceR!] using balanceR!_pair_congr
maxView_kv_eq_maxView! maxView_tree_impl_eq_maxView! rfl
theorem insert_eq_insert! [Ord α] {k : α} {v : β k} {l : Impl α β} {h} :
(insert k v l h).impl = insert! k v l := by
induction l, h using insert.induct k v <;>
simp_all [insert, insert!, balanceL_eq_balanceL!, balanceR_eq_balanceR!]
theorem insert_eq_insertₘ [Ord α] {k : α} {v : β k} {l : Impl α β} {h} :
(insert k v l h).impl = insertₘ k v l h := by
simp only [insertₘ]
induction l
· simp only [insert, updateCell]
split <;> split <;> simp_all [balanceL_eq_balance, balanceR_eq_balance]
· simp [insert, updateCell]
theorem insert!_eq_insertₘ [Ord α] {k : α} {v : β k} {l : Impl α β} (h : l.Balanced) :
insert! k v l = insertₘ k v l h := by
rw [← insert_eq_insert! (h := h), insert_eq_insertₘ]
theorem erase_eq_erase! [Ord α] {k : α} {t : Impl α β} {h} :
(erase k t h).impl = erase! k t := by
induction t, h using erase.induct k <;>
simp_all [erase, erase!, balanceLErase_eq_balanceL!, balanceRErase_eq_balanceR!,
glue_eq_glue!]
theorem erase_eq_eraseₘ [Ord α] {k : α} {t : Impl α β} {h} :
(erase k t h).impl = eraseₘ k t h := by
simp only [eraseₘ]
induction t using tree_split_ind_no_gen (compare k) <;>
simp only [erase, updateCell, *, Cell.empty_inner, balanceRErase_eq_balance, balanceLErase_eq_balance]
theorem erase!_eq_eraseₘ [Ord α] {k : α} {t : Impl α β} (h : t.Balanced) :
erase! k t = eraseₘ k t h := by
rw [← erase_eq_erase! (h := h), erase_eq_eraseₘ]
theorem containsThenInsert!_fst_eq_containsThenInsert_fst [Ord α] (t : Impl α β) (htb : t.Balanced) (a : α) (b : β a) :
(t.containsThenInsert! a b).1 = (t.containsThenInsert a b htb).1 := by
cases t <;> simp [containsThenInsert, containsThenInsert.size,
containsThenInsert!, containsThenInsert!.size, insert!_eq_insertₘ, insert_eq_insertₘ, htb]
theorem containsThenInsert!_snd_eq_containsThenInsert_snd [Ord α] (t : Impl α β) (htb : t.Balanced) (a : α) (b : β a) :
(t.containsThenInsert! a b).2 = (t.containsThenInsert a b htb).2.impl := by
cases t <;> simp [containsThenInsert, containsThenInsert!, insert!_eq_insertₘ htb,
insert_eq_insertₘ]
theorem containsThenInsert_snd_eq_insertₘ [Ord α] (t : Impl α β) (htb : t.Balanced) (a : α) (b : β a) :
(t.containsThenInsert a b htb).2.impl = t.insertₘ a b htb := by
rw [containsThenInsert, insert_eq_insertₘ]
theorem containsThenInsert!_snd_eq_insertₘ [Ord α] (t : Impl α β) (htb : t.Balanced) (a : α) (b : β a) :
(t.containsThenInsert! a b).2 = t.insertₘ a b htb := by
rw [containsThenInsert!_snd_eq_containsThenInsert_snd, containsThenInsert_snd_eq_insertₘ]
theorem insertIfNew_eq_insertIfNew! [Ord α] {k : α} {v : β k} {l : Impl α β} {h} :
(insertIfNew k v l h).impl = insertIfNew! k v l := by
simp only [insertIfNew, insertIfNew!]
split
· rfl
· simp [insert_eq_insert!]
theorem containsThenInsertIfNew!_fst_eq_containsThenInsertIfNew_fst [Ord α] (t : Impl α β) (htb : t.Balanced) (a : α) (b : β a) :
(t.containsThenInsertIfNew! a b).1 = (t.containsThenInsertIfNew a b htb).1 := by
simp only [containsThenInsertIfNew!, containsThenInsertIfNew]
split <;> rfl
theorem containsThenInsertIfNew!_snd_eq_containsThenInsertIfNew_snd [Ord α] (t : Impl α β) (htb : t.Balanced) (a : α) (b : β a) :
(t.containsThenInsertIfNew! a b).2 = (t.containsThenInsertIfNew a b htb).2.impl := by
simp only [containsThenInsertIfNew!, containsThenInsertIfNew]
split
· rfl
· simp [insert!_eq_insertₘ, insert_eq_insertₘ, htb]
theorem containsThenInsertIfNew_fst_eq_containsₘ [Ord α] [TransOrd α] (t : Impl α β) (htb : t.Balanced)
(a : α) (b : β a) : (t.containsThenInsertIfNew a b htb).1 = t.containsₘ a := by
simp only [containsThenInsertIfNew, contains_eq_containsₘ]
split <;> next h => simp only [h]
theorem containsThenInsertIfNew_snd_eq_insertIfNew [Ord α] (t : Impl α β) (htb : t.Balanced) (a : α) (b : β a) :
(t.containsThenInsertIfNew a b htb).2 = (t.insertIfNew a b htb) := by
rw [containsThenInsertIfNew, insertIfNew]
split <;> rfl
theorem containsThenInsertIfNew!_fst_eq_containsₘ [Ord α] [TransOrd α] (t : Impl α β)
(a : α) (b : β a) : (t.containsThenInsertIfNew! a b).1 = t.containsₘ a := by
simp only [containsThenInsertIfNew!, contains_eq_containsₘ]
split <;> next h => simp only [h]
theorem containsThenInsertIfNew!_snd_eq_insertIfNew! [Ord α] (t : Impl α β) (a : α) (b : β a) :
(t.containsThenInsertIfNew! a b).2 = t.insertIfNew! a b:= by
rw [containsThenInsertIfNew!, insertIfNew!]
split <;> rfl
theorem insertMin_eq_insertMin! [Ord α] {a b} {t : Impl α β} (htb) :
(t.insertMin a b htb).impl = t.insertMin! a b := by
fun_cases insertMin!
· rfl
· simp only [insertMin, balanceL_eq_balanceL!, insertMin_eq_insertMin! htb.left]
theorem insertMax_eq_insertMax! [Ord α] {a b} {t : Impl α β} (htb) :
(t.insertMax a b htb).impl = t.insertMax! a b := by
fun_cases insertMax!
· rfl
· simp only [insertMax, balanceR_eq_balanceR!, insertMax_eq_insertMax! htb.right]
theorem link_eq_link! [Ord α] {k v} {l r : Impl α β} (hlb hrb) :
(link k v l r hlb hrb).impl = link! k v l r := by
fun_induction link! <;>
simp [*, link, balanceLErase_eq_balanceL!, balanceRErase_eq_balanceR!, insertMin_eq_insertMin!, insertMax_eq_insertMax!, size]
theorem link2_eq_link2! [Ord α] {l r : Impl α β} (hlb hrb) :
(link2 l r hlb hrb).impl = link2! l r := by
fun_induction link2! <;>
simp [*, link2, balanceLErase_eq_balanceL!, balanceRErase_eq_balanceR!, glue_eq_glue!]
namespace Const
variable {β : Type v}
theorem get?_eq_get?ₘ [Ord α] (k : α) (l : Impl α (fun _ => β)) :
Const.get? l k = Const.get?ₘ l k := by
simp only [Const.get?ₘ]
induction l using tree_split_ind_no_gen (compare k) <;>
simp only [*, get?, applyCell, Cell.Const.get?, Cell.empty_inner, Cell.ofEq_inner]
theorem get_eq_get? [Ord α] (k : α) (l : Impl α (fun _ => β)) {h} :
some (get l k h) = get? l k := by
induction l using tree_split_ind_no_gen (compare k) <;> simp only [*, get, get?] <;> contradiction
theorem get_eq_getₘ [Ord α] (k : α) (l : Impl α (fun _ => β)) {h} (h') :
get l k h = getₘ l k h' := by
apply Option.some.inj
simp [get_eq_get?, get?_eq_get?ₘ, getₘ]
theorem get!_eq_get!ₘ [Ord α] (k : α) [Inhabited β] (l : Impl α (fun _ => β)) :
get! l k = get!ₘ l k := by
rw [get!ₘ, get?ₘ]
induction l using tree_split_ind_no_gen (compare k) <;>
simp only [*, get!, applyCell, Cell.Const.get?, Cell.ofEq, Option.get!_some]
· rfl
theorem getD_eq_getDₘ [Ord α] (k : α) (l : Impl α (fun _ => β))
(fallback : β) : getD l k fallback = getDₘ l k fallback := by
rw [getDₘ, get?ₘ]
induction l using tree_split_ind_no_gen (compare k) <;>
simp only [*, getD, applyCell, Cell.Const.get?, Cell.ofEq, Option.getD_some]
· rfl
end Const
theorem entryAtIdx?_eq_some_entryAtIdx {t : Impl α β} (htb : t.Balanced) {i : Nat} (h) :
t.entryAtIdx? i = some (t.entryAtIdx htb i h) := by
induction t, htb, i, h using entryAtIdx.induct_unfolding <;> simp only [entryAtIdx?, *]
theorem entryAtIdx!_eq_get!_entryAtIdx? {t : Impl α β} {i : Nat} [Inhabited ((a : α) × β a)] :
t.entryAtIdx! i = (t.entryAtIdx? i).get! := by
induction t, i using entryAtIdx?.induct_unfolding <;> simp only [entryAtIdx!, *] <;> trivial
theorem entryAtIdxD_eq_getD_entryAtIdx? {t : Impl α β} {i : Nat} {fallback : (a : α) × β a} :
t.entryAtIdxD i fallback = (t.entryAtIdx? i).getD fallback := by
induction t, i using entryAtIdx?.induct_unfolding <;> simp only [entryAtIdxD, *] <;> trivial
theorem keyAtIdx?_eq_entryAtIdx? {t : Impl α β} {i : Nat} :
t.keyAtIdx? i = (t.entryAtIdx? i).map (·.1) := by
induction t, i using entryAtIdx?.induct_unfolding <;> simp only [keyAtIdx?, *] <;> trivial
theorem keyAtIdx_eq_entryAtIdx_fst {t : Impl α β} (htb : t.Balanced) {i : Nat} {h} :
t.keyAtIdx htb i h = (t.entryAtIdx htb i h).1 := by
induction t, htb, i, h using keyAtIdx.induct_unfolding <;> simp only [entryAtIdx, *]
theorem keyAtIdx!_eq_get!_keyAtIdx? [Inhabited α] {t : Impl α β} {i : Nat} :
t.keyAtIdx! i = (t.keyAtIdx? i).get! := by
induction t, i using keyAtIdx?.induct_unfolding <;> simp only [keyAtIdx!, *] <;> trivial
theorem keyAtIdxD_eq_getD_keyAtIdx? {t : Impl α β} {i : Nat} {fallback : α} :
t.keyAtIdxD i fallback = (t.keyAtIdx? i).getD fallback := by
induction t, i using keyAtIdx?.induct_unfolding <;> simp only [keyAtIdxD, *] <;> trivial
/-- Implementation detail of the tree map -/
def getEntryGE?ₘ [Ord α] (k : α) (t : Impl α β) : Option ((a : α) × β a) :=
applyPartition (compare k) t fun _ c _ r => c.inner.or r.head?
/-- Implementation detail of the tree map -/
def getEntryGE?ₘ' [Ord α] (k : α) (t : Impl α β) : Option ((a : α) × β a) :=
t.explore (compare k) none fun
| _, .lt k' _ v _ => some ⟨k', v⟩
| base, .eq _ c r => (c.inner.or r.head?).or base
| base, .gt _ _ _ _ => base
theorem getEntryGE?_eq_getEntryGE?ₘ' [Ord α] (k : α) (t : Impl α β) :
getEntryGE? k t = getEntryGE?ₘ' k t := by
rw [getEntryGE?ₘ', getEntryGE?]
induction t, none using tree_split_ind (compare k) <;> simp [*, getEntryGE?.go, explore]
theorem getEntryGE?_eq_getEntryGE?ₘ [Ord α] (k : α) (t : Impl α β) :
getEntryGE? k t = getEntryGE?ₘ k t := by
rw [getEntryGE?_eq_getEntryGE?ₘ', getEntryGE?ₘ', getEntryGE?ₘ, explore_eq_applyPartition] <;> simp
/-- Implementation detail of the tree map -/
def getEntryGT?ₘ [Ord α] (k : α) (t : Impl α β) : Option ((a : α) × β a) :=
applyPartition (fun k' => (compare k k').then .gt) t fun _ _ _ r => r.head?
/-- Implementation detail of the tree map -/
def getEntryGT?ₘ' [Ord α] (k : α) (t : Impl α β) : Option ((a : α) × β a) :=
t.explore (fun k' => (compare k k').then .gt) none fun
| _, .lt k' _ v _ => some ⟨k', v⟩
| base, .eq _ _ r => r.head?.or base
| base, .gt _ _ _ _ => base
theorem getEntryGT?_eq_getEntryGT?ₘ' [Ord α] (k : α) (t : Impl α β) :
getEntryGT? k t = getEntryGT?ₘ' k t := by
rw [getEntryGT?ₘ', getEntryGT?]
induction t, none using tree_split_ind (compare k) <;> simp [*, getEntryGT?.go, explore]
theorem getEntryGT?_eq_getEntryGT?ₘ [Ord α] (k : α) (t : Impl α β) :
getEntryGT? k t = getEntryGT?ₘ k t := by
rw [getEntryGT?_eq_getEntryGT?ₘ', getEntryGT?ₘ', getEntryGT?ₘ, explore_eq_applyPartition] <;> simp
theorem getEntryLT?_eq_getEntryGT?_reverse [o : Ord α] [TransOrd α] {t : Impl α β} {k : α} :
getEntryLT? k t = @getEntryGT? α β o.opposite k t.reverse := by
rw [getEntryLT?, @getEntryGT?.eq_def, Ord.opposite]
induction t, none using tree_split_ind (compare k) <;>
simp only [*, getEntryLT?.go, reverse, getEntryGT?.go, OrientedCmp.eq_swap (b := k),
Ordering.swap]
theorem getEntryLE?_eq_getEntryGE?_reverse [o : Ord α] [TransOrd α] {t : Impl α β} {k : α} :
getEntryLE? k t = @getEntryGE? α β o.opposite k t.reverse := by
rw [getEntryLE?, @getEntryGE?.eq_def, Ord.opposite]
induction t, none using tree_split_ind (compare k) <;>
simp only [*, getEntryLE?.go, reverse, getEntryGE?.go, OrientedCmp.eq_swap (b := k),
Ordering.swap]
theorem getEntryGE!_eq_get!_getEntryGE? [Ord α] {t : Impl α β} {k : α} [Inhabited ((a : α) × β a)] :
t.getEntryGE! k = (t.getEntryGE? k).get! := rfl
theorem getEntryGT!_eq_get!_getEntryGT? [Ord α] {t : Impl α β} {k : α} [Inhabited ((a : α) × β a)] :
t.getEntryGT! k = (t.getEntryGT? k).get! := rfl
theorem getEntryLE!_eq_get!_getEntryLE? [Ord α] {t : Impl α β} {k : α} [Inhabited ((a : α) × β a)] :
t.getEntryLE! k = (t.getEntryLE? k).get! := rfl
theorem getEntryLT!_eq_get!_getEntryLT? [Ord α] {t : Impl α β} {k : α} [Inhabited ((a : α) × β a)] :
t.getEntryLT! k = (t.getEntryLT? k).get! := rfl
theorem getEntryGED_eq_getD_getEntryGE? [Ord α] {t : Impl α β} {k : α} {fallback : (a : α) × β a} :
t.getEntryGED k fallback = (t.getEntryGE? k).getD fallback := rfl
theorem getEntryGTD_eq_getD_getEntryGT? [Ord α] {t : Impl α β} {k : α} {fallback : (a : α) × β a} :
t.getEntryGTD k fallback = (t.getEntryGT? k).getD fallback := rfl
theorem getEntryLED_eq_getD_getEntryLE? [Ord α] {t : Impl α β} {k : α} {fallback : (a : α) × β a} :
t.getEntryLED k fallback = (t.getEntryLE? k).getD fallback := rfl
theorem getEntryLTD_eq_getD_getEntryLT? [Ord α] {t : Impl α β} {k : α} {fallback : (a : α) × β a} :
t.getEntryLTD k fallback = (t.getEntryLT? k).getD fallback := rfl
theorem getEntryGE?.eq_go [Ord α] (k : α) (x) (t : Impl α β) :
(getEntryGE? k t).or x = getEntryGE?.go k x t := by
rw [getEntryGE?]
induction t, x using tree_split_ind (compare k) <;>
simp only [go, Option.none_or, Option.some_or, *]
case _ ih _ => rw [← ih, Option.or_assoc, Option.some_or]
theorem getEntryGT?.eq_go [Ord α] (k : α) (x) (t : Impl α β) :
(getEntryGT? k t).or x = getEntryGT?.go k x t := by
rw [getEntryGT?]
induction t, x using tree_split_ind (compare k) <;>
simp only [go, Option.none_or, *]
case _ ih _ => rw [← ih, Option.or_assoc, Option.some_or]
theorem getEntryLE?.eq_go [Ord α] (k : α) (x) (t : Impl α β) :
(getEntryLE? k t).or x = getEntryLE?.go k x t := by
rw [getEntryLE?]
induction t, x using tree_split_ind (compare k) <;>
simp only [go, Option.none_or, Option.some_or, *]
case _ ih _ => rw [← ih, Option.or_assoc, Option.some_or]
theorem getEntryLT?.eq_go [Ord α] (k : α) (x) (t : Impl α β) :
(getEntryLT? k t).or x = getEntryLT?.go k x t := by
rw [getEntryLT?]
induction t, x using tree_split_ind (compare k) <;>
simp only [go, Option.none_or, *]
case _ ih _ => rw [← ih, Option.or_assoc, Option.some_or]
theorem some_getEntryGE_eq_getEntryGE? [Ord α] [TransOrd α] (k : α) (t : Impl α β) {ho he} :
some (getEntryGE k t ho he) = getEntryGE? k t := by
rw [getEntryGE?]; apply of_eq_true
induction t, none using tree_split_ind (compare k) <;>
simp only [*, getEntryGE?.go, getEntryGE, getEntryGED, ← Option.or_some,
getEntryGE?.eq_go] <;> contradiction
theorem some_getEntryGT_eq_getEntryGT? [Ord α] [TransOrd α] (k : α) (t : Impl α β) {ho he} :
some (getEntryGT k t ho he) = getEntryGT? k t := by
rw [getEntryGT?]; apply of_eq_true
induction t, none using tree_split_ind (compare k) <;>
simp only [*, getEntryGT?.go, getEntryGT, getEntryGTD, ← Option.or_some,
getEntryGT?.eq_go, ↓reduceDIte, reduceCtorEq] <;> contradiction
theorem some_getEntryLE_eq_getEntryLE? [Ord α] [TransOrd α] (k : α) (t : Impl α β) {ho he} :
some (getEntryLE k t ho he) = getEntryLE? k t := by
rw [getEntryLE?]; apply of_eq_true
induction t, none using tree_split_ind (compare k) <;>
simp only [*, getEntryLE?.go, getEntryLE, getEntryLED, ← Option.or_some,
getEntryLE?.eq_go] <;> contradiction
theorem some_getEntryLT_eq_getEntryLT? [Ord α] [TransOrd α] (k : α) (t : Impl α β) {ho he} :
some (getEntryLT k t ho he) = getEntryLT? k t := by
rw [getEntryLT?]; apply of_eq_true
induction t, none using tree_split_ind (compare k) <;>
simp only [*, getEntryLT?.go, getEntryLT, getEntryLTD, ← Option.or_some,
getEntryLT?.eq_go, ↓reduceDIte, reduceCtorEq] <;> contradiction
theorem getKeyGE?_eq_getEntryGE? [Ord α] {t : Impl α β} {k : α} :
getKeyGE? k t = (getEntryGE? k t).map (·.1) := by
rw [getKeyGE?, getEntryGE?]; symm
change _ = getKeyGE?.go k (Option.map (·.1) (none : Option ((a : α) × β a))) _
induction t, none using tree_split_ind (compare k) <;> simp [getKeyGE?.go, getEntryGE?.go, *]
theorem getKeyGT?_eq_getEntryGT? [Ord α] {t : Impl α β} {k : α} :
getKeyGT? k t = (getEntryGT? k t).map (·.1) := by
rw [getKeyGT?, getEntryGT?]; symm
change _ = getKeyGT?.go k (Option.map (·.1) (none : Option ((a : α) × β a))) _
induction t, none using tree_split_ind (compare k) <;> simp [getKeyGT?.go, getEntryGT?.go, *]
theorem getKeyLE?_eq_getEntryLE? [Ord α] {t : Impl α β} {k : α} :
getKeyLE? k t = (getEntryLE? k t).map (·.1) := by
rw [getKeyLE?, getEntryLE?]; symm
change _ = getKeyLE?.go k (Option.map (·.1) (none : Option ((a : α) × β a))) _
induction t, none using tree_split_ind (compare k) <;> simp [getKeyLE?.go, getEntryLE?.go, *]
theorem getKeyLT?_eq_getEntryLT? [Ord α] {t : Impl α β} {k : α} :
getKeyLT? k t = (getEntryLT? k t).map (·.1) := by
rw [getKeyLT?, getEntryLT?]; symm
change _ = getKeyLT?.go k (Option.map (·.1) (none : Option ((a : α) × β a))) _
induction t, none using tree_split_ind (compare k) <;> simp [getKeyLT?.go, getEntryLT?.go, *]
theorem getKeyGE!_eq_get!_getKeyGE? [Ord α] {t : Impl α β} {k : α} [Inhabited α] :
t.getKeyGE! k = (t.getKeyGE? k).get! := rfl
theorem getKeyGT!_eq_get!_getKeyGT? [Ord α] {t : Impl α β} {k : α} [Inhabited α] :
t.getKeyGT! k = (t.getKeyGT? k).get! := rfl
theorem getKeyLE!_eq_get!_getKeyLE? [Ord α] {t : Impl α β} {k : α} [Inhabited α] :
t.getKeyLE! k = (t.getKeyLE? k).get! := rfl
theorem getKeyLT!_eq_get!_getKeyLT? [Ord α] {t : Impl α β} {k : α} [Inhabited α] :
t.getKeyLT! k = (t.getKeyLT? k).get! := rfl
theorem getKeyGED_eq_getD_getKeyGE? [Ord α] {t : Impl α β} {k fallback : α} :
t.getKeyGED k fallback = (t.getKeyGE? k).getD fallback := rfl
theorem getKeyGTD_eq_getD_getKeyGT? [Ord α] {t : Impl α β} {k fallback : α} :
t.getKeyGTD k fallback = (t.getKeyGT? k).getD fallback := rfl
theorem getKeyLED_eq_getD_getKeyLE? [Ord α] {t : Impl α β} {k fallback : α} :
t.getKeyLED k fallback = (t.getKeyLE? k).getD fallback := rfl
theorem getKeyLTD_eq_getD_getKeyLT? [Ord α] {t : Impl α β} {k fallback : α} :
t.getKeyLTD k fallback = (t.getKeyLT? k).getD fallback := rfl
theorem getKeyGE_eq_getEntryGE [Ord α] [TransOrd α] {t : Impl α β} {k : α} {hto he} :
getKeyGE k t hto he = (getEntryGE k t hto he).1 := by
induction t using tree_split_ind_no_gen (compare k) <;> simp only [getKeyGE, getEntryGE, *]
· contradiction
· rw [getKeyGED, getEntryGED, getKeyGE?_eq_getEntryGE?]; symm
exact (Option.getD_map _ _ _).symm
theorem getKeyGT_eq_getEntryGT [Ord α] [TransOrd α] {t : Impl α β} {k : α} {hto he} :
getKeyGT k t hto he = (getEntryGT k t hto he).1 := by
induction t using tree_split_ind_no_gen (compare k) <;>
simp only [getKeyGT, getEntryGT, *, ↓reduceDIte, reduceCtorEq]
· contradiction
· rw [getKeyGTD, getEntryGTD, getKeyGT?_eq_getEntryGT?]; symm
exact (Option.getD_map _ _ _).symm
theorem getKeyLE_eq_getEntryLE [Ord α] [TransOrd α] {t : Impl α β} {k : α} {hto he} :
getKeyLE k t hto he = (getEntryLE k t hto he).1 := by
induction t using tree_split_ind_no_gen (compare k) <;> simp only [getKeyLE, getEntryLE, *]
· contradiction
· rw [getKeyLED, getEntryLED, getKeyLE?_eq_getEntryLE?]; symm
exact (Option.getD_map _ _ _).symm
theorem getKeyLT_eq_getEntryLT [Ord α] [TransOrd α] {t : Impl α β} {k : α} {hto he} :
getKeyLT k t hto he = (getEntryLT k t hto he).1 := by
induction t using tree_split_ind_no_gen (compare k) <;>
simp only [getKeyLT, getEntryLT, *, ↓reduceDIte, reduceCtorEq]
· contradiction
· rw [getKeyLTD, getEntryLTD, getKeyLT?_eq_getEntryLT?]; symm
exact (Option.getD_map _ _ _).symm
namespace Const
variable {β : Type v}
theorem entryAtIdx?_eq_map {t : Impl α fun _ => β} {i : Nat} :
entryAtIdx? t i = (t.entryAtIdx? i).map (fun x => (x.1, x.2)) := by
induction t, i using entryAtIdx?.induct_unfolding <;> simp only [Impl.entryAtIdx?, *] <;> rfl
theorem entryAtIdx_eq {t : Impl α fun _ => β} (htb : t.Balanced) {i : Nat} {h} :
entryAtIdx t htb i h = ((t.entryAtIdx htb i h).1, (t.entryAtIdx htb i h).2) := by
induction t, htb, i, h using entryAtIdx.induct_unfolding <;> simp only [Impl.entryAtIdx, *]
theorem entryAtIdx!_eq_get!_entryAtIdx? {t : Impl α fun _ => β} {i : Nat} [Inhabited (α × β)] :
entryAtIdx! t i = (entryAtIdx? t i).get! := by
induction t, i using entryAtIdx?.induct_unfolding <;> simp only [entryAtIdx!, *] <;> rfl
theorem entryAtIdxD_eq_getD_entryAtIdx? {t : Impl α fun _ => β} {i : Nat} {fallback : α × β} :
entryAtIdxD t i fallback = (entryAtIdx? t i).getD fallback := by
induction t, i using entryAtIdx?.induct_unfolding <;> simp only [entryAtIdxD, *] <;> rfl
theorem getEntryGE?_eq_map [Ord α] {t : Impl α fun _ => β} {k : α} :
getEntryGE? k t = (Impl.getEntryGE? k t).map (fun x => (x.1, x.2)) := by
rw [getEntryGE?, Impl.getEntryGE?]; symm
change _ = getEntryGE?.go k (Option.map (fun x => (x.1, x.2)) (none : Option ((_ : α) × β))) _
induction t, none using tree_split_ind (compare k) <;> simp [getEntryGE?.go, Impl.getEntryGE?.go, *]
theorem getEntryGT?_eq_map [Ord α] {t : Impl α fun _ => β} {k : α} :
getEntryGT? k t = (Impl.getEntryGT? k t).map (fun x => (x.1, x.2)) := by
rw [getEntryGT?, Impl.getEntryGT?]; symm
change _ = getEntryGT?.go k (Option.map (fun x => (x.1, x.2)) (none : Option ((_ : α) × β))) _
induction t, none using tree_split_ind (compare k) <;> simp [getEntryGT?.go, Impl.getEntryGT?.go, *]
theorem getEntryLE?_eq_map [Ord α] {t : Impl α fun _ => β} {k : α} :
getEntryLE? k t = (Impl.getEntryLE? k t).map (fun x => (x.1, x.2)) := by
rw [getEntryLE?, Impl.getEntryLE?]; symm
change _ = getEntryLE?.go k (Option.map (fun x => (x.1, x.2)) (none : Option ((_ : α) × β))) _
induction t, none using tree_split_ind (compare k) <;> simp [getEntryLE?.go, Impl.getEntryLE?.go, *]
theorem getEntryLT?_eq_map [Ord α] {t : Impl α fun _ => β} {k : α} :
getEntryLT? k t = (Impl.getEntryLT? k t).map (fun x => (x.1, x.2)) := by
rw [getEntryLT?, Impl.getEntryLT?]; symm
change _ = getEntryLT?.go k (Option.map (fun x => (x.1, x.2)) (none : Option ((_ : α) × β))) _
induction t, none using tree_split_ind (compare k) <;> simp [getEntryLT?.go, Impl.getEntryLT?.go, *]
theorem getEntryGE!_eq_get!_getEntryGE? [Ord α] {t : Impl α fun _ => β} {k : α} [Inhabited (α × β)] :
getEntryGE! k t = (getEntryGE? k t).get! := rfl
theorem getEntryGT!_eq_get!_getEntryGT? [Ord α] {t : Impl α fun _ => β} {k : α} [Inhabited (α × β)] :
getEntryGT! k t = (getEntryGT? k t).get! := rfl
theorem getEntryLE!_eq_get!_getEntryLE? [Ord α] {t : Impl α fun _ => β} {k : α} [Inhabited (α × β)] :
getEntryLE! k t = (getEntryLE? k t).get! := rfl
theorem getEntryLT!_eq_get!_getEntryLT? [Ord α] {t : Impl α fun _ => β} {k : α} [Inhabited (α × β)] :
getEntryLT! k t = (getEntryLT? k t).get! := rfl
theorem getEntryGED_eq_getD_getEntryGE? [Ord α] {t : Impl α fun _ => β} {k : α} {fallback : α × β} :
getEntryGED k t fallback = (getEntryGE? k t).getD fallback := rfl
theorem getEntryGTD_eq_getD_getEntryGT? [Ord α] {t : Impl α fun _ => β} {k : α} {fallback : α × β} :
getEntryGTD k t fallback = (getEntryGT? k t).getD fallback := rfl
theorem getEntryLED_eq_getD_getEntryLE? [Ord α] {t : Impl α fun _ => β} {k : α} {fallback : α × β} :
getEntryLED k t fallback = (getEntryLE? k t).getD fallback := rfl
theorem getEntryLTD_eq_getD_getEntryLT? [Ord α] {t : Impl α fun _ => β} {k : α} {fallback : α × β} :
getEntryLTD k t fallback = (getEntryLT? k t).getD fallback := rfl
theorem getEntryGE_eq [Ord α] [TransOrd α] {t : Impl α fun _ => β} (hto : t.Ordered) {k : α} (he) :
getEntryGE k t hto he = (letI e := Impl.getEntryGE k t hto he; (e.1, e.2)) := by
induction t using tree_split_ind_no_gen (compare k) <;> simp only [getEntryGE, Impl.getEntryGE, *]
· contradiction
· rename_i l _ _ _
rw [getEntryGED, Impl.getEntryGED, getEntryGE?_eq_map]
exact Option.getD_map (fun x => (x.1, x.2)) ⟨_, _⟩ (Impl.getEntryGE? k l)
theorem getEntryGT_eq [Ord α] [TransOrd α] {t : Impl α fun _ => β} (hto : t.Ordered) {k : α} (he) :
getEntryGT k t hto he = (letI e := Impl.getEntryGT k t hto he; (e.1, e.2)) := by
induction t using tree_split_ind_no_gen (compare k) <;>
simp only [getEntryGT, Impl.getEntryGT, *, ↓reduceDIte, reduceCtorEq]
· contradiction
· rename_i l _ _ _
rw [getEntryGTD, Impl.getEntryGTD, getEntryGT?_eq_map]
exact Option.getD_map (fun x => (x.1, x.2)) ⟨_, _⟩ (Impl.getEntryGT? k l)
theorem getEntryLE_eq [Ord α] [TransOrd α] {t : Impl α fun _ => β} (hto : t.Ordered) {k : α} (he) :
getEntryLE k t hto he = (letI e := Impl.getEntryLE k t hto he; (e.1, e.2)) := by
induction t using tree_split_ind_no_gen (compare k) <;> simp only [getEntryLE, Impl.getEntryLE, *]
· contradiction
· rename_i r _ _
rw [getEntryLED, Impl.getEntryLED, getEntryLE?_eq_map]
exact Option.getD_map (fun x => (x.1, x.2)) ⟨_, _⟩ (Impl.getEntryLE? k r)
theorem getEntryLT_eq [Ord α] [TransOrd α] {t : Impl α fun _ => β} (hto : t.Ordered) {k : α} (he) :
getEntryLT k t hto he = (letI e := Impl.getEntryLT k t hto he; (e.1, e.2)) := by
induction t using tree_split_ind_no_gen (compare k) <;>
simp only [getEntryLT, Impl.getEntryLT, *, ↓reduceDIte, reduceCtorEq]
· contradiction
· rename_i r _ _
rw [getEntryLTD, Impl.getEntryLTD, getEntryLT?_eq_map]
exact Option.getD_map (fun x => (x.1, x.2)) ⟨_, _⟩ (Impl.getEntryLT? k r)
end Const
end Impl
end Std.DTreeMap.Internal