Tree map lemmas

This file contains lemmas about Std.Data.TreeMap. Most of the lemmas require TransCmp cmp for the comparison function cmp.

@[simp]

theorem Std.TreeMap.isEmpty_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} : ∅.isEmpty = true

@[simp]

theorem Std.TreeMap.isEmpty_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).isEmpty = false

theorem Std.TreeMap.mem_iff_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {k : α} : k ∈ t ↔ t.contains k = true

theorem Std.TreeMap.contains_congr {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} (hab : cmp k k' = Ordering.eq) : t.contains k = t.contains k'

theorem Std.TreeMap.mem_congr {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} (hab : cmp k k' = Ordering.eq) : k ∈ t ↔ k' ∈ t

@[simp]

theorem Std.TreeMap.contains_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} {k : α} : ∅.contains k = false

@[simp]

theorem Std.TreeMap.not_mem_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} {k : α} : ¬k ∈ ∅

theorem Std.TreeMap.contains_of_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : t.isEmpty = true → t.contains a = false

theorem Std.TreeMap.not_mem_of_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : t.isEmpty = true → ¬a ∈ t

theorem Std.TreeMap.isEmpty_eq_false_iff_exists_contains_eq_true {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.isEmpty = false ↔ ∃ (a : α), t.contains a = true

theorem Std.TreeMap.isEmpty_eq_false_iff_exists_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.isEmpty = false ↔ ∃ (a : α), a ∈ t

theorem Std.TreeMap.isEmpty_eq_false_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} (hc : t.contains a = true) : t.isEmpty = false

theorem Std.TreeMap.isEmpty_iff_forall_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.isEmpty = true ↔ ∀ (a : α), t.contains a = false

theorem Std.TreeMap.isEmpty_iff_forall_not_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.isEmpty = true ↔ ∀ (a : α), ¬a ∈ t

@[simp]

theorem Std.TreeMap.insert_eq_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {p : α × β} : Insert.insert p t = t.insert p.fst p.snd

@[simp]

theorem Std.TreeMap.singleton_eq_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {p : α × β} : {p} = ∅.insert p.fst p.snd

@[simp]

theorem Std.TreeMap.contains_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [h : TransCmp cmp] {k a : α} {v : β} : (t.insert k v).contains a = (cmp k a == Ordering.eq || t.contains a)

@[simp]

theorem Std.TreeMap.mem_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} : a ∈ t.insert k v ↔ cmp k a = Ordering.eq ∨ a ∈ t

theorem Std.TreeMap.contains_insert_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).contains k = true

theorem Std.TreeMap.mem_insert_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : k ∈ t.insert k v

theorem Std.TreeMap.contains_of_contains_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} : (t.insert k v).contains a = true → cmp k a ≠ Ordering.eq → t.contains a = true

theorem Std.TreeMap.mem_of_mem_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} : a ∈ t.insert k v → cmp k a ≠ Ordering.eq → a ∈ t

@[simp]

theorem Std.TreeMap.size_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} : ∅.size = 0

theorem Std.TreeMap.isEmpty_eq_size_eq_zero {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} : t.isEmpty = (t.size == 0)

theorem Std.TreeMap.size_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).size = if t.contains k = true then t.size else t.size + 1

theorem Std.TreeMap.size_le_size_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : t.size ≤ (t.insert k v).size

theorem Std.TreeMap.size_insert_le {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).size ≤ t.size + 1

@[simp]

theorem Std.TreeMap.erase_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} {k : α} : ∅.erase k = ∅

@[simp]

theorem Std.TreeMap.isEmpty_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : (t.erase k).isEmpty = (t.isEmpty || t.size == 1 && t.contains k)

theorem Std.TreeMap.isEmpty_eq_isEmpty_erase_and_not_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (k : α) : t.isEmpty = ((t.erase k).isEmpty && !t.contains k)

theorem Std.TreeMap.isEmpty_eq_false_of_isEmpty_erase_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (he : (t.erase k).isEmpty = false) : t.isEmpty = false

@[simp]

theorem Std.TreeMap.contains_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} : (t.erase k).contains a = (cmp k a != Ordering.eq && t.contains a)

@[simp]

theorem Std.TreeMap.mem_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} : a ∈ t.erase k ↔ cmp k a ≠ Ordering.eq ∧ a ∈ t

theorem Std.TreeMap.contains_of_contains_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} : (t.erase k).contains a = true → t.contains a = true

theorem Std.TreeMap.mem_of_mem_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} : a ∈ t.erase k → a ∈ t

theorem Std.TreeMap.size_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : (t.erase k).size = if t.contains k = true then t.size - 1 else t.size

theorem Std.TreeMap.size_erase_le {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : (t.erase k).size ≤ t.size

theorem Std.TreeMap.size_le_size_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : t.size ≤ (t.erase k).size + 1

@[simp]

theorem Std.TreeMap.containsThenInsert_fst {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.containsThenInsert k v).fst = t.contains k

@[simp]

theorem Std.TreeMap.containsThenInsert_snd {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.containsThenInsert k v).snd = t.insert k v

@[simp]

theorem Std.TreeMap.containsThenInsertIfNew_fst {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.containsThenInsertIfNew k v).fst = t.contains k

@[simp]

theorem Std.TreeMap.containsThenInsertIfNew_snd {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.containsThenInsertIfNew k v).snd = t.insertIfNew k v

@[simp]

theorem Std.TreeMap.get_eq_getElem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {a : α} {h : a ∈ t} : t.get a h = t[a]

@[simp]

theorem Std.TreeMap.get?_eq_getElem? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {a : α} : t.get? a = t[a]?

@[simp]

theorem Std.TreeMap.get!_eq_getElem! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [Inhabited β] {a : α} : t.get! a = t[a]!

@[simp]

theorem Std.TreeMap.getElem?_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {a : α} : ∅[a]? = none

theorem Std.TreeMap.getElem?_of_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : t.isEmpty = true → t[a]? = none

theorem Std.TreeMap.getElem?_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a k : α} {v : β} : (t.insert k v)[a]? = if cmp k a = Ordering.eq then some v else t[a]?

@[simp]

theorem Std.TreeMap.getElem?_insert_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v)[k]? = some v

theorem Std.TreeMap.contains_eq_isSome_getElem? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : t.contains a = t[a]?.isSome

theorem Std.TreeMap.mem_iff_isSome_getElem? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : a ∈ t ↔ t[a]?.isSome = true

theorem Std.TreeMap.getElem?_eq_none_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : t.contains a = false → t[a]? = none

theorem Std.TreeMap.getElem?_eq_none {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : ¬a ∈ t → t[a]? = none

theorem Std.TreeMap.getElem?_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} : (t.erase k)[a]? = if cmp k a = Ordering.eq then none else t[a]?

@[simp]

theorem Std.TreeMap.getElem?_erase_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : (t.erase k)[k]? = none

theorem Std.TreeMap.getElem?_congr {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a b : α} (hab : cmp a b = Ordering.eq) : t[a]? = t[b]?

theorem Std.TreeMap.getElem_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} {h₁ : a ∈ t.insert k v} : (t.insert k v)[a] = if h₂ : cmp k a = Ordering.eq then v else t.get a ⋯

@[simp]

theorem Std.TreeMap.getElem_insert_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v)[k] = v

@[simp]

theorem Std.TreeMap.getElem_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {h' : a ∈ t.erase k} : (t.erase k)[a] = t[a]

theorem Std.TreeMap.getElem?_eq_some_getElem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} {h : a ∈ t} : t[a]? = some t[a]

theorem Std.TreeMap.getElem_congr {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a b : α} (hab : cmp a b = Ordering.eq) {h' : a ∈ t} : t[a] = t[b]

@[simp]

theorem Std.TreeMap.getElem!_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] [Inhabited β] {a : α} : ∅[a]! = default

theorem Std.TreeMap.getElem!_of_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {a : α} : t.isEmpty = true → t[a]! = default

theorem Std.TreeMap.getElem!_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {k a : α} {v : β} : (t.insert k v)[a]! = if cmp k a = Ordering.eq then v else t[a]!

@[simp]

theorem Std.TreeMap.getElem!_insert_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {k : α} {v : β} : (t.insert k v)[k]! = v

theorem Std.TreeMap.getElem!_eq_default_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {a : α} : t.contains a = false → t[a]! = default

theorem Std.TreeMap.getElem!_eq_default {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {a : α} : ¬a ∈ t → t[a]! = default

theorem Std.TreeMap.getElem!_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {k a : α} : (t.erase k)[a]! = if cmp k a = Ordering.eq then default else t[a]!

@[simp]

theorem Std.TreeMap.getElem!_erase_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {k : α} : (t.erase k)[k]! = default

theorem Std.TreeMap.getElem?_eq_some_getElem!_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {a : α} : t.contains a = true → t[a]? = some t[a]!

theorem Std.TreeMap.getElem?_eq_some_getElem! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {a : α} : a ∈ t → t[a]? = some t[a]!

theorem Std.TreeMap.getElem!_eq_get!_getElem? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {a : α} : t[a]! = t[a]?.get!

@[deprecated Std.TreeMap.getElem!_eq_get!_getElem? (since := "2025-03-19")]

theorem Std.TreeMap.getElem!_eq_getElem!_getElem? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {a : α} : t[a]! = t[a]?.get!

theorem Std.TreeMap.getElem_eq_getElem! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {a : α} {h : a ∈ t} : t[a] = t[a]!

theorem Std.TreeMap.getElem!_congr {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {a b : α} (hab : cmp a b = Ordering.eq) : t[a]! = t[b]!

@[simp]

theorem Std.TreeMap.getD_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {a : α} {fallback : β} : ∅.getD a fallback = fallback

theorem Std.TreeMap.getD_of_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} {fallback : β} : t.isEmpty = true → t.getD a fallback = fallback

theorem Std.TreeMap.getD_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {fallback v : β} : (t.insert k v).getD a fallback = if cmp k a = Ordering.eq then v else t.getD a fallback

@[simp]

theorem Std.TreeMap.getD_insert_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {fallback v : β} : (t.insert k v).getD k fallback = v

theorem Std.TreeMap.getD_eq_fallback_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} {fallback : β} : t.contains a = false → t.getD a fallback = fallback

theorem Std.TreeMap.getD_eq_fallback {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} {fallback : β} : ¬a ∈ t → t.getD a fallback = fallback

theorem Std.TreeMap.getD_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {fallback : β} : (t.erase k).getD a fallback = if cmp k a = Ordering.eq then fallback else t.getD a fallback

@[simp]

theorem Std.TreeMap.getD_erase_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {fallback : β} : (t.erase k).getD k fallback = fallback

theorem Std.TreeMap.getElem?_eq_some_getD_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} {fallback : β} : t.contains a = true → t.get? a = some (t.getD a fallback)

theorem Std.TreeMap.getElem?_eq_some_getD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} {fallback : β} : a ∈ t → t[a]? = some (t.getD a fallback)

theorem Std.TreeMap.getD_eq_getD_getElem? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} {fallback : β} : t.getD a fallback = t[a]?.getD fallback

theorem Std.TreeMap.getElem_eq_getD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} {fallback : β} {h : a ∈ t} : t[a] = t.getD a fallback

theorem Std.TreeMap.getElem!_eq_getD_default {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {a : α} : t[a]! = t.getD a default

theorem Std.TreeMap.getD_congr {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a b : α} {fallback : β} (hab : cmp a b = Ordering.eq) : t.getD a fallback = t.getD b fallback

@[simp]

theorem Std.TreeMap.getKey?_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} {a : α} : ∅.getKey? a = none

theorem Std.TreeMap.getKey?_of_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : t.isEmpty = true → t.getKey? a = none

theorem Std.TreeMap.getKey?_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a k : α} {v : β} : (t.insert k v).getKey? a = if cmp k a = Ordering.eq then some k else t.getKey? a

@[simp]

theorem Std.TreeMap.getKey?_insert_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).getKey? k = some k

theorem Std.TreeMap.contains_eq_isSome_getKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : t.contains a = (t.getKey? a).isSome

theorem Std.TreeMap.mem_iff_isSome_getKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : a ∈ t ↔ (t.getKey? a).isSome = true

theorem Std.TreeMap.getKey?_eq_none_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : t.contains a = false → t.getKey? a = none

theorem Std.TreeMap.getKey?_eq_none {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} : ¬a ∈ t → t.getKey? a = none

theorem Std.TreeMap.getKey?_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} : (t.erase k).getKey? a = if cmp k a = Ordering.eq then none else t.getKey? a

@[simp]

