blob: 61b9f6c98cfab57ece20d2fab1d02b364a2fffa0 [file]
/-
Copyright (c) 2025 Robin Arnez. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Robin Arnez, Markus Himmel, Paul Reichert
-/
module
prelude
public import Std.Data.DTreeMap.Lemmas
@[expose] public section
/-!
# Extensional dependent tree maps
This file develops the type `Std.ExtDTreeMap` of extensional dependent tree maps.
Lemmas about the operations on `Std.ExtDTreeMap` will be available in the
module `Std.Data.ExtDTreeMap.Lemmas`.
See the module `Std.Data.DTreeMap.Raw.Basic` for a variant of this type which is safe to use in
nested inductive types.
-/
set_option autoImplicit false
set_option linter.missingDocs true
universe u v w w₂
variable {α : Type u} {β : α → Type v} {γ : α → Type w} {cmp : α → α → Ordering}
attribute [local instance] Std.DTreeMap.isSetoid
open scoped Std.DTreeMap
namespace Std
/--
Extensional dependent tree maps.
A tree map stores an assignment of keys to values. It depends on a comparator function that
defines an ordering on the keys and provides efficient order-dependent queries, such as retrieval
of the minimum or maximum.
To ensure that the operations behave as expected, the comparator function `cmp` should satisfy
certain laws that ensure a consistent ordering:
* If `a` is less than (or equal) to `b`, then `b` is greater than (or equal) to `a`
and vice versa (see the `OrientedCmp` typeclass).
* If `a` is less than or equal to `b` and `b` is, in turn, less than or equal to `c`, then `a`
is less than or equal to `c` (see the `TransCmp` typeclass).
Keys for which `cmp a b = Ordering.eq` are considered the same, i.e., there can be only one entry
with key either `a` or `b` in a tree map. Looking up either `a` or `b` always yields the same entry,
if any is present. The `get` operations of the _dependent_ tree map additionally require a
`LawfulEqCmp` instance to ensure that `cmp a b = .eq` always implies `a = b`, so that their
respective value types are equal.
To avoid expensive copies, users should make sure that the tree map is used linearly.
Internally, the tree maps are represented as size-bounded trees, a type of self-balancing binary
search tree with efficient order statistic lookups.
In contrast to regular dependent tree maps, `Std.ExtDTreeMap` offers several extensionality lemmas
and therefore has more lemmas about equality of tree maps. This doesn't affect the amount of
supported functions though: `Std.ExtDTreeMap` supports all operations from `Std.DTreeMap`.
In order to use most functions, a `TransCmp` instance is required. This is necessary to make sure
that the functions are congruent, i.e. equivalent tree maps as parameters produce equivalent return
values.
These tree maps contain a bundled well-formedness invariant, which means that they cannot
be used in nested inductive types. For these use cases, `Std.DTreeMap.Raw` and
`Std.DTreeMap.Raw.WF` unbundle the invariant from the tree map. When in doubt, prefer
`ExtDTreeMap` over `DTreeMap.Raw`.
-/
structure ExtDTreeMap (α : Type u) (β : α → Type v) (cmp : α → α → Ordering := by exact compare) where
/-- Implementation detail of the tree map -/
mk' ::
/-- Implementation detail of the tree map -/
inner : Quotient (DTreeMap.isSetoid α β cmp)
/-- Implementation detail of the tree map -/
abbrev ExtDTreeMap.mk (t : DTreeMap α β cmp) : ExtDTreeMap α β cmp :=
.mk' (Quotient.mk _ t)
/-- Implementation detail of the tree map -/
abbrev ExtDTreeMap.lift {γ : Sort w} (f : DTreeMap α β cmp → γ) (h : ∀ a b, a ~m b → f a = f b)
(t : ExtDTreeMap α β cmp) : γ :=
t.1.lift f h
/-- Implementation detail of the tree map -/
def ExtDTreeMap.lift₂ {γ : Sort w} (f : DTreeMap α β cmp → DTreeMap α β cmp → γ) (h : ∀ a b c d, a ~m c → b ~m d → f a b = f c d) (m₁ m₂ : ExtDTreeMap α β cmp) : γ :=
Quotient.lift₂ f h m₁.inner m₂.inner
/-- Implementation detail of the tree map -/
abbrev ExtDTreeMap.liftOn₂ {γ : Sort w} (t₁ t₂ : ExtDTreeMap α β cmp)
(f : DTreeMap α β cmp → DTreeMap α β cmp → γ) (h : ∀ a b c d, a ~m c → b ~m d → f a b = f c d) : γ :=
t₁.1.liftOn₂ t₂.1 f h
/-- Implementation detail of the tree map -/
abbrev ExtDTreeMap.pliftOn {γ : Sort w} (t : ExtDTreeMap α β cmp)
(f : (x : DTreeMap α β cmp) → t = mk x → γ) (h : ∀ a b h₁ h₂, a ~m b → f a h₁ = f b h₂) : γ :=
t.1.pliftOn (fun x hx => f x (by cases t; cases hx; rfl)) (fun a b _ _ h' => h a b _ _ h')
theorem ExtDTreeMap.sound {t₁ t₂ : DTreeMap α β cmp} (h : t₁ ~m t₂) : mk t₁ = mk t₂ :=
congrArg mk' (Quotient.sound h)
theorem ExtDTreeMap.exact {t₁ t₂ : DTreeMap α β cmp} (h : mk t₁ = mk t₂) : t₁ ~m t₂ :=
Quotient.exact (congrArg inner h)
@[cases_eliminator, induction_eliminator, elab_as_elim]
theorem ExtDTreeMap.inductionOn {motive : ExtDTreeMap α β cmp → Prop}
(t : ExtDTreeMap α β cmp) (mk : ∀ a, motive (mk a)) : motive t :=
(t.1.inductionOn fun _ => mk _ : motive ⟨t.1⟩)
@[elab_as_elim]
theorem ExtDTreeMap.inductionOn₂ {motive : ExtDTreeMap α β cmp → ExtDTreeMap α β cmp → Prop}
(t₁ t₂ : ExtDTreeMap α β cmp) (mk : ∀ a b, motive (mk a) (mk b)) : motive t₁ t₂ :=
t₁.inductionOn fun _ => t₂.inductionOn fun _ => mk _ _
namespace ExtDTreeMap
local instance : Coe (Type v) (α → Type v) where coe γ := fun _ => γ
@[inline, inherit_doc DTreeMap.empty]
def empty : ExtDTreeMap α β cmp :=
mk .empty
instance : EmptyCollection (ExtDTreeMap α β cmp) where
emptyCollection := empty
instance : Inhabited (ExtDTreeMap α β cmp) where
default := ∅
@[simp, grind =]
theorem empty_eq_emptyc : (empty : ExtDTreeMap α β cmp) = ∅ :=
rfl
@[inline, inherit_doc DTreeMap.insert]
def insert [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (b : β a) : ExtDTreeMap α β cmp :=
t.lift (fun m => mk (m.insert a b)) (fun _ _ h => sound (h.insert a b))
instance [TransCmp cmp] : Singleton ((a : α) × β a) (ExtDTreeMap α β cmp) where
singleton e := (∅ : ExtDTreeMap α β cmp).insert e.1 e.2
instance [TransCmp cmp] : Insert ((a : α) × β a) (ExtDTreeMap α β cmp) where
insert e s := s.insert e.1 e.2
instance [TransCmp cmp] : LawfulSingleton ((a : α) × β a) (ExtDTreeMap α β cmp) where
insert_empty_eq _ := rfl
@[inline, inherit_doc DTreeMap.insertIfNew]
def insertIfNew [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (b : β a) : ExtDTreeMap α β cmp :=
t.lift (fun m => mk (m.insertIfNew a b)) (fun _ _ h => sound (h.insertIfNew a b))
@[inline, inherit_doc DTreeMap.containsThenInsert]
def containsThenInsert [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (b : β a) : Bool × ExtDTreeMap α β cmp :=
t.lift (fun m => let m' := m.containsThenInsert a b; (m'.1, mk m'.2))
(fun m m' h =>
Prod.ext
(m.containsThenInsert_fst.symm ▸ m'.containsThenInsert_fst.symm ▸ h.contains_eq)
(sound <|
m.containsThenInsert_snd.symm ▸ m'.containsThenInsert_snd.symm ▸ h.insert a b))
@[inline, inherit_doc DTreeMap.containsThenInsertIfNew]
def containsThenInsertIfNew [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (b : β a) :
Bool × ExtDTreeMap α β cmp :=
t.lift (fun m => let m' := m.containsThenInsertIfNew a b; (m'.1, mk m'.2))
(fun m m' h =>
Prod.ext
(m.containsThenInsertIfNew_fst.symm ▸ m'.containsThenInsertIfNew_fst.symm ▸ h.contains_eq)
(sound <|
m.containsThenInsertIfNew_snd.symm ▸ m'.containsThenInsertIfNew_snd.symm ▸ h.insertIfNew a b))
@[inline, inherit_doc DTreeMap.getThenInsertIfNew?]
def getThenInsertIfNew? [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (b : β a) :
Option (β a) × ExtDTreeMap α β cmp :=
t.lift (fun m => let m' := m.getThenInsertIfNew? a b; (m'.1, mk m'.2))
(fun m m' h =>
Prod.ext
(m.getThenInsertIfNew?_fst.symm ▸ m'.getThenInsertIfNew?_fst.symm ▸ h.get?_eq)
(sound <|
m.getThenInsertIfNew?_snd.symm ▸ m'.getThenInsertIfNew?_snd.symm ▸ h.insertIfNew a b))
@[inline, inherit_doc DTreeMap.contains]
def contains [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) : Bool :=
t.lift (fun m => m.contains a) (fun _ _ h => h.contains_eq)
instance [TransCmp cmp] : Membership α (ExtDTreeMap α β cmp) where
mem m a := m.contains a
instance [TransCmp cmp] {m : ExtDTreeMap α β cmp} {a : α} : Decidable (a ∈ m) :=
inferInstanceAs <| Decidable (m.contains a)
@[inline, inherit_doc DTreeMap.size]
def size (t : ExtDTreeMap α β cmp) : Nat :=
t.lift (fun m => m.size) (fun _ _ h => h.size_eq)
@[inline, inherit_doc DTreeMap.isEmpty]
def isEmpty (t : ExtDTreeMap α β cmp) : Bool :=
t.lift (fun m => m.isEmpty) (fun _ _ h => h.isEmpty_eq)
@[simp, grind =]
theorem isEmpty_iff {t : ExtDTreeMap α β cmp} [TransCmp cmp] : t.isEmpty ↔ t = ∅ := by
rcases t with ⟨⟨t⟩⟩
refine t.equiv_empty_iff_isEmpty.symm.trans ?_
exact ⟨fun h => sound h, exact⟩
@[simp]
theorem isEmpty_eq_false_iff {t : ExtDTreeMap α β cmp} [TransCmp cmp] : t.isEmpty = false ↔ ¬t = ∅ :=
(Bool.not_eq_true _).symm.to_iff.trans (not_congr isEmpty_iff)
@[inline, inherit_doc DTreeMap.erase]
def erase [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) : ExtDTreeMap α β cmp :=
t.lift (fun m => mk (m.erase a))
(fun _ _ h => sound (h.erase a))
@[inline, inherit_doc DTreeMap.get?]
def get? [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) : Option (β a) :=
t.lift (fun m => m.get? a) (fun _ _ h => h.get?_eq)
@[inline, inherit_doc DTreeMap.get]
def get [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (h : a ∈ t) : β a :=
t.pliftOn (fun m h' => m.get a (h' ▸ h :))
(fun _ _ _ _ h => h.get_eq)
@[inline, inherit_doc DTreeMap.get!]
def get! [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) [Inhabited (β a)] : β a :=
t.lift (fun m => m.get! a) (fun _ _ h => h.get!_eq)
@[inline, inherit_doc DTreeMap.getD]
def getD [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (fallback : β a) : β a :=
t.lift (fun m => m.getD a fallback) (fun _ _ h => h.getD_eq)
@[inline, inherit_doc DTreeMap.getKey?]
def getKey? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) : Option α :=
t.lift (fun m => m.getKey? a) (fun _ _ h => h.getKey?_eq)
@[inline, inherit_doc DTreeMap.getKey]
def getKey [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (h : a ∈ t) : α :=
t.pliftOn (fun m h' => m.getKey a (h' ▸ h :))
(fun _ _ _ _ h => h.getKey_eq)
@[inline, inherit_doc DTreeMap.getKey!]
def getKey! [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (a : α) : α :=
t.lift (fun m => m.getKey! a) (fun _ _ h => h.getKey!_eq)
@[inline, inherit_doc DTreeMap.getKeyD]
def getKeyD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (fallback : α) : α :=
t.lift (fun m => m.getKeyD a fallback) (fun _ _ h => h.getKeyD_eq)
@[inline, inherit_doc DTreeMap.minEntry?]
def minEntry? [TransCmp cmp] (t : ExtDTreeMap α β cmp) : Option ((a : α) × β a) :=
t.lift (fun m => m.minEntry?) (fun _ _ h => h.minEntry?_eq)
@[inline, inherit_doc DTreeMap.minEntry]
def minEntry [TransCmp cmp] (t : ExtDTreeMap α β cmp) (h : t ≠ ∅) : (a : α) × β a :=
t.pliftOn (fun m h' => m.minEntry (h' ▸ isEmpty_eq_false_iff.mpr h :))
(fun _ _ _ _ h => h.minEntry_eq)
@[inline, inherit_doc DTreeMap.minEntry!]
def minEntry! [TransCmp cmp] [Inhabited ((a : α) × β a)] (t : ExtDTreeMap α β cmp) : (a : α) × β a :=
t.lift (fun m => m.minEntry!) (fun _ _ h => h.minEntry!_eq)
@[inline, inherit_doc DTreeMap.minEntryD]
def minEntryD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (fallback : (a : α) × β a) : (a : α) × β a :=
t.lift (fun m => m.minEntryD fallback) (fun _ _ h => h.minEntryD_eq)
@[inline, inherit_doc DTreeMap.maxEntry?]
def maxEntry? [TransCmp cmp] (t : ExtDTreeMap α β cmp) : Option ((a : α) × β a) :=
t.lift (fun m => m.maxEntry?) (fun _ _ h => h.maxEntry?_eq)
@[inline, inherit_doc DTreeMap.maxEntry]
def maxEntry [TransCmp cmp] (t : ExtDTreeMap α β cmp) (h : t ≠ ∅) : (a : α) × β a :=
t.pliftOn (fun m h' => m.maxEntry (h' ▸ isEmpty_eq_false_iff.mpr h :))
(fun _ _ _ _ h => h.maxEntry_eq)
@[inline, inherit_doc DTreeMap.maxEntry!]
def maxEntry! [TransCmp cmp] [Inhabited ((a : α) × β a)] (t : ExtDTreeMap α β cmp) : (a : α) × β a :=
t.lift (fun m => m.maxEntry!) (fun _ _ h => h.maxEntry!_eq)
@[inline, inherit_doc DTreeMap.maxEntryD]
def maxEntryD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (fallback : (a : α) × β a) : (a : α) × β a :=
t.lift (fun m => m.maxEntryD fallback) (fun _ _ h => h.maxEntryD_eq)
@[inline, inherit_doc DTreeMap.minKey?]
def minKey? [TransCmp cmp] (t : ExtDTreeMap α β cmp) : Option α :=
t.lift (fun m => m.minKey?) (fun _ _ h => h.minKey?_eq)
@[inline, inherit_doc DTreeMap.minKey]
def minKey [TransCmp cmp] (t : ExtDTreeMap α β cmp) (h : t ≠ ∅) : α :=
t.pliftOn (fun m h' => m.minKey (h' ▸ isEmpty_eq_false_iff.mpr h :))
(fun _ _ _ _ h => h.minKey_eq)
@[inline, inherit_doc DTreeMap.minKey!]
def minKey! [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) : α :=
t.lift (fun m => m.minKey!) (fun _ _ h => h.minKey!_eq)
@[inline, inherit_doc DTreeMap.minKeyD]
def minKeyD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (fallback : α) : α :=
t.lift (fun m => m.minKeyD fallback) (fun _ _ h => h.minKeyD_eq)
@[inline, inherit_doc DTreeMap.maxKey?]
def maxKey? [TransCmp cmp] (t : ExtDTreeMap α β cmp) : Option α :=
t.lift (fun m => m.maxKey?) (fun _ _ h => h.maxKey?_eq)
@[inline, inherit_doc DTreeMap.maxKey]
def maxKey [TransCmp cmp] (t : ExtDTreeMap α β cmp) (h : t ≠ ∅) : α :=
t.pliftOn (fun m h' => m.maxKey (h' ▸ isEmpty_eq_false_iff.mpr h :))
(fun _ _ _ _ h => h.maxKey_eq)
@[inline, inherit_doc DTreeMap.maxKey!]
def maxKey! [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) : α :=
t.lift (fun m => m.maxKey!) (fun _ _ h => h.maxKey!_eq)
@[inline, inherit_doc DTreeMap.maxKeyD]
def maxKeyD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (fallback : α) : α :=
t.lift (fun m => m.maxKeyD fallback) (fun _ _ h => h.maxKeyD_eq)
@[inline, inherit_doc DTreeMap.entryAtIdx?]
def entryAtIdx? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) : Option ((a : α) × β a) :=
t.lift (fun m => m.entryAtIdx? n) (fun _ _ h => h.entryAtIdx?_eq)
@[inline, inherit_doc DTreeMap.entryAtIdx]
def entryAtIdx [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) (h : n < t.size) : (a : α) × β a :=
t.pliftOn (fun m h' => m.entryAtIdx n (h' ▸ h :))
(fun _ _ _ _ h => h.entryAtIdx_eq)
@[inline, inherit_doc DTreeMap.entryAtIdx!]
def entryAtIdx! [TransCmp cmp] [Inhabited ((a : α) × β a)] (t : ExtDTreeMap α β cmp) (n : Nat) : (a : α) × β a :=
t.lift (fun m => m.entryAtIdx! n) (fun _ _ h => h.entryAtIdx!_eq)
@[inline, inherit_doc DTreeMap.entryAtIdxD]
def entryAtIdxD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat)
(fallback : (a : α) × β a) : (a : α) × β a :=
t.lift (fun m => m.entryAtIdxD n fallback) (fun _ _ h => h.entryAtIdxD_eq)
@[inline, inherit_doc DTreeMap.keyAtIdx?]
def keyAtIdx? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) : Option α :=
t.lift (fun m => m.keyAtIdx? n) (fun _ _ h => h.keyAtIdx?_eq)
@[inline, inherit_doc DTreeMap.keyAtIdx]
def keyAtIdx [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) (h : n < t.size) : α :=
t.pliftOn (fun m h' => m.keyAtIdx n (h' ▸ h :))
(fun _ _ _ _ h => h.keyAtIdx_eq)
@[inline, inherit_doc DTreeMap.keyAtIdx!]
def keyAtIdx! [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (n : Nat) : α :=
t.lift (fun m => m.keyAtIdx! n) (fun _ _ h => h.keyAtIdx!_eq)
@[inline, inherit_doc DTreeMap.keyAtIdxD]
def keyAtIdxD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) (fallback : α) : α :=
t.lift (fun m => m.keyAtIdxD n fallback) (fun _ _ h => h.keyAtIdxD_eq)
@[inline, inherit_doc DTreeMap.getEntryGE?]
def getEntryGE? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option ((a : α) × β a) :=
t.lift (fun m => m.getEntryGE? k) (fun _ _ h => h.getEntryGE?_eq)
@[inline, inherit_doc DTreeMap.getEntryGT?]
def getEntryGT? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option ((a : α) × β a) :=
t.lift (fun m => m.getEntryGT? k) (fun _ _ h => h.getEntryGT?_eq)
@[inline, inherit_doc DTreeMap.getEntryLE?]
def getEntryLE? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option ((a : α) × β a) :=
t.lift (fun m => m.getEntryLE? k) (fun _ _ h => h.getEntryLE?_eq)
@[inline, inherit_doc DTreeMap.getEntryLT?]
def getEntryLT? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option ((a : α) × β a) :=
t.lift (fun m => m.getEntryLT? k) (fun _ _ h => h.getEntryLT?_eq)
@[inline, inherit_doc DTreeMap.getEntryGE]
def getEntryGE [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, (cmp a k).isGE) :
(a : α) × β a :=
t.pliftOn (fun m h' => m.getEntryGE k (h' ▸ h :))
(fun _ _ _ _ h => h.getEntryGE_eq)
@[inline, inherit_doc DTreeMap.getEntryGT]
def getEntryGT [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, cmp a k = .gt) :
(a : α) × β a :=
t.pliftOn (fun m h' => m.getEntryGT k (h' ▸ h :))
(fun _ _ _ _ h => h.getEntryGT_eq)
@[inline, inherit_doc DTreeMap.getEntryLE]
def getEntryLE [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, (cmp a k).isLE) :
(a : α) × β a :=
t.pliftOn (fun m h' => m.getEntryLE k (h' ▸ h :))
(fun _ _ _ _ h => h.getEntryLE_eq)
@[inline, inherit_doc DTreeMap.getEntryLT]
def getEntryLT [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, cmp a k = .lt) :
(a : α) × β a :=
t.pliftOn (fun m h' => m.getEntryLT k (h' ▸ h :))
(fun _ _ _ _ h => h.getEntryLT_eq)
@[inline, inherit_doc DTreeMap.getEntryGE!]
def getEntryGE! [TransCmp cmp] [Inhabited (Sigma β)] (t : ExtDTreeMap α β cmp) (k : α) : (a : α) × β a :=
t.lift (fun m => m.getEntryGE! k) (fun _ _ h => h.getEntryGE!_eq)
@[inline, inherit_doc DTreeMap.getEntryGT!]
def getEntryGT! [TransCmp cmp] [Inhabited (Sigma β)] (t : ExtDTreeMap α β cmp) (k : α) : (a : α) × β a :=
t.lift (fun m => m.getEntryGT! k) (fun _ _ h => h.getEntryGT!_eq)
@[inline, inherit_doc DTreeMap.getEntryLE!]
def getEntryLE! [TransCmp cmp] [Inhabited (Sigma β)] (t : ExtDTreeMap α β cmp) (k : α) : (a : α) × β a :=
t.lift (fun m => m.getEntryLE! k) (fun _ _ h => h.getEntryLE!_eq)
@[inline, inherit_doc DTreeMap.getEntryLT!]
def getEntryLT! [TransCmp cmp] [Inhabited (Sigma β)] (t : ExtDTreeMap α β cmp) (k : α) : (a : α) × β a :=
t.lift (fun m => m.getEntryLT! k) (fun _ _ h => h.getEntryLT!_eq)
@[inline, inherit_doc DTreeMap.getEntryGED]
def getEntryGED [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : Sigma β) : (a : α) × β a :=
t.lift (fun m => m.getEntryGED k fallback) (fun _ _ h => h.getEntryGED_eq)
@[inline, inherit_doc DTreeMap.getEntryGTD]
def getEntryGTD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : Sigma β) : (a : α) × β a :=
t.lift (fun m => m.getEntryGTD k fallback) (fun _ _ h => h.getEntryGTD_eq)
@[inline, inherit_doc DTreeMap.getEntryLED]
def getEntryLED [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : Sigma β) : (a : α) × β a :=
t.lift (fun m => m.getEntryLED k fallback) (fun _ _ h => h.getEntryLED_eq)
@[inline, inherit_doc DTreeMap.getEntryLTD]
def getEntryLTD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : Sigma β) : (a : α) × β a :=
t.lift (fun m => m.getEntryLTD k fallback) (fun _ _ h => h.getEntryLTD_eq)
@[inline, inherit_doc DTreeMap.getKeyGE?]
def getKeyGE? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option α :=
t.lift (fun m => m.getKeyGE? k) (fun _ _ h => h.getKeyGE?_eq)
@[inline, inherit_doc DTreeMap.getKeyGT?]
def getKeyGT? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option α :=
t.lift (fun m => m.getKeyGT? k) (fun _ _ h => h.getKeyGT?_eq)
@[inline, inherit_doc DTreeMap.getKeyLE?]
def getKeyLE? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option α :=
t.lift (fun m => m.getKeyLE? k) (fun _ _ h => h.getKeyLE?_eq)
@[inline, inherit_doc DTreeMap.getKeyLT?]
def getKeyLT? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option α :=
t.lift (fun m => m.getKeyLT? k) (fun _ _ h => h.getKeyLT?_eq)
@[inline, inherit_doc DTreeMap.getKeyGE]
def getKeyGE [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, (cmp a k).isGE) : α :=
t.pliftOn (fun m h' => m.getKeyGE k (h' ▸ h :))
(fun _ _ _ _ h => h.getKeyGE_eq)
@[inline, inherit_doc DTreeMap.getKeyGT]
def getKeyGT [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, cmp a k = .gt) : α :=
t.pliftOn (fun m h' => m.getKeyGT k (h' ▸ h :))
(fun _ _ _ _ h => h.getKeyGT_eq)
@[inline, inherit_doc DTreeMap.getKeyLE]
def getKeyLE [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, (cmp a k).isLE) : α :=
t.pliftOn (fun m h' => m.getKeyLE k (h' ▸ h :))
(fun _ _ _ _ h => h.getKeyLE_eq)
@[inline, inherit_doc DTreeMap.getKeyLT]
def getKeyLT [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, cmp a k = .lt) : α :=
t.pliftOn (fun m h' => m.getKeyLT k (h' ▸ h :))
(fun _ _ _ _ h => h.getKeyLT_eq)
@[inline, inherit_doc DTreeMap.getKeyGE!]
def getKeyGE! [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (k : α) : α :=
t.lift (fun m => m.getKeyGE! k) (fun _ _ h => h.getKeyGE!_eq)
@[inline, inherit_doc DTreeMap.getKeyGT!]
def getKeyGT! [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (k : α) : α :=
t.lift (fun m => m.getKeyGT! k) (fun _ _ h => h.getKeyGT!_eq)
@[inline, inherit_doc DTreeMap.getKeyLE!]
def getKeyLE! [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (k : α) : α :=
t.lift (fun m => m.getKeyLE! k) (fun _ _ h => h.getKeyLE!_eq)
@[inline, inherit_doc DTreeMap.getKeyLT!]
def getKeyLT! [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (k : α) : α :=
t.lift (fun m => m.getKeyLT! k) (fun _ _ h => h.getKeyLT!_eq)
@[inline, inherit_doc DTreeMap.getKeyGED]
def getKeyGED [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : α) : α :=
t.lift (fun m => m.getKeyGED k fallback) (fun _ _ h => h.getKeyGED_eq)
@[inline, inherit_doc DTreeMap.getKeyGTD]
def getKeyGTD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : α) : α :=
t.lift (fun m => m.getKeyGTD k fallback) (fun _ _ h => h.getKeyGTD_eq)
@[inline, inherit_doc DTreeMap.getKeyLED]
def getKeyLED [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : α) : α :=
t.lift (fun m => m.getKeyLED k fallback) (fun _ _ h => h.getKeyLED_eq)
@[inline, inherit_doc DTreeMap.getKeyLTD]
def getKeyLTD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : α) : α :=
t.lift (fun m => m.getKeyLTD k fallback) (fun _ _ h => h.getKeyLTD_eq)
namespace Const
variable {β : Type v}
@[inline, inherit_doc ExtDTreeMap.getThenInsertIfNew?]
def getThenInsertIfNew? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (b : β) :
Option β × ExtDTreeMap α β cmp :=
t.lift (fun m => let m' := DTreeMap.Const.getThenInsertIfNew? m a b; (m'.1, mk m'.2))
(fun m m' h =>
Prod.ext
((DTreeMap.Const.getThenInsertIfNew?_fst (t := m)).symm ▸
(DTreeMap.Const.getThenInsertIfNew?_fst (t := m')).symm ▸
h.constGet?_eq)
(sound <|
(DTreeMap.Const.getThenInsertIfNew?_snd (t := m)).symm ▸
(DTreeMap.Const.getThenInsertIfNew?_snd (t := m')).symm ▸
h.insertIfNew a b))
@[inline, inherit_doc ExtDTreeMap.get?]
def get? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) : Option β :=
t.lift (fun m => DTreeMap.Const.get? m a)
(fun _ _ h => h.constGet?_eq)
@[inline, inherit_doc ExtDTreeMap.get]
def get [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (h : a ∈ t) : β :=
t.pliftOn (fun m h' => DTreeMap.Const.get m a (h' ▸ h :))
(fun _ _ _ _ h => h.constGet_eq)
@[inline, inherit_doc ExtDTreeMap.get!]
def get! [TransCmp cmp] [Inhabited β] (t : ExtDTreeMap α β cmp) (a : α) : β :=
t.lift (fun m => DTreeMap.Const.get! m a)
(fun _ _ h => h.constGet!_eq)
@[inline, inherit_doc ExtDTreeMap.getD]
def getD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (fallback : β) : β :=
t.lift (fun m => DTreeMap.Const.getD m a fallback)
(fun _ _ h => h.constGetD_eq)
@[inline, inherit_doc ExtDTreeMap.minEntry?]
def minEntry? [TransCmp cmp] (t : ExtDTreeMap α β cmp) : Option (α × β) :=
t.lift (fun m => DTreeMap.Const.minEntry? m)
(fun _ _ h => h.constMinEntry?_eq)
@[inline, inherit_doc ExtDTreeMap.minEntry]
def minEntry [TransCmp cmp] (t : ExtDTreeMap α β cmp) (h : t ≠ ∅) : α × β :=
t.pliftOn (fun m h' => DTreeMap.Const.minEntry m (h' ▸ isEmpty_eq_false_iff.mpr h :))
(fun _ _ _ _ h => h.constMinEntry_eq)
@[inline, inherit_doc ExtDTreeMap.minEntry!]
def minEntry! [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α β cmp) : α × β :=
t.lift (fun m => DTreeMap.Const.minEntry! m)
(fun _ _ h => h.constMinEntry!_eq)
@[inline, inherit_doc ExtDTreeMap.minEntryD]
def minEntryD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (fallback : α × β) : α × β :=
t.lift (fun m => DTreeMap.Const.minEntryD m fallback)
(fun _ _ h => h.constMinEntryD_eq)
@[inline, inherit_doc ExtDTreeMap.maxEntry?]
def maxEntry? [TransCmp cmp] (t : ExtDTreeMap α β cmp) : Option (α × β) :=
t.lift (fun m => DTreeMap.Const.maxEntry? m)
(fun _ _ h => h.constMaxEntry?_eq)
@[inline, inherit_doc ExtDTreeMap.maxEntry]
def maxEntry [TransCmp cmp] (t : ExtDTreeMap α β cmp) (h : t ≠ ∅) : α × β :=
t.pliftOn (fun m h' => DTreeMap.Const.maxEntry m (h' ▸ isEmpty_eq_false_iff.mpr h :))
(fun _ _ _ _ h => h.constMaxEntry_eq)
@[inline, inherit_doc ExtDTreeMap.maxEntry!]
def maxEntry! [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α β cmp) : α × β :=
t.lift (fun m => DTreeMap.Const.maxEntry! m)
(fun _ _ h => h.constMaxEntry!_eq)
@[inline, inherit_doc ExtDTreeMap.maxEntryD]
def maxEntryD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (fallback : α × β) : α × β :=
t.lift (fun m => DTreeMap.Const.maxEntryD m fallback)
(fun _ _ h => h.constMaxEntryD_eq)
@[inline, inherit_doc ExtDTreeMap.entryAtIdx?]
def entryAtIdx? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) : Option (α × β) :=
t.lift (fun m => DTreeMap.Const.entryAtIdx? m n)
(fun _ _ h => h.constEntryAtIdx?_eq)
@[inline, inherit_doc ExtDTreeMap.entryAtIdx]
def entryAtIdx [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) (h : n < t.size) : α × β :=
t.pliftOn (fun m h' => DTreeMap.Const.entryAtIdx m n (h' ▸ h :))
(fun _ _ _ _ h => h.constEntryAtIdx_eq)
@[inline, inherit_doc ExtDTreeMap.entryAtIdx!]
def entryAtIdx! [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α β cmp) (n : Nat) : α × β :=
t.lift (fun m => DTreeMap.Const.entryAtIdx! m n)
(fun _ _ h => h.constEntryAtIdx!_eq)
@[inline, inherit_doc ExtDTreeMap.entryAtIdxD]
def entryAtIdxD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat)
(fallback : α × β) : α × β :=
t.lift (fun m => DTreeMap.Const.entryAtIdxD m n fallback)
(fun _ _ h => h.constEntryAtIdxD_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryGE?]
def getEntryGE? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryGE? m k)
(fun _ _ h => h.constGetEntryGE?_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryGT?]
def getEntryGT? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryGT? m k)
(fun _ _ h => h.constGetEntryGT?_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryLE?]
def getEntryLE? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryLE? m k)
(fun _ _ h => h.constGetEntryLE?_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryLT?]
def getEntryLT? [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) : Option (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryLT? m k)
(fun _ _ h => h.constGetEntryLT?_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryGE]
def getEntryGE [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, (cmp a k).isGE) :
α × β :=
t.pliftOn (fun m h' => DTreeMap.Const.getEntryGE m k (h' ▸ h :))
(fun _ _ _ _ h => h.constGetEntryGE_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryGT]
def getEntryGT [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, cmp a k = .gt) :
α × β :=
t.pliftOn (fun m h' => DTreeMap.Const.getEntryGT m k (h' ▸ h :))
(fun _ _ _ _ h => h.constGetEntryGT_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryLE]
def getEntryLE [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, (cmp a k).isLE) :
α × β :=
t.pliftOn (fun m h' => DTreeMap.Const.getEntryLE m k (h' ▸ h :))
(fun _ _ _ _ h => h.constGetEntryLE_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryLT]
def getEntryLT [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : ∃ a ∈ t, cmp a k = .lt) :
α × β :=
t.pliftOn (fun m h' => DTreeMap.Const.getEntryLT m k (h' ▸ h :))
(fun _ _ _ _ h => h.constGetEntryLT_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryGE!]
def getEntryGE! [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α β cmp) (k : α) : (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryGE! m k)
(fun _ _ h => h.constGetEntryGE!_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryGT!]
def getEntryGT! [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α β cmp) (k : α) : (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryGT! m k)
(fun _ _ h => h.constGetEntryGT!_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryLE!]
def getEntryLE! [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α β cmp) (k : α) : (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryLE! m k)
(fun _ _ h => h.constGetEntryLE!_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryLT!]
def getEntryLT! [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α β cmp) (k : α) : (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryLT! m k)
(fun _ _ h => h.constGetEntryLT!_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryGED]
def getEntryGED [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : α × β) : (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryGED m k fallback)
(fun _ _ h => h.constGetEntryGED_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryGTD]
def getEntryGTD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : α × β) : (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryGTD m k fallback)
(fun _ _ h => h.constGetEntryGTD_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryLED]
def getEntryLED [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : α × β) : (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryLED m k fallback)
(fun _ _ h => h.constGetEntryLED_eq)
@[inline, inherit_doc ExtDTreeMap.getEntryLTD]
def getEntryLTD [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : α × β) : (α × β) :=
t.lift (fun m => DTreeMap.Const.getEntryLTD m k fallback)
(fun _ _ h => h.constGetEntryLTD_eq)
end Const
variable {δ : Type w} {m : Type w → Type w₂} [Monad m] [LawfulMonad m]
@[inline, inherit_doc DTreeMap.filter]
def filter (f : (a : α) → β a → Bool) (t : ExtDTreeMap α β cmp) : ExtDTreeMap α β cmp :=
t.lift (fun m => mk (m.filter f))
(fun _ _ h => sound (h.filter f))
@[inline, inherit_doc DTreeMap.filterMap]
def filterMap (f : (a : α) → β a → Option (γ a)) (t : ExtDTreeMap α β cmp) : ExtDTreeMap α γ cmp :=
t.lift (fun m => mk (m.filterMap f))
(fun _ _ h => sound (h.filterMap f))
@[inline, inherit_doc DTreeMap.map]
def map (f : (a : α) → β a → γ a) (t : ExtDTreeMap α β cmp) : ExtDTreeMap α γ cmp :=
t.lift (fun m => mk (m.map f))
(fun _ _ h => sound (h.map f))
@[inline, inherit_doc DTreeMap.foldlM]
def foldlM [TransCmp cmp] (f : δ → (a : α) → β a → m δ) (init : δ) (t : ExtDTreeMap α β cmp) : m δ :=
t.lift (fun m => m.foldlM f init) (fun _ _ h => h.foldlM_eq)
@[inline, inherit_doc DTreeMap.foldl]
def foldl [TransCmp cmp] (f : δ → (a : α) → β a → δ) (init : δ) (t : ExtDTreeMap α β cmp) : δ :=
t.lift (fun m => m.foldl f init) (fun _ _ h => h.foldl_eq)
@[inline, inherit_doc DTreeMap.foldrM]
def foldrM [TransCmp cmp] (f : (a : α) → β a → δ → m δ) (init : δ) (t : ExtDTreeMap α β cmp) : m δ :=
t.lift (fun m => m.foldrM f init) (fun _ _ h => h.foldrM_eq)
@[inline, inherit_doc DTreeMap.foldr]
def foldr [TransCmp cmp] (f : (a : α) → β a → δ → δ) (init : δ) (t : ExtDTreeMap α β cmp) : δ :=
t.lift (fun m => m.foldr f init) (fun _ _ h => h.foldr_eq)
@[inline, inherit_doc DTreeMap.partition]
def partition [TransCmp cmp] (f : (a : α) → β a → Bool)
(t : ExtDTreeMap α β cmp) : ExtDTreeMap α β cmp × ExtDTreeMap α β cmp :=
t.foldl (init := (∅, ∅)) fun ⟨l, r⟩ a b =>
if f a b then
(l.insert a b, r)
else
(l, r.insert a b)
@[inline, inherit_doc DTreeMap.forM]
def forM [TransCmp cmp] (f : (a : α) → β a → m PUnit) (t : ExtDTreeMap α β cmp) : m PUnit :=
t.lift (fun m => m.forM f) (fun _ _ h => h.forM_eq (f := fun x => f x.1 x.2))
@[inline, inherit_doc DTreeMap.forIn]
def forIn [TransCmp cmp] (f : (a : α) → β a → δ → m (ForInStep δ)) (init : δ) (t : ExtDTreeMap α β cmp) : m δ :=
t.lift (fun m => m.forIn f init) (fun _ _ h => h.forIn_eq (f := fun x => f x.1 x.2))
instance [TransCmp cmp] [Monad m] [LawfulMonad m] : ForM m (ExtDTreeMap α β cmp) ((a : α) × β a) where
forM t f := forM (fun a b => f ⟨a, b⟩) t
instance [TransCmp cmp] [Monad m] [LawfulMonad m] : ForIn m (ExtDTreeMap α β cmp) ((a : α) × β a) where
forIn m init f := forIn (fun a b acc => f ⟨a, b⟩ acc) init m
namespace Const
variable {β : Type v}
/-!
We do not define `ForM` and `ForIn` instances that are specialized to constant `β`. Instead, we
define uncurried versions of `forM` and `forIn` that will be used in the `Const` lemmas and to
define the `ForM` and `ForIn` instances for `ExtDTreeMap`.
-/
@[inline, inherit_doc ExtDTreeMap.forM]
def forMUncurried [TransCmp cmp] (f : α × β → m PUnit) (t : ExtDTreeMap α β cmp) : m PUnit :=
t.forM fun a b => f ⟨a, b⟩
@[inline, inherit_doc ExtDTreeMap.forIn]
def forInUncurried [TransCmp cmp] (f : α × β → δ → m (ForInStep δ)) (init : δ) (t : ExtDTreeMap α β cmp) : m δ :=
t.forIn (fun a b acc => f ⟨a, b⟩ acc) init
end Const
@[inline, inherit_doc DTreeMap.any]
def any [TransCmp cmp] (t : ExtDTreeMap α β cmp) (p : (a : α) → β a → Bool) : Bool :=
t.lift (fun m => m.any p) (fun _ _ h => h.any_eq)
@[inline, inherit_doc DTreeMap.all]
def all [TransCmp cmp] (t : ExtDTreeMap α β cmp) (p : (a : α) → β a → Bool) : Bool :=
t.lift (fun m => m.all p) (fun _ _ h => h.all_eq)
@[inline, inherit_doc DTreeMap.keys]
def keys [TransCmp cmp] (t : ExtDTreeMap α β cmp) : List α :=
t.lift (fun m => m.keys) (fun _ _ h => h.keys_eq)
@[inline, inherit_doc DTreeMap.keysArray]
def keysArray [TransCmp cmp] (t : ExtDTreeMap α β cmp) : Array α :=
t.lift (fun m => m.keysArray) (fun _ _ h => h.keysArray_eq)
@[inline, inherit_doc DTreeMap.values]
def values [TransCmp cmp] {β : Type v} (t : ExtDTreeMap α β cmp) : List β :=
t.lift (fun m => m.values) (fun _ _ h => h.values_eq)
@[inline, inherit_doc DTreeMap.valuesArray]
def valuesArray [TransCmp cmp] {β : Type v} (t : ExtDTreeMap α β cmp) : Array β :=
t.lift (fun m => m.valuesArray) (fun _ _ h => h.valuesArray_eq)
@[inline, inherit_doc DTreeMap.toList]
def toList [TransCmp cmp] (t : ExtDTreeMap α β cmp) : List ((a : α) × β a) :=
t.lift (fun m => m.toList) (fun _ _ h => h.toList_eq)
@[inline, inherit_doc DTreeMap.ofList]
def ofList (l : List ((a : α) × β a)) (cmp : α → α → Ordering := by exact compare) :
ExtDTreeMap α β cmp :=
mk (.ofList l cmp)
@[inline, inherit_doc DTreeMap.toArray]
def toArray [TransCmp cmp] (t : ExtDTreeMap α β cmp) : Array ((a : α) × β a) :=
t.lift (fun m => m.toArray) (fun _ _ h => h.toArray_eq)
@[inline, inherit_doc DTreeMap.ofArray]
def ofArray (a : Array ((a : α) × β a)) (cmp : α → α → Ordering := by exact compare) :
ExtDTreeMap α β cmp :=
mk (.ofArray a cmp)
@[inline, inherit_doc DTreeMap.modify]
def modify [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (f : β a → β a) :
ExtDTreeMap α β cmp :=
t.lift (fun m => mk (m.modify a f))
(fun _ _ h => sound (h.modify a f))
@[inline, inherit_doc DTreeMap.alter]
def alter [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (f : Option (β a) → Option (β a)) :
ExtDTreeMap α β cmp :=
t.lift (fun m => mk (m.alter a f))
(fun _ _ h => sound (h.alter a f))
@[inline, inherit_doc DTreeMap.mergeWith]
def mergeWith [TransCmp cmp] [LawfulEqCmp cmp] (mergeFn : (a : α) → β a → β a → β a) (t₁ t₂ : ExtDTreeMap α β cmp) :
ExtDTreeMap α β cmp :=
t₁.liftOn₂ t₂ (fun m₁ m₂ => mk (m₁.mergeWith mergeFn m₂))
(fun _ _ _ _ h₁ h₂ => sound (h₁.mergeWith mergeFn h₂))
namespace Const
variable {β : Type v}
@[inline, inherit_doc ExtDTreeMap.toList]
def toList [TransCmp cmp] (t : ExtDTreeMap α β cmp) : List (α × β) :=
t.lift (fun m => DTreeMap.Const.toList m)
(fun _ _ h => h.constToList_eq)
@[inline, inherit_doc ExtDTreeMap.ofList]
def ofList (l : List (α × β)) (cmp : α → α → Ordering := by exact compare) : ExtDTreeMap α β cmp :=
mk (DTreeMap.Const.ofList l cmp)
@[inline, inherit_doc ExtDTreeMap.toArray]
def toArray [TransCmp cmp] (t : ExtDTreeMap α β cmp) : Array (α × β) :=
t.lift (fun m => DTreeMap.Const.toArray m)
(fun _ _ h => h.constToArray_eq)
@[inline, inherit_doc ExtDTreeMap.ofList]
def ofArray (a : Array (α × β)) (cmp : α → α → Ordering := by exact compare) : ExtDTreeMap α β cmp :=
mk (DTreeMap.Const.ofArray a cmp)
@[inline, inherit_doc DTreeMap.Const.unitOfList]
def unitOfList (l : List α) (cmp : α → α → Ordering := by exact compare) : ExtDTreeMap α Unit cmp :=
mk (DTreeMap.Const.unitOfList l cmp)
@[inline, inherit_doc DTreeMap.Const.unitOfArray]
def unitOfArray (a : Array α) (cmp : α → α → Ordering := by exact compare) : ExtDTreeMap α Unit cmp :=
mk (DTreeMap.Const.unitOfArray a cmp)
@[inline, inherit_doc ExtDTreeMap.modify]
def modify [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (f : β → β) : ExtDTreeMap α β cmp :=
t.lift (fun m => mk (DTreeMap.Const.modify m a f))
(fun _ _ h => sound (h.constModify a f))
@[inline, inherit_doc ExtDTreeMap.alter]
def alter [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (f : Option β → Option β) : ExtDTreeMap α β cmp :=
t.lift (fun m => mk (DTreeMap.Const.alter m a f))
(fun _ _ h => sound (h.constAlter a f))
@[inline, inherit_doc ExtDTreeMap.mergeWith]
def mergeWith [TransCmp cmp] (mergeFn : α → β → β → β) (t₁ t₂ : ExtDTreeMap α β cmp) : ExtDTreeMap α β cmp :=
t₁.liftOn₂ t₂ (fun m₁ m₂ => mk (DTreeMap.Const.mergeWith mergeFn m₁ m₂))
(fun _ _ _ _ h₁ h₂ => sound (h₁.constMergeWith mergeFn h₂))
end Const
@[inline, inherit_doc DTreeMap.insertMany]
def insertMany [TransCmp cmp] {ρ} [ForIn Id ρ ((a : α) × β a)] (t : ExtDTreeMap α β cmp) (l : ρ) :
ExtDTreeMap α β cmp := Id.run do
let mut acc : { a // ∀ P : _ → Prop, P t → (∀ t a b, P t → P (t.insert a b)) → P a } :=
⟨t, fun _ h _ => h⟩
for ⟨a, b⟩ in l do
acc := ⟨acc.1.insert a b, fun P h h' => h' acc.1 a b (acc.2 P h h')⟩
return acc.1
@[inline, inherit_doc DTreeMap.eraseMany]
def eraseMany [TransCmp cmp] {ρ} [ForIn Id ρ α] (t : ExtDTreeMap α β cmp) (l : ρ) :
ExtDTreeMap α β cmp := Id.run do
let mut acc : { a // ∀ P : _ → Prop, P t → (∀ t a, P t → P (t.erase a)) → P a } :=
⟨t, fun _ h _ => h⟩
for a in l do
acc := ⟨acc.1.erase a, fun P h h' => h' acc.1 a (acc.2 P h h')⟩
return acc.1
namespace Const
variable {β : Type v}
@[inline, inherit_doc ExtDTreeMap.insertMany]
def insertMany [TransCmp cmp] {ρ} [ForIn Id ρ (α × β)] (t : ExtDTreeMap α β cmp) (l : ρ) :
ExtDTreeMap α β cmp := Id.run do
let mut acc : { a // ∀ P : _ → Prop, P t → (∀ t a b, P t → P (t.insert a b)) → P a } :=
⟨t, fun _ h _ => h⟩
for ⟨a, b⟩ in l do
acc := ⟨acc.1.insert a b, fun P h h' => h' acc.1 a b (acc.2 P h h')⟩
return acc.1
@[inline, inherit_doc DTreeMap.Const.insertManyIfNewUnit]
def insertManyIfNewUnit [TransCmp cmp] {ρ} [ForIn Id ρ α] (t : ExtDTreeMap α Unit cmp) (l : ρ) :
ExtDTreeMap α Unit cmp := Id.run do
let mut acc : { a // ∀ P : _ → Prop, P t → (∀ t a, P t → P (t.insertIfNew a ())) → P a } :=
⟨t, fun _ h _ => h⟩
for a in l do
acc := ⟨acc.1.insertIfNew a (), fun P h h' => h' acc.1 a (acc.2 P h h')⟩
return acc.1
end Const
@[inline, inherit_doc DTreeMap.union]
def union [TransCmp cmp] (m₁ m₂ : ExtDTreeMap α β cmp) : ExtDTreeMap α β cmp := lift₂ (fun x y : DTreeMap α β cmp => mk (x.union y))
(fun a b c d equiv₁ equiv₂ => by
simp only [DTreeMap.union_eq, mk'.injEq]
apply Quotient.sound
apply DTreeMap.Equiv.union_congr
. exact equiv₁
. exact equiv₂) m₁ m₂
instance [TransCmp cmp] : Union (ExtDTreeMap α β cmp) := ⟨union⟩
@[inline, inherit_doc DTreeMap.union]
def inter [TransCmp cmp] (m₁ m₂ : ExtDTreeMap α β cmp) : ExtDTreeMap α β cmp := lift₂ (fun x y : DTreeMap α β cmp => mk (x.inter y))
(fun a b c d equiv₁ equiv₂ => by
simp only [DTreeMap.inter_eq, mk'.injEq]
apply Quotient.sound
apply DTreeMap.Equiv.inter_congr
. exact equiv₁
. exact equiv₂) m₁ m₂
instance [TransCmp cmp] : Inter (ExtDTreeMap α β cmp) := ⟨inter⟩
instance [LawfulEqCmp cmp] [TransCmp cmp] [∀ k, BEq (β k)] : BEq (ExtDTreeMap α β cmp) where
beq := lift₂ (fun x y : DTreeMap α β cmp => x.beq y) fun _ _ _ _ => DTreeMap.Equiv.beq_congr
instance [LawfulEqCmp cmp] [TransCmp cmp] [∀ k, BEq (β k)] [∀ k, ReflBEq (β k)] : ReflBEq (ExtDTreeMap α β cmp) where
rfl {a} := a.inductionOn fun _ => DTreeMap.Equiv.beq <| DTreeMap.Equiv.rfl
instance [LawfulEqCmp cmp] [TransCmp cmp] [∀ k, BEq (β k)] [∀ k, LawfulBEq (β k)] : LawfulBEq (ExtDTreeMap α β cmp) where
eq_of_beq {a} {b} := a.inductionOn₂ b fun _ _ h => sound <| DTreeMap.equiv_of_beq h
instance {α : Type u} {β : α → Type v} {cmp : α → α → Ordering} [TransCmp cmp] [LawfulEqCmp cmp] [∀ k, BEq (β k)] [∀ k, LawfulBEq (β k)] : DecidableEq (ExtDTreeMap α β cmp) :=
fun _ _ => decidable_of_iff _ beq_iff_eq
namespace Const
variable {β : Type v}
@[inline, inherit_doc DTreeMap.beq]
def beq [TransCmp cmp] [BEq β] (m₁ m₂ : ExtDTreeMap α (fun _ => β) cmp) : Bool := lift₂ (fun x y : DTreeMap α (fun _ => β) cmp => DTreeMap.Const.beq x y)
(fun _ _ _ _ => DTreeMap.Const.Equiv.beq_congr) m₁ m₂
theorem beq_of_eq [TransCmp cmp] [BEq β] [ReflBEq β] (m₁ m₂ : ExtDTreeMap α (fun _ => β) cmp) : m₁ = m₂ → Const.beq m₁ m₂ :=
m₁.inductionOn₂ m₂ fun _ _ h => DTreeMap.Const.Equiv.beq <| exact h
theorem eq_of_beq [TransCmp cmp] [LawfulEqCmp cmp] [BEq β] [LawfulBEq β] (m₁ m₂ : ExtDTreeMap α (fun _ => β) cmp) : Const.beq m₁ m₂ → m₁ = m₂ :=
m₁.inductionOn₂ m₂ fun _ _ h => sound <| DTreeMap.Const.equiv_of_beq h
end Const
@[inline, inherit_doc DTreeMap.diff]
def diff [TransCmp cmp] (m₁ m₂ : ExtDTreeMap α β cmp) : ExtDTreeMap α β cmp := lift₂ (fun x y : DTreeMap α β cmp => mk (x.diff y))
(fun a b c d equiv₁ equiv₂ => by
simp only [DTreeMap.diff_eq, mk'.injEq]
apply Quotient.sound
apply DTreeMap.Equiv.diff_congr
. exact equiv₁
. exact equiv₂) m₁ m₂
instance [TransCmp cmp] : SDiff (ExtDTreeMap α β cmp) := ⟨diff⟩
instance [TransCmp cmp] [Repr α] [(a : α) → Repr (β a)] : Repr (ExtDTreeMap α β cmp) where
reprPrec m prec := Repr.addAppParen ("Std.ExtDTreeMap.ofList " ++ repr m.toList) prec
end ExtDTreeMap
end Std