theorem Std.TreeMap.getKey?_erase_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : (t.erase k).getKey? k = none

theorem Std.TreeMap.compare_getKey?_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : Option.all (fun (x : α) => decide (cmp x k = Ordering.eq)) (t.getKey? k) = true

theorem Std.TreeMap.getKey?_congr {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} (h' : cmp k k' = Ordering.eq) : t.getKey? k = t.getKey? k'

theorem Std.TreeMap.getKey?_eq_some_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k : α} (h' : t.contains k = true) : t.getKey? k = some k

theorem Std.TreeMap.getKey?_eq_some {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k : α} (h' : k ∈ t) : t.getKey? k = some k

theorem Std.TreeMap.getKey_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} {h₁ : a ∈ t.insert k v} : (t.insert k v).getKey a h₁ = if h₂ : cmp k a = Ordering.eq then k else t.getKey a ⋯

@[simp]

theorem Std.TreeMap.getKey_insert_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).getKey k ⋯ = k

@[simp]

theorem Std.TreeMap.getKey_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {h' : a ∈ t.erase k} : (t.erase k).getKey a h' = t.getKey a ⋯

theorem Std.TreeMap.getKey?_eq_some_getKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a : α} {h' : a ∈ t} : t.getKey? a = some (t.getKey a h')

theorem Std.TreeMap.compare_getKey_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (h' : k ∈ t) : cmp (t.getKey k h') k = Ordering.eq

theorem Std.TreeMap.getKey_congr {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k₁ k₂ : α} (h' : cmp k₁ k₂ = Ordering.eq) (h₁ : k₁ ∈ t) : t.getKey k₁ h₁ = t.getKey k₂ ⋯

@[simp]

theorem Std.TreeMap.getKey_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k : α} (h' : k ∈ t) : t.getKey k h' = k

@[simp]

theorem Std.TreeMap.getKey!_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} {a : α} [Inhabited α] : ∅.getKey! a = default

theorem Std.TreeMap.getKey!_of_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {a : α} : t.isEmpty = true → t.getKey! a = default

theorem Std.TreeMap.getKey!_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k a : α} {v : β} : (t.insert k v).getKey! a = if cmp k a = Ordering.eq then k else t.getKey! a

@[simp]

theorem Std.TreeMap.getKey!_insert_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {a : α} {b : β} : (t.insert a b).getKey! a = a

theorem Std.TreeMap.getKey!_eq_default_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {a : α} : t.contains a = false → t.getKey! a = default

theorem Std.TreeMap.getKey!_eq_default {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {a : α} : ¬a ∈ t → t.getKey! a = default

theorem Std.TreeMap.getKey!_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k a : α} : (t.erase k).getKey! a = if cmp k a = Ordering.eq then default else t.getKey! a

@[simp]

theorem Std.TreeMap.getKey!_erase_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} : (t.erase k).getKey! k = default

theorem Std.TreeMap.getKey?_eq_some_getKey!_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {a : α} : t.contains a = true → t.getKey? a = some (t.getKey! a)

theorem Std.TreeMap.getKey?_eq_some_getKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {a : α} : a ∈ t → t.getKey? a = some (t.getKey! a)

theorem Std.TreeMap.getKey!_eq_get!_getKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {a : α} : t.getKey! a = (t.getKey? a).get!

theorem Std.TreeMap.getKey_eq_getKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {a : α} {h : a ∈ t} : t.getKey a h = t.getKey! a

theorem Std.TreeMap.getKey!_congr {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k k' : α} (h' : cmp k k' = Ordering.eq) : t.getKey! k = t.getKey! k'

theorem Std.TreeMap.getKey!_eq_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] [Inhabited α] {k : α} (h' : t.contains k = true) : t.getKey! k = k

theorem Std.TreeMap.getKey!_eq_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] [Inhabited α] {k : α} (h' : k ∈ t) : t.getKey! k = k

@[simp]

theorem Std.TreeMap.getKeyD_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} {a fallback : α} : ∅.getKeyD a fallback = fallback

theorem Std.TreeMap.getKeyD_of_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a fallback : α} : t.isEmpty = true → t.getKeyD a fallback = fallback

theorem Std.TreeMap.getKeyD_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a fallback : α} {v : β} : (t.insert k v).getKeyD a fallback = if cmp k a = Ordering.eq then k else t.getKeyD a fallback

@[simp]

theorem Std.TreeMap.getKeyD_insert_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a fallback : α} {b : β} : (t.insert a b).getKeyD a fallback = a

theorem Std.TreeMap.getKeyD_eq_fallback_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a fallback : α} : t.contains a = false → t.getKeyD a fallback = fallback

theorem Std.TreeMap.getKeyD_eq_fallback {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a fallback : α} : ¬a ∈ t → t.getKeyD a fallback = fallback

theorem Std.TreeMap.getKeyD_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a fallback : α} : (t.erase k).getKeyD a fallback = if cmp k a = Ordering.eq then fallback else t.getKeyD a fallback

@[simp]

theorem Std.TreeMap.getKeyD_erase_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k fallback : α} : (t.erase k).getKeyD k fallback = fallback

theorem Std.TreeMap.getKey?_eq_some_getKeyD_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a fallback : α} : t.contains a = true → t.getKey? a = some (t.getKeyD a fallback)

theorem Std.TreeMap.getKey?_eq_some_getKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a fallback : α} : a ∈ t → t.getKey? a = some (t.getKeyD a fallback)

theorem Std.TreeMap.getKeyD_eq_getD_getKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a fallback : α} : t.getKeyD a fallback = (t.getKey? a).getD fallback

theorem Std.TreeMap.getKey_eq_getKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {a fallback : α} {h : a ∈ t} : t.getKey a h = t.getKeyD a fallback

theorem Std.TreeMap.getKey!_eq_getKeyD_default {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {a : α} : t.getKey! a = t.getKeyD a default

theorem Std.TreeMap.getKeyD_congr {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' fallback : α} (h' : cmp k k' = Ordering.eq) : t.getKeyD k fallback = t.getKeyD k' fallback

theorem Std.TreeMap.getKeyD_eq_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k fallback : α} (h' : t.contains k = true) : t.getKeyD k fallback = k

theorem Std.TreeMap.getKeyD_eq_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k fallback : α} (h' : k ∈ t) : t.getKeyD k fallback = k

@[simp]

theorem Std.TreeMap.isEmpty_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insertIfNew k v).isEmpty = false

@[simp]

theorem Std.TreeMap.contains_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} : (t.insertIfNew k v).contains a = (cmp k a == Ordering.eq || t.contains a)

@[simp]

theorem Std.TreeMap.mem_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} : a ∈ t.insertIfNew k v ↔ cmp k a = Ordering.eq ∨ a ∈ t

@[simp]

theorem Std.TreeMap.contains_insertIfNew_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insertIfNew k v).contains k = true

@[simp]

theorem Std.TreeMap.mem_insertIfNew_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : k ∈ t.insertIfNew k v

theorem Std.TreeMap.contains_of_contains_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} : (t.insertIfNew k v).contains a = true → cmp k a ≠ Ordering.eq → t.contains a = true

theorem Std.TreeMap.mem_of_mem_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} : a ∈ t.insertIfNew k v → cmp k a ≠ Ordering.eq → a ∈ t

theorem Std.TreeMap.mem_of_mem_insertIfNew' {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} : a ∈ t.insertIfNew k v → ¬(cmp k a = Ordering.eq ∧ ¬k ∈ t) → a ∈ t

This is a restatement of mem_of_mem_insertIfNew that is written to exactly match the proof obligation in the statement of get_insertIfNew.

theorem Std.TreeMap.size_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insertIfNew k v).size = if k ∈ t then t.size else t.size + 1

theorem Std.TreeMap.size_le_size_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : t.size ≤ (t.insertIfNew k v).size

theorem Std.TreeMap.size_insertIfNew_le {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insertIfNew k v).size ≤ t.size + 1

theorem Std.TreeMap.getElem?_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} : (t.insertIfNew k v)[a]? = if cmp k a = Ordering.eq ∧ ¬k ∈ t then some v else t[a]?

theorem Std.TreeMap.getElem_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} {h₁ : a ∈ t.insertIfNew k v} : (t.insertIfNew k v)[a] = if h₂ : cmp k a = Ordering.eq ∧ ¬k ∈ t then v else t[a]

theorem Std.TreeMap.getElem!_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited β] {k a : α} {v : β} : (t.insertIfNew k v)[a]! = if cmp k a = Ordering.eq ∧ ¬k ∈ t then v else t[a]!

theorem Std.TreeMap.getD_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {fallback v : β} : (t.insertIfNew k v).getD a fallback = if cmp k a = Ordering.eq ∧ ¬k ∈ t then v else t.getD a fallback

theorem Std.TreeMap.getKey?_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} : (t.insertIfNew k v).getKey? a = if cmp k a = Ordering.eq ∧ ¬k ∈ t then some k else t.getKey? a

theorem Std.TreeMap.getKey_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a : α} {v : β} {h₁ : a ∈ t.insertIfNew k v} : (t.insertIfNew k v).getKey a h₁ = if h₂ : cmp k a = Ordering.eq ∧ ¬k ∈ t then k else t.getKey a ⋯

theorem Std.TreeMap.getKey!_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k a : α} {v : β} : (t.insertIfNew k v).getKey! a = if cmp k a = Ordering.eq ∧ ¬k ∈ t then k else t.getKey! a

theorem Std.TreeMap.getKeyD_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k a fallback : α} {v : β} : (t.insertIfNew k v).getKeyD a fallback = if cmp k a = Ordering.eq ∧ ¬k ∈ t then k else t.getKeyD a fallback

@[simp]

theorem Std.TreeMap.getThenInsertIfNew?_fst {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.getThenInsertIfNew? k v).fst = t.get? k

@[simp]

theorem Std.TreeMap.getThenInsertIfNew?_snd {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.getThenInsertIfNew? k v).snd = t.insertIfNew k v

@[simp]

theorem Std.TreeMap.length_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.keys.length = t.size

@[simp]

theorem Std.TreeMap.isEmpty_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} : t.keys.isEmpty = t.isEmpty

@[simp]

theorem Std.TreeMap.contains_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [BEq α] [LawfulBEqCmp cmp] [TransCmp cmp] {k : α} : t.keys.contains k = t.contains k

@[simp]

theorem Std.TreeMap.mem_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [LawfulEqCmp cmp] [TransCmp cmp] {k : α} : k ∈ t.keys ↔ k ∈ t

theorem Std.TreeMap.distinct_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : List.Pairwise (fun (a b : α) => ¬cmp a b = Ordering.eq) t.keys

theorem Std.TreeMap.ordered_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : List.Pairwise (fun (a b : α) => cmp a b = Ordering.lt) t.keys

@[simp]

theorem Std.TreeMap.map_fst_toList_eq_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} : List.map Prod.fst t.toList = t.keys

@[simp]

theorem Std.TreeMap.length_toList {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} : t.toList.length = t.size

@[simp]

theorem Std.TreeMap.isEmpty_toList {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} : t.toList.isEmpty = t.isEmpty

@[simp]

theorem Std.TreeMap.mem_toList_iff_getElem?_eq_some {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k : α} {v : β} : (k, v) ∈ t.toList ↔ t[k]? = some v

@[simp]

theorem Std.TreeMap.mem_toList_iff_getKey?_eq_some_and_getElem?_eq_some {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (k, v) ∈ t.toList ↔ t.getKey? k = some k ∧ t[k]? = some v

theorem Std.TreeMap.getElem?_eq_some_iff_exists_compare_eq_eq_and_mem_toList {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : t[k]? = some v ↔ ∃ (k' : α), cmp k k' = Ordering.eq ∧ (k', v) ∈ t.toList

theorem Std.TreeMap.find?_toList_eq_some_iff_getKey?_eq_some_and_getElem?_eq_some {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {v : β} : List.find? (fun (x : α × β) => cmp x.fst k == Ordering.eq) t.toList = some (k', v) ↔ t.getKey? k = some k' ∧ t[k]? = some v

theorem Std.TreeMap.find?_toList_eq_none_iff_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : List.find? (fun (x : α × β) => cmp x.fst k == Ordering.eq) t.toList = none ↔ t.contains k = false

@[simp]

theorem Std.TreeMap.find?_toList_eq_none_iff_not_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : List.find? (fun (x : α × β) => cmp x.fst k == Ordering.eq) t.toList = none ↔ ¬k ∈ t

theorem Std.TreeMap.distinct_keys_toList {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) t.toList

theorem Std.TreeMap.ordered_keys_toList {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : List.Pairwise (fun (a b : α × β) => cmp a.fst b.fst = Ordering.lt) t.toList

theorem Std.TreeMap.foldlM_eq_foldlM_toList {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {δ : Type w} {m : Type w → Type w} [Monad m] [LawfulMonad m] {f : δ → α → β → m δ} {init : δ} : foldlM f init t = List.foldlM (fun (a : δ) (b : α × β) => f a b.fst b.snd) init t.toList

theorem Std.TreeMap.foldl_eq_foldl_toList {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {δ : Type w} {f : δ → α → β → δ} {init : δ} : foldl f init t = List.foldl (fun (a : δ) (b : α × β) => f a b.fst b.snd) init t.toList

theorem Std.TreeMap.foldrM_eq_foldrM_toList {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {δ : Type w} {m : Type w → Type w} [Monad m] [LawfulMonad m] {f : α → β → δ → m δ} {init : δ} : foldrM f init t = List.foldrM (fun (a : α × β) (b : δ) => f a.fst a.snd b) init t.toList

theorem Std.TreeMap.foldr_eq_foldr_toList {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {δ : Type w} {f : α → β → δ → δ} {init : δ} : foldr f init t = List.foldr (fun (a : α × β) (b : δ) => f a.fst a.snd b) init t.toList

@[simp]

theorem Std.TreeMap.forM_eq_forM {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {m : Type w → Type w} [Monad m] [LawfulMonad m] {f : α → β → m PUnit} : forM f t = ForM.forM t fun (a : α × β) => f a.fst a.snd

theorem Std.TreeMap.forM_eq_forM_toList {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {m : Type w → Type w} [Monad m] [LawfulMonad m] {f : α × β → m PUnit} : ForM.forM t f = ForM.forM t.toList f

@[simp]

theorem Std.TreeMap.forIn_eq_forIn {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {δ : Type w} {m : Type w → Type w} [Monad m] [LawfulMonad m] {f : α → β → δ → m (ForInStep δ)} {init : δ} : forIn f init t = ForIn.forIn t init fun (a : α × β) (d : δ) => f a.fst a.snd d

theorem Std.TreeMap.forIn_eq_forIn_toList {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {δ : Type w} {m : Type w → Type w} [Monad m] [LawfulMonad m] {f : α × β → δ → m (ForInStep δ)} {init : δ} : ForIn.forIn t init f = ForIn.forIn t.toList init f

theorem Std.TreeMap.foldlM_eq_foldlM_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {δ : Type w} {m : Type w → Type w} [Monad m] [LawfulMonad m] {f : δ → α → m δ} {init : δ} : foldlM (fun (d : δ) (a : α) (x : β) => f d a) init t = List.foldlM f init t.keys

theorem Std.TreeMap.foldl_eq_foldl_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {δ : Type w} {f : δ → α → δ} {init : δ} : foldl (fun (d : δ) (a : α) (x : β) => f d a) init t = List.foldl f init t.keys

theorem Std.TreeMap.foldrM_eq_foldrM_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {δ : Type w} {m : Type w → Type w} [Monad m] [LawfulMonad m] {f : α → δ → m δ} {init : δ} : foldrM (fun (a : α) (x : β) (d : δ) => f a d) init t = List.foldrM f init t.keys

theorem Std.TreeMap.foldr_eq_foldr_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {δ : Type w} {f : α → δ → δ} {init : δ} : foldr (fun (a : α) (x : β) (d : δ) => f a d) init t = List.foldr f init t.keys

theorem Std.TreeMap.forM_eq_forM_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {m : Type w → Type w} [Monad m] [LawfulMonad m] {f : α → m PUnit} : (ForM.forM t fun (a : α × β) => f a.fst) = t.keys.forM f

theorem Std.TreeMap.forIn_eq_forIn_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {δ : Type w} {m : Type w → Type w} [Monad m] [LawfulMonad m] {f : α → δ → m (ForInStep δ)} {init : δ} : (ForIn.forIn t init fun (a : α × β) (d : δ) => f a.fst d) = ForIn.forIn t.keys init f

@[simp]

theorem Std.TreeMap.insertMany_nil {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} : t.insertMany [] = t

@[simp]

theorem Std.TreeMap.insertMany_list_singleton {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {k : α} {v : β} : t.insertMany [(k, v)] = t.insert k v

theorem Std.TreeMap.insertMany_cons {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} {l : List (α × β)} {k : α} {v : β} : t.insertMany ((k, v) :: l) = (t.insert k v).insertMany l

@[simp]

theorem Std.TreeMap.contains_insertMany_list {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} : (t.insertMany l).contains k = (t.contains k || (List.map Prod.fst l).contains k)

@[simp]

theorem Std.TreeMap.mem_insertMany_list {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} : k ∈ t.insertMany l ↔ k ∈ t ∨ (List.map Prod.fst l).contains k = true

theorem Std.TreeMap.mem_of_mem_insertMany_list {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} : k ∈ t.insertMany l → (List.map Prod.fst l).contains k = false → k ∈ t

theorem Std.TreeMap.getKey?_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (t.insertMany l).getKey? k = t.getKey? k

theorem Std.TreeMap.getKey?_insertMany_list_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : k ∈ List.map Prod.fst l) : (t.insertMany l).getKey? k' = some k

theorem Std.TreeMap.getKey_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) {h' : k ∈ t.insertMany l} : (t.insertMany l).getKey k h' = t.getKey k ⋯

theorem Std.TreeMap.getKey_insertMany_list_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : k ∈ List.map Prod.fst l) {h' : k' ∈ t.insertMany l} : (t.insertMany l).getKey k' h' = k

theorem Std.TreeMap.getKey!_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] [Inhabited α] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (t.insertMany l).getKey! k = t.getKey! k

theorem Std.TreeMap.getKey!_insertMany_list_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : k ∈ List.map Prod.fst l) : (t.insertMany l).getKey! k' = k

theorem Std.TreeMap.getKeyD_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k fallback : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (t.insertMany l).getKeyD k fallback = t.getKeyD k fallback

theorem Std.TreeMap.getKeyD_insertMany_list_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {l : List (α × β)} {k k' fallback : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : k ∈ List.map Prod.fst l) : (t.insertMany l).getKeyD k' fallback = k

theorem Std.TreeMap.size_insertMany_list {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) : (∀ (a : α), a ∈ t → (List.map Prod.fst l).contains a = false) → (t.insertMany l).size = t.size + l.length

theorem Std.TreeMap.size_le_size_insertMany_list {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {l : List (α × β)} : t.size ≤ (t.insertMany l).size

theorem Std.TreeMap.size_insertMany_list_le {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {l : List (α × β)} : (t.insertMany l).size ≤ t.size + l.length

@[simp]

theorem Std.TreeMap.isEmpty_insertMany_list {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {l : List (α × β)} : (t.insertMany l).isEmpty = (t.isEmpty && l.isEmpty)

theorem Std.TreeMap.getElem?_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (t.insertMany l)[k]? = t[k]?

theorem Std.TreeMap.getElem?_insertMany_list_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) {v : β} (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : (k, v) ∈ l) : (t.insertMany l)[k']? = some v

theorem Std.TreeMap.getElem_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} (contains : (List.map Prod.fst l).contains k = false) {h' : k ∈ t.insertMany l} : (t.insertMany l)[k] = t.get k ⋯

theorem Std.TreeMap.getElem_insertMany_list_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) {v : β} (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : (k, v) ∈ l) {h' : k' ∈ t.insertMany l} : (t.insertMany l)[k'] = v

theorem Std.TreeMap.getElem!_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} [Inhabited β] (contains_eq_false : (List.map Prod.fst l).contains k = false) : (t.insertMany l)[k]! = t.get! k

theorem Std.TreeMap.getElem!_insertMany_list_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) {v : β} [Inhabited β] (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : (k, v) ∈ l) : (t.insertMany l)[k']! = v

theorem Std.TreeMap.getD_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} {fallback : β} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (t.insertMany l).getD k fallback = t.getD k fallback

theorem Std.TreeMap.getD_insertMany_list_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) {v fallback : β} (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : (k, v) ∈ l) : (t.insertMany l).getD k' fallback = v

@[simp]

theorem Std.TreeMap.insertManyIfNewUnit_nil {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} : t.insertManyIfNewUnit [] = t

@[simp]

theorem Std.TreeMap.insertManyIfNewUnit_list_singleton {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} {k : α} : t.insertManyIfNewUnit [k] = t.insertIfNew k ()

theorem Std.TreeMap.insertManyIfNewUnit_cons {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} {l : List α} {k : α} : t.insertManyIfNewUnit (k :: l) = (t.insertIfNew k ()).insertManyIfNewUnit l

@[simp]

theorem Std.TreeMap.contains_insertManyIfNewUnit_list {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} {k : α} : (t.insertManyIfNewUnit l).contains k = (t.contains k || l.contains k)

@[simp]

theorem Std.TreeMap.mem_insertManyIfNewUnit_list {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} {k : α} : k ∈ t.insertManyIfNewUnit l ↔ k ∈ t ∨ l.contains k = true

theorem Std.TreeMap.mem_of_mem_insertManyIfNewUnit_list {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} {k : α} (contains_eq_false : l.contains k = false) : k ∈ t.insertManyIfNewUnit l → k ∈ t

theorem Std.TreeMap.getKey?_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} {k : α} (not_mem : ¬k ∈ t) (contains_eq_false : l.contains k = false) : (t.insertManyIfNewUnit l).getKey? k = none

theorem Std.TreeMap.getKey?_insertManyIfNewUnit_list_of_not_mem_of_mem {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] {l : List α} {k k' : α} (k_eq : cmp k k' = Ordering.eq) (not_mem : ¬k ∈ t) (distinct : List.Pairwise (fun (a b : α) => ¬cmp a b = Ordering.eq) l) (mem : k ∈ l) : (t.insertManyIfNewUnit l).getKey? k' = some k

theorem Std.TreeMap.getKey?_insertManyIfNewUnit_list_of_mem {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] {l : List α} {k : α} (mem : k ∈ t) : (t.insertManyIfNewUnit l).getKey? k = t.getKey? k

theorem Std.TreeMap.getKey_insertManyIfNewUnit_list_of_mem {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] {l : List α} {k : α} {h' : k ∈ t.insertManyIfNewUnit l} (contains : k ∈ t) : (t.insertManyIfNewUnit l).getKey k h' = t.getKey k contains

theorem Std.TreeMap.getKey_insertManyIfNewUnit_list_of_not_mem_of_mem {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] {l : List α} {k k' : α} (k_eq : cmp k k' = Ordering.eq) {h' : k' ∈ t.insertManyIfNewUnit l} (not_mem : ¬k ∈ t) (distinct : List.Pairwise (fun (a b : α) => ¬cmp a b = Ordering.eq) l) (mem : k ∈ l) : (t.insertManyIfNewUnit l).getKey k' h' = k

theorem Std.TreeMap.getKey!_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] [Inhabited α] {l : List α} {k : α} (not_mem : ¬k ∈ t) (contains_eq_false : l.contains k = false) : (t.insertManyIfNewUnit l).getKey! k = default

theorem Std.TreeMap.getKey!_insertManyIfNewUnit_list_of_not_mem_of_mem {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] [Inhabited α] {l : List α} {k k' : α} (k_eq : cmp k k' = Ordering.eq) (not_mem : ¬k ∈ t) (distinct : List.Pairwise (fun (a b : α) => ¬cmp a b = Ordering.eq) l) (mem : k ∈ l) : (t.insertManyIfNewUnit l).getKey! k' = k

theorem Std.TreeMap.getKey!_insertManyIfNewUnit_list_of_mem {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] [Inhabited α] {l : List α} {k : α} (mem : k ∈ t) : (t.insertManyIfNewUnit l).getKey! k = t.getKey! k

theorem Std.TreeMap.getKeyD_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} {k fallback : α} (not_mem : ¬k ∈ t) (contains_eq_false : l.contains k = false) : (t.insertManyIfNewUnit l).getKeyD k fallback = fallback

theorem Std.TreeMap.getKeyD_insertManyIfNewUnit_list_of_not_mem_of_mem {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] {l : List α} {k k' fallback : α} (k_eq : cmp k k' = Ordering.eq) (not_mem : ¬k ∈ t) (distinct : List.Pairwise (fun (a b : α) => ¬cmp a b = Ordering.eq) l) (mem : k ∈ l) : (t.insertManyIfNewUnit l).getKeyD k' fallback = k

theorem Std.TreeMap.getKeyD_insertManyIfNewUnit_list_of_mem {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] {l : List α} {k fallback : α} (mem : k ∈ t) : (t.insertManyIfNewUnit l).getKeyD k fallback = t.getKeyD k fallback

theorem Std.TreeMap.size_insertManyIfNewUnit_list {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} (distinct : List.Pairwise (fun (a b : α) => ¬cmp a b = Ordering.eq) l) : (∀ (a : α), a ∈ t → l.contains a = false) → (t.insertManyIfNewUnit l).size = t.size + l.length

theorem Std.TreeMap.size_le_size_insertManyIfNewUnit_list {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] {l : List α} : t.size ≤ (t.insertManyIfNewUnit l).size

theorem Std.TreeMap.size_insertManyIfNewUnit_list_le {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] {l : List α} : (t.insertManyIfNewUnit l).size ≤ t.size + l.length

@[simp]

theorem Std.TreeMap.isEmpty_insertManyIfNewUnit_list {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] {l : List α} : (t.insertManyIfNewUnit l).isEmpty = (t.isEmpty && l.isEmpty)

@[simp]

theorem Std.TreeMap.getElem?_insertManyIfNewUnit_list {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} {k : α} : (t.insertManyIfNewUnit l)[k]? = if k ∈ t ∨ l.contains k = true then some () else none

@[simp]

theorem Std.TreeMap.getElem_insertManyIfNewUnit_list {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} {l : List α} {k : α} {h' : k ∈ t.insertManyIfNewUnit l} : (t.insertManyIfNewUnit l)[k] = ()

@[simp]

theorem Std.TreeMap.getElem!_insertManyIfNewUnit_list {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} {l : List α} {k : α} : (t.insertManyIfNewUnit l)[k]! = ()

@[simp]

theorem Std.TreeMap.getD_insertManyIfNewUnit_list {α : Type u} {cmp : α → α → Ordering} {t : TreeMap α Unit cmp} {l : List α} {k : α} {fallback : Unit} : (t.insertManyIfNewUnit l).getD k fallback = ()

@[simp]

theorem Std.TreeMap.ofList_nil {α : Type u} {β : Type v} {cmp : α → α → Ordering} : ofList [] cmp = ∅

@[simp]

theorem Std.TreeMap.ofList_singleton {α : Type u} {β : Type v} {cmp : α → α → Ordering} {k : α} {v : β} : ofList [(k, v)] cmp = ∅.insert k v

theorem Std.TreeMap.ofList_cons {α : Type u} {β : Type v} {cmp : α → α → Ordering} {k : α} {v : β} {tl : List (α × β)} : ofList ((k, v) :: tl) cmp = (∅.insert k v).insertMany tl

@[simp]

theorem Std.TreeMap.contains_ofList {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} : (ofList l cmp).contains k = (List.map Prod.fst l).contains k

@[simp]

theorem Std.TreeMap.mem_ofList {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} : k ∈ ofList l cmp ↔ (List.map Prod.fst l).contains k = true

theorem Std.TreeMap.getElem?_ofList_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l cmp)[k]? = none

theorem Std.TreeMap.getElem?_ofList_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) {v : β} (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : (k, v) ∈ l) : (ofList l cmp)[k']? = some v

theorem Std.TreeMap.getElem_ofList_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) {v : β} (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : (k, v) ∈ l) {h : k' ∈ ofList l cmp} : (ofList l cmp)[k'] = v

theorem Std.TreeMap.getElem!_ofList_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} [Inhabited β] (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l cmp)[k]! = default

theorem Std.TreeMap.getElem!_ofList_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) {v : β} [Inhabited β] (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : (k, v) ∈ l) : (ofList l cmp)[k']! = v

theorem Std.TreeMap.getD_ofList_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} {fallback : β} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l cmp).getD k fallback = fallback

theorem Std.TreeMap.getD_ofList_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) {v fallback : β} (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : (k, v) ∈ l) : (ofList l cmp).getD k' fallback = v

theorem Std.TreeMap.getKey?_ofList_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l cmp).getKey? k = none

theorem Std.TreeMap.getKey?_ofList_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : k ∈ List.map Prod.fst l) : (ofList l cmp).getKey? k' = some k

theorem Std.TreeMap.getKey_ofList_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : k ∈ List.map Prod.fst l) {h' : k' ∈ ofList l cmp} : (ofList l cmp).getKey k' h' = k

theorem Std.TreeMap.getKey!_ofList_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] [Inhabited α] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l cmp).getKey! k = default

theorem Std.TreeMap.getKey!_ofList_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] [Inhabited α] {l : List (α × β)} {k k' : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : k ∈ List.map Prod.fst l) : (ofList l cmp).getKey! k' = k

theorem Std.TreeMap.getKeyD_ofList_of_contains_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List (α × β)} {k fallback : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l cmp).getKeyD k fallback = fallback

theorem Std.TreeMap.getKeyD_ofList_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {l : List (α × β)} {k k' fallback : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) (mem : k ∈ List.map Prod.fst l) : (ofList l cmp).getKeyD k' fallback = k

theorem Std.TreeMap.size_ofList {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {l : List (α × β)} (distinct : List.Pairwise (fun (a b : α × β) => ¬cmp a.fst b.fst = Ordering.eq) l) : (ofList l cmp).size = l.length

theorem Std.TreeMap.size_ofList_le {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {l : List (α × β)} : (ofList l cmp).size ≤ l.length

theorem Std.TreeMap.isEmpty_ofList {α : Type u} {β : Type v} {cmp : α → α → Ordering} [TransCmp cmp] {l : List (α × β)} : (ofList l cmp).isEmpty = l.isEmpty

@[simp]

theorem Std.TreeMap.unitOfList_nil {α : Type u} {cmp : α → α → Ordering} : unitOfList [] cmp = ∅

@[simp]

theorem Std.TreeMap.unitOfList_singleton {α : Type u} {cmp : α → α → Ordering} {k : α} : unitOfList [k] cmp = ∅.insertIfNew k ()

theorem Std.TreeMap.unitOfList_cons {α : Type u} {cmp : α → α → Ordering} {hd : α} {tl : List α} : unitOfList (hd :: tl) cmp = (∅.insertIfNew hd ()).insertManyIfNewUnit tl

@[simp]

theorem Std.TreeMap.contains_unitOfList {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} {k : α} : (unitOfList l cmp).contains k = l.contains k

@[simp]

theorem Std.TreeMap.mem_unitOfList {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} {k : α} : k ∈ unitOfList l cmp ↔ l.contains k = true

theorem Std.TreeMap.getKey?_unitOfList_of_contains_eq_false {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} {k : α} (contains_eq_false : l.contains k = false) : (unitOfList l cmp).getKey? k = none

theorem Std.TreeMap.getKey?_unitOfList_of_mem {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] {l : List α} {k k' : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α) => ¬cmp a b = Ordering.eq) l) (mem : k ∈ l) : (unitOfList l cmp).getKey? k' = some k

theorem Std.TreeMap.getKey_unitOfList_of_mem {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] {l : List α} {k k' : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α) => ¬cmp a b = Ordering.eq) l) (mem : k ∈ l) {h' : k' ∈ unitOfList l cmp} : (unitOfList l cmp).getKey k' h' = k

theorem Std.TreeMap.getKey!_unitOfList_of_contains_eq_false {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] [Inhabited α] {l : List α} {k : α} (contains_eq_false : l.contains k = false) : (unitOfList l cmp).getKey! k = default

theorem Std.TreeMap.getKey!_unitOfList_of_mem {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] [Inhabited α] {l : List α} {k k' : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α) => ¬cmp a b = Ordering.eq) l) (mem : k ∈ l) : (unitOfList l cmp).getKey! k' = k

theorem Std.TreeMap.getKeyD_unitOfList_of_contains_eq_false {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} {k fallback : α} (contains_eq_false : l.contains k = false) : (unitOfList l cmp).getKeyD k fallback = fallback

theorem Std.TreeMap.getKeyD_unitOfList_of_mem {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] {l : List α} {k k' fallback : α} (k_eq : cmp k k' = Ordering.eq) (distinct : List.Pairwise (fun (a b : α) => ¬cmp a b = Ordering.eq) l) (mem : k ∈ l) : (unitOfList l cmp).getKeyD k' fallback = k

theorem Std.TreeMap.size_unitOfList {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] {l : List α} (distinct : List.Pairwise (fun (a b : α) => ¬cmp a b = Ordering.eq) l) : (unitOfList l cmp).size = l.length

theorem Std.TreeMap.size_unitOfList_le {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] {l : List α} : (unitOfList l cmp).size ≤ l.length

@[simp]

theorem Std.TreeMap.isEmpty_unitOfList {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] {l : List α} : (unitOfList l cmp).isEmpty = l.isEmpty

@[simp]

theorem Std.TreeMap.getElem?_unitOfList {α : Type u} {cmp : α → α → Ordering} [TransCmp cmp] [BEq α] [LawfulBEqCmp cmp] {l : List α} {k : α} : (unitOfList l cmp)[k]? = if l.contains k = true then some () else none

@[simp]

theorem Std.TreeMap.getElem_unitOfList {α : Type u} {cmp : α → α → Ordering} {l : List α} {k : α} {h : k ∈ unitOfList l cmp} : (unitOfList l cmp)[k] = ()

@[simp]

theorem Std.TreeMap.getElem!_unitOfList {α : Type u} {cmp : α → α → Ordering} {l : List α} {k : α} : (unitOfList l cmp)[k]! = ()

@[simp]

theorem Std.TreeMap.getD_unitOfList {α : Type u} {cmp : α → α → Ordering} {l : List α} {k : α} {fallback : Unit} : (unitOfList l cmp).getD k fallback = ()

theorem Std.TreeMap.isEmpty_alter_eq_isEmpty_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} : (t.alter k f).isEmpty = ((t.erase k).isEmpty && (f t[k]?).isNone)

@[simp]

theorem Std.TreeMap.isEmpty_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} : (t.alter k f).isEmpty = ((t.isEmpty || t.size == 1 && t.contains k) && (f t[k]?).isNone)

theorem Std.TreeMap.contains_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : Option β → Option β} : (t.alter k f).contains k' = if cmp k k' = Ordering.eq then (f t[k]?).isSome else t.contains k'

theorem Std.TreeMap.mem_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : Option β → Option β} : k' ∈ t.alter k f ↔ if cmp k k' = Ordering.eq then (f t[k]?).isSome = true else k' ∈ t

theorem Std.TreeMap.mem_alter_of_compare_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : Option β → Option β} (he : cmp k k' = Ordering.eq) : k' ∈ t.alter k f ↔ (f t[k]?).isSome = true

@[simp]

theorem Std.TreeMap.contains_alter_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} : (t.alter k f).contains k = (f t[k]?).isSome

@[simp]

theorem Std.TreeMap.mem_alter_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} : k ∈ t.alter k f ↔ (f t[k]?).isSome = true

theorem Std.TreeMap.contains_alter_of_not_compare_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : Option β → Option β} (he : ¬cmp k k' = Ordering.eq) : (t.alter k f).contains k' = t.contains k'

theorem Std.TreeMap.mem_alter_of_not_compare_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : Option β → Option β} (he : ¬cmp k k' = Ordering.eq) : k' ∈ t.alter k f ↔ k' ∈ t

theorem Std.TreeMap.size_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} : (t.alter k f).size = if k ∈ t ∧ (f t[k]?).isNone = true then t.size - 1 else if ¬k ∈ t ∧ (f t[k]?).isSome = true then t.size + 1 else t.size

theorem Std.TreeMap.size_alter_eq_add_one {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} (h₁ : ¬k ∈ t) (h₂ : (f t[k]?).isSome = true) : (t.alter k f).size = t.size + 1

theorem Std.TreeMap.size_alter_eq_sub_one {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} (h₁ : k ∈ t) (h₂ : (f t[k]?).isNone = true) : (t.alter k f).size = t.size - 1

theorem Std.TreeMap.size_alter_eq_self_of_not_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} (h₁ : ¬k ∈ t) (h₂ : (f t[k]?).isNone = true) : (t.alter k f).size = t.size

theorem Std.TreeMap.size_alter_eq_self_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} (h₁ : k ∈ t) (h₂ : (f t[k]?).isSome = true) : (t.alter k f).size = t.size

theorem Std.TreeMap.size_alter_le_size {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} : (t.alter k f).size ≤ t.size + 1

theorem Std.TreeMap.size_le_size_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} : t.size - 1 ≤ (t.alter k f).size

theorem Std.TreeMap.getElem?_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : Option β → Option β} : (t.alter k f)[k']? = if cmp k k' = Ordering.eq then f t[k]? else t[k']?

@[simp]

theorem Std.TreeMap.getElem?_alter_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} : (t.alter k f)[k]? = f t[k]?

theorem Std.TreeMap.getElem_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : Option β → Option β} {hc : k' ∈ t.alter k f} : (t.alter k f)[k'] = if heq : cmp k k' = Ordering.eq then (f t[k]?).get ⋯ else t[k']

@[simp]

theorem Std.TreeMap.getElem_alter_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} {hc : k ∈ t.alter k f} : (t.alter k f)[k] = (f t[k]?).get ⋯

theorem Std.TreeMap.getElem!_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} [Inhabited β] {f : Option β → Option β} : (t.alter k f)[k']! = if cmp k k' = Ordering.eq then (f t[k]?).get! else t[k']!

@[simp]

theorem Std.TreeMap.getElem!_alter_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} [Inhabited β] {f : Option β → Option β} : (t.alter k f)[k]! = (f t[k]?).get!

theorem Std.TreeMap.getD_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {fallback : β} {f : Option β → Option β} : (t.alter k f).getD k' fallback = if cmp k k' = Ordering.eq then (f t[k]?).getD fallback else t.getD k' fallback

@[simp]

theorem Std.TreeMap.getD_alter_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {fallback : β} {f : Option β → Option β} : (t.alter k f).getD k fallback = (f t[k]?).getD fallback

theorem Std.TreeMap.getKey?_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : Option β → Option β} : (t.alter k f).getKey? k' = if cmp k k' = Ordering.eq then if (f t[k]?).isSome = true then some k else none else t.getKey? k'

theorem Std.TreeMap.getKey?_alter_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} : (t.alter k f).getKey? k = if (f t[k]?).isSome = true then some k else none

theorem Std.TreeMap.getKey!_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k k' : α} {f : Option β → Option β} : (t.alter k f).getKey! k' = if cmp k k' = Ordering.eq then if (f t[k]?).isSome = true then k else default else t.getKey! k'

theorem Std.TreeMap.getKey!_alter_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {f : Option β → Option β} : (t.alter k f).getKey! k = if (f t[k]?).isSome = true then k else default

theorem Std.TreeMap.getKey_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k k' : α} {f : Option β → Option β} {hc : k' ∈ t.alter k f} : (t.alter k f).getKey k' hc = if heq : cmp k k' = Ordering.eq then k else t.getKey k' ⋯

@[simp]

theorem Std.TreeMap.getKey_alter_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {f : Option β → Option β} {hc : k ∈ t.alter k f} : (t.alter k f).getKey k hc = k

theorem Std.TreeMap.getKeyD_alter {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' fallback : α} {f : Option β → Option β} : (t.alter k f).getKeyD k' fallback = if cmp k k' = Ordering.eq then if (f t[k]?).isSome = true then k else fallback else t.getKeyD k' fallback

@[simp]

theorem Std.TreeMap.getKeyD_alter_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k fallback : α} {f : Option β → Option β} : (t.alter k f).getKeyD k fallback = if (f t[k]?).isSome = true then k else fallback

@[simp]

theorem Std.TreeMap.isEmpty_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} : (t.modify k f).isEmpty = t.isEmpty

theorem Std.TreeMap.contains_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : β → β} : (t.modify k f).contains k' = t.contains k'

theorem Std.TreeMap.mem_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : β → β} : k' ∈ t.modify k f ↔ k' ∈ t

theorem Std.TreeMap.size_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} : (t.modify k f).size = t.size

theorem Std.TreeMap.getElem?_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : β → β} : (t.modify k f)[k']? = if cmp k k' = Ordering.eq then Option.map f t[k]? else t[k']?

@[simp]

theorem Std.TreeMap.getElem?_modify_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} : (t.modify k f)[k]? = Option.map f t[k]?

theorem Std.TreeMap.getElem_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : β → β} {hc : k' ∈ t.modify k f} : (t.modify k f)[k'] = if heq : cmp k k' = Ordering.eq then f t[k] else t[k']

@[simp]

theorem Std.TreeMap.getElem_modify_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} {hc : k ∈ t.modify k f} : (t.modify k f)[k] = f t[k]

theorem Std.TreeMap.getElem!_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} [hi : Inhabited β] {f : β → β} : (t.modify k f)[k']! = if cmp k k' = Ordering.eq then (Option.map f t[k]?).get! else t[k']!

@[simp]

theorem Std.TreeMap.getElem!_modify_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} [Inhabited β] {f : β → β} : (t.modify k f)[k]! = (Option.map f t[k]?).get!

theorem Std.TreeMap.getD_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {fallback : β} {f : β → β} : (t.modify k f).getD k' fallback = if cmp k k' = Ordering.eq then (Option.map f t[k]?).getD fallback else t.getD k' fallback

@[simp]

theorem Std.TreeMap.getD_modify_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {fallback : β} {f : β → β} : (t.modify k f).getD k fallback = (Option.map f t[k]?).getD fallback

theorem Std.TreeMap.getKey?_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' : α} {f : β → β} : (t.modify k f).getKey? k' = if cmp k k' = Ordering.eq then if k ∈ t then some k else none else t.getKey? k'

theorem Std.TreeMap.getKey?_modify_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} : (t.modify k f).getKey? k = if k ∈ t then some k else none

theorem Std.TreeMap.getKey!_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k k' : α} {f : β → β} : (t.modify k f).getKey! k' = if cmp k k' = Ordering.eq then if k ∈ t then k else default else t.getKey! k'

theorem Std.TreeMap.getKey!_modify_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {f : β → β} : (t.modify k f).getKey! k = if k ∈ t then k else default

theorem Std.TreeMap.getKey_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k k' : α} {f : β → β} {hc : k' ∈ t.modify k f} : (t.modify k f).getKey k' hc = if cmp k k' = Ordering.eq then k else t.getKey k' ⋯

@[simp]

theorem Std.TreeMap.getKey_modify_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {f : β → β} {hc : k ∈ t.modify k f} : (t.modify k f).getKey k hc = k

theorem Std.TreeMap.getKeyD_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k k' fallback : α} {f : β → β} : (t.modify k f).getKeyD k' fallback = if cmp k k' = Ordering.eq then if k ∈ t then k else fallback else t.getKeyD k' fallback

theorem Std.TreeMap.getKeyD_modify_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k fallback : α} {f : β → β} : (t.modify k f).getKeyD k fallback = if k ∈ t then k else fallback

@[simp]

theorem Std.TreeMap.minKey?_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} : ∅.minKey? = none

theorem Std.TreeMap.minKey?_of_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = true) : t.minKey? = none

@[simp]

theorem Std.TreeMap.minKey?_eq_none_iff {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.minKey? = none ↔ t.isEmpty = true

theorem Std.TreeMap.minKey?_eq_some_iff_getKey?_eq_self_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {km : α} : t.minKey? = some km ↔ t.getKey? km = some km ∧ ∀ (k : α), k ∈ t → (cmp km k).isLE = true

theorem Std.TreeMap.minKey?_eq_some_iff_mem_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {km : α} : t.minKey? = some km ↔ km ∈ t ∧ ∀ (k : α), k ∈ t → (cmp km k).isLE = true

@[simp]

theorem Std.TreeMap.isNone_minKey?_eq_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.minKey?.isNone = t.isEmpty

@[simp]

theorem Std.TreeMap.isSome_minKey?_eq_not_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.minKey?.isSome = !t.isEmpty

theorem Std.TreeMap.isSome_minKey?_iff_isEmpty_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.minKey?.isSome = true ↔ t.isEmpty = false

theorem Std.TreeMap.minKey?_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).minKey? = some (t.minKey?.elim k fun (k' : α) => if (cmp k k').isLE = true then k else k')

theorem Std.TreeMap.isSome_minKey?_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).minKey?.isSome = true

theorem Std.TreeMap.minKey?_insert_le_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {km kmi : α} (hkm : t.minKey? = some km) (hkmi : (t.insert k v).minKey?.get ⋯ = kmi) : (cmp kmi km).isLE = true

theorem Std.TreeMap.minKey?_insert_le_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {kmi : α} (hkmi : (t.insert k v).minKey?.get ⋯ = kmi) : (cmp kmi k).isLE = true

theorem Std.TreeMap.contains_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {km : α} (hkm : t.minKey? = some km) : t.contains km = true

theorem Std.TreeMap.isSome_minKey?_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : t.contains k = true) : t.minKey?.isSome = true

theorem Std.TreeMap.isSome_minKey?_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : k ∈ t → t.minKey?.isSome = true

theorem Std.TreeMap.minKey?_le_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k km : α} (hc : t.contains k = true) (hkm : t.minKey?.get ⋯ = km) : (cmp km k).isLE = true

theorem Std.TreeMap.minKey?_le_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k km : α} (hc : k ∈ t) (hkm : t.minKey?.get ⋯ = km) : (cmp km k).isLE = true

theorem Std.TreeMap.le_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : (∀ (k' : α), t.minKey? = some k' → (cmp k k').isLE = true) ↔ ∀ (k' : α), k' ∈ t → (cmp k k').isLE = true

theorem Std.TreeMap.getKey?_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {km : α} (hkm : t.minKey? = some km) : t.getKey? km = some km

theorem Std.TreeMap.getKey_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {km : α} {hc : t.contains km = true} (hkm : t.minKey?.get ⋯ = km) : t.getKey km hc = km

theorem Std.TreeMap.getKey!_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {km : α} (hkm : t.minKey? = some km) : t.getKey! km = km

theorem Std.TreeMap.getKeyD_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {km fallback : α} (hkm : t.minKey? = some km) : t.getKeyD km fallback = km

@[simp]

theorem Std.TreeMap.minKey?_bind_getKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.minKey?.bind t.getKey? = t.minKey?

theorem Std.TreeMap.minKey?_erase_eq_iff_not_compare_eq_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : (t.erase k).minKey? = t.minKey? ↔ ∀ {km : α}, t.minKey? = some km → ¬cmp k km = Ordering.eq

theorem Std.TreeMap.minKey?_erase_eq_of_not_compare_eq_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : ∀ {km : α}, t.minKey? = some km → ¬cmp k km = Ordering.eq) : (t.erase k).minKey? = t.minKey?

theorem Std.TreeMap.isSome_minKey?_of_isSome_minKey?_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hs : (t.erase k).minKey?.isSome = true) : t.minKey?.isSome = true

theorem Std.TreeMap.minKey?_le_minKey?_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k km kme : α} (hkme : (t.erase k).minKey? = some kme) (hkm : t.minKey?.get ⋯ = km) : (cmp km kme).isLE = true

theorem Std.TreeMap.minKey?_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insertIfNew k v).minKey? = some (t.minKey?.elim k fun (k' : α) => if cmp k k' = Ordering.lt then k else k')

theorem Std.TreeMap.isSome_minKey?_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insertIfNew k v).minKey?.isSome = true

theorem Std.TreeMap.minKey?_insertIfNew_le_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {km kmi : α} (hkm : t.minKey? = some km) (hkmi : (t.insertIfNew k v).minKey?.get ⋯ = kmi) : (cmp kmi km).isLE = true

theorem Std.TreeMap.minKey?_insertIfNew_le_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {kmi : α} (hkmi : (t.insertIfNew k v).minKey?.get ⋯ = kmi) : (cmp kmi k).isLE = true

theorem Std.TreeMap.minKey?_eq_head?_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.minKey? = t.keys.head?

theorem Std.TreeMap.minKey?_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} : (t.modify k f).minKey? = Option.map (fun (km : α) => if cmp km k = Ordering.eq then k else km) t.minKey?

@[simp]

theorem Std.TreeMap.minKey?_modify_eq_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k : α} {f : β → β} : (t.modify k f).minKey? = t.minKey?

theorem Std.TreeMap.isSome_minKey?_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} : (t.modify k f).minKey?.isSome = !t.isEmpty

theorem Std.TreeMap.isSome_minKey?_modify_eq_isSome {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} : (t.modify k f).minKey?.isSome = t.minKey?.isSome

theorem Std.TreeMap.compare_minKey?_modify_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} {km kmm : α} (hkm : t.minKey? = some km) (hkmm : (t.modify k f).minKey?.get ⋯ = kmm) : cmp kmm km = Ordering.eq

theorem Std.TreeMap.minKey?_alter_eq_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} : (t.alter k f).minKey? = some k ↔ (f t[k]?).isSome = true ∧ ∀ (k' : α), k' ∈ t → (cmp k k').isLE = true

theorem Std.TreeMap.minKey_eq_get_minKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.minKey he = t.minKey?.get ⋯

theorem Std.TreeMap.minKey?_eq_some_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.minKey? = some (t.minKey he)

theorem Std.TreeMap.minKey_eq_iff_getKey?_eq_self_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} {km : α} : t.minKey he = km ↔ t.getKey? km = some km ∧ ∀ (k : α), k ∈ t → (cmp km k).isLE = true

theorem Std.TreeMap.minKey_eq_iff_mem_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {he : t.isEmpty = false} {km : α} : t.minKey he = km ↔ km ∈ t ∧ ∀ (k : α), k ∈ t → (cmp km k).isLE = true

theorem Std.TreeMap.minKey_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).minKey ⋯ = t.minKey?.elim k fun (k' : α) => if (cmp k k').isLE = true then k else k'

theorem Std.TreeMap.minKey_insert_le_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {he : t.isEmpty = false} : (cmp ((t.insert k v).minKey ⋯) (t.minKey he)).isLE = true

theorem Std.TreeMap.minKey_insert_le_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (cmp ((t.insert k v).minKey ⋯) k).isLE = true

theorem Std.TreeMap.contains_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.contains (t.minKey he) = true

theorem Std.TreeMap.minKey_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.minKey he ∈ t

theorem Std.TreeMap.minKey_le_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : t.contains k = true) : (cmp (t.minKey ⋯) k).isLE = true

theorem Std.TreeMap.minKey_le_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : k ∈ t) : (cmp (t.minKey ⋯) k).isLE = true

theorem Std.TreeMap.le_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {he : t.isEmpty = false} : (cmp k (t.minKey he)).isLE = true ↔ ∀ (k' : α), k' ∈ t → (cmp k k').isLE = true

@[simp]

theorem Std.TreeMap.getKey?_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.getKey? (t.minKey he) = some (t.minKey he)

@[simp]

theorem Std.TreeMap.getKey_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} {hc : t.minKey he ∈ t} : t.getKey (t.minKey he) hc = t.minKey he

@[simp]

theorem Std.TreeMap.getKey!_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {he : t.isEmpty = false} : t.getKey! (t.minKey he) = t.minKey he

@[simp]

theorem Std.TreeMap.getKeyD_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} {fallback : α} : t.getKeyD (t.minKey he) fallback = t.minKey he

@[simp]

theorem Std.TreeMap.minKey_erase_eq_iff_not_compare_eq_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {he : (t.erase k).isEmpty = false} : (t.erase k).minKey he = t.minKey ⋯ ↔ ¬cmp k (t.minKey ⋯) = Ordering.eq

theorem Std.TreeMap.minKey_erase_eq_of_not_compare_eq_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {he : (t.erase k).isEmpty = false} (hc : ¬cmp k (t.minKey ⋯) = Ordering.eq) : (t.erase k).minKey he = t.minKey ⋯

theorem Std.TreeMap.minKey_le_minKey_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {he : (t.erase k).isEmpty = false} : (cmp (t.minKey ⋯) ((t.erase k).minKey he)).isLE = true

theorem Std.TreeMap.minKey_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insertIfNew k v).minKey ⋯ = t.minKey?.elim k fun (k' : α) => if cmp k k' = Ordering.lt then k else k'

theorem Std.TreeMap.minKey_insertIfNew_le_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {he : t.isEmpty = false} : (cmp ((t.insertIfNew k v).minKey ⋯) (t.minKey he)).isLE = true

theorem Std.TreeMap.minKey_insertIfNew_le_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (cmp ((t.insertIfNew k v).minKey ⋯) k).isLE = true

theorem Std.TreeMap.minKey_eq_head_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.minKey he = t.keys.head ⋯

theorem Std.TreeMap.minKey_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} {he : (t.modify k f).isEmpty = false} : (t.modify k f).minKey he = if cmp (t.minKey ⋯) k = Ordering.eq then k else t.minKey ⋯

@[simp]

theorem Std.TreeMap.minKey_modify_eq_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k : α} {f : β → β} {he : (t.modify k f).isEmpty = false} : (t.modify k f).minKey he = t.minKey ⋯

theorem Std.TreeMap.compare_minKey_modify_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} {he : (t.modify k f).isEmpty = false} : cmp ((t.modify k f).minKey he) (t.minKey ⋯) = Ordering.eq

@[simp]

theorem Std.TreeMap.ordCompare_minKey_modify_eq {α : Type u} {β : Type v} [Ord α] [TransOrd α] {t : TreeMap α β compare} {k : α} {f : β → β} {he : (t.modify k f).isEmpty = false} : compare ((t.modify k f).minKey he) (t.minKey ⋯) = Ordering.eq

theorem Std.TreeMap.minKey_alter_eq_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} {he : (t.alter k f).isEmpty = false} : (t.alter k f).minKey he = k ↔ (f t[k]?).isSome = true ∧ ∀ (k' : α), k' ∈ t → (cmp k k').isLE = true

theorem Std.TreeMap.minKey?_eq_some_minKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) : t.minKey? = some t.minKey!

theorem Std.TreeMap.minKey_eq_minKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {he : t.isEmpty = false} : t.minKey he = t.minKey!

theorem Std.TreeMap.minKey!_eq_default {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = true) : t.minKey! = default

theorem Std.TreeMap.minKey!_eq_iff_getKey?_eq_self_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {km : α} : t.minKey! = km ↔ t.getKey? km = some km ∧ ∀ (k : α), k ∈ t → (cmp km k).isLE = true

theorem Std.TreeMap.minKey!_eq_iff_mem_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] [Inhabited α] (he : t.isEmpty = false) {km : α} : t.minKey! = km ↔ km ∈ t ∧ ∀ (k : α), k ∈ t → (cmp km k).isLE = true

theorem Std.TreeMap.minKey!_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {v : β} : (t.insert k v).minKey! = t.minKey?.elim k fun (k' : α) => if (cmp k k').isLE = true then k else k'

theorem Std.TreeMap.minKey!_insert_le_minKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {k : α} {v : β} : (cmp (t.insert k v).minKey! t.minKey!).isLE = true

theorem Std.TreeMap.minKey!_insert_le_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {v : β} : (cmp (t.insert k v).minKey! k).isLE = true

theorem Std.TreeMap.contains_minKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) : t.contains t.minKey! = true

theorem Std.TreeMap.minKey!_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) : t.minKey! ∈ t

theorem Std.TreeMap.minKey!_le_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} (hc : t.contains k = true) : (cmp t.minKey! k).isLE = true

theorem Std.TreeMap.minKey!_le_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} (hc : k ∈ t) : (cmp t.minKey! k).isLE = true

theorem Std.TreeMap.le_minKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {k : α} : (cmp k t.minKey!).isLE = true ↔ ∀ (k' : α), k' ∈ t → (cmp k k').isLE = true

theorem Std.TreeMap.getKey?_minKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) : t.getKey? t.minKey! = some t.minKey!

theorem Std.TreeMap.getKey_minKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {hc : t.minKey! ∈ t} : t.getKey t.minKey! hc = t.minKey!

@[simp]

theorem Std.TreeMap.getKey_minKey!_eq_minKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {hc : t.minKey! ∈ t} : t.getKey t.minKey! hc = t.minKey ⋯

theorem Std.TreeMap.getKey!_minKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) : t.getKey! t.minKey! = t.minKey!

theorem Std.TreeMap.getKeyD_minKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {fallback : α} : t.getKeyD t.minKey! fallback = t.minKey!

theorem Std.TreeMap.minKey!_erase_eq_of_not_compare_minKey!_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} (he : (t.erase k).isEmpty = false) (heq : ¬cmp k t.minKey! = Ordering.eq) : (t.erase k).minKey! = t.minKey!

theorem Std.TreeMap.minKey!_le_minKey!_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} (he : (t.erase k).isEmpty = false) : (cmp t.minKey! (t.erase k).minKey!).isLE = true

theorem Std.TreeMap.minKey!_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {v : β} : (t.insertIfNew k v).minKey! = t.minKey?.elim k fun (k' : α) => if cmp k k' = Ordering.lt then k else k'

theorem Std.TreeMap.minKey!_insertIfNew_le_minKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {k : α} {v : β} : (cmp (t.insertIfNew k v).minKey! t.minKey!).isLE = true

theorem Std.TreeMap.minKey!_insertIfNew_le_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {v : β} : (cmp (t.insertIfNew k v).minKey! k).isLE = true

theorem Std.TreeMap.minKey!_eq_head!_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] : t.minKey! = t.keys.head!

theorem Std.TreeMap.minKey!_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {f : β → β} (he : (t.modify k f).isEmpty = false) : (t.modify k f).minKey! = if cmp t.minKey! k = Ordering.eq then k else t.minKey!

@[simp]

theorem Std.TreeMap.minKey!_modify_eq_minKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] [Inhabited α] {k : α} {f : β → β} : (t.modify k f).minKey! = t.minKey!

theorem Std.TreeMap.compare_minKey!_modify_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {f : β → β} : cmp (t.modify k f).minKey! t.minKey! = Ordering.eq

@[simp]

theorem Std.TreeMap.ordCompare_minKey!_modify_eq {α : Type u} {β : Type v} [Ord α] [TransOrd α] {t : TreeMap α β compare} [Inhabited α] {k : α} {f : β → β} : compare (t.modify k f).minKey! t.minKey! = Ordering.eq

theorem Std.TreeMap.minKey!_alter_eq_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {f : Option β → Option β} (he : (t.alter k f).isEmpty = false) : (t.alter k f).minKey! = k ↔ (f (t.get? k)).isSome = true ∧ ∀ (k' : α), k' ∈ t → (cmp k k').isLE = true

theorem Std.TreeMap.minKey?_eq_some_minKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {fallback : α} : t.minKey? = some (t.minKeyD fallback)

theorem Std.TreeMap.minKeyD_eq_fallback {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = true) {fallback : α} : t.minKeyD fallback = fallback

theorem Std.TreeMap.minKey!_eq_minKeyD_default {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] : t.minKey! = t.minKeyD default

theorem Std.TreeMap.minKeyD_eq_iff_getKey?_eq_self_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {km fallback : α} : t.minKeyD fallback = km ↔ t.getKey? km = some km ∧ ∀ (k : α), k ∈ t → (cmp km k).isLE = true

theorem Std.TreeMap.minKeyD_eq_iff_mem_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] (he : t.isEmpty = false) {km fallback : α} : t.minKeyD fallback = km ↔ km ∈ t ∧ ∀ (k : α), k ∈ t → (cmp km k).isLE = true

theorem Std.TreeMap.minKeyD_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {fallback : α} : (t.insert k v).minKeyD fallback = t.minKey?.elim k fun (k' : α) => if (cmp k k').isLE = true then k else k'

theorem Std.TreeMap.minKeyD_insert_le_minKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {k : α} {v : β} {fallback : α} : (cmp ((t.insert k v).minKeyD fallback) (t.minKeyD fallback)).isLE = true

theorem Std.TreeMap.minKeyD_insert_le_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {fallback : α} : (cmp ((t.insert k v).minKeyD fallback) k).isLE = true

theorem Std.TreeMap.contains_minKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {fallback : α} : t.contains (t.minKeyD fallback) = true

theorem Std.TreeMap.minKeyD_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {fallback : α} : t.minKeyD fallback ∈ t

theorem Std.TreeMap.minKeyD_le_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : t.contains k = true) {fallback : α} : (cmp (t.minKeyD fallback) k).isLE = true

theorem Std.TreeMap.minKeyD_le_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : k ∈ t) {fallback : α} : (cmp (t.minKeyD fallback) k).isLE = true

theorem Std.TreeMap.le_minKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {k fallback : α} : (cmp k (t.minKeyD fallback)).isLE = true ↔ ∀ (k' : α), k' ∈ t → (cmp k k').isLE = true

theorem Std.TreeMap.getKey?_minKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {fallback : α} : t.getKey? (t.minKeyD fallback) = some (t.minKeyD fallback)

theorem Std.TreeMap.getKey_minKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {fallback : α} {hc : t.minKeyD fallback ∈ t} : t.getKey (t.minKeyD fallback) hc = t.minKeyD fallback

theorem Std.TreeMap.getKey!_minKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {fallback : α} : t.getKey! (t.minKeyD fallback) = t.minKeyD fallback

theorem Std.TreeMap.getKeyD_minKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {fallback fallback' : α} : t.getKeyD (t.minKeyD fallback) fallback' = t.minKeyD fallback

theorem Std.TreeMap.minKeyD_erase_eq_of_not_compare_minKeyD_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k fallback : α} (he : (t.erase k).isEmpty = false) (heq : ¬cmp k (t.minKeyD fallback) = Ordering.eq) : (t.erase k).minKeyD fallback = t.minKeyD fallback

theorem Std.TreeMap.minKeyD_le_minKeyD_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (he : (t.erase k).isEmpty = false) {fallback : α} : (cmp (t.minKeyD fallback) ((t.erase k).minKeyD fallback)).isLE = true

theorem Std.TreeMap.minKeyD_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {fallback : α} : (t.insertIfNew k v).minKeyD fallback = t.minKey?.elim k fun (k' : α) => if cmp k k' = Ordering.lt then k else k'

theorem Std.TreeMap.minKeyD_insertIfNew_le_minKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {k : α} {v : β} {fallback : α} : (cmp ((t.insertIfNew k v).minKeyD fallback) (t.minKeyD fallback)).isLE = true

theorem Std.TreeMap.minKeyD_insertIfNew_le_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {fallback : α} : (cmp ((t.insertIfNew k v).minKeyD fallback) k).isLE = true

theorem Std.TreeMap.minKeyD_eq_headD_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {fallback : α} : t.minKeyD fallback = t.keys.headD fallback

theorem Std.TreeMap.minKeyD_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} (he : (t.modify k f).isEmpty = false) {fallback : α} : (t.modify k f).minKeyD fallback = if cmp (t.minKeyD fallback) k = Ordering.eq then k else t.minKeyD fallback

@[simp]

theorem Std.TreeMap.minKeyD_modify_eq_minKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k : α} {f : β → β} {fallback : α} : (t.modify k f).minKeyD fallback = t.minKeyD fallback

theorem Std.TreeMap.compare_minKeyD_modify_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} {fallback : α} : cmp ((t.modify k f).minKeyD fallback) (t.minKeyD fallback) = Ordering.eq

@[simp]

theorem Std.TreeMap.ordCompare_minKeyD_modify_eq {α : Type u} {β : Type v} [Ord α] [TransOrd α] {t : TreeMap α β compare} {k : α} {f : β → β} {fallback : α} : compare ((t.modify k f).minKeyD fallback) (t.minKeyD fallback) = Ordering.eq

theorem Std.TreeMap.minKeyD_alter_eq_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} (he : (t.alter k f).isEmpty = false) {fallback : α} : (t.alter k f).minKeyD fallback = k ↔ (f (t.get? k)).isSome = true ∧ ∀ (k' : α), k' ∈ t → (cmp k k').isLE = true

@[simp]

theorem Std.TreeMap.maxKey?_emptyc {α : Type u} {β : Type v} {cmp : α → α → Ordering} : ∅.maxKey? = none

theorem Std.TreeMap.maxKey?_of_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = true) : t.maxKey? = none

@[simp]

theorem Std.TreeMap.maxKey?_eq_none_iff {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.maxKey? = none ↔ t.isEmpty = true

theorem Std.TreeMap.maxKey?_eq_some_iff_getKey?_eq_self_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {km : α} : t.maxKey? = some km ↔ t.getKey? km = some km ∧ ∀ (k : α), k ∈ t → (cmp k km).isLE = true

theorem Std.TreeMap.maxKey?_eq_some_iff_mem_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {km : α} : t.maxKey? = some km ↔ km ∈ t ∧ ∀ (k : α), k ∈ t → (cmp k km).isLE = true

@[simp]

theorem Std.TreeMap.isNone_maxKey?_eq_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.maxKey?.isNone = t.isEmpty

@[simp]

theorem Std.TreeMap.isSome_maxKey?_eq_not_isEmpty {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.maxKey?.isSome = !t.isEmpty

theorem Std.TreeMap.isSome_maxKey?_iff_isEmpty_eq_false {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.maxKey?.isSome = true ↔ t.isEmpty = false

theorem Std.TreeMap.maxKey?_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).maxKey? = some (t.maxKey?.elim k fun (k' : α) => if (cmp k' k).isLE = true then k else k')

theorem Std.TreeMap.isSome_maxKey?_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).maxKey?.isSome = true

theorem Std.TreeMap.maxKey?_le_maxKey?_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {km kmi : α} (hkm : t.maxKey? = some km) (hkmi : (t.insert k v).maxKey?.get ⋯ = kmi) : (cmp km kmi).isLE = true

theorem Std.TreeMap.self_le_maxKey?_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {kmi : α} (hkmi : (t.insert k v).maxKey?.get ⋯ = kmi) : (cmp k kmi).isLE = true

theorem Std.TreeMap.contains_maxKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {km : α} (hkm : t.maxKey? = some km) : t.contains km = true

theorem Std.TreeMap.isSome_maxKey?_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : t.contains k = true) : t.maxKey?.isSome = true

theorem Std.TreeMap.isSome_maxKey?_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : k ∈ t → t.maxKey?.isSome = true

theorem Std.TreeMap.le_maxKey?_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k km : α} (hc : t.contains k = true) (hkm : t.maxKey?.get ⋯ = km) : (cmp k km).isLE = true

theorem Std.TreeMap.le_maxKey?_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k km : α} (hc : k ∈ t) (hkm : t.maxKey?.get ⋯ = km) : (cmp k km).isLE = true

theorem Std.TreeMap.maxKey?_le {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : (∀ (k' : α), t.maxKey? = some k' → (cmp k' k).isLE = true) ↔ ∀ (k' : α), k' ∈ t → (cmp k' k).isLE = true

theorem Std.TreeMap.getKey?_maxKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {km : α} (hkm : t.maxKey? = some km) : t.getKey? km = some km

theorem Std.TreeMap.getKey_maxKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {km : α} {hc : t.contains km = true} (hkm : t.maxKey?.get ⋯ = km) : t.getKey km hc = km

theorem Std.TreeMap.getKey!_maxKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {km : α} (hkm : t.maxKey? = some km) : t.getKey! km = km

theorem Std.TreeMap.getKeyD_maxKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {km fallback : α} (hkm : t.maxKey? = some km) : t.getKeyD km fallback = km

@[simp]

theorem Std.TreeMap.maxKey?_bind_getKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.maxKey?.bind t.getKey? = t.maxKey?

theorem Std.TreeMap.maxKey?_erase_eq_iff_not_compare_eq_maxKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} : (t.erase k).maxKey? = t.maxKey? ↔ ∀ {km : α}, t.maxKey? = some km → ¬cmp k km = Ordering.eq

theorem Std.TreeMap.maxKey?_erase_eq_of_not_compare_eq_maxKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : ∀ {km : α}, t.maxKey? = some km → ¬cmp k km = Ordering.eq) : (t.erase k).maxKey? = t.maxKey?

theorem Std.TreeMap.isSome_maxKey?_of_isSome_maxKey?_erase {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hs : (t.erase k).maxKey?.isSome = true) : t.maxKey?.isSome = true

theorem Std.TreeMap.maxKey?_erase_le_maxKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k km kme : α} (hkme : (t.erase k).maxKey? = some kme) (hkm : t.maxKey?.get ⋯ = km) : (cmp kme km).isLE = true

theorem Std.TreeMap.maxKey?_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insertIfNew k v).maxKey? = some (t.maxKey?.elim k fun (k' : α) => if cmp k' k = Ordering.lt then k else k')

theorem Std.TreeMap.isSome_maxKey?_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insertIfNew k v).maxKey?.isSome = true

theorem Std.TreeMap.maxKey?_le_maxKey?_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {km kmi : α} (hkm : t.maxKey? = some km) (hkmi : (t.insertIfNew k v).maxKey?.get ⋯ = kmi) : (cmp km kmi).isLE = true

theorem Std.TreeMap.self_le_maxKey?_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {kmi : α} (hkmi : (t.insertIfNew k v).maxKey?.get ⋯ = kmi) : (cmp k kmi).isLE = true

theorem Std.TreeMap.maxKey?_eq_getLast?_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] : t.maxKey? = t.keys.getLast?

theorem Std.TreeMap.maxKey?_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} : (t.modify k f).maxKey? = Option.map (fun (km : α) => if cmp km k = Ordering.eq then k else km) t.maxKey?

@[simp]

theorem Std.TreeMap.maxKey?_modify_eq_maxKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k : α} {f : β → β} : (t.modify k f).maxKey? = t.maxKey?

theorem Std.TreeMap.isSome_maxKey?_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} : (t.modify k f).maxKey?.isSome = !t.isEmpty

theorem Std.TreeMap.isSome_maxKey?_modify_eq_isSome {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} : (t.modify k f).maxKey?.isSome = t.maxKey?.isSome

theorem Std.TreeMap.compare_maxKey?_modify_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} {km kmm : α} (hkm : t.maxKey? = some km) (hkmm : (t.modify k f).maxKey?.get ⋯ = kmm) : cmp kmm km = Ordering.eq

theorem Std.TreeMap.maxKey?_alter_eq_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} : (t.alter k f).maxKey? = some k ↔ (f t[k]?).isSome = true ∧ ∀ (k' : α), k' ∈ t → (cmp k' k).isLE = true

theorem Std.TreeMap.maxKey_eq_get_maxKey? {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.maxKey he = t.maxKey?.get ⋯

theorem Std.TreeMap.maxKey?_eq_some_maxKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.maxKey? = some (t.maxKey he)

theorem Std.TreeMap.maxKey_eq_iff_getKey?_eq_self_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} {km : α} : t.maxKey he = km ↔ t.getKey? km = some km ∧ ∀ (k : α), k ∈ t → (cmp k km).isLE = true

theorem Std.TreeMap.maxKey_eq_iff_mem_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {he : t.isEmpty = false} {km : α} : t.maxKey he = km ↔ km ∈ t ∧ ∀ (k : α), k ∈ t → (cmp k km).isLE = true

theorem Std.TreeMap.maxKey_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insert k v).maxKey ⋯ = t.maxKey?.elim k fun (k' : α) => if (cmp k' k).isLE = true then k else k'

theorem Std.TreeMap.maxKey_le_maxKey_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {he : t.isEmpty = false} : (cmp (t.maxKey he) ((t.insert k v).maxKey ⋯)).isLE = true

theorem Std.TreeMap.self_le_maxKey_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (cmp k ((t.insert k v).maxKey ⋯)).isLE = true

theorem Std.TreeMap.contains_maxKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.contains (t.maxKey he) = true

theorem Std.TreeMap.maxKey_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.maxKey he ∈ t

theorem Std.TreeMap.le_maxKey_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : t.contains k = true) : (cmp k (t.maxKey ⋯)).isLE = true

theorem Std.TreeMap.le_maxKey_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : k ∈ t) : (cmp k (t.maxKey ⋯)).isLE = true

theorem Std.TreeMap.maxKey_le {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {he : t.isEmpty = false} : (cmp (t.maxKey he) k).isLE = true ↔ ∀ (k' : α), k' ∈ t → (cmp k' k).isLE = true

@[simp]

theorem Std.TreeMap.getKey?_maxKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.getKey? (t.maxKey he) = some (t.maxKey he)

@[simp]

theorem Std.TreeMap.getKey_maxKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} {hc : t.maxKey he ∈ t} : t.getKey (t.maxKey he) hc = t.maxKey he

@[simp]

theorem Std.TreeMap.getKey!_maxKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {he : t.isEmpty = false} : t.getKey! (t.maxKey he) = t.maxKey he

@[simp]

theorem Std.TreeMap.getKeyD_maxKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} {fallback : α} : t.getKeyD (t.maxKey he) fallback = t.maxKey he

@[simp]

theorem Std.TreeMap.maxKey_erase_eq_iff_not_compare_eq_maxKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {he : (t.erase k).isEmpty = false} : (t.erase k).maxKey he = t.maxKey ⋯ ↔ ¬cmp k (t.maxKey ⋯) = Ordering.eq

theorem Std.TreeMap.maxKey_erase_eq_of_not_compare_eq_maxKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {he : (t.erase k).isEmpty = false} (hc : ¬cmp k (t.maxKey ⋯) = Ordering.eq) : (t.erase k).maxKey he = t.maxKey ⋯

theorem Std.TreeMap.maxKey_erase_le_maxKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {he : (t.erase k).isEmpty = false} : (cmp ((t.erase k).maxKey he) (t.maxKey ⋯)).isLE = true

theorem Std.TreeMap.maxKey_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (t.insertIfNew k v).maxKey ⋯ = t.maxKey?.elim k fun (k' : α) => if cmp k' k = Ordering.lt then k else k'

theorem Std.TreeMap.maxKey_le_maxKey_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {he : t.isEmpty = false} : (cmp (t.maxKey he) ((t.insertIfNew k v).maxKey ⋯)).isLE = true

theorem Std.TreeMap.self_le_maxKey_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} : (cmp k ((t.insertIfNew k v).maxKey ⋯)).isLE = true

theorem Std.TreeMap.maxKey_eq_getLast_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {he : t.isEmpty = false} : t.maxKey he = t.keys.getLast ⋯

theorem Std.TreeMap.maxKey_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} {he : (t.modify k f).isEmpty = false} : (t.modify k f).maxKey he = if cmp (t.maxKey ⋯) k = Ordering.eq then k else t.maxKey ⋯

@[simp]

theorem Std.TreeMap.maxKey_modify_eq_maxKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k : α} {f : β → β} {he : (t.modify k f).isEmpty = false} : (t.modify k f).maxKey he = t.maxKey ⋯

theorem Std.TreeMap.compare_maxKey_modify_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} {he : (t.modify k f).isEmpty = false} : cmp ((t.modify k f).maxKey he) (t.maxKey ⋯) = Ordering.eq

@[simp]

theorem Std.TreeMap.ordCompare_maxKey_modify_eq {α : Type u} {β : Type v} [Ord α] [TransOrd α] {t : TreeMap α β compare} {k : α} {f : β → β} {he : (t.modify k f).isEmpty = false} : compare ((t.modify k f).maxKey he) (t.maxKey ⋯) = Ordering.eq

theorem Std.TreeMap.maxKey_alter_eq_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} {he : (t.alter k f).isEmpty = false} : (t.alter k f).maxKey he = k ↔ (f t[k]?).isSome = true ∧ ∀ (k' : α), k' ∈ t → (cmp k' k).isLE = true

theorem Std.TreeMap.maxKey?_eq_some_maxKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) : t.maxKey? = some t.maxKey!

theorem Std.TreeMap.maxKey_eq_maxKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {he : t.isEmpty = false} : t.maxKey he = t.maxKey!

theorem Std.TreeMap.maxKey!_eq_default {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = true) : t.maxKey! = default

theorem Std.TreeMap.maxKey!_eq_iff_getKey?_eq_self_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {km : α} : t.maxKey! = km ↔ t.getKey? km = some km ∧ ∀ (k : α), k ∈ t → (cmp k km).isLE = true

theorem Std.TreeMap.maxKey!_eq_iff_mem_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] [Inhabited α] (he : t.isEmpty = false) {km : α} : t.maxKey! = km ↔ km ∈ t ∧ ∀ (k : α), k ∈ t → (cmp k km).isLE = true

theorem Std.TreeMap.maxKey!_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {v : β} : (t.insert k v).maxKey! = t.maxKey?.elim k fun (k' : α) => if (cmp k' k).isLE = true then k else k'

theorem Std.TreeMap.maxKey!_le_maxKey!_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {k : α} {v : β} : (cmp t.maxKey! (t.insert k v).maxKey!).isLE = true

theorem Std.TreeMap.self_le_maxKey!_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {v : β} : (cmp k (t.insert k v).maxKey!).isLE = true

theorem Std.TreeMap.contains_maxKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) : t.contains t.maxKey! = true

theorem Std.TreeMap.maxKey!_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) : t.maxKey! ∈ t

theorem Std.TreeMap.le_maxKey!_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} (hc : t.contains k = true) : (cmp k t.maxKey!).isLE = true

theorem Std.TreeMap.le_maxKey!_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} (hc : k ∈ t) : (cmp k t.maxKey!).isLE = true

theorem Std.TreeMap.maxKey!_le {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {k : α} : (cmp t.maxKey! k).isLE = true ↔ ∀ (k' : α), k' ∈ t → (cmp k' k).isLE = true

theorem Std.TreeMap.getKey?_maxKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) : t.getKey? t.maxKey! = some t.maxKey!

theorem Std.TreeMap.getKey_maxKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {hc : t.maxKey! ∈ t} : t.getKey t.maxKey! hc = t.maxKey!

@[simp]

theorem Std.TreeMap.getKey_maxKey!_eq_maxKey {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {hc : t.maxKey! ∈ t} : t.getKey t.maxKey! hc = t.maxKey ⋯

theorem Std.TreeMap.getKey!_maxKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) : t.getKey! t.maxKey! = t.maxKey!

theorem Std.TreeMap.getKeyD_maxKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {fallback : α} : t.getKeyD t.maxKey! fallback = t.maxKey!

theorem Std.TreeMap.maxKey!_erase_eq_of_not_compare_maxKey!_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} (he : (t.erase k).isEmpty = false) (heq : ¬cmp k t.maxKey! = Ordering.eq) : (t.erase k).maxKey! = t.maxKey!

theorem Std.TreeMap.maxKey!_erase_le_maxKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} (he : (t.erase k).isEmpty = false) : (cmp (t.erase k).maxKey! t.maxKey!).isLE = true

theorem Std.TreeMap.maxKey!_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {v : β} : (t.insertIfNew k v).maxKey! = t.maxKey?.elim k fun (k' : α) => if cmp k' k = Ordering.lt then k else k'

theorem Std.TreeMap.maxKey!_le_maxKey!_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {k : α} {v : β} : (cmp t.maxKey! (t.insertIfNew k v).maxKey!).isLE = true

theorem Std.TreeMap.self_le_maxKey!_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {v : β} : (cmp k (t.insertIfNew k v).maxKey!).isLE = true

theorem Std.TreeMap.maxKey!_eq_getLast!_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] : t.maxKey! = t.keys.getLast!

theorem Std.TreeMap.maxKey!_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {f : β → β} (he : (t.modify k f).isEmpty = false) : (t.modify k f).maxKey! = if cmp t.maxKey! k = Ordering.eq then k else t.maxKey!

@[simp]

theorem Std.TreeMap.maxKey!_modify_eq_maxKey! {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] [Inhabited α] {k : α} {f : β → β} : (t.modify k f).maxKey! = t.maxKey!

theorem Std.TreeMap.compare_maxKey!_modify_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {f : β → β} : cmp (t.modify k f).maxKey! t.maxKey! = Ordering.eq

@[simp]

theorem Std.TreeMap.ordCompare_maxKey!_modify_eq {α : Type u} {β : Type v} [Ord α] [TransOrd α] {t : TreeMap α β compare} [Inhabited α] {k : α} {f : β → β} : compare (t.modify k f).maxKey! t.maxKey! = Ordering.eq

theorem Std.TreeMap.maxKey!_alter_eq_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] {k : α} {f : Option β → Option β} (he : (t.alter k f).isEmpty = false) : (t.alter k f).maxKey! = k ↔ (f (t.get? k)).isSome = true ∧ ∀ (k' : α), k' ∈ t → (cmp k' k).isLE = true

theorem Std.TreeMap.maxKey?_eq_some_maxKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {fallback : α} : t.maxKey? = some (t.maxKeyD fallback)

theorem Std.TreeMap.maxKeyD_eq_fallback {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = true) {fallback : α} : t.maxKeyD fallback = fallback

theorem Std.TreeMap.maxKey!_eq_maxKeyD_default {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] : t.maxKey! = t.maxKeyD default

theorem Std.TreeMap.maxKeyD_eq_iff_getKey?_eq_self_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {km fallback : α} : t.maxKeyD fallback = km ↔ t.getKey? km = some km ∧ ∀ (k : α), k ∈ t → (cmp k km).isLE = true

theorem Std.TreeMap.maxKeyD_eq_iff_mem_and_forall {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] (he : t.isEmpty = false) {km fallback : α} : t.maxKeyD fallback = km ↔ km ∈ t ∧ ∀ (k : α), k ∈ t → (cmp k km).isLE = true

theorem Std.TreeMap.maxKeyD_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {fallback : α} : (t.insert k v).maxKeyD fallback = t.maxKey?.elim k fun (k' : α) => if (cmp k' k).isLE = true then k else k'

theorem Std.TreeMap.maxKeyD_le_maxKeyD_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {k : α} {v : β} {fallback : α} : (cmp (t.maxKeyD fallback) ((t.insert k v).maxKeyD fallback)).isLE = true

theorem Std.TreeMap.self_le_maxKeyD_insert {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {fallback : α} : (cmp k ((t.insert k v).maxKeyD fallback)).isLE = true

theorem Std.TreeMap.contains_maxKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {fallback : α} : t.contains (t.maxKeyD fallback) = true

theorem Std.TreeMap.maxKeyD_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {fallback : α} : t.maxKeyD fallback ∈ t

theorem Std.TreeMap.le_maxKeyD_of_contains {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : t.contains k = true) {fallback : α} : (cmp k (t.maxKeyD fallback)).isLE = true

theorem Std.TreeMap.le_maxKeyD_of_mem {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (hc : k ∈ t) {fallback : α} : (cmp k (t.maxKeyD fallback)).isLE = true

theorem Std.TreeMap.maxKeyD_le {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {k fallback : α} : (cmp (t.maxKeyD fallback) k).isLE = true ↔ ∀ (k' : α), k' ∈ t → (cmp k' k).isLE = true

theorem Std.TreeMap.getKey?_maxKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {fallback : α} : t.getKey? (t.maxKeyD fallback) = some (t.maxKeyD fallback)

theorem Std.TreeMap.getKey_maxKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {fallback : α} {hc : t.maxKeyD fallback ∈ t} : t.getKey (t.maxKeyD fallback) hc = t.maxKeyD fallback

theorem Std.TreeMap.getKey!_maxKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [Inhabited α] (he : t.isEmpty = false) {fallback : α} : t.getKey! (t.maxKeyD fallback) = t.maxKeyD fallback

theorem Std.TreeMap.getKeyD_maxKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {fallback fallback' : α} : t.getKeyD (t.maxKeyD fallback) fallback' = t.maxKeyD fallback

theorem Std.TreeMap.maxKeyD_erase_eq_of_not_compare_maxKeyD_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k fallback : α} (he : (t.erase k).isEmpty = false) (heq : ¬cmp k (t.maxKeyD fallback) = Ordering.eq) : (t.erase k).maxKeyD fallback = t.maxKeyD fallback

theorem Std.TreeMap.maxKeyD_erase_le_maxKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} (he : (t.erase k).isEmpty = false) {fallback : α} : (cmp ((t.erase k).maxKeyD fallback) (t.maxKeyD fallback)).isLE = true

theorem Std.TreeMap.maxKeyD_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {fallback : α} : (t.insertIfNew k v).maxKeyD fallback = t.maxKey?.elim k fun (k' : α) => if cmp k' k = Ordering.lt then k else k'

theorem Std.TreeMap.maxKeyD_le_maxKeyD_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] (he : t.isEmpty = false) {k : α} {v : β} {fallback : α} : (cmp (t.maxKeyD fallback) ((t.insertIfNew k v).maxKeyD fallback)).isLE = true

theorem Std.TreeMap.self_le_maxKeyD_insertIfNew {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {v : β} {fallback : α} : (cmp k ((t.insertIfNew k v).maxKeyD fallback)).isLE = true

theorem Std.TreeMap.maxKeyD_eq_getLastD_keys {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {fallback : α} : t.maxKeyD fallback = t.keys.getLastD fallback

theorem Std.TreeMap.maxKeyD_modify {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} (he : (t.modify k f).isEmpty = false) {fallback : α} : (t.modify k f).maxKeyD fallback = if cmp (t.maxKeyD fallback) k = Ordering.eq then k else t.maxKeyD fallback

@[simp]

theorem Std.TreeMap.maxKeyD_modify_eq_maxKeyD {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] [LawfulEqCmp cmp] {k : α} {f : β → β} {fallback : α} : (t.modify k f).maxKeyD fallback = t.maxKeyD fallback

theorem Std.TreeMap.compare_maxKeyD_modify_eq {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : β → β} {fallback : α} : cmp ((t.modify k f).maxKeyD fallback) (t.maxKeyD fallback) = Ordering.eq

@[simp]

theorem Std.TreeMap.ordCompare_maxKeyD_modify_eq {α : Type u} {β : Type v} [Ord α] [TransOrd α] {t : TreeMap α β compare} {k : α} {f : β → β} {fallback : α} : compare ((t.modify k f).maxKeyD fallback) (t.maxKeyD fallback) = Ordering.eq

theorem Std.TreeMap.maxKeyD_alter_eq_self {α : Type u} {β : Type v} {cmp : α → α → Ordering} {t : TreeMap α β cmp} [TransCmp cmp] {k : α} {f : Option β → Option β} (he : (t.alter k f).isEmpty = false) {fallback : α} : (t.alter k f).maxKeyD fallback = k ↔ (f (t.get? k)).isSome = true ∧ ∀ (k' : α), k' ∈ t → (cmp k' k).isLE = true