| /- | |
| Copyright (c) 2025 Robin Arnez. All rights reserved. | |
| Released under Apache 2.0 license as described in the file LICENSE. | |
| Authors: Robin Arnez | |
| -/ | |
| module | |
| prelude | |
| public import Std.Data.ExtDHashMap.Basic | |
| import all Std.Data.ExtDHashMap.Basic | |
| import all Std.Data.DHashMap.Basic | |
| import all Std.Data.DHashMap.Raw | |
| import all Std.Data.DHashMap.Internal.Defs | |
| public section | |
| /-! | |
| # Extensional dependent hash map lemmas | |
| This file contains lemmas about `Std.ExtDHashMap`. | |
| -/ | |
| set_option linter.missingDocs true | |
| set_option autoImplicit false | |
| attribute [local instance] Std.DHashMap.isSetoid | |
| universe u v w w' | |
| variable {α : Type u} {_ : BEq α} {_ : Hashable α} | |
| variable {β : α → Type v} {γ : α → Type w} | |
| namespace Std.ExtDHashMap | |
| variable {m : ExtDHashMap α β} | |
| @[simp, grind =] | |
| theorem isEmpty_iff [EquivBEq α] [LawfulHashable α] : m.isEmpty ↔ m = ∅ := by | |
| cases m with | mk m | |
| refine m.equiv_empty_iff_isEmpty.symm.trans ?_ | |
| exact ⟨fun h => sound h, exact⟩ | |
| @[simp] | |
| theorem isEmpty_eq_false_iff [EquivBEq α] [LawfulHashable α] : m.isEmpty = false ↔ ¬m = ∅ := | |
| (Bool.not_eq_true _).symm.to_iff.trans (not_congr isEmpty_iff) | |
| @[simp] | |
| theorem empty_eq : ∅ = m ↔ m = ∅ := eq_comm | |
| @[simp, grind =] | |
| theorem emptyWithCapacity_eq [EquivBEq α] [LawfulHashable α] {c} : (emptyWithCapacity c : ExtDHashMap α β) = ∅ := | |
| isEmpty_iff.mp DHashMap.isEmpty_emptyWithCapacity | |
| @[simp] | |
| theorem not_insert_eq_empty [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| ¬m.insert k v = ∅ := | |
| m.inductionOn fun _ => isEmpty_eq_false_iff.mp DHashMap.isEmpty_insert | |
| theorem mem_iff_contains [EquivBEq α] [LawfulHashable α] {a : α} : a ∈ m ↔ m.contains a := | |
| Iff.rfl | |
| @[simp, grind _=_] | |
| theorem contains_iff_mem [EquivBEq α] [LawfulHashable α] {a : α} : m.contains a ↔ a ∈ m := | |
| Iff.rfl | |
| theorem contains_congr [EquivBEq α] [LawfulHashable α] {a b : α} (hab : a == b) : m.contains a = m.contains b := | |
| m.inductionOn fun _ => DHashMap.contains_congr hab | |
| theorem mem_congr [EquivBEq α] [LawfulHashable α] {a b : α} (hab : a == b) : a ∈ m ↔ b ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_congr hab | |
| @[simp, grind =] | |
| theorem contains_empty [EquivBEq α] [LawfulHashable α] {a : α} : (∅ : DHashMap α β).contains a = false := | |
| DHashMap.contains_empty | |
| @[simp] | |
| theorem not_mem_empty [EquivBEq α] [LawfulHashable α] {a : α} : ¬a ∈ (∅ : DHashMap α β) := | |
| DHashMap.not_mem_empty | |
| theorem eq_empty_iff_forall_contains [EquivBEq α] [LawfulHashable α] : m = ∅ ↔ ∀ a, m.contains a = false := | |
| isEmpty_iff.symm.trans <| m.inductionOn fun _ => DHashMap.isEmpty_iff_forall_contains | |
| theorem eq_empty_iff_forall_not_mem [EquivBEq α] [LawfulHashable α] : m = ∅ ↔ ∀ a, ¬a ∈ m := | |
| isEmpty_iff.symm.trans <| m.inductionOn fun _ => DHashMap.isEmpty_iff_forall_not_mem | |
| @[simp] | |
| theorem insert_eq_insert [EquivBEq α] [LawfulHashable α] {p : (a : α) × β a} : | |
| Insert.insert p m = m.insert p.1 p.2 := | |
| rfl | |
| @[simp] | |
| theorem singleton_eq_insert [EquivBEq α] [LawfulHashable α] {p : (a : α) × β a} : | |
| Singleton.singleton p = (∅ : DHashMap α β).insert p.1 p.2 := | |
| rfl | |
| @[simp, grind =] | |
| theorem contains_insert [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} : | |
| (m.insert k v).contains a = (k == a || m.contains a) := | |
| m.inductionOn fun _ => DHashMap.contains_insert | |
| @[simp, grind =] | |
| theorem mem_insert [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} : a ∈ m.insert k v ↔ k == a ∨ a ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_insert | |
| theorem contains_of_contains_insert [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} : | |
| (m.insert k v).contains a → (k == a) = false → m.contains a := | |
| m.inductionOn fun _ => DHashMap.contains_of_contains_insert | |
| theorem mem_of_mem_insert [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} : a ∈ m.insert k v → (k == a) = false → a ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_of_mem_insert | |
| theorem contains_insert_self [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : (m.insert k v).contains k := by simp | |
| theorem mem_insert_self [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : k ∈ m.insert k v := by simp | |
| @[simp, grind =] | |
| theorem size_empty [EquivBEq α] [LawfulHashable α] : (∅ : ExtDHashMap α β).size = 0 := (rfl) | |
| theorem eq_empty_iff_size_eq_zero [EquivBEq α] [LawfulHashable α] : m = ∅ ↔ m.size = 0 := | |
| isEmpty_iff.symm.trans <| m.inductionOn fun _ => | |
| (Bool.eq_iff_iff.mp DHashMap.isEmpty_eq_size_eq_zero).trans beq_iff_eq | |
| @[grind =] theorem size_insert [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| (m.insert k v).size = if k ∈ m then m.size else m.size + 1 := | |
| m.inductionOn fun _ => DHashMap.size_insert | |
| theorem size_le_size_insert [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : m.size ≤ (m.insert k v).size := | |
| m.inductionOn fun _ => DHashMap.size_le_size_insert | |
| theorem size_insert_le [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : (m.insert k v).size ≤ m.size + 1 := | |
| m.inductionOn fun _ => DHashMap.size_insert_le | |
| @[simp, grind =] | |
| theorem erase_empty [EquivBEq α] [LawfulHashable α] {k : α} : (∅ : ExtDHashMap α β).erase k = ∅ := | |
| congrArg mk DHashMap.erase_empty | |
| @[simp] | |
| theorem erase_eq_empty_iff [EquivBEq α] [LawfulHashable α] {k : α} : | |
| m.erase k = ∅ ↔ m = ∅ ∨ m.size = 1 ∧ k ∈ m := by | |
| cases m with | mk m | |
| simp only [← isEmpty_iff, ← decide_eq_decide, Bool.decide_eq_true, Bool.decide_or, | |
| Bool.decide_and, mem_iff_contains] | |
| exact DHashMap.isEmpty_erase | |
| @[simp, grind =] | |
| theorem contains_erase [EquivBEq α] [LawfulHashable α] {k a : α} : | |
| (m.erase k).contains a = (!(k == a) && m.contains a) := | |
| m.inductionOn fun _ => DHashMap.contains_erase | |
| @[simp, grind =] | |
| theorem mem_erase [EquivBEq α] [LawfulHashable α] {k a : α} : | |
| a ∈ m.erase k ↔ (k == a) = false ∧ a ∈ m := by | |
| simp [← contains_iff_mem, contains_erase] | |
| theorem contains_of_contains_erase [EquivBEq α] [LawfulHashable α] {k a : α} : | |
| (m.erase k).contains a → m.contains a := | |
| m.inductionOn fun _ => DHashMap.contains_of_contains_erase | |
| theorem mem_of_mem_erase [EquivBEq α] [LawfulHashable α] {k a : α} : a ∈ m.erase k → a ∈ m := by | |
| simp | |
| @[grind =] theorem size_erase [EquivBEq α] [LawfulHashable α] {k : α} : | |
| (m.erase k).size = if k ∈ m then m.size - 1 else m.size := | |
| m.inductionOn fun _ => DHashMap.size_erase | |
| theorem size_erase_le [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).size ≤ m.size := | |
| m.inductionOn fun _ => DHashMap.size_erase_le | |
| theorem size_le_size_erase [EquivBEq α] [LawfulHashable α] {k : α} : | |
| m.size ≤ (m.erase k).size + 1 := | |
| m.inductionOn fun _ => DHashMap.size_le_size_erase | |
| @[simp, grind =] | |
| theorem containsThenInsert_fst [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : (m.containsThenInsert k v).1 = m.contains k := | |
| m.inductionOn fun _ => DHashMap.containsThenInsert_fst | |
| @[simp, grind =] | |
| theorem containsThenInsert_snd [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : (m.containsThenInsert k v).2 = m.insert k v := | |
| m.inductionOn fun _ => congrArg mk DHashMap.containsThenInsert_snd | |
| @[simp, grind =] | |
| theorem containsThenInsertIfNew_fst [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| (m.containsThenInsertIfNew k v).1 = m.contains k := | |
| m.inductionOn fun _ => DHashMap.containsThenInsertIfNew_fst | |
| @[simp, grind =] | |
| theorem containsThenInsertIfNew_snd [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| (m.containsThenInsertIfNew k v).2 = m.insertIfNew k v := | |
| m.inductionOn fun _ => congrArg mk DHashMap.containsThenInsertIfNew_snd | |
| @[simp, grind =] | |
| theorem get?_empty [LawfulBEq α] {a : α} : (∅ : ExtDHashMap α β).get? a = none := | |
| DHashMap.get?_empty | |
| @[grind =] theorem get?_insert [LawfulBEq α] {a k : α} {v : β k} : (m.insert k v).get? a = | |
| if h : k == a then some (cast (congrArg β (eq_of_beq h)) v) else m.get? a := | |
| m.inductionOn fun _ => DHashMap.get?_insert | |
| @[simp] | |
| theorem get?_insert_self [LawfulBEq α] {k : α} {v : β k} : (m.insert k v).get? k = some v := | |
| m.inductionOn fun _ => DHashMap.get?_insert_self | |
| theorem contains_eq_isSome_get? [LawfulBEq α] {a : α} : m.contains a = (m.get? a).isSome := | |
| m.inductionOn fun _ => DHashMap.contains_eq_isSome_get? | |
| @[simp, grind =] | |
| theorem isSome_get?_eq_contains [LawfulBEq α] {a : α} : (m.get? a).isSome = m.contains a := | |
| contains_eq_isSome_get?.symm | |
| theorem mem_iff_isSome_get? [LawfulBEq α] {a : α} : a ∈ m ↔ (m.get? a).isSome := | |
| m.inductionOn fun _ => DHashMap.mem_iff_isSome_get? | |
| @[simp] | |
| theorem isSome_get?_iff_mem [LawfulBEq α] {a : α} : (m.get? a).isSome ↔ a ∈ m := | |
| mem_iff_isSome_get?.symm | |
| theorem get?_eq_some_iff [LawfulBEq α] {k : α} {v : β k} : | |
| m.get? k = some v ↔ ∃ h : k ∈ m, m.get k h = v := | |
| m.inductionOn fun _ => DHashMap.get?_eq_some_iff | |
| theorem get?_eq_none_of_contains_eq_false [LawfulBEq α] {a : α} : | |
| m.contains a = false → m.get? a = none := | |
| m.inductionOn fun _ => DHashMap.get?_eq_none_of_contains_eq_false | |
| theorem get?_eq_none [LawfulBEq α] {a : α} : ¬a ∈ m → m.get? a = none := by | |
| simpa [← contains_iff_mem] using get?_eq_none_of_contains_eq_false | |
| @[grind =] theorem get?_erase [LawfulBEq α] {k a : α} : | |
| (m.erase k).get? a = if k == a then none else m.get? a := | |
| m.inductionOn fun _ => DHashMap.get?_erase | |
| @[simp] | |
| theorem get?_erase_self [LawfulBEq α] {k : α} : (m.erase k).get? k = none := | |
| m.inductionOn fun _ => DHashMap.get?_erase_self | |
| namespace Const | |
| variable {β : Type v} {m : ExtDHashMap α (fun _ => β)} | |
| @[simp, grind =] | |
| theorem get?_empty [EquivBEq α] [LawfulHashable α] {a : α} : get? (∅ : ExtDHashMap α (fun _ => β)) a = none := | |
| DHashMap.Const.get?_empty | |
| @[grind =] theorem get?_insert [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : | |
| get? (m.insert k v) a = if k == a then some v else get? m a := | |
| m.inductionOn fun _ => DHashMap.Const.get?_insert | |
| @[simp] | |
| theorem get?_insert_self [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : | |
| get? (m.insert k v) k = some v := | |
| m.inductionOn fun _ => DHashMap.Const.get?_insert_self | |
| theorem contains_eq_isSome_get? [EquivBEq α] [LawfulHashable α] {a : α} : | |
| m.contains a = (get? m a).isSome := | |
| m.inductionOn fun _ => DHashMap.Const.contains_eq_isSome_get? | |
| @[simp, grind =] | |
| theorem isSome_get?_eq_contains [EquivBEq α] [LawfulHashable α] {a : α} : | |
| (get? m a).isSome = m.contains a := | |
| contains_eq_isSome_get?.symm | |
| theorem mem_iff_isSome_get? [EquivBEq α] [LawfulHashable α] {a : α} : a ∈ m ↔ (get? m a).isSome := | |
| m.inductionOn fun _ => DHashMap.Const.mem_iff_isSome_get? | |
| @[simp] | |
| theorem isSome_get?_iff_mem [EquivBEq α] [LawfulHashable α] {a : α} : | |
| (get? m a).isSome ↔ a ∈ m := | |
| mem_iff_isSome_get?.symm | |
| theorem get?_eq_some_iff [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : | |
| get? m k = some v ↔ ∃ h : k ∈ m, get m k h = v := | |
| m.inductionOn fun _ => DHashMap.Const.get?_eq_some_iff | |
| theorem get?_eq_none_of_contains_eq_false [EquivBEq α] [LawfulHashable α] {a : α} : | |
| m.contains a = false → get? m a = none := | |
| m.inductionOn fun _ => DHashMap.Const.get?_eq_none_of_contains_eq_false | |
| theorem get?_eq_none [EquivBEq α] [LawfulHashable α] {a : α} : ¬a ∈ m → get? m a = none := by | |
| simpa [← contains_iff_mem] using get?_eq_none_of_contains_eq_false | |
| @[grind =] theorem get?_erase [EquivBEq α] [LawfulHashable α] {k a : α} : | |
| Const.get? (m.erase k) a = if k == a then none else get? m a := | |
| m.inductionOn fun _ => DHashMap.Const.get?_erase | |
| @[simp] | |
| theorem get?_erase_self [EquivBEq α] [LawfulHashable α] {k : α} : get? (m.erase k) k = none := | |
| m.inductionOn fun _ => DHashMap.Const.get?_erase_self | |
| theorem get?_eq_get? [LawfulBEq α] {a : α} : get? m a = m.get? a := | |
| m.inductionOn fun _ => DHashMap.Const.get?_eq_get? | |
| theorem get?_congr [EquivBEq α] [LawfulHashable α] {a b : α} (hab : a == b) : get? m a = get? m b := | |
| m.inductionOn fun _ => DHashMap.Const.get?_congr hab | |
| end Const | |
| @[grind =] theorem get_insert [LawfulBEq α] {k a : α} {v : β k} {h₁} : | |
| (m.insert k v).get a h₁ = | |
| if h₂ : k == a then | |
| cast (congrArg β (eq_of_beq h₂)) v | |
| else | |
| m.get a (mem_of_mem_insert h₁ (Bool.eq_false_iff.2 h₂)) := | |
| m.inductionOn (fun _ _ => DHashMap.get_insert) h₁ | |
| @[simp] | |
| theorem get_insert_self [LawfulBEq α] {k : α} {v : β k} : | |
| (m.insert k v).get k mem_insert_self = v := | |
| m.inductionOn fun _ => DHashMap.get_insert_self | |
| @[simp, grind =] | |
| theorem get_erase [LawfulBEq α] {k a : α} {h'} : | |
| (m.erase k).get a h' = m.get a (mem_of_mem_erase h') := | |
| m.inductionOn (fun _ _ => DHashMap.get_erase) h' | |
| theorem get?_eq_some_get [LawfulBEq α] {a : α} (h) : m.get? a = some (m.get a h) := | |
| m.inductionOn (fun _ h => DHashMap.get?_eq_some_get h) h | |
| theorem get_eq_get_get? [LawfulBEq α] {a : α} {h} : | |
| m.get a h = (m.get? a).get (mem_iff_isSome_get?.mp h) := | |
| m.inductionOn (fun _ _ => DHashMap.get_eq_get_get?) h | |
| @[grind =] theorem get_get? [LawfulBEq α] {a : α} {h} : | |
| (m.get? a).get h = m.get a (mem_iff_isSome_get?.mpr h) := | |
| m.inductionOn (fun _ _ => DHashMap.get_get?) h | |
| namespace Const | |
| variable {β : Type v} {m : ExtDHashMap α (fun _ => β)} | |
| @[grind =] theorem get_insert [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} {h₁} : | |
| get (m.insert k v) a h₁ = | |
| if h₂ : k == a then v else get m a (mem_of_mem_insert h₁ (Bool.eq_false_iff.2 h₂)) := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_insert) h₁ | |
| @[simp] | |
| theorem get_insert_self [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : | |
| get (m.insert k v) k mem_insert_self = v := | |
| m.inductionOn fun _ => DHashMap.Const.get_insert_self | |
| @[simp, grind =] | |
| theorem get_erase [EquivBEq α] [LawfulHashable α] {k a : α} {h'} : | |
| get (m.erase k) a h' = get m a (mem_of_mem_erase h') := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_erase) h' | |
| theorem get?_eq_some_get [EquivBEq α] [LawfulHashable α] {a : α} (h) : | |
| get? m a = some (get m a h) := | |
| m.inductionOn (fun _ h => DHashMap.Const.get?_eq_some_get h) h | |
| theorem get_eq_get_get? [EquivBEq α] [LawfulHashable α] {a : α} {h} : | |
| get m a h = (get? m a).get (mem_iff_isSome_get?.mp h) := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_eq_get_get?) h | |
| @[grind =] theorem get_get? [EquivBEq α] [LawfulHashable α] {a : α} {h} : | |
| (get? m a).get h = get m a (mem_iff_isSome_get?.mpr h) := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_get?) h | |
| theorem get_eq_get [LawfulBEq α] {a : α} {h} : get m a h = m.get a h := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_eq_get) h | |
| theorem get_congr [EquivBEq α] [LawfulHashable α] {a b : α} (hab : a == b) {h'} : | |
| get m a h' = get m b ((mem_congr hab).1 h') := | |
| m.inductionOn (fun _ hab _ => DHashMap.Const.get_congr hab) hab h' | |
| end Const | |
| @[simp, grind =] | |
| theorem get!_empty [LawfulBEq α] {a : α} [Inhabited (β a)] : | |
| (∅ : ExtDHashMap α β).get! a = default := | |
| DHashMap.get!_empty | |
| @[grind =] theorem get!_insert [LawfulBEq α] {k a : α} [Inhabited (β a)] {v : β k} : | |
| (m.insert k v).get! a = | |
| if h : k == a then cast (congrArg β (eq_of_beq h)) v else m.get! a := | |
| m.inductionOn fun _ => DHashMap.get!_insert | |
| @[simp] | |
| theorem get!_insert_self [LawfulBEq α] {a : α} [Inhabited (β a)] {b : β a} : | |
| (m.insert a b).get! a = b := | |
| m.inductionOn fun _ => DHashMap.get!_insert_self | |
| theorem get!_eq_default_of_contains_eq_false [LawfulBEq α] {a : α} [Inhabited (β a)] : | |
| m.contains a = false → m.get! a = default := | |
| m.inductionOn fun _ => DHashMap.get!_eq_default_of_contains_eq_false | |
| theorem get!_eq_default [LawfulBEq α] {a : α} [Inhabited (β a)] : | |
| ¬a ∈ m → m.get! a = default := | |
| m.inductionOn fun _ => DHashMap.get!_eq_default | |
| @[grind =] theorem get!_erase [LawfulBEq α] {k a : α} [Inhabited (β a)] : | |
| (m.erase k).get! a = if k == a then default else m.get! a := | |
| m.inductionOn fun _ => DHashMap.get!_erase | |
| @[simp] | |
| theorem get!_erase_self [LawfulBEq α] {k : α} [Inhabited (β k)] : | |
| (m.erase k).get! k = default := | |
| m.inductionOn fun _ => DHashMap.get!_erase_self | |
| theorem get?_eq_some_get!_of_contains [LawfulBEq α] {a : α} [Inhabited (β a)] : | |
| m.contains a = true → m.get? a = some (m.get! a) := | |
| m.inductionOn fun _ => DHashMap.get?_eq_some_get!_of_contains | |
| theorem get?_eq_some_get! [LawfulBEq α] {a : α} [Inhabited (β a)] : | |
| a ∈ m → m.get? a = some (m.get! a) := | |
| m.inductionOn fun _ => DHashMap.get?_eq_some_get! | |
| theorem get!_eq_get!_get? [LawfulBEq α] {a : α} [Inhabited (β a)] : | |
| m.get! a = (m.get? a).get! := | |
| m.inductionOn fun _ => DHashMap.get!_eq_get!_get? | |
| theorem get_eq_get! [LawfulBEq α] {a : α} [Inhabited (β a)] {h} : | |
| m.get a h = m.get! a := | |
| m.inductionOn (fun _ _ => DHashMap.get_eq_get!) h | |
| namespace Const | |
| variable {β : Type v} {m : ExtDHashMap α (fun _ => β)} | |
| @[simp, grind =] | |
| theorem get!_empty [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : get! (∅ : ExtDHashMap α (fun _ => β)) a = default := | |
| DHashMap.Const.get!_empty | |
| @[grind =] theorem get!_insert [EquivBEq α] [LawfulHashable α] [Inhabited β] {k a : α} {v : β} : | |
| get! (m.insert k v) a = if k == a then v else get! m a := | |
| m.inductionOn fun _ => DHashMap.Const.get!_insert | |
| @[simp] | |
| theorem get!_insert_self [EquivBEq α] [LawfulHashable α] [Inhabited β] {k : α} {v : β} : | |
| get! (m.insert k v) k = v := | |
| m.inductionOn fun _ => DHashMap.Const.get!_insert_self | |
| theorem get!_eq_default_of_contains_eq_false [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : | |
| m.contains a = false → get! m a = default := | |
| m.inductionOn fun _ => DHashMap.Const.get!_eq_default_of_contains_eq_false | |
| theorem get!_eq_default [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : | |
| ¬a ∈ m → get! m a = default := | |
| m.inductionOn fun _ => DHashMap.Const.get!_eq_default | |
| @[grind =] theorem get!_erase [EquivBEq α] [LawfulHashable α] [Inhabited β] {k a : α} : | |
| get! (m.erase k) a = if k == a then default else get! m a := | |
| m.inductionOn fun _ => DHashMap.Const.get!_erase | |
| @[simp] | |
| theorem get!_erase_self [EquivBEq α] [LawfulHashable α] [Inhabited β] {k : α} : | |
| get! (m.erase k) k = default := | |
| m.inductionOn fun _ => DHashMap.Const.get!_erase_self | |
| theorem get?_eq_some_get!_of_contains [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : | |
| m.contains a = true → get? m a = some (get! m a) := | |
| m.inductionOn fun _ => DHashMap.Const.get?_eq_some_get!_of_contains | |
| theorem get?_eq_some_get! [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : | |
| a ∈ m → get? m a = some (get! m a) := | |
| m.inductionOn fun _ => DHashMap.Const.get?_eq_some_get! | |
| theorem get!_eq_get!_get? [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : | |
| get! m a = (get? m a).get! := | |
| m.inductionOn fun _ => DHashMap.Const.get!_eq_get!_get? | |
| theorem get_eq_get! [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} {h} : | |
| get m a h = get! m a := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_eq_get!) h | |
| theorem get!_eq_get! [LawfulBEq α] [Inhabited β] {a : α} : | |
| get! m a = m.get! a := | |
| m.inductionOn fun _ => DHashMap.Const.get!_eq_get! | |
| theorem get!_congr [EquivBEq α] [LawfulHashable α] [Inhabited β] {a b : α} (hab : a == b) : | |
| get! m a = get! m b := | |
| m.inductionOn (fun _ hab => DHashMap.Const.get!_congr hab) hab | |
| end Const | |
| @[simp, grind =] | |
| theorem getD_empty [LawfulBEq α] {a : α} {fallback : β a} : | |
| (∅ : ExtDHashMap α β).getD a fallback = fallback := | |
| DHashMap.getD_empty | |
| @[grind =] theorem getD_insert [LawfulBEq α] {k a : α} {fallback : β a} {v : β k} : | |
| (m.insert k v).getD a fallback = | |
| if h : k == a then cast (congrArg β (eq_of_beq h)) v else m.getD a fallback := | |
| m.inductionOn fun _ => DHashMap.getD_insert | |
| @[simp] | |
| theorem getD_insert_self [LawfulBEq α] {k : α} {fallback v : β k} : | |
| (m.insert k v).getD k fallback = v := | |
| m.inductionOn fun _ => DHashMap.getD_insert_self | |
| theorem getD_eq_fallback_of_contains_eq_false [LawfulBEq α] {a : α} {fallback : β a} : | |
| m.contains a = false → m.getD a fallback = fallback := | |
| m.inductionOn fun _ => DHashMap.getD_eq_fallback_of_contains_eq_false | |
| theorem getD_eq_fallback [LawfulBEq α] {a : α} {fallback : β a} : | |
| ¬a ∈ m → m.getD a fallback = fallback := | |
| m.inductionOn fun _ => DHashMap.getD_eq_fallback | |
| @[grind =] theorem getD_erase [LawfulBEq α] {k a : α} {fallback : β a} : | |
| (m.erase k).getD a fallback = if k == a then fallback else m.getD a fallback := | |
| m.inductionOn fun _ => DHashMap.getD_erase | |
| @[simp] | |
| theorem getD_erase_self [LawfulBEq α] {k : α} {fallback : β k} : | |
| (m.erase k).getD k fallback = fallback := | |
| m.inductionOn fun _ => DHashMap.getD_erase_self | |
| theorem get?_eq_some_getD_of_contains [LawfulBEq α] {a : α} {fallback : β a} : | |
| m.contains a = true → m.get? a = some (m.getD a fallback) := | |
| m.inductionOn fun _ => DHashMap.get?_eq_some_getD_of_contains | |
| theorem get?_eq_some_getD [LawfulBEq α] {a : α} {fallback : β a} : | |
| a ∈ m → m.get? a = some (m.getD a fallback) := | |
| m.inductionOn fun _ => DHashMap.get?_eq_some_getD | |
| theorem getD_eq_getD_get? [LawfulBEq α] {a : α} {fallback : β a} : | |
| m.getD a fallback = (m.get? a).getD fallback := | |
| m.inductionOn fun _ => DHashMap.getD_eq_getD_get? | |
| theorem get_eq_getD [LawfulBEq α] {a : α} {fallback : β a} {h} : | |
| m.get a h = m.getD a fallback := | |
| m.inductionOn (fun _ _ => DHashMap.get_eq_getD) h | |
| theorem get!_eq_getD_default [LawfulBEq α] {a : α} [Inhabited (β a)] : | |
| m.get! a = m.getD a default := | |
| m.inductionOn fun _ => DHashMap.get!_eq_getD_default | |
| namespace Const | |
| variable {β : Type v} {m : ExtDHashMap α (fun _ => β)} | |
| @[simp, grind =] | |
| theorem getD_empty [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} : | |
| getD (∅ : ExtDHashMap α (fun _ => β)) a fallback = fallback := | |
| DHashMap.Const.getD_empty | |
| @[grind =] theorem getD_insert [EquivBEq α] [LawfulHashable α] {k a : α} {fallback v : β} : | |
| getD (m.insert k v) a fallback = if k == a then v else getD m a fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_insert | |
| @[simp] | |
| theorem getD_insert_self [EquivBEq α] [LawfulHashable α] {k : α} {fallback v : β} : | |
| getD (m.insert k v) k fallback = v := | |
| m.inductionOn fun _ => DHashMap.Const.getD_insert_self | |
| theorem getD_eq_fallback_of_contains_eq_false [EquivBEq α] [LawfulHashable α] {a : α} | |
| {fallback : β} : m.contains a = false → getD m a fallback = fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_eq_fallback_of_contains_eq_false | |
| theorem getD_eq_fallback [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} : | |
| ¬a ∈ m → getD m a fallback = fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_eq_fallback | |
| @[grind =] theorem getD_erase [EquivBEq α] [LawfulHashable α] {k a : α} {fallback : β} : | |
| getD (m.erase k) a fallback = if k == a then fallback else getD m a fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_erase | |
| @[simp] | |
| theorem getD_erase_self [EquivBEq α] [LawfulHashable α] {k : α} {fallback : β} : | |
| getD (m.erase k) k fallback = fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_erase_self | |
| theorem get?_eq_some_getD_of_contains [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} : | |
| m.contains a = true → get? m a = some (getD m a fallback) := | |
| m.inductionOn fun _ => DHashMap.Const.get?_eq_some_getD_of_contains | |
| theorem get?_eq_some_getD [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} : | |
| a ∈ m → get? m a = some (getD m a fallback) := | |
| m.inductionOn fun _ => DHashMap.Const.get?_eq_some_getD | |
| theorem getD_eq_getD_get? [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} : | |
| getD m a fallback = (get? m a).getD fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_eq_getD_get? | |
| theorem get_eq_getD [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} {h} : | |
| get m a h = getD m a fallback := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_eq_getD) h | |
| theorem get!_eq_getD_default [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : | |
| get! m a = getD m a default := | |
| m.inductionOn fun _ => DHashMap.Const.get!_eq_getD_default | |
| theorem getD_eq_getD [LawfulBEq α] {a : α} {fallback : β} : | |
| getD m a fallback = m.getD a fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_eq_getD | |
| theorem getD_congr [EquivBEq α] [LawfulHashable α] {a b : α} {fallback : β} (hab : a == b) : | |
| getD m a fallback = getD m b fallback := | |
| m.inductionOn (fun _ hab => DHashMap.Const.getD_congr hab) hab | |
| end Const | |
| @[simp, grind =] | |
| theorem getKey?_empty [EquivBEq α] [LawfulHashable α] {a : α} : (∅ : ExtDHashMap α β).getKey? a = none := | |
| DHashMap.getKey?_empty | |
| @[grind =] theorem getKey?_insert [EquivBEq α] [LawfulHashable α] {a k : α} {v : β k} : | |
| (m.insert k v).getKey? a = if k == a then some k else m.getKey? a := | |
| m.inductionOn fun _ => DHashMap.getKey?_insert | |
| @[simp] | |
| theorem getKey?_insert_self [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| (m.insert k v).getKey? k = some k := | |
| m.inductionOn fun _ => DHashMap.getKey?_insert_self | |
| theorem contains_eq_isSome_getKey? [EquivBEq α] [LawfulHashable α] {a : α} : | |
| m.contains a = (m.getKey? a).isSome := | |
| m.inductionOn fun _ => DHashMap.contains_eq_isSome_getKey? | |
| @[simp, grind =] | |
| theorem isSome_getKey?_eq_contains [EquivBEq α] [LawfulHashable α] {a : α} : | |
| (m.getKey? a).isSome = m.contains a := | |
| contains_eq_isSome_getKey?.symm | |
| theorem mem_iff_isSome_getKey? [EquivBEq α] [LawfulHashable α] {a : α} : | |
| a ∈ m ↔ (m.getKey? a).isSome := | |
| m.inductionOn fun _ => DHashMap.mem_iff_isSome_getKey? | |
| @[simp] | |
| theorem isSome_getKey?_iff_mem [EquivBEq α] [LawfulHashable α] {a : α} : | |
| (m.getKey? a).isSome ↔ a ∈ m := | |
| mem_iff_isSome_getKey?.symm | |
| theorem getKey?_eq_some_iff [EquivBEq α] [LawfulHashable α] {k k' : α} : | |
| m.getKey? k = some k' ↔ ∃ h : k ∈ m, m.getKey k h = k' := | |
| m.inductionOn fun _ => DHashMap.getKey?_eq_some_iff | |
| theorem mem_of_getKey?_eq_some [EquivBEq α] [LawfulHashable α] {k k' : α} | |
| (h : m.getKey? k = some k') : k' ∈ m := | |
| m.inductionOn (fun _ h => DHashMap.mem_of_getKey?_eq_some h) h | |
| theorem getKey?_eq_none_of_contains_eq_false [EquivBEq α] [LawfulHashable α] {a : α} : | |
| m.contains a = false → m.getKey? a = none := | |
| m.inductionOn fun _ => DHashMap.getKey?_eq_none_of_contains_eq_false | |
| theorem getKey?_eq_none [EquivBEq α] [LawfulHashable α] {a : α} : ¬a ∈ m → m.getKey? a = none := | |
| m.inductionOn fun _ => DHashMap.getKey?_eq_none | |
| @[grind =] theorem getKey?_erase [EquivBEq α] [LawfulHashable α] {k a : α} : | |
| (m.erase k).getKey? a = if k == a then none else m.getKey? a := | |
| m.inductionOn fun _ => DHashMap.getKey?_erase | |
| @[simp] | |
| theorem getKey?_erase_self [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).getKey? k = none := | |
| m.inductionOn fun _ => DHashMap.getKey?_erase_self | |
| theorem getKey?_beq [EquivBEq α] [LawfulHashable α] {k : α} : | |
| (m.getKey? k).all (· == k) := | |
| m.inductionOn fun _ => DHashMap.getKey?_beq | |
| theorem getKey?_congr [EquivBEq α] [LawfulHashable α] {k k' : α} (h : k == k') : | |
| m.getKey? k = m.getKey? k' := | |
| m.inductionOn (fun _ h => DHashMap.getKey?_congr h) h | |
| theorem getKey?_eq_some_of_contains [LawfulBEq α] {k : α} (h : m.contains k) : | |
| m.getKey? k = some k := | |
| m.inductionOn (fun _ h => DHashMap.getKey?_eq_some_of_contains h) h | |
| theorem getKey?_eq_some [LawfulBEq α] {k : α} (h : k ∈ m) : m.getKey? k = some k := | |
| m.inductionOn (fun _ h => DHashMap.getKey?_eq_some h) h | |
| @[grind =] theorem getKey_insert [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} {h₁} : | |
| (m.insert k v).getKey a h₁ = | |
| if h₂ : k == a then | |
| k | |
| else | |
| m.getKey a (mem_of_mem_insert h₁ (Bool.eq_false_iff.2 h₂)) := | |
| m.inductionOn (fun _ _ => DHashMap.getKey_insert) h₁ | |
| @[simp] | |
| theorem getKey_insert_self [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| (m.insert k v).getKey k mem_insert_self = k := | |
| m.inductionOn fun _ => DHashMap.getKey_insert_self | |
| @[simp, grind =] | |
| theorem getKey_erase [EquivBEq α] [LawfulHashable α] {k a : α} {h'} : | |
| (m.erase k).getKey a h' = m.getKey a (mem_of_mem_erase h') := | |
| m.inductionOn (fun _ _ => DHashMap.getKey_erase) h' | |
| theorem getKey?_eq_some_getKey [EquivBEq α] [LawfulHashable α] {a : α} (h) : | |
| m.getKey? a = some (m.getKey a h) := | |
| m.inductionOn (fun _ h => DHashMap.getKey?_eq_some_getKey h) h | |
| theorem getKey_eq_get_getKey? [EquivBEq α] [LawfulHashable α] {a : α} {h} : | |
| m.getKey a h = (m.getKey? a).get (mem_iff_isSome_getKey?.mp h) := | |
| m.inductionOn (fun _ _ => DHashMap.getKey_eq_get_getKey?) h | |
| @[simp, grind =] | |
| theorem get_getKey? [EquivBEq α] [LawfulHashable α] {a : α} {h} : | |
| (m.getKey? a).get h = m.getKey a (mem_iff_isSome_getKey?.mpr h) := | |
| m.inductionOn (fun _ _ => DHashMap.get_getKey?) h | |
| theorem getKey_beq [EquivBEq α] [LawfulHashable α] {k : α} (h : k ∈ m) : m.getKey k h == k := | |
| m.inductionOn (fun _ h => DHashMap.getKey_beq h) h | |
| theorem getKey_congr [EquivBEq α] [LawfulHashable α] {k₁ k₂ : α} (h : k₁ == k₂) | |
| (h₁ : k₁ ∈ m) : m.getKey k₁ h₁ = m.getKey k₂ ((mem_congr h).mp h₁) := | |
| m.inductionOn (fun _ h h₁ => DHashMap.getKey_congr h h₁) h h₁ | |
| @[simp, grind =] | |
| theorem getKey_eq [LawfulBEq α] {k : α} (h : k ∈ m) : m.getKey k h = k := | |
| m.inductionOn (fun _ h => DHashMap.getKey_eq h) h | |
| @[simp, grind =] | |
| theorem getKey!_empty [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : | |
| (∅ : ExtDHashMap α β).getKey! a = default := | |
| DHashMap.getKey!_empty | |
| @[grind =] theorem getKey!_insert [EquivBEq α] [LawfulHashable α] [Inhabited α] {k a : α} {v : β k} : | |
| (m.insert k v).getKey! a = | |
| if k == a then k else m.getKey! a := | |
| m.inductionOn fun _ => DHashMap.getKey!_insert | |
| @[simp] | |
| theorem getKey!_insert_self [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} {b : β a} : | |
| (m.insert a b).getKey! a = a := | |
| m.inductionOn fun _ => DHashMap.getKey!_insert_self | |
| theorem getKey!_eq_default_of_contains_eq_false [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {a : α} : | |
| m.contains a = false → m.getKey! a = default := | |
| m.inductionOn fun _ => DHashMap.getKey!_eq_default_of_contains_eq_false | |
| theorem getKey!_eq_default [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : | |
| ¬a ∈ m → m.getKey! a = default := | |
| m.inductionOn fun _ => DHashMap.getKey!_eq_default | |
| @[grind =] theorem getKey!_erase [EquivBEq α] [LawfulHashable α] [Inhabited α] {k a : α} : | |
| (m.erase k).getKey! a = if k == a then default else m.getKey! a := | |
| m.inductionOn fun _ => DHashMap.getKey!_erase | |
| @[simp] | |
| theorem getKey!_erase_self [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} : | |
| (m.erase k).getKey! k = default := | |
| m.inductionOn fun _ => DHashMap.getKey!_erase_self | |
| theorem getKey?_eq_some_getKey!_of_contains [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : | |
| m.contains a = true → m.getKey? a = some (m.getKey! a) := | |
| m.inductionOn fun _ => DHashMap.getKey?_eq_some_getKey!_of_contains | |
| theorem getKey?_eq_some_getKey! [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : | |
| a ∈ m → m.getKey? a = some (m.getKey! a) := | |
| m.inductionOn fun _ => DHashMap.getKey?_eq_some_getKey! | |
| theorem getKey!_eq_get!_getKey? [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : | |
| m.getKey! a = (m.getKey? a).get! := | |
| m.inductionOn fun _ => DHashMap.getKey!_eq_get!_getKey? | |
| theorem getKey_eq_getKey! [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} {h} : | |
| m.getKey a h = m.getKey! a := | |
| m.inductionOn (fun _ _ => DHashMap.getKey_eq_getKey!) h | |
| theorem getKey!_congr [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} (h : k == k') : | |
| m.getKey! k = m.getKey! k' := | |
| m.inductionOn (fun _ h => DHashMap.getKey!_congr h) h | |
| theorem getKey!_eq_of_contains [LawfulBEq α] [Inhabited α] {k : α} (h : m.contains k) : | |
| m.getKey! k = k := | |
| m.inductionOn (fun _ h => DHashMap.getKey!_eq_of_contains h) h | |
| theorem getKey!_eq_of_mem [LawfulBEq α] [Inhabited α] {k : α} (h : k ∈ m) : m.getKey! k = k := | |
| m.inductionOn (fun _ h => DHashMap.getKey!_eq_of_mem h) h | |
| @[simp, grind =] | |
| theorem getKeyD_empty [EquivBEq α] [LawfulHashable α] {a fallback : α} : | |
| (∅ : ExtDHashMap α β).getKeyD a fallback = fallback := | |
| DHashMap.getKeyD_empty | |
| @[grind =] theorem getKeyD_insert [EquivBEq α] [LawfulHashable α] {k a fallback : α} {v : β k} : | |
| (m.insert k v).getKeyD a fallback = | |
| if k == a then k else m.getKeyD a fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_insert | |
| @[simp] | |
| theorem getKeyD_insert_self [EquivBEq α] [LawfulHashable α] {k fallback : α} {v : β k} : | |
| (m.insert k v).getKeyD k fallback = k := | |
| m.inductionOn fun _ => DHashMap.getKeyD_insert_self | |
| theorem getKeyD_eq_fallback_of_contains_eq_false [EquivBEq α] [LawfulHashable α] {a : α} | |
| {fallback : α} : | |
| m.contains a = false → m.getKeyD a fallback = fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_eq_fallback_of_contains_eq_false | |
| theorem getKeyD_eq_fallback [EquivBEq α] [LawfulHashable α] {a fallback : α} : | |
| ¬a ∈ m → m.getKeyD a fallback = fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_eq_fallback | |
| @[grind =] theorem getKeyD_erase [EquivBEq α] [LawfulHashable α] {k a fallback : α} : | |
| (m.erase k).getKeyD a fallback = if k == a then fallback else m.getKeyD a fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_erase | |
| @[simp] | |
| theorem getKeyD_erase_self [EquivBEq α] [LawfulHashable α] {k fallback : α} : | |
| (m.erase k).getKeyD k fallback = fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_erase_self | |
| theorem getKey?_eq_some_getKeyD_of_contains [EquivBEq α] [LawfulHashable α] {a fallback : α} : | |
| m.contains a = true → m.getKey? a = some (m.getKeyD a fallback) := | |
| m.inductionOn fun _ => DHashMap.getKey?_eq_some_getKeyD_of_contains | |
| theorem getKey?_eq_some_getKeyD [EquivBEq α] [LawfulHashable α] {a fallback : α} : | |
| a ∈ m → m.getKey? a = some (m.getKeyD a fallback) := | |
| m.inductionOn fun _ => DHashMap.getKey?_eq_some_getKeyD | |
| theorem getKeyD_eq_getD_getKey? [EquivBEq α] [LawfulHashable α] {a fallback : α} : | |
| m.getKeyD a fallback = (m.getKey? a).getD fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_eq_getD_getKey? | |
| theorem getKey_eq_getKeyD [EquivBEq α] [LawfulHashable α] {a fallback : α} {h} : | |
| m.getKey a h = m.getKeyD a fallback := | |
| m.inductionOn (fun _ _ => DHashMap.getKey_eq_getKeyD) h | |
| theorem getKey!_eq_getKeyD_default [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : | |
| m.getKey! a = m.getKeyD a default := | |
| m.inductionOn fun _ => DHashMap.getKey!_eq_getKeyD_default | |
| theorem getKeyD_congr [EquivBEq α] [LawfulHashable α] {k k' fallback : α} | |
| (h : k == k') : m.getKeyD k fallback = m.getKeyD k' fallback := | |
| m.inductionOn (fun _ h => DHashMap.getKeyD_congr h) h | |
| theorem getKeyD_eq_of_contains [LawfulBEq α] {k fallback : α} (h : m.contains k) : | |
| m.getKeyD k fallback = k := | |
| m.inductionOn (fun _ h => DHashMap.getKeyD_eq_of_contains h) h | |
| theorem getKeyD_eq_of_mem [LawfulBEq α] {k fallback : α} (h : k ∈ m) : | |
| m.getKeyD k fallback = k := | |
| m.inductionOn (fun _ h => DHashMap.getKeyD_eq_of_mem h) h | |
| @[simp] | |
| theorem not_insertIfNew_eq_empty [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| ¬m.insertIfNew k v = ∅ := | |
| isEmpty_eq_false_iff.mp <| m.inductionOn fun _ => DHashMap.isEmpty_insertIfNew | |
| @[simp, grind =] | |
| theorem contains_insertIfNew [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} : | |
| (m.insertIfNew k v).contains a = (k == a || m.contains a) := | |
| m.inductionOn fun _ => DHashMap.contains_insertIfNew | |
| @[simp, grind =] | |
| theorem mem_insertIfNew [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} : | |
| a ∈ m.insertIfNew k v ↔ k == a ∨ a ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_insertIfNew | |
| theorem contains_insertIfNew_self [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| (m.insertIfNew k v).contains k := | |
| m.inductionOn fun _ => DHashMap.contains_insertIfNew_self | |
| theorem mem_insertIfNew_self [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| k ∈ m.insertIfNew k v := | |
| m.inductionOn fun _ => DHashMap.mem_insertIfNew_self | |
| theorem contains_of_contains_insertIfNew [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} : | |
| (m.insertIfNew k v).contains a → (k == a) = false → m.contains a := | |
| m.inductionOn fun _ => DHashMap.contains_of_contains_insertIfNew | |
| theorem mem_of_mem_insertIfNew [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} : | |
| a ∈ m.insertIfNew k v → (k == a) = false → a ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_of_mem_insertIfNew | |
| /-- This is a restatement of `contains_of_contains_insertIfNew` that is written to exactly match the proof | |
| obligation in the statement of `get_insertIfNew`. -/ | |
| theorem contains_of_contains_insertIfNew' [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} : | |
| (m.insertIfNew k v).contains a → ¬((k == a) ∧ m.contains k = false) → m.contains a := | |
| m.inductionOn fun _ => DHashMap.contains_of_contains_insertIfNew' | |
| /-- 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 mem_of_mem_insertIfNew' [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} : | |
| a ∈ m.insertIfNew k v → ¬((k == a) ∧ ¬k ∈ m) → a ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_of_mem_insertIfNew' | |
| @[grind =] theorem size_insertIfNew [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| (m.insertIfNew k v).size = if k ∈ m then m.size else m.size + 1 := | |
| m.inductionOn fun _ => DHashMap.size_insertIfNew | |
| theorem size_le_size_insertIfNew [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| m.size ≤ (m.insertIfNew k v).size := | |
| m.inductionOn fun _ => DHashMap.size_le_size_insertIfNew | |
| theorem size_insertIfNew_le [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| (m.insertIfNew k v).size ≤ m.size + 1 := | |
| m.inductionOn fun _ => DHashMap.size_insertIfNew_le | |
| @[grind =] theorem get?_insertIfNew [LawfulBEq α] {k a : α} {v : β k} : (m.insertIfNew k v).get? a = | |
| if h : k == a ∧ ¬k ∈ m then some (cast (congrArg β (eq_of_beq h.1)) v) else m.get? a := | |
| m.inductionOn fun _ => DHashMap.get?_insertIfNew | |
| @[grind =] theorem get_insertIfNew [LawfulBEq α] {k a : α} {v : β k} {h₁} : (m.insertIfNew k v).get a h₁ = | |
| if h₂ : k == a ∧ ¬k ∈ m then cast (congrArg β (eq_of_beq h₂.1)) v else m.get a | |
| (mem_of_mem_insertIfNew' h₁ h₂) := | |
| m.inductionOn (fun _ _ => DHashMap.get_insertIfNew) h₁ | |
| @[grind =] theorem get!_insertIfNew [LawfulBEq α] {k a : α} [Inhabited (β a)] {v : β k} : | |
| (m.insertIfNew k v).get! a = | |
| if h : k == a ∧ ¬k ∈ m then cast (congrArg β (eq_of_beq h.1)) v else m.get! a := | |
| m.inductionOn fun _ => DHashMap.get!_insertIfNew | |
| @[grind =] theorem getD_insertIfNew [LawfulBEq α] {k a : α} {fallback : β a} {v : β k} : | |
| (m.insertIfNew k v).getD a fallback = | |
| if h : k == a ∧ ¬k ∈ m then cast (congrArg β (eq_of_beq h.1)) v | |
| else m.getD a fallback := | |
| m.inductionOn fun _ => DHashMap.getD_insertIfNew | |
| namespace Const | |
| variable {β : Type v} {m : ExtDHashMap α (fun _ => β)} | |
| @[grind =] theorem get?_insertIfNew [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : | |
| get? (m.insertIfNew k v) a = if k == a ∧ ¬k ∈ m then some v else get? m a := | |
| m.inductionOn fun _ => DHashMap.Const.get?_insertIfNew | |
| @[grind =] theorem get_insertIfNew [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} {h₁} : | |
| get (m.insertIfNew k v) a h₁ = | |
| if h₂ : k == a ∧ ¬k ∈ m then v else get m a (mem_of_mem_insertIfNew' h₁ h₂) := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_insertIfNew) h₁ | |
| @[grind =] theorem get!_insertIfNew [EquivBEq α] [LawfulHashable α] [Inhabited β] {k a : α} {v : β} : | |
| get! (m.insertIfNew k v) a = if k == a ∧ ¬k ∈ m then v else get! m a := | |
| m.inductionOn fun _ => DHashMap.Const.get!_insertIfNew | |
| @[grind =] theorem getD_insertIfNew [EquivBEq α] [LawfulHashable α] {k a : α} {fallback v : β} : | |
| getD (m.insertIfNew k v) a fallback = | |
| if k == a ∧ ¬k ∈ m then v else getD m a fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_insertIfNew | |
| end Const | |
| @[grind =] theorem getKey?_insertIfNew [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} : | |
| getKey? (m.insertIfNew k v) a = if k == a ∧ ¬k ∈ m then some k else getKey? m a := | |
| m.inductionOn fun _ => DHashMap.getKey?_insertIfNew | |
| @[grind =] theorem getKey_insertIfNew [EquivBEq α] [LawfulHashable α] {k a : α} {v : β k} {h₁} : | |
| getKey (m.insertIfNew k v) a h₁ = | |
| if h₂ : k == a ∧ ¬k ∈ m then k else getKey m a (mem_of_mem_insertIfNew' h₁ h₂) := | |
| m.inductionOn (fun _ _ => DHashMap.getKey_insertIfNew) h₁ | |
| @[grind =] theorem getKey!_insertIfNew [EquivBEq α] [LawfulHashable α] [Inhabited α] {k a : α} {v : β k} : | |
| getKey! (m.insertIfNew k v) a = if k == a ∧ ¬k ∈ m then k else getKey! m a := | |
| m.inductionOn fun _ => DHashMap.getKey!_insertIfNew | |
| @[grind =] theorem getKeyD_insertIfNew [EquivBEq α] [LawfulHashable α] {k a fallback : α} {v : β k} : | |
| getKeyD (m.insertIfNew k v) a fallback = | |
| if k == a ∧ ¬k ∈ m then k else getKeyD m a fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_insertIfNew | |
| @[simp, grind =] | |
| theorem getThenInsertIfNew?_fst [LawfulBEq α] {k : α} {v : β k} : | |
| (m.getThenInsertIfNew? k v).1 = m.get? k := | |
| m.inductionOn fun _ => DHashMap.getThenInsertIfNew?_fst | |
| @[simp, grind =] | |
| theorem getThenInsertIfNew?_snd [LawfulBEq α] {k : α} {v : β k} : | |
| (m.getThenInsertIfNew? k v).2 = m.insertIfNew k v := | |
| m.inductionOn fun _ => congrArg mk DHashMap.getThenInsertIfNew?_snd | |
| theorem mem_of_get_eq [LawfulBEq α] {k : α} {v : β k} {w} (_ : m.get k w = v) : k ∈ m := w | |
| namespace Const | |
| variable {β : Type v} {m : ExtDHashMap α (fun _ => β)} | |
| @[simp, grind =] | |
| theorem getThenInsertIfNew?_fst [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (getThenInsertIfNew? m k v).1 = get? m k := | |
| m.inductionOn fun _ => DHashMap.Const.getThenInsertIfNew?_fst | |
| @[simp, grind =] | |
| theorem getThenInsertIfNew?_snd [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : | |
| (getThenInsertIfNew? m k v).2 = m.insertIfNew k v := | |
| m.inductionOn fun _ => congrArg mk DHashMap.Const.getThenInsertIfNew?_snd | |
| end Const | |
| section insertMany | |
| variable {ρ : Type w} [ForIn Id ρ ((a : α) × β a)] | |
| @[simp, grind =] | |
| theorem insertMany_nil [EquivBEq α] [LawfulHashable α] : m.insertMany [] = m := (rfl) | |
| @[simp, grind =] | |
| theorem insertMany_list_singleton [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| m.insertMany [⟨k, v⟩] = m.insert k v := (rfl) | |
| @[grind _=_] | |
| theorem insertMany_cons [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} {p : (a : α) × β a} : | |
| m.insertMany (p :: l) = (m.insert p.1 p.2).insertMany l := by | |
| rcases p with ⟨k, v⟩ | |
| unfold insertMany | |
| simp only [bind_pure_comp, map_pure, List.forIn_pure_yield_eq_foldl, List.foldl_cons, Id.run_pure] | |
| refine Eq.trans ?_ (Eq.symm ?_ : l.foldl (fun b a => b.insert a.1 a.2) (m.insert k v) = _) | |
| exact (List.foldl_hom (f := Subtype.val) fun x y => rfl).symm | |
| exact (List.foldl_hom (f := Subtype.val) fun x y => rfl).symm | |
| @[grind _=_] | |
| theorem insertMany_append [EquivBEq α] [LawfulHashable α] {l₁ l₂ : List ((a : α) × β a)} : | |
| insertMany m (l₁ ++ l₂) = insertMany (insertMany m l₁) l₂ := by | |
| induction l₁ generalizing m with | |
| | nil => simp | |
| | cons hd tl ih => | |
| rw [List.cons_append, insertMany_cons, insertMany_cons, ih] | |
| private theorem insertMany_list_mk [EquivBEq α] [LawfulHashable α] | |
| {m : DHashMap α β} {l : List ((a : α) × β a)} : | |
| (ExtDHashMap.insertMany (mk m) l : ExtDHashMap α β) = mk (m.insertMany l) := by | |
| simp only [mk, Quotient.mk] | |
| induction l generalizing m with | |
| | nil => rfl | |
| | cons x l ih => | |
| rcases x with ⟨k, v⟩ | |
| simp only [insertMany_cons, insert, mk, Quotient.mk, ih, DHashMap.insertMany_cons, lift] | |
| @[elab_as_elim] | |
| theorem insertMany_ind [EquivBEq α] [LawfulHashable α] {motive : ExtDHashMap α β → Prop} | |
| (m : ExtDHashMap α β) (l : ρ) | |
| (init : motive m) (insert : ∀ m a b, motive m → motive (m.insert a b)) : | |
| motive (m.insertMany l) := by | |
| change motive (Subtype.val ?my_mvar) | |
| exact Subtype.property ?my_mvar motive init (insert _ _ _) | |
| @[simp, grind =] | |
| theorem contains_insertMany_list [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} {k : α} : | |
| (m.insertMany l).contains k = (m.contains k || (l.map Sigma.fst).contains k) := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.contains_insertMany_list | |
| @[simp, grind =] | |
| theorem mem_insertMany_list [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} {k : α} : | |
| k ∈ m.insertMany l ↔ k ∈ m ∨ (l.map Sigma.fst).contains k := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.mem_insertMany_list | |
| theorem mem_of_mem_insertMany_list [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} {k : α} (mem : k ∈ m.insertMany l) | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| k ∈ m := by | |
| refine m.inductionOn (fun _ mem contains_eq_false => ?_) mem contains_eq_false | |
| simp only [insertMany_list_mk] at mem | |
| exact DHashMap.mem_of_mem_insertMany_list mem contains_eq_false | |
| theorem mem_insertMany_of_mem [EquivBEq α] [LawfulHashable α] {l : ρ} {k : α} (h' : k ∈ m) : k ∈ m.insertMany l := | |
| insertMany_ind m l h' fun _ _ _ h => mem_insert.mpr (.inr h) | |
| theorem get?_insertMany_list_of_contains_eq_false [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k : α} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (m.insertMany l).get? k = m.get? k := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.get?_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem get?_insertMany_list_of_mem [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k k' : α} (k_beq : k == k') {v : β k} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) : | |
| (m.insertMany l).get? k' = some (cast (by congr; apply LawfulBEq.eq_of_beq k_beq) v) := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.get?_insertMany_list_of_mem k_beq distinct mem | |
| theorem get_insertMany_list_of_contains_eq_false [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k : α} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) | |
| {h} : | |
| (m.insertMany l).get k h = | |
| m.get k (mem_of_mem_insertMany_list h contains_eq_false) := by | |
| refine m.inductionOn (fun _ contains_eq_false _ => ?_) contains_eq_false h | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.get_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem get_insertMany_list_of_mem [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k k' : α} (k_beq : k == k') {v : β k} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) | |
| {h} : | |
| (m.insertMany l).get k' h = cast (by congr; apply LawfulBEq.eq_of_beq k_beq) v := by | |
| refine m.inductionOn (fun _ k_beq distinct mem _ => ?_) k_beq distinct mem h | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.get_insertMany_list_of_mem k_beq distinct mem | |
| theorem get!_insertMany_list_of_contains_eq_false [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k : α} [Inhabited (β k)] | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (m.insertMany l).get! k = m.get! k := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.get!_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem get!_insertMany_list_of_mem [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k k' : α} (k_beq : k == k') {v : β k} [Inhabited (β k')] | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) : | |
| (m.insertMany l).get! k' = cast (by congr; apply LawfulBEq.eq_of_beq k_beq) v := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.get!_insertMany_list_of_mem k_beq distinct mem | |
| theorem getD_insertMany_list_of_contains_eq_false [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k : α} {fallback : β k} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (m.insertMany l).getD k fallback = m.getD k fallback := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.getD_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem getD_insertMany_list_of_mem [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k k' : α} (k_beq : k == k') {v : β k} {fallback : β k'} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) : | |
| (m.insertMany l).getD k' fallback = cast (by congr; apply LawfulBEq.eq_of_beq k_beq) v := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.getD_insertMany_list_of_mem k_beq distinct mem | |
| theorem getKey?_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} {k : α} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (m.insertMany l).getKey? k = m.getKey? k := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.getKey?_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem getKey?_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Sigma.fst) : | |
| (m.insertMany l).getKey? k' = some k := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.getKey?_insertMany_list_of_mem k_beq distinct mem | |
| theorem getKey_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} {k : α} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) | |
| {h} : | |
| (m.insertMany l).getKey k h = | |
| m.getKey k (mem_of_mem_insertMany_list h contains_eq_false) := by | |
| refine m.inductionOn (fun _ contains_eq_false _ => ?_) contains_eq_false h | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.getKey_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem getKey_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Sigma.fst) | |
| {h} : | |
| (m.insertMany l).getKey k' h = k := by | |
| refine m.inductionOn (fun _ k_beq distinct mem _ => ?_) k_beq distinct mem h | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.getKey_insertMany_list_of_mem k_beq distinct mem | |
| theorem getKey!_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {l : List ((a : α) × β a)} {k : α} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (m.insertMany l).getKey! k = m.getKey! k := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.getKey!_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem getKey!_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {l : List ((a : α) × β a)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Sigma.fst) : | |
| (m.insertMany l).getKey! k' = k := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.getKey!_insertMany_list_of_mem k_beq distinct mem | |
| theorem getKeyD_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} {k fallback : α} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (m.insertMany l).getKeyD k fallback = m.getKeyD k fallback := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.getKeyD_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem getKeyD_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} | |
| {k k' fallback : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Sigma.fst) : | |
| (m.insertMany l).getKeyD k' fallback = k := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.getKeyD_insertMany_list_of_mem k_beq distinct mem | |
| theorem size_insertMany_list [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) : | |
| (∀ (a : α), a ∈ m → (l.map Sigma.fst).contains a = false) → | |
| (m.insertMany l).size = m.size + l.length := by | |
| refine m.inductionOn (fun _ distinct => ?_) distinct | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.size_insertMany_list distinct | |
| theorem size_le_size_insertMany_list [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} : | |
| m.size ≤ (m.insertMany l).size := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.size_le_size_insertMany_list | |
| theorem size_le_size_insertMany [EquivBEq α] [LawfulHashable α] {l : ρ} : m.size ≤ (m.insertMany l).size := | |
| insertMany_ind m l (Nat.le_refl _) fun _ _ _ h => Nat.le_trans h size_le_size_insert | |
| grind_pattern size_le_size_insertMany_list => (m.insertMany l).size | |
| theorem size_insertMany_list_le [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} : | |
| (m.insertMany l).size ≤ m.size + l.length := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.size_insertMany_list_le | |
| grind_pattern size_insertMany_list_le => (m.insertMany l).size | |
| @[simp] | |
| theorem insertMany_list_eq_empty_iff [EquivBEq α] [LawfulHashable α] {l : List ((a : α) × β a)} : | |
| m.insertMany l = ∅ ↔ m = ∅ ∧ l = [] := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertMany_list_mk, ← isEmpty_iff, ← List.isEmpty_iff, | |
| Bool.coe_iff_coe, ← Bool.and_eq_true] | |
| exact DHashMap.isEmpty_insertMany_list | |
| theorem eq_empty_of_insertMany_eq_empty [EquivBEq α] [LawfulHashable α] {l : ρ} : | |
| m.insertMany l = ∅ → m = ∅ := | |
| insertMany_ind m l id fun _ _ _ _ h => absurd h not_insert_eq_empty | |
| namespace Const | |
| variable {β : Type v} {m : ExtDHashMap α (fun _ => β)} | |
| variable {ρ : Type w} [ForIn Id ρ (α × β)] | |
| @[simp, grind =] | |
| theorem insertMany_nil [EquivBEq α] [LawfulHashable α] : insertMany m [] = m := | |
| (rfl) | |
| @[simp, grind =] | |
| theorem insertMany_list_singleton [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : | |
| insertMany m [⟨k, v⟩] = m.insert k v := (rfl) | |
| @[grind _=_] | |
| theorem insertMany_cons [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {p : α × β} : | |
| insertMany m (p :: l) = insertMany (m.insert p.1 p.2) l := by | |
| rcases p with ⟨k, v⟩ | |
| unfold insertMany | |
| simp only [bind_pure_comp, map_pure, List.forIn_pure_yield_eq_foldl, List.foldl_cons, Id.run_pure] | |
| refine Eq.trans ?_ (Eq.symm ?_ : l.foldl (fun b a => b.insert a.1 a.2) (m.insert k v) = _) | |
| exact (List.foldl_hom (f := Subtype.val) fun x y => rfl).symm | |
| exact (List.foldl_hom (f := Subtype.val) fun x y => rfl).symm | |
| @[grind _=_] | |
| theorem insertMany_append [EquivBEq α] [LawfulHashable α] {l₁ l₂ : List (α × β)} : | |
| insertMany m (l₁ ++ l₂) = insertMany (insertMany m l₁) l₂ := by | |
| induction l₁ generalizing m with | |
| | nil => simp | |
| | cons hd tl ih => | |
| rw [List.cons_append, insertMany_cons, insertMany_cons, ih] | |
| private theorem insertMany_list_mk [EquivBEq α] [LawfulHashable α] | |
| {m : DHashMap α fun _ => β} {l : List (α × β)} : | |
| (insertMany (mk m) l : ExtDHashMap α fun _ => β) = | |
| mk (DHashMap.Const.insertMany m l) := by | |
| simp only [mk, Quotient.mk] | |
| induction l generalizing m with | |
| | nil => rfl | |
| | cons x l ih => | |
| rcases x with ⟨k, v⟩ | |
| simp only [insertMany_cons, insert, mk, Quotient.mk, ih, DHashMap.Const.insertMany_cons, lift] | |
| @[elab_as_elim] | |
| theorem insertMany_ind [EquivBEq α] [LawfulHashable α] {motive : ExtDHashMap α (fun _ => β) → Prop} | |
| (m : ExtDHashMap α fun _ => β) (l : ρ) | |
| (init : motive m) (insert : ∀ m a b, motive m → motive (m.insert a b)) : | |
| motive (insertMany m l) := by | |
| change motive (Subtype.val ?my_mvar) | |
| exact Subtype.property ?my_mvar motive init (insert _ _ _) | |
| @[simp, grind =] | |
| theorem contains_insertMany_list [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} : | |
| (Const.insertMany m l).contains k = (m.contains k || (l.map Prod.fst).contains k) := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.contains_insertMany_list | |
| @[simp, grind =] | |
| theorem mem_insertMany_list [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} : | |
| k ∈ insertMany m l ↔ k ∈ m ∨ (l.map Prod.fst).contains k := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.mem_insertMany_list | |
| theorem mem_of_mem_insertMany_list [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} (mem : k ∈ insertMany m l) | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| k ∈ m := by | |
| refine m.inductionOn (fun _ mem contains_eq_false => ?_) mem contains_eq_false | |
| simp only [insertMany_list_mk] at mem | |
| exact DHashMap.Const.mem_of_mem_insertMany_list mem contains_eq_false | |
| theorem mem_insertMany_of_mem [EquivBEq α] [LawfulHashable α] {l : ρ} {k : α} (h' : k ∈ m) : k ∈ insertMany m l := | |
| insertMany_ind m l h' fun _ _ _ h => mem_insert.mpr (.inr h) | |
| theorem getKey?_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| (insertMany m l).getKey? k = m.getKey? k := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.getKey?_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem getKey?_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Prod.fst) : | |
| (insertMany m l).getKey? k' = some k := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.getKey?_insertMany_list_of_mem k_beq distinct mem | |
| theorem getKey_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) | |
| {h} : | |
| (insertMany m l).getKey k h = | |
| m.getKey k (mem_of_mem_insertMany_list h contains_eq_false) := by | |
| refine m.inductionOn (fun _ contains_eq_false _ => ?_) contains_eq_false h | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.getKey_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem getKey_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Prod.fst) | |
| {h} : | |
| (insertMany m l).getKey k' h = k := by | |
| refine m.inductionOn (fun _ k_beq distinct mem _ => ?_) k_beq distinct mem h | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.getKey_insertMany_list_of_mem k_beq distinct mem | |
| theorem getKey!_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {l : List (α × β)} {k : α} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| (insertMany m l).getKey! k = m.getKey! k := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.getKey!_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem getKey!_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {l : List (α × β)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Prod.fst) : | |
| (insertMany m l).getKey! k' = k := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.getKey!_insertMany_list_of_mem k_beq distinct mem | |
| theorem getKeyD_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k fallback : α} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| (insertMany m l).getKeyD k fallback = m.getKeyD k fallback := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.getKeyD_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem getKeyD_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} | |
| {k k' fallback : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Prod.fst) : | |
| (insertMany m l).getKeyD k' fallback = k := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.getKeyD_insertMany_list_of_mem k_beq distinct mem | |
| theorem size_insertMany_list [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) : | |
| (∀ (a : α), a ∈ m → (l.map Prod.fst).contains a = false) → | |
| (insertMany m l).size = m.size + l.length := by | |
| refine m.inductionOn (fun _ distinct => ?_) distinct | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.size_insertMany_list distinct | |
| theorem size_le_size_insertMany_list [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} : | |
| m.size ≤ (insertMany m l).size := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.size_le_size_insertMany_list | |
| theorem size_le_size_insertMany [EquivBEq α] [LawfulHashable α] {l : ρ} : m.size ≤ (insertMany m l).size := | |
| insertMany_ind m l (Nat.le_refl _) fun _ _ _ h => Nat.le_trans h size_le_size_insert | |
| grind_pattern size_le_size_insertMany => (insertMany m l).size | |
| theorem size_insertMany_list_le [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} : | |
| (insertMany m l).size ≤ m.size + l.length := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.size_insertMany_list_le | |
| grind_pattern size_insertMany_list_le => (insertMany m l).size | |
| @[simp] | |
| theorem insertMany_list_eq_empty_iff [EquivBEq α] [LawfulHashable α] {l : List (α × β)} : | |
| insertMany m l = ∅ ↔ m = ∅ ∧ l = [] := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertMany_list_mk, ← isEmpty_iff, ← List.isEmpty_iff, | |
| Bool.coe_iff_coe, ← Bool.and_eq_true] | |
| exact DHashMap.Const.isEmpty_insertMany_list | |
| theorem eq_empty_of_insertMany_eq_empty [EquivBEq α] [LawfulHashable α] {l : ρ} : insertMany m l = ∅ → m = ∅ := | |
| insertMany_ind m l id fun _ _ _ _ h => absurd h not_insert_eq_empty | |
| theorem get?_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| get? (insertMany m l) k = get? m k := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.get?_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem get?_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k k' : α} (k_beq : k == k') {v : β} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) (mem : ⟨k, v⟩ ∈ l) : | |
| get? (insertMany m l) k' = some v := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.get?_insertMany_list_of_mem k_beq distinct mem | |
| @[grind =] theorem get?_insertMany_list [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} : | |
| get? (insertMany m l) k = | |
| (l.findSomeRev? (fun ⟨a, b⟩ => if a == k then some b else none)).or (get? m k) := by | |
| refine m.inductionOn (fun _ => ?_) | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.get?_insertMany_list | |
| theorem get_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) | |
| {h} : | |
| get (insertMany m l) k h = get m k (mem_of_mem_insertMany_list h contains_eq_false) := by | |
| refine m.inductionOn (fun _ contains_eq_false _ => ?_) contains_eq_false h | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.get_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem get_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k k' : α} (k_beq : k == k') {v : β} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) (mem : ⟨k, v⟩ ∈ l) {h} : | |
| get (insertMany m l) k' h = v := by | |
| refine m.inductionOn (fun _ k_beq distinct mem _ => ?_) k_beq distinct mem h | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.get_insertMany_list_of_mem k_beq distinct mem | |
| theorem get!_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| [Inhabited β] {l : List (α × β)} {k : α} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| get! (insertMany m l) k = get! m k := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.get!_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem get!_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] [Inhabited β] | |
| {l : List (α × β)} {k k' : α} (k_beq : k == k') {v : β} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) (mem : ⟨k, v⟩ ∈ l) : | |
| get! (insertMany m l) k' = v := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.get!_insertMany_list_of_mem k_beq distinct mem | |
| theorem getD_insertMany_list_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} {fallback : β} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| getD (insertMany m l) k fallback = getD m k fallback := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.getD_insertMany_list_of_contains_eq_false contains_eq_false | |
| theorem getD_insertMany_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k k' : α} (k_beq : k == k') {v fallback : β} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) (mem : ⟨k, v⟩ ∈ l) : | |
| getD (insertMany m l) k' fallback = v := by | |
| refine m.inductionOn (fun _ k_beq distinct mem => ?_) k_beq distinct mem | |
| simp only [insertMany_list_mk] | |
| exact DHashMap.Const.getD_insertMany_list_of_mem k_beq distinct mem | |
| variable {m : ExtDHashMap α (fun _ => Unit)} | |
| variable {ρ : Type w} [ForIn Id ρ α] | |
| @[simp] | |
| theorem insertManyIfNewUnit_nil [EquivBEq α] [LawfulHashable α] : | |
| insertManyIfNewUnit m [] = m := | |
| (rfl) | |
| @[simp] | |
| theorem insertManyIfNewUnit_list_singleton [EquivBEq α] [LawfulHashable α] {k : α} : | |
| insertManyIfNewUnit m [k] = m.insertIfNew k () := (rfl) | |
| theorem insertManyIfNewUnit_cons [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} : | |
| insertManyIfNewUnit m (k :: l) = insertManyIfNewUnit (m.insertIfNew k ()) l := by | |
| unfold insertManyIfNewUnit | |
| simp only [bind_pure_comp, map_pure, List.forIn_pure_yield_eq_foldl, List.foldl_cons, Id.run_pure] | |
| refine Eq.trans ?_ (Eq.symm ?_ : l.foldl (fun b a => b.insertIfNew a ()) (m.insertIfNew k ()) = _) | |
| exact (List.foldl_hom (f := Subtype.val) fun x y => rfl).symm | |
| exact (List.foldl_hom (f := Subtype.val) fun x y => rfl).symm | |
| private theorem insertManyIfNewUnit_list_mk [EquivBEq α] [LawfulHashable α] | |
| {m : DHashMap α fun _ => Unit} {l : List α} : | |
| (insertManyIfNewUnit (mk m) l : ExtDHashMap α fun _ => Unit) = | |
| mk (DHashMap.Const.insertManyIfNewUnit m l) := by | |
| simp only [mk, Quotient.mk] | |
| induction l generalizing m with | |
| | nil => rfl | |
| | cons x l ih => | |
| simp only [insertManyIfNewUnit_cons, insertIfNew, mk, Quotient.mk, ih, | |
| DHashMap.Const.insertManyIfNewUnit_cons, lift] | |
| @[elab_as_elim] | |
| theorem insertManyIfNewUnit_ind [EquivBEq α] [LawfulHashable α] {motive : ExtDHashMap α (fun _ => Unit) → Prop} | |
| (m : ExtDHashMap α fun _ => Unit) (l : ρ) | |
| (init : motive m) (insert : ∀ m a, motive m → motive (m.insertIfNew a ())) : | |
| motive (insertManyIfNewUnit m l) := by | |
| change motive (Subtype.val ?my_mvar) | |
| exact Subtype.property ?my_mvar motive init (insert _ _) | |
| @[simp] | |
| theorem contains_insertManyIfNewUnit_list [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} : | |
| (insertManyIfNewUnit m l).contains k = (m.contains k || l.contains k) := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.contains_insertManyIfNewUnit_list | |
| @[simp] | |
| theorem mem_insertManyIfNewUnit_list [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} : | |
| k ∈ insertManyIfNewUnit m l ↔ k ∈ m ∨ l.contains k := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.mem_insertManyIfNewUnit_list | |
| theorem mem_of_mem_insertManyIfNewUnit_list [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} (contains_eq_false : l.contains k = false) : | |
| k ∈ insertManyIfNewUnit m l → k ∈ m := by | |
| refine m.inductionOn (fun _ contains_eq_false => ?_) contains_eq_false | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.mem_of_mem_insertManyIfNewUnit_list contains_eq_false | |
| theorem mem_insertManyIfNewUnit_of_mem [EquivBEq α] [LawfulHashable α] {l : ρ} {k : α} (h : k ∈ m) : | |
| k ∈ insertManyIfNewUnit m l := | |
| insertManyIfNewUnit_ind m l h fun _ _ h => mem_insertIfNew.mpr (.inr h) | |
| theorem getKey?_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} | |
| (not_mem : ¬ k ∈ m) (contains_eq_false : l.contains k = false) : | |
| getKey? (insertManyIfNewUnit m l) k = none := by | |
| refine m.inductionOn (fun _ not_mem contains_eq_false => ?_) not_mem contains_eq_false | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.getKey?_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false not_mem contains_eq_false | |
| theorem getKey?_insertManyIfNewUnit_list_of_not_mem_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k k' : α} (k_beq : k == k') | |
| (not_mem : ¬ k ∈ m) | |
| (distinct : l.Pairwise (fun a b => (a == b) = false)) (mem : k ∈ l) : | |
| getKey? (insertManyIfNewUnit m l) k' = some k := by | |
| refine m.inductionOn (fun _ k_beq not_mem distinct mem => ?_) k_beq not_mem distinct mem | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.getKey?_insertManyIfNewUnit_list_of_not_mem_of_mem k_beq not_mem distinct mem | |
| theorem getKey?_insertManyIfNewUnit_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} (h' : k ∈ m) : | |
| getKey? (insertManyIfNewUnit m l) k = getKey? m k := by | |
| refine m.inductionOn (fun _ h' => ?_) h' | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.getKey?_insertManyIfNewUnit_list_of_mem h' | |
| theorem getKey_insertManyIfNewUnit_list_of_not_mem_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List α} | |
| {k k' : α} (k_beq : k == k') | |
| (not_mem : ¬ k ∈ m) (distinct : l.Pairwise (fun a b => (a == b) = false)) | |
| (mem : k ∈ l) {h} : | |
| getKey (insertManyIfNewUnit m l) k' h = k := by | |
| refine m.inductionOn (fun _ k_beq not_mem distinct mem _ => ?_) k_beq not_mem distinct mem h | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.getKey_insertManyIfNewUnit_list_of_not_mem_of_mem k_beq not_mem distinct mem | |
| theorem getKey_insertManyIfNewUnit_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} (mem : k ∈ m) {h} : | |
| getKey (insertManyIfNewUnit m l) k h = getKey m k mem := by | |
| refine m.inductionOn (fun _ mem _ => ?_) mem h | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.getKey_insertManyIfNewUnit_list_of_mem mem | |
| theorem getKey!_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| [Inhabited α] {l : List α} {k : α} | |
| (not_mem : ¬ k ∈ m) (contains_eq_false : l.contains k = false) : | |
| getKey! (insertManyIfNewUnit m l) k = default := by | |
| refine m.inductionOn (fun _ not_mem contains_eq_false => ?_) not_mem contains_eq_false | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.getKey!_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false not_mem contains_eq_false | |
| theorem getKey!_insertManyIfNewUnit_list_of_not_mem_of_mem [EquivBEq α] [LawfulHashable α] | |
| [Inhabited α] {l : List α} {k k' : α} (k_beq : k == k') | |
| (not_mem : ¬ k ∈ m) (distinct : l.Pairwise (fun a b => (a == b) = false)) | |
| (mem : k ∈ l) : | |
| getKey! (insertManyIfNewUnit m l) k' = k := by | |
| refine m.inductionOn (fun _ k_beq not_mem distinct mem => ?_) k_beq not_mem distinct mem | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.getKey!_insertManyIfNewUnit_list_of_not_mem_of_mem k_beq not_mem distinct mem | |
| theorem getKey!_insertManyIfNewUnit_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| [Inhabited α] {l : List α} {k : α} (mem : k ∈ m) : | |
| getKey! (insertManyIfNewUnit m l) k = getKey! m k := by | |
| refine m.inductionOn (fun _ mem => ?_) mem | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.getKey!_insertManyIfNewUnit_list_of_mem mem | |
| theorem getKeyD_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k fallback : α} | |
| (not_mem : ¬ k ∈ m) (contains_eq_false : l.contains k = false) : | |
| getKeyD (insertManyIfNewUnit m l) k fallback = fallback := by | |
| refine m.inductionOn (fun _ not_mem contains_eq_false => ?_) not_mem contains_eq_false | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.getKeyD_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false not_mem contains_eq_false | |
| theorem getKeyD_insertManyIfNewUnit_list_of_not_mem_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k k' fallback : α} (k_beq : k == k') | |
| (not_mem : ¬ k ∈ m) | |
| (distinct : l.Pairwise (fun a b => (a == b) = false)) (mem : k ∈ l) : | |
| getKeyD (insertManyIfNewUnit m l) k' fallback = k := by | |
| refine m.inductionOn (fun _ k_beq not_mem distinct mem => ?_) k_beq not_mem distinct mem | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.getKeyD_insertManyIfNewUnit_list_of_not_mem_of_mem k_beq not_mem distinct mem | |
| theorem getKeyD_insertManyIfNewUnit_list_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k fallback : α} (mem : k ∈ m) : | |
| getKeyD (insertManyIfNewUnit m l) k fallback = getKeyD m k fallback := by | |
| refine m.inductionOn (fun _ mem => ?_) mem | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.getKeyD_insertManyIfNewUnit_list_of_mem mem | |
| theorem size_insertManyIfNewUnit_list [EquivBEq α] [LawfulHashable α] | |
| {l : List α} | |
| (distinct : l.Pairwise (fun a b => (a == b) = false)) : | |
| (∀ (a : α), a ∈ m → l.contains a = false) → | |
| (insertManyIfNewUnit m l).size = m.size + l.length := by | |
| refine m.inductionOn (fun _ distinct => ?_) distinct | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.size_insertManyIfNewUnit_list distinct | |
| theorem size_le_size_insertManyIfNewUnit_list [EquivBEq α] [LawfulHashable α] | |
| {l : List α} : | |
| m.size ≤ (insertManyIfNewUnit m l).size := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.size_le_size_insertManyIfNewUnit_list | |
| theorem size_le_size_insertManyIfNewUnit [EquivBEq α] [LawfulHashable α] | |
| {l : ρ} : m.size ≤ (insertManyIfNewUnit m l).size := | |
| insertManyIfNewUnit_ind m l (Nat.le_refl _) fun _ _ h => Nat.le_trans h size_le_size_insertIfNew | |
| theorem size_insertManyIfNewUnit_list_le [EquivBEq α] [LawfulHashable α] | |
| {l : List α} : | |
| (insertManyIfNewUnit m l).size ≤ m.size + l.length := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.size_insertManyIfNewUnit_list_le | |
| @[simp] | |
| theorem insertManyIfNewUnit_list_eq_empty_iff [EquivBEq α] [LawfulHashable α] {l : List α} : | |
| insertManyIfNewUnit m l = ∅ ↔ m = ∅ ∧ l = [] := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertManyIfNewUnit_list_mk, ← isEmpty_iff, ← List.isEmpty_iff, | |
| Bool.coe_iff_coe, ← Bool.and_eq_true] | |
| exact DHashMap.Const.isEmpty_insertManyIfNewUnit_list | |
| theorem eq_empty_of_insertManyIfNewUnit_eq_empty [EquivBEq α] [LawfulHashable α] {l : ρ} : | |
| insertManyIfNewUnit m l = ∅ → m = ∅ := | |
| insertManyIfNewUnit_ind m l id fun _ _ _ h => absurd h not_insertIfNew_eq_empty | |
| theorem get?_insertManyIfNewUnit_list [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} : | |
| get? (insertManyIfNewUnit m l) k = | |
| if k ∈ m ∨ l.contains k then some () else none := by | |
| refine m.inductionOn fun _ => ?_ | |
| simp only [insertManyIfNewUnit_list_mk] | |
| exact DHashMap.Const.get?_insertManyIfNewUnit_list | |
| theorem get_insertManyIfNewUnit_list [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} {h} : | |
| get (insertManyIfNewUnit m l) k h = () := | |
| rfl | |
| theorem get!_insertManyIfNewUnit_list [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} : | |
| get! (insertManyIfNewUnit m l) k = () := | |
| rfl | |
| theorem getD_insertManyIfNewUnit_list [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} {fallback : Unit} : | |
| getD (insertManyIfNewUnit m l) k fallback = () := | |
| rfl | |
| end Const | |
| end insertMany | |
| end ExtDHashMap | |
| namespace ExtDHashMap | |
| @[simp, grind =] | |
| theorem ofList_nil [EquivBEq α] [LawfulHashable α] : | |
| ofList ([] : List ((a : α) × β a)) = ∅ := (rfl) | |
| @[simp, grind =] | |
| theorem ofList_singleton [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} : | |
| ofList [⟨k, v⟩] = (∅ : ExtDHashMap α β).insert k v := (rfl) | |
| @[grind _=_] | |
| theorem ofList_cons [EquivBEq α] [LawfulHashable α] {k : α} {v : β k} {tl : List ((a : α) × β a)} : | |
| ofList (⟨k, v⟩ :: tl) = ((∅ : ExtDHashMap α β).insert k v).insertMany tl := by | |
| conv => rhs; apply insertMany_list_mk | |
| exact congrArg mk DHashMap.ofList_cons | |
| theorem ofList_eq_insertMany_empty [EquivBEq α] [LawfulHashable α] {l : List ((a : α) × β a)} : | |
| ofList l = insertMany (∅ : ExtDHashMap α β) l := by | |
| conv => rhs; apply insertMany_list_mk | |
| exact congrArg mk DHashMap.ofList_eq_insertMany_empty | |
| @[simp, grind =] | |
| theorem contains_ofList [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} {k : α} : | |
| (ofList l).contains k = (l.map Sigma.fst).contains k := | |
| DHashMap.contains_ofList | |
| @[simp, grind =] | |
| theorem mem_ofList [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} {k : α} : | |
| k ∈ ofList l ↔ (l.map Sigma.fst).contains k := | |
| DHashMap.mem_ofList | |
| theorem get?_ofList_of_contains_eq_false [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k : α} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (ofList l).get? k = none := | |
| DHashMap.get?_ofList_of_contains_eq_false contains_eq_false | |
| theorem get?_ofList_of_mem [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k k' : α} (k_beq : k == k') {v : β k} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) : | |
| (ofList l).get? k' = some (cast (by congr; apply LawfulBEq.eq_of_beq k_beq) v) := | |
| DHashMap.get?_ofList_of_mem k_beq distinct mem | |
| theorem get_ofList_of_mem [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k k' : α} (k_beq : k == k') {v : β k} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) | |
| {h} : | |
| (ofList l).get k' h = cast (by congr; apply LawfulBEq.eq_of_beq k_beq) v := | |
| DHashMap.get_ofList_of_mem k_beq distinct mem | |
| theorem get!_ofList_of_contains_eq_false [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k : α} [Inhabited (β k)] | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (ofList l).get! k = default := | |
| DHashMap.get!_ofList_of_contains_eq_false contains_eq_false | |
| theorem get!_ofList_of_mem [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k k' : α} (k_beq : k == k') {v : β k} [Inhabited (β k')] | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) : | |
| (ofList l).get! k' = cast (by congr; apply LawfulBEq.eq_of_beq k_beq) v := | |
| DHashMap.get!_ofList_of_mem k_beq distinct mem | |
| theorem getD_ofList_of_contains_eq_false [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k : α} {fallback : β k} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (ofList l).getD k fallback = fallback := | |
| DHashMap.getD_ofList_of_contains_eq_false contains_eq_false | |
| theorem getD_ofList_of_mem [LawfulBEq α] | |
| {l : List ((a : α) × β a)} {k k' : α} (k_beq : k == k') {v : β k} {fallback : β k'} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) : | |
| (ofList l).getD k' fallback = cast (by congr; apply LawfulBEq.eq_of_beq k_beq) v := | |
| DHashMap.getD_ofList_of_mem k_beq distinct mem | |
| theorem getKey?_ofList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} {k : α} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (ofList l).getKey? k = none := | |
| DHashMap.getKey?_ofList_of_contains_eq_false contains_eq_false | |
| theorem getKey?_ofList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Sigma.fst) : | |
| (ofList l).getKey? k' = some k := | |
| DHashMap.getKey?_ofList_of_mem k_beq distinct mem | |
| theorem getKey_ofList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Sigma.fst) | |
| {h} : | |
| (ofList l).getKey k' h = k := | |
| DHashMap.getKey_ofList_of_mem k_beq distinct mem | |
| theorem getKey!_ofList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {l : List ((a : α) × β a)} {k : α} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (ofList l).getKey! k = default := | |
| DHashMap.getKey!_ofList_of_contains_eq_false contains_eq_false | |
| theorem getKey!_ofList_of_mem [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {l : List ((a : α) × β a)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Sigma.fst) : | |
| (ofList l).getKey! k' = k := | |
| DHashMap.getKey!_ofList_of_mem k_beq distinct mem | |
| theorem getKeyD_ofList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} {k fallback : α} | |
| (contains_eq_false : (l.map Sigma.fst).contains k = false) : | |
| (ofList l).getKeyD k fallback = fallback := | |
| DHashMap.getKeyD_ofList_of_contains_eq_false contains_eq_false | |
| theorem getKeyD_ofList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} | |
| {k k' fallback : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Sigma.fst) : | |
| (ofList l).getKeyD k' fallback = k := | |
| DHashMap.getKeyD_ofList_of_mem k_beq distinct mem | |
| theorem size_ofList [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) : | |
| (ofList l).size = l.length := | |
| DHashMap.size_ofList distinct | |
| theorem size_ofList_le [EquivBEq α] [LawfulHashable α] | |
| {l : List ((a : α) × β a)} : | |
| (ofList l).size ≤ l.length := | |
| DHashMap.size_ofList_le | |
| grind_pattern size_ofList_le => (ofList l).size | |
| @[simp] | |
| theorem ofList_eq_empty_iff [EquivBEq α] [LawfulHashable α] {l : List ((a : α) × β a)} : | |
| ofList l = ∅ ↔ l = [] := by | |
| simpa only [← isEmpty_iff, ← List.isEmpty_iff, Bool.coe_iff_coe] using | |
| DHashMap.isEmpty_ofList | |
| namespace Const | |
| variable {β : Type v} | |
| @[simp, grind =] | |
| theorem ofList_nil [EquivBEq α] [LawfulHashable α] : | |
| ofList ([] : List (α × β)) = ∅ := | |
| (rfl) | |
| @[simp, grind =] | |
| theorem ofList_singleton [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : | |
| ofList [⟨k, v⟩] = (∅ : ExtDHashMap α (fun _ => β)).insert k v := | |
| (rfl) | |
| @[grind _=_] | |
| theorem ofList_cons [EquivBEq α] [LawfulHashable α] {k : α} {v : β} {tl : List (α × β)} : | |
| ofList (⟨k, v⟩ :: tl) = insertMany ((∅ : ExtDHashMap α (fun _ => β)).insert k v) tl := by | |
| conv => rhs; apply insertMany_list_mk | |
| exact congrArg mk DHashMap.Const.ofList_cons | |
| theorem ofList_eq_insertMany_empty [EquivBEq α] [LawfulHashable α] {l : List (α × β)} : | |
| ofList l = insertMany (∅ : ExtDHashMap α (fun _ => β)) l := by | |
| conv => rhs; apply insertMany_list_mk | |
| exact congrArg mk DHashMap.Const.ofList_eq_insertMany_empty | |
| @[simp, grind =] | |
| theorem contains_ofList [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} : | |
| (ofList l).contains k = (l.map Prod.fst).contains k := | |
| DHashMap.Const.contains_ofList | |
| @[simp, grind =] | |
| theorem mem_ofList [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} : | |
| k ∈ ofList l ↔ (l.map Prod.fst).contains k := | |
| DHashMap.Const.mem_ofList | |
| theorem get?_ofList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| get? (ofList l) k = none := | |
| DHashMap.Const.get?_ofList_of_contains_eq_false contains_eq_false | |
| theorem get?_ofList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k k' : α} (k_beq : k == k') {v : β} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) : | |
| get? (ofList l) k' = some v := | |
| DHashMap.Const.get?_ofList_of_mem k_beq distinct mem | |
| theorem get_ofList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k k' : α} (k_beq : k == k') {v : β} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) | |
| {h} : | |
| get (ofList l) k' h = v := | |
| DHashMap.Const.get_ofList_of_mem k_beq distinct mem | |
| theorem get!_ofList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} [Inhabited β] | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| get! (ofList l) k = (default : β) := | |
| DHashMap.Const.get!_ofList_of_contains_eq_false contains_eq_false | |
| theorem get!_ofList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k k' : α} (k_beq : k == k') {v : β} [Inhabited β] | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) : | |
| get! (ofList l) k' = v := | |
| DHashMap.Const.get!_ofList_of_mem k_beq distinct mem | |
| theorem getD_ofList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} {fallback : β} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| getD (ofList l) k fallback = fallback := | |
| DHashMap.Const.getD_ofList_of_contains_eq_false contains_eq_false | |
| theorem getD_ofList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k k' : α} (k_beq : k == k') {v : β} {fallback : β} | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : ⟨k, v⟩ ∈ l) : | |
| getD (ofList l) k' fallback = v := | |
| DHashMap.Const.getD_ofList_of_mem k_beq distinct mem | |
| theorem getKey?_ofList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k : α} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| (ofList l).getKey? k = none := | |
| DHashMap.Const.getKey?_ofList_of_contains_eq_false contains_eq_false | |
| theorem getKey?_ofList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Prod.fst) : | |
| (ofList l).getKey? k' = some k := | |
| DHashMap.Const.getKey?_ofList_of_mem k_beq distinct mem | |
| theorem getKey_ofList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Prod.fst) | |
| {h} : | |
| (ofList l).getKey k' h = k := | |
| DHashMap.Const.getKey_ofList_of_mem k_beq distinct mem | |
| theorem getKey!_ofList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| [Inhabited α] {l : List (α × β)} {k : α} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| (ofList l).getKey! k = default := | |
| DHashMap.Const.getKey!_ofList_of_contains_eq_false contains_eq_false | |
| theorem getKey!_ofList_of_mem [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {l : List (α × β)} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Prod.fst) : | |
| (ofList l).getKey! k' = k := | |
| DHashMap.Const.getKey!_ofList_of_mem k_beq distinct mem | |
| theorem getKeyD_ofList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} {k fallback : α} | |
| (contains_eq_false : (l.map Prod.fst).contains k = false) : | |
| (ofList l).getKeyD k fallback = fallback := | |
| DHashMap.Const.getKeyD_ofList_of_contains_eq_false contains_eq_false | |
| theorem getKeyD_ofList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} | |
| {k k' fallback : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) | |
| (mem : k ∈ l.map Prod.fst) : | |
| (ofList l).getKeyD k' fallback = k := | |
| DHashMap.Const.getKeyD_ofList_of_mem k_beq distinct mem | |
| theorem size_ofList [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} (distinct : l.Pairwise (fun a b => (a.1 == b.1) = false)) : | |
| (ofList l).size = l.length := | |
| DHashMap.Const.size_ofList distinct | |
| theorem size_ofList_le [EquivBEq α] [LawfulHashable α] | |
| {l : List (α × β)} : | |
| (ofList l).size ≤ l.length := | |
| DHashMap.Const.size_ofList_le | |
| grind_pattern size_ofList_le => (ofList l).size | |
| @[simp] | |
| theorem ofList_eq_empty_iff [EquivBEq α] [LawfulHashable α] {l : List (α × β)} : | |
| ofList l = ∅ ↔ l = [] := by | |
| simpa only [← isEmpty_iff, ← List.isEmpty_iff, Bool.coe_iff_coe] using | |
| DHashMap.Const.isEmpty_ofList | |
| @[simp] | |
| theorem unitOfList_nil [EquivBEq α] [LawfulHashable α] : | |
| unitOfList ([] : List α) = ∅ := | |
| congrArg mk DHashMap.Const.unitOfList_nil | |
| @[simp] | |
| theorem unitOfList_singleton [EquivBEq α] [LawfulHashable α] {k : α} : | |
| unitOfList [k] = (∅ : ExtDHashMap α (fun _ => Unit)).insertIfNew k () := | |
| congrArg mk DHashMap.Const.unitOfList_singleton | |
| theorem unitOfList_cons [EquivBEq α] [LawfulHashable α] {hd : α} {tl : List α} : | |
| unitOfList (hd :: tl) = | |
| insertManyIfNewUnit ((∅ : ExtDHashMap α (fun _ => Unit)).insertIfNew hd ()) tl := by | |
| conv => rhs; apply insertManyIfNewUnit_list_mk | |
| exact congrArg mk DHashMap.Const.unitOfList_cons | |
| @[simp] | |
| theorem contains_unitOfList [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} : | |
| (unitOfList l).contains k = l.contains k := | |
| DHashMap.Const.contains_unitOfList | |
| @[simp] | |
| theorem mem_unitOfList [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} : | |
| k ∈ unitOfList l ↔ l.contains k := | |
| DHashMap.Const.mem_unitOfList | |
| theorem getKey?_unitOfList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} (contains_eq_false : l.contains k = false) : | |
| getKey? (unitOfList l) k = none := | |
| DHashMap.Const.getKey?_unitOfList_of_contains_eq_false contains_eq_false | |
| theorem getKey?_unitOfList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a == b) = false)) (mem : k ∈ l) : | |
| getKey? (unitOfList l) k' = some k := | |
| DHashMap.Const.getKey?_unitOfList_of_mem k_beq distinct mem | |
| theorem getKey_unitOfList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List α} | |
| {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a == b) = false)) | |
| (mem : k ∈ l) {h} : | |
| getKey (unitOfList l) k' h = k := | |
| DHashMap.Const.getKey_unitOfList_of_mem k_beq distinct mem | |
| theorem getKey!_unitOfList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| [Inhabited α] {l : List α} {k : α} | |
| (contains_eq_false : l.contains k = false) : | |
| getKey! (unitOfList l) k = default := | |
| DHashMap.Const.getKey!_unitOfList_of_contains_eq_false contains_eq_false | |
| theorem getKey!_unitOfList_of_mem [EquivBEq α] [LawfulHashable α] | |
| [Inhabited α] {l : List α} {k k' : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a == b) = false)) | |
| (mem : k ∈ l) : | |
| getKey! (unitOfList l) k' = k := | |
| DHashMap.Const.getKey!_unitOfList_of_mem k_beq distinct mem | |
| theorem getKeyD_unitOfList_of_contains_eq_false [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k fallback : α} | |
| (contains_eq_false : l.contains k = false) : | |
| getKeyD (unitOfList l) k fallback = fallback := | |
| DHashMap.Const.getKeyD_unitOfList_of_contains_eq_false contains_eq_false | |
| theorem getKeyD_unitOfList_of_mem [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k k' fallback : α} (k_beq : k == k') | |
| (distinct : l.Pairwise (fun a b => (a == b) = false)) | |
| (mem : k ∈ l) : | |
| getKeyD (unitOfList l) k' fallback = k := | |
| DHashMap.Const.getKeyD_unitOfList_of_mem k_beq distinct mem | |
| theorem size_unitOfList [EquivBEq α] [LawfulHashable α] | |
| {l : List α} | |
| (distinct : l.Pairwise (fun a b => (a == b) = false)) : | |
| (unitOfList l).size = l.length := | |
| DHashMap.Const.size_unitOfList distinct | |
| theorem size_unitOfList_le [EquivBEq α] [LawfulHashable α] | |
| {l : List α} : | |
| (unitOfList l).size ≤ l.length := | |
| DHashMap.Const.size_unitOfList_le | |
| @[simp] | |
| theorem unitOfList_eq_empty_iff [EquivBEq α] [LawfulHashable α] {l : List α} : | |
| unitOfList l = ∅ ↔ l = [] := by | |
| simpa only [← isEmpty_iff, ← List.isEmpty_iff, Bool.coe_iff_coe] using | |
| DHashMap.Const.isEmpty_unitOfList | |
| @[simp] | |
| theorem get?_unitOfList [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} : | |
| get? (unitOfList l) k = | |
| if l.contains k then some () else none := | |
| DHashMap.Const.get?_unitOfList | |
| @[simp] | |
| theorem get_unitOfList [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} {h} : | |
| get (unitOfList l) k h = () := | |
| DHashMap.Const.get_unitOfList | |
| @[simp] | |
| theorem get!_unitOfList [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} : | |
| get! (unitOfList l) k = () := | |
| DHashMap.Const.get!_unitOfList | |
| @[simp] | |
| theorem getD_unitOfList [EquivBEq α] [LawfulHashable α] | |
| {l : List α} {k : α} {fallback : Unit} : | |
| getD (unitOfList l) k fallback = () := | |
| DHashMap.Const.getD_unitOfList | |
| end Const | |
| section Union | |
| variable (m₁ m₂ : ExtDHashMap α β) | |
| variable {m₁ m₂} | |
| @[simp] | |
| theorem union_eq [EquivBEq α] [LawfulHashable α] : m₁.union m₂ = m₁ ∪ m₂ := by | |
| simp only [Union.union] | |
| private theorem union_mk [EquivBEq α] [LawfulHashable α] | |
| {m₁ m₂ : DHashMap α β} : | |
| (ExtDHashMap.union (mk m₁) (mk m₂) : ExtDHashMap α β) = mk (m₁ ∪ m₂) := by congr | |
| /- contains -/ | |
| @[simp] | |
| theorem contains_union [EquivBEq α] [LawfulHashable α] | |
| {k : α} : | |
| (m₁ ∪ m₂).contains k = (m₁.contains k || m₂.contains k) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.contains_union | |
| /- mem -/ | |
| theorem mem_union_of_left [EquivBEq α] [LawfulHashable α] {k : α} : | |
| k ∈ m₁ → k ∈ m₁ ∪ m₂ := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.mem_union_of_left | |
| theorem mem_union_of_right [EquivBEq α] [LawfulHashable α] {k : α} : | |
| k ∈ m₂ → k ∈ m₁ ∪ m₂ := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.mem_union_of_right | |
| @[simp] | |
| theorem mem_union_iff [EquivBEq α] [LawfulHashable α] {k : α} : | |
| k ∈ m₁ ∪ m₂ ↔ k ∈ m₁ ∨ k ∈ m₂ := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.mem_union_iff | |
| theorem mem_of_mem_union_of_not_mem_right [EquivBEq α] | |
| [LawfulHashable α] {k : α} : | |
| k ∈ m₁ ∪ m₂ → ¬k ∈ m₂ → k ∈ m₁ := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.mem_of_mem_union_of_not_mem_right | |
| theorem mem_of_mem_union_of_not_mem_left [EquivBEq α] | |
| [LawfulHashable α] {k : α} : | |
| k ∈ m₁ ∪ m₂ → ¬k ∈ m₁ → k ∈ m₂ := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.mem_of_mem_union_of_not_mem_left | |
| theorem union_insert_right_eq_insert_union [EquivBEq α] [LawfulHashable α] {p : (a : α) × β a} : | |
| (m₁ ∪ (m₂.insert p.fst p.snd)) = ((m₁ ∪ m₂).insert p.fst p.snd) := | |
| m₁.inductionOn₂ m₂ fun _ _ => sound DHashMap.union_insert_right_equiv_insert_union | |
| /- get? -/ | |
| theorem get?_union [LawfulBEq α] {k : α} : | |
| (m₁ ∪ m₂).get? k = (m₂.get? k).or (m₁.get? k) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.get?_union | |
| theorem get?_union_of_not_mem_left [LawfulBEq α] | |
| {k : α} (not_mem : ¬k ∈ m₁) : | |
| (m₁ ∪ m₂).get? k = m₂.get? k := by | |
| induction m₁ with | |
| | mk a => | |
| induction m₂ with | |
| | mk b => | |
| exact @DHashMap.get?_union_of_not_mem_left α β _ _ a b _ k not_mem | |
| theorem get?_union_of_not_mem_right [LawfulBEq α] | |
| {k : α} (not_mem : ¬k ∈ m₂) : | |
| (m₁ ∪ m₂).get? k = m₁.get? k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get?_union_of_not_mem_right h | |
| /- get -/ | |
| theorem get_union_of_mem_right [LawfulBEq α] | |
| {k : α} (mem : k ∈ m₂) : | |
| (m₁ ∪ m₂).get k (mem_union_of_right mem) = m₂.get k mem := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get_union_of_mem_right h | |
| theorem get_union_of_not_mem_left [LawfulBEq α] | |
| {k : α} (not_mem : ¬k ∈ m₁) {h'} : | |
| (m₁ ∪ m₂).get k h' = m₂.get k (mem_of_mem_union_of_not_mem_left h' not_mem) := by | |
| revert not_mem h' | |
| exact m₁.inductionOn₂ m₂ fun _ _ not_mem _ => DHashMap.get_union_of_not_mem_left not_mem | |
| /- getD -/ | |
| theorem getD_union [LawfulBEq α] {k : α} {fallback : β k} : | |
| (m₁ ∪ m₂).getD k fallback = m₂.getD k (m₁.getD k fallback) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getD_union | |
| theorem getD_union_of_not_mem_left [LawfulBEq α] | |
| {k : α} {fallback : β k} (not_mem : ¬k ∈ m₁) : | |
| (m₁ ∪ m₂).getD k fallback = m₂.getD k fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ not_mem => DHashMap.getD_union_of_not_mem_left not_mem | |
| theorem getD_union_of_not_mem_right [LawfulBEq α] | |
| {k : α} {fallback : β k} (not_mem : ¬k ∈ m₂) : | |
| (m₁ ∪ m₂).getD k fallback = m₁.getD k fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ not_mem => DHashMap.getD_union_of_not_mem_right not_mem | |
| /- get! -/ | |
| theorem get!_union [LawfulBEq α] {k : α} [Inhabited (β k)] : | |
| (m₁ ∪ m₂).get! k = m₂.getD k (m₁.get! k) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.get!_union | |
| theorem get!_union_of_not_mem_left [LawfulBEq α] | |
| {k : α} [Inhabited (β k)] (not_mem : ¬k ∈ m₁) : | |
| (m₁ ∪ m₂).get! k = m₂.get! k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get!_union_of_not_mem_left h | |
| theorem get!_union_of_not_mem_right [LawfulBEq α] | |
| {k : α} [Inhabited (β k)] (not_mem : ¬k ∈ m₂) : | |
| (m₁ ∪ m₂).get! k = m₁.get! k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get!_union_of_not_mem_right h | |
| /- getKey? -/ | |
| theorem getKey?_union [EquivBEq α] [LawfulHashable α] {k : α} : | |
| (m₁ ∪ m₂).getKey? k = (m₂.getKey? k).or (m₁.getKey? k) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getKey?_union | |
| theorem getKey?_union_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : ¬k ∈ m₁) : | |
| (m₁ ∪ m₂).getKey? k = m₂.getKey? k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey?_union_of_not_mem_left h | |
| /- getKey -/ | |
| theorem getKey_union_of_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (mem : k ∈ m₂) : | |
| (m₁ ∪ m₂).getKey k (mem_union_of_right mem) = m₂.getKey k mem := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey_union_of_mem_right h | |
| theorem getKey_union_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : ¬k ∈ m₁) {h'} : | |
| (m₁ ∪ m₂).getKey k h' = m₂.getKey k (mem_of_mem_union_of_not_mem_left h' not_mem) := by | |
| revert not_mem h' | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey_union_of_not_mem_left h | |
| theorem getKey_union_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : ¬k ∈ m₂) {h'} : | |
| (m₁ ∪ m₂).getKey k h' = m₁.getKey k (mem_of_mem_union_of_not_mem_right h' not_mem) := by | |
| revert not_mem h' | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey_union_of_not_mem_right h | |
| /- getKeyD -/ | |
| theorem getKeyD_union [EquivBEq α] [LawfulHashable α] {k fallback : α} : | |
| (m₁ ∪ m₂).getKeyD k fallback = m₂.getKeyD k (m₁.getKeyD k fallback) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getKeyD_union | |
| theorem getKeyD_union_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k fallback : α} (not_mem : ¬k ∈ m₁) : | |
| (m₁ ∪ m₂).getKeyD k fallback = m₂.getKeyD k fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKeyD_union_of_not_mem_left h | |
| theorem getKeyD_union_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k fallback : α} (not_mem : ¬k ∈ m₂) : | |
| (m₁ ∪ m₂).getKeyD k fallback = m₁.getKeyD k fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKeyD_union_of_not_mem_right h | |
| /- getKey! -/ | |
| theorem getKey!_union [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} : (m₁ ∪ m₂).getKey! k = m₂.getKeyD k (m₁.getKey! k) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getKey!_union | |
| theorem getKey!_union_of_not_mem_left [Inhabited α] | |
| [EquivBEq α] [LawfulHashable α] {k : α} | |
| (not_mem : ¬k ∈ m₁) : | |
| (m₁ ∪ m₂).getKey! k = m₂.getKey! k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey!_union_of_not_mem_left h | |
| theorem getKey!_union_of_not_mem_right [Inhabited α] | |
| [EquivBEq α] [LawfulHashable α] {k : α} | |
| (not_mem : ¬k ∈ m₂) : | |
| (m₁ ∪ m₂).getKey! k = m₁.getKey! k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getKey!_union_of_not_mem_right | |
| /- size -/ | |
| theorem size_union_of_not_mem [EquivBEq α] [LawfulHashable α] : | |
| (∀ (a : α), a ∈ m₁ → ¬a ∈ m₂) → | |
| (m₁ ∪ m₂).size = m₁.size + m₂.size := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.size_union_of_not_mem | |
| theorem size_left_le_size_union [EquivBEq α] [LawfulHashable α] : m₁.size ≤ (m₁ ∪ m₂).size := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.size_left_le_size_union | |
| theorem size_right_le_size_union [EquivBEq α] [LawfulHashable α] : | |
| m₂.size ≤ (m₁ ∪ m₂).size := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.size_right_le_size_union | |
| theorem size_union_le_size_add_size [EquivBEq α] [LawfulHashable α] : | |
| (m₁ ∪ m₂).size ≤ m₁.size + m₂.size := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.size_union_le_size_add_size | |
| /- isEmpty -/ | |
| @[simp] | |
| theorem isEmpty_union [EquivBEq α] [LawfulHashable α] : | |
| (m₁ ∪ m₂).isEmpty = (m₁.isEmpty && m₂.isEmpty) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.isEmpty_union | |
| end Union | |
| namespace Const | |
| variable {β : Type v} {m₁ m₂ : ExtDHashMap α (fun _ => β)} | |
| /- get? -/ | |
| theorem get?_union [EquivBEq α] [LawfulHashable α] {k : α} : | |
| Const.get? (m₁.union m₂) k = (Const.get? m₂ k).or (Const.get? m₁ k) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.Const.get?_union | |
| theorem get?_union_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : ¬k ∈ m₁) : | |
| Const.get? (m₁.union m₂) k = Const.get? m₂ k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get?_union_of_not_mem_left h | |
| theorem get?_union_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : ¬k ∈ m₂) : | |
| Const.get? (m₁.union m₂) k = Const.get? m₁ k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get?_union_of_not_mem_right h | |
| /- get -/ | |
| theorem get_union_of_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (mem : m₂.contains k) : | |
| Const.get (m₁.union m₂) k (mem_union_of_right mem) = Const.get m₂ k mem := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get_union_of_mem_right h | |
| theorem get_union_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : ¬k ∈ m₁) {h'} : | |
| Const.get (m₁.union m₂) k h' = Const.get m₂ k (mem_of_mem_union_of_not_mem_left h' not_mem) := by | |
| revert not_mem h' | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get_union_of_not_mem_left h | |
| theorem get_union_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : ¬k ∈ m₂) {h'} : | |
| Const.get (m₁.union m₂) k h' = Const.get m₁ k (mem_of_mem_union_of_not_mem_right h' not_mem) := by | |
| revert not_mem h' | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get_union_of_not_mem_right h | |
| /- getD -/ | |
| theorem getD_union [EquivBEq α] [LawfulHashable α] {k : α} {fallback : β} : | |
| Const.getD (m₁.union m₂) k fallback = Const.getD m₂ k (Const.getD m₁ k fallback) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.Const.getD_union | |
| theorem getD_union_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k : α} {fallback : β} (not_mem : ¬k ∈ m₁) : | |
| Const.getD (m₁.union m₂) k fallback = Const.getD m₂ k fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.getD_union_of_not_mem_left h | |
| theorem getD_union_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} {fallback : β} (not_mem : ¬k ∈ m₂) : | |
| Const.getD (m₁.union m₂) k fallback = Const.getD m₁ k fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.getD_union_of_not_mem_right h | |
| /- get! -/ | |
| theorem get!_union [EquivBEq α] [LawfulHashable α] [Inhabited β] {k : α} : | |
| Const.get! (m₁.union m₂) k = Const.getD m₂ k (Const.get! m₁ k) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.Const.get!_union | |
| theorem get!_union_of_not_mem_left [EquivBEq α] [LawfulHashable α] [Inhabited β] | |
| {k : α} (not_mem : ¬k ∈ m₁) : | |
| Const.get! (m₁.union m₂) k = Const.get! m₂ k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get!_union_of_not_mem_left h | |
| theorem get!_union_of_not_mem_right [EquivBEq α] [LawfulHashable α] [Inhabited β] | |
| {k : α} (not_mem : ¬k ∈ m₂) : | |
| Const.get! (m₁.union m₂) k = Const.get! m₁ k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get!_union_of_not_mem_right h | |
| end Const | |
| section Inter | |
| variable (m₁ m₂ : ExtDHashMap α β) | |
| variable {m₁ m₂} | |
| @[simp] | |
| theorem inter_eq [EquivBEq α] [LawfulHashable α] : m₁.inter m₂ = m₁ ∩ m₂ := by | |
| simp only [Inter.inter] | |
| /- contains -/ | |
| @[simp] | |
| theorem contains_inter [EquivBEq α] [LawfulHashable α] | |
| {k : α} : | |
| (m₁ ∩ m₂).contains k = (m₁.contains k && m₂.contains k) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.contains_inter | |
| /- mem -/ | |
| @[simp] | |
| theorem mem_inter_iff [EquivBEq α] [LawfulHashable α] {k : α} : | |
| k ∈ m₁ ∩ m₂ ↔ k ∈ m₁ ∧ k ∈ m₂ := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.mem_inter_iff | |
| theorem not_mem_inter_of_not_mem_left [EquivBEq α] [LawfulHashable α] {k : α} | |
| (not_mem : k ∉ m₁) : | |
| k ∉ m₁ ∩ m₂ := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ => DHashMap.not_mem_inter_of_not_mem_left | |
| theorem not_mem_inter_of_not_mem_right [EquivBEq α] [LawfulHashable α] {k : α} | |
| (not_mem : k ∉ m₂) : | |
| k ∉ m₁ ∩ m₂ := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ => DHashMap.not_mem_inter_of_not_mem_right | |
| /- get? -/ | |
| theorem get?_inter [LawfulBEq α] {k : α} : | |
| (m₁ ∩ m₂).get? k = | |
| if k ∈ m₂ then m₁.get? k else none := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.get?_inter | |
| theorem get?_inter_of_mem_right [LawfulBEq α] | |
| {k : α} (mem : k ∈ m₂) : | |
| (m₁ ∩ m₂).get? k = m₁.get? k := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get?_inter_of_mem_right h | |
| theorem get?_inter_of_not_mem_left [LawfulBEq α] | |
| {k : α} (not_mem : k ∉ m₁) : | |
| (m₁ ∩ m₂).get? k = none := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get?_inter_of_not_mem_left h | |
| theorem get?_inter_of_not_mem_right [LawfulBEq α] | |
| {k : α} (not_mem : k ∉ m₂) : | |
| (m₁ ∩ m₂).get? k = none := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get?_inter_of_not_mem_right h | |
| /- get -/ | |
| @[simp] | |
| theorem get_inter [LawfulBEq α] | |
| {k : α} {h_mem : k ∈ m₁ ∩ m₂} : | |
| (m₁ ∩ m₂).get k h_mem = | |
| m₁.get k (mem_inter_iff.1 h_mem).1 := by | |
| induction m₁ | |
| case mk a => | |
| induction m₂ | |
| case mk b => | |
| apply DHashMap.get_inter | |
| /- getD -/ | |
| theorem getD_inter [LawfulBEq α] {k : α} {fallback : β k} : | |
| (m₁ ∩ m₂).getD k fallback = | |
| if k ∈ m₂ then m₁.getD k fallback else fallback := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getD_inter | |
| theorem getD_inter_of_mem_right [LawfulBEq α] | |
| {k : α} {fallback : β k} (mem : k ∈ m₂) : | |
| (m₁ ∩ m₂).getD k fallback = m₁.getD k fallback := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getD_inter_of_mem_right h | |
| theorem getD_inter_of_not_mem_right [LawfulBEq α] | |
| {k : α} {fallback : β k} (not_mem : k ∉ m₂) : | |
| (m₁ ∩ m₂).getD k fallback = fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getD_inter_of_not_mem_right h | |
| theorem getD_inter_of_not_mem_left [LawfulBEq α] | |
| {k : α} {fallback : β k} (not_mem : k ∉ m₁) : | |
| (m₁ ∩ m₂).getD k fallback = fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getD_inter_of_not_mem_left h | |
| /- get! -/ | |
| theorem get!_inter [LawfulBEq α] {k : α} [Inhabited (β k)] : | |
| (m₁ ∩ m₂).get! k = | |
| if k ∈ m₂ then m₁.get! k else default := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.get!_inter | |
| theorem get!_inter_of_mem_right [LawfulBEq α] | |
| {k : α} [Inhabited (β k)] (mem : k ∈ m₂) : | |
| (m₁ ∩ m₂).get! k = m₁.get! k := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get!_inter_of_mem_right h | |
| theorem get!_inter_of_not_mem_right [LawfulBEq α] | |
| {k : α} [Inhabited (β k)] (not_mem : k ∉ m₂) : | |
| (m₁ ∩ m₂).get! k = default := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get!_inter_of_not_mem_right h | |
| theorem get!_inter_of_not_mem_left [LawfulBEq α] | |
| {k : α} [Inhabited (β k)] (not_mem : k ∉ m₁) : | |
| (m₁ ∩ m₂).get! k = default := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get!_inter_of_not_mem_left h | |
| /- getKey? -/ | |
| theorem getKey?_inter [EquivBEq α] [LawfulHashable α] {k : α} : | |
| (m₁ ∩ m₂).getKey? k = | |
| if k ∈ m₂ then m₁.getKey? k else none := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getKey?_inter | |
| theorem getKey?_inter_of_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (mem : k ∈ m₂) : | |
| (m₁ ∩ m₂).getKey? k = m₁.getKey? k := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey?_inter_of_mem_right h | |
| theorem getKey?_inter_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : k ∉ m₂) : | |
| (m₁ ∩ m₂).getKey? k = none := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey?_inter_of_not_mem_right h | |
| theorem getKey?_inter_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : k ∉ m₁) : | |
| (m₁ ∩ m₂).getKey? k = none := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey?_inter_of_not_mem_left h | |
| /- getKey -/ | |
| @[simp] | |
| theorem getKey_inter [EquivBEq α] [LawfulHashable α] | |
| {k : α} {h_mem : k ∈ m₁ ∩ m₂} : | |
| (m₁ ∩ m₂).getKey k h_mem = | |
| m₁.getKey k (mem_inter_iff.1 h_mem).1 := by | |
| induction m₁ | |
| case mk a => | |
| induction m₂ | |
| case mk b => | |
| apply DHashMap.getKey_inter | |
| /- getKeyD -/ | |
| theorem getKeyD_inter [EquivBEq α] [LawfulHashable α] {k fallback : α} : | |
| (m₁ ∩ m₂).getKeyD k fallback = | |
| if k ∈ m₂ then m₁.getKeyD k fallback else fallback := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getKeyD_inter | |
| theorem getKeyD_inter_of_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k fallback : α} (mem : k ∈ m₂) : | |
| (m₁ ∩ m₂).getKeyD k fallback = m₁.getKeyD k fallback := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKeyD_inter_of_mem_right h | |
| theorem getKeyD_inter_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k fallback : α} (not_mem : k ∉ m₂) : | |
| (m₁ ∩ m₂).getKeyD k fallback = fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKeyD_inter_of_not_mem_right h | |
| theorem getKeyD_inter_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k fallback : α} (not_mem : k ∉ m₁) : | |
| (m₁ ∩ m₂).getKeyD k fallback = fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKeyD_inter_of_not_mem_left h | |
| /- getKey! -/ | |
| theorem getKey!_inter [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} : | |
| (m₁ ∩ m₂).getKey! k = | |
| if k ∈ m₂ then m₁.getKey! k else default := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getKey!_inter | |
| theorem getKey!_inter_of_mem_right [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {k : α} (mem : k ∈ m₂) : | |
| (m₁ ∩ m₂).getKey! k = m₁.getKey! k := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey!_inter_of_mem_right h | |
| theorem getKey!_inter_of_not_mem_right [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {k : α} (not_mem : k ∉ m₂) : | |
| (m₁ ∩ m₂).getKey! k = default := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey!_inter_of_not_mem_right h | |
| theorem getKey!_inter_of_not_mem_left [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {k : α} (not_mem : k ∉ m₁) : | |
| (m₁ ∩ m₂).getKey! k = default := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey!_inter_of_not_mem_left h | |
| /- size -/ | |
| theorem size_inter_le_size_left [EquivBEq α] [LawfulHashable α] : | |
| (m₁ ∩ m₂).size ≤ m₁.size := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.size_inter_le_size_left | |
| theorem size_inter_le_size_right [EquivBEq α] [LawfulHashable α] : | |
| (m₁ ∩ m₂).size ≤ m₂.size := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.size_inter_le_size_right | |
| theorem size_inter_eq_size_left [EquivBEq α] [LawfulHashable α] | |
| (h : ∀ (a : α), a ∈ m₁ → a ∈ m₂) : | |
| (m₁ ∩ m₂).size = m₁.size := | |
| m₁.inductionOn₂ m₂ (fun _ _ => DHashMap.size_inter_eq_size_left) h | |
| theorem size_inter_eq_size_right [EquivBEq α] [LawfulHashable α] | |
| (h : ∀ (a : α), a ∈ m₂ → a ∈ m₁) : | |
| (m₁ ∩ m₂).size = m₂.size := | |
| m₁.inductionOn₂ m₂ (fun _ _ => DHashMap.size_inter_eq_size_right) h | |
| theorem size_add_size_eq_size_union_add_size_inter [EquivBEq α] [LawfulHashable α] : | |
| m₁.size + m₂.size = (m₁ ∪ m₂).size + (m₁ ∩ m₂).size := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.size_add_size_eq_size_union_add_size_inter | |
| /- isEmpty -/ | |
| @[simp] | |
| theorem isEmpty_inter_left [EquivBEq α] [LawfulHashable α] (h : m₁.isEmpty) : | |
| (m₁ ∩ m₂).isEmpty = true := by | |
| revert h | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.isEmpty_inter_left h | |
| @[simp] | |
| theorem isEmpty_inter_right [EquivBEq α] [LawfulHashable α] (h : m₂.isEmpty) : | |
| (m₁ ∩ m₂).isEmpty = true := by | |
| revert h | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.isEmpty_inter_right h | |
| theorem isEmpty_inter_iff [EquivBEq α] [LawfulHashable α] : | |
| (m₁ ∩ m₂).isEmpty ↔ ∀ k, k ∈ m₁ → k ∉ m₂ := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.isEmpty_inter_iff | |
| end Inter | |
| namespace Const | |
| variable {β : Type v} {m₁ m₂ : ExtDHashMap α (fun _ => β)} | |
| /- get? -/ | |
| theorem get?_inter [EquivBEq α] [LawfulHashable α] {k : α} : | |
| Const.get? (m₁ ∩ m₂) k = | |
| if k ∈ m₂ then Const.get? m₁ k else none := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.Const.get?_inter | |
| theorem get?_inter_of_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (mem : k ∈ m₂) : | |
| Const.get? (m₁ ∩ m₂) k = Const.get? m₁ k := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get?_inter_of_mem_right h | |
| theorem get?_inter_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : k ∉ m₁) : | |
| Const.get? (m₁ ∩ m₂) k = none := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get?_inter_of_not_mem_left h | |
| theorem get?_inter_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : k ∉ m₂) : | |
| Const.get? (m₁ ∩ m₂) k = none := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get?_inter_of_not_mem_right h | |
| /- get -/ | |
| @[simp] | |
| theorem get_inter [EquivBEq α] [LawfulHashable α] | |
| {k : α} {h_mem : k ∈ m₁ ∩ m₂} : | |
| Const.get (m₁ ∩ m₂) k h_mem = | |
| Const.get m₁ k (mem_inter_iff.1 h_mem).1 := by | |
| induction m₁ | |
| case mk a => | |
| induction m₂ | |
| case mk b => | |
| apply DHashMap.Const.get_inter | |
| /- getD -/ | |
| theorem getD_inter [EquivBEq α] [LawfulHashable α] {k : α} {fallback : β} : | |
| Const.getD (m₁ ∩ m₂) k fallback = | |
| if k ∈ m₂ then Const.getD m₁ k fallback else fallback := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.Const.getD_inter | |
| theorem getD_inter_of_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} {fallback : β} (mem : k ∈ m₂) : | |
| Const.getD (m₁ ∩ m₂) k fallback = Const.getD m₁ k fallback := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.getD_inter_of_mem_right h | |
| theorem getD_inter_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} {fallback : β} (not_mem : k ∉ m₂) : | |
| Const.getD (m₁ ∩ m₂) k fallback = fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.getD_inter_of_not_mem_right h | |
| theorem getD_inter_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k : α} {fallback : β} (not_mem : k ∉ m₁) : | |
| Const.getD (m₁ ∩ m₂) k fallback = fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.getD_inter_of_not_mem_left h | |
| /- get! -/ | |
| theorem get!_inter [EquivBEq α] [LawfulHashable α] [Inhabited β] {k : α} : | |
| Const.get! (m₁ ∩ m₂) k = | |
| if k ∈ m₂ then Const.get! m₁ k else default := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.Const.get!_inter | |
| theorem get!_inter_of_mem_right [EquivBEq α] [LawfulHashable α] [Inhabited β] | |
| {k : α} (mem : k ∈ m₂) : | |
| Const.get! (m₁ ∩ m₂) k = Const.get! m₁ k := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get!_inter_of_mem_right h | |
| theorem get!_inter_of_not_mem_right [EquivBEq α] [LawfulHashable α] [Inhabited β] | |
| {k : α} (not_mem : k ∉ m₂) : | |
| Const.get! (m₁ ∩ m₂) k = default := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get!_inter_of_not_mem_right h | |
| theorem get!_inter_of_not_mem_left [EquivBEq α] [LawfulHashable α] [Inhabited β] | |
| {k : α} (not_mem : k ∉ m₁) : | |
| Const.get! (m₁ ∩ m₂) k = default := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get!_inter_of_not_mem_left h | |
| end Const | |
| section Diff | |
| variable {m₁ m₂ : ExtDHashMap α β} | |
| @[simp] | |
| theorem diff_eq [EquivBEq α] [LawfulHashable α] : m₁.diff m₂ = m₁ \ m₂ := by | |
| simp only [SDiff.sdiff] | |
| /- contains -/ | |
| @[simp] | |
| theorem contains_diff [EquivBEq α] [LawfulHashable α] | |
| {k : α} : | |
| (m₁ \ m₂).contains k = (m₁.contains k && !m₂.contains k) := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.contains_diff | |
| /- mem -/ | |
| @[simp] | |
| theorem mem_diff_iff [EquivBEq α] [LawfulHashable α] {k : α} : | |
| k ∈ m₁ \ m₂ ↔ k ∈ m₁ ∧ k ∉ m₂ := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.mem_diff_iff | |
| theorem not_mem_diff_of_not_mem_left [EquivBEq α] [LawfulHashable α] {k : α} | |
| (not_mem : k ∉ m₁) : | |
| k ∉ m₁ \ m₂ := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ => DHashMap.not_mem_diff_of_not_mem_left | |
| theorem not_mem_diff_of_mem_right [EquivBEq α] [LawfulHashable α] {k : α} | |
| (mem : k ∈ m₂) : | |
| k ∉ m₁ \ m₂ := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ => DHashMap.not_mem_diff_of_mem_right | |
| /- get? -/ | |
| theorem get?_diff [LawfulBEq α] {k : α} : | |
| (m₁ \ m₂).get? k = if k ∈ m₂ then none else m₁.get? k := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.get?_diff | |
| theorem get?_diff_of_not_mem_right [LawfulBEq α] | |
| {k : α} (not_mem : k ∉ m₂) : | |
| (m₁ \ m₂).get? k = m₁.get? k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get?_diff_of_not_mem_right h | |
| theorem get?_diff_of_not_mem_left [LawfulBEq α] | |
| {k : α} (not_mem : k ∉ m₁) : | |
| (m₁ \ m₂).get? k = none := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get?_diff_of_not_mem_left h | |
| theorem get?_diff_of_mem_right [LawfulBEq α] | |
| {k : α} (mem : k ∈ m₂) : | |
| (m₁ \ m₂).get? k = none := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get?_diff_of_mem_right h | |
| /- get -/ | |
| @[simp] | |
| theorem get_diff [LawfulBEq α] | |
| {k : α} {h_mem : k ∈ m₁ \ m₂} : | |
| (m₁ \ m₂).get k h_mem = | |
| m₁.get k (mem_diff_iff.1 h_mem).1 := by | |
| induction m₁ | |
| case mk a => | |
| induction m₂ | |
| case mk b => | |
| apply DHashMap.get_diff | |
| /- getD -/ | |
| theorem getD_diff [LawfulBEq α] {k : α} {fallback : β k} : | |
| (m₁ \ m₂).getD k fallback = | |
| if k ∈ m₂ then fallback else m₁.getD k fallback := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getD_diff | |
| theorem getD_diff_of_not_mem_right [LawfulBEq α] | |
| {k : α} {fallback : β k} (not_mem : k ∉ m₂) : | |
| (m₁ \ m₂).getD k fallback = m₁.getD k fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getD_diff_of_not_mem_right h | |
| theorem getD_diff_of_mem_right [LawfulBEq α] | |
| {k : α} {fallback : β k} (mem : k ∈ m₂) : | |
| (m₁ \ m₂).getD k fallback = fallback := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getD_diff_of_mem_right h | |
| theorem getD_diff_of_not_mem_left [LawfulBEq α] | |
| {k : α} {fallback : β k} (not_mem : k ∉ m₁) : | |
| (m₁ \ m₂).getD k fallback = fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getD_diff_of_not_mem_left h | |
| /- get! -/ | |
| theorem get!_diff [LawfulBEq α] {k : α} [Inhabited (β k)] : | |
| (m₁ \ m₂).get! k = | |
| if k ∈ m₂ then default else m₁.get! k := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.get!_diff | |
| theorem get!_diff_of_not_mem_right [LawfulBEq α] | |
| {k : α} [Inhabited (β k)] (not_mem : k ∉ m₂) : | |
| (m₁ \ m₂).get! k = m₁.get! k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get!_diff_of_not_mem_right h | |
| theorem get!_diff_of_mem_right [LawfulBEq α] | |
| {k : α} [Inhabited (β k)] (mem : k ∈ m₂) : | |
| (m₁ \ m₂).get! k = default := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get!_diff_of_mem_right h | |
| theorem get!_diff_of_not_mem_left [LawfulBEq α] | |
| {k : α} [Inhabited (β k)] (not_mem : k ∉ m₁) : | |
| (m₁ \ m₂).get! k = default := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.get!_diff_of_not_mem_left h | |
| /- getKey? -/ | |
| theorem getKey?_diff [EquivBEq α] [LawfulHashable α] {k : α} : | |
| (m₁ \ m₂).getKey? k = | |
| if k ∈ m₂ then none else m₁.getKey? k := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getKey?_diff | |
| theorem getKey?_diff_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : k ∉ m₂) : | |
| (m₁ \ m₂).getKey? k = m₁.getKey? k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey?_diff_of_not_mem_right h | |
| theorem getKey?_diff_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : k ∉ m₁) : | |
| (m₁ \ m₂).getKey? k = none := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey?_diff_of_not_mem_left h | |
| theorem getKey?_diff_of_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (mem : k ∈ m₂) : | |
| (m₁ \ m₂).getKey? k = none := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey?_diff_of_mem_right h | |
| /- getKey -/ | |
| @[simp] | |
| theorem getKey_diff [EquivBEq α] [LawfulHashable α] | |
| {k : α} {h_mem : k ∈ m₁ \ m₂} : | |
| (m₁ \ m₂).getKey k h_mem = | |
| m₁.getKey k (mem_diff_iff.1 h_mem).1 := by | |
| induction m₁ | |
| case mk a => | |
| induction m₂ | |
| case mk b => | |
| apply DHashMap.getKey_diff | |
| /- getKeyD -/ | |
| theorem getKeyD_diff [EquivBEq α] [LawfulHashable α] {k fallback : α} : | |
| (m₁ \ m₂).getKeyD k fallback = | |
| if k ∈ m₂ then fallback else m₁.getKeyD k fallback := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getKeyD_diff | |
| theorem getKeyD_diff_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k fallback : α} (not_mem : k ∉ m₂) : | |
| (m₁ \ m₂).getKeyD k fallback = m₁.getKeyD k fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKeyD_diff_of_not_mem_right h | |
| theorem getKeyD_diff_of_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k fallback : α} (mem : k ∈ m₂) : | |
| (m₁ \ m₂).getKeyD k fallback = fallback := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKeyD_diff_of_mem_right h | |
| theorem getKeyD_diff_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k fallback : α} (not_mem : k ∉ m₁) : | |
| (m₁ \ m₂).getKeyD k fallback = fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKeyD_diff_of_not_mem_left h | |
| /- getKey! -/ | |
| theorem getKey!_diff [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} : | |
| (m₁ \ m₂).getKey! k = | |
| if k ∈ m₂ then default else m₁.getKey! k := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.getKey!_diff | |
| theorem getKey!_diff_of_not_mem_right [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {k : α} (not_mem : k ∉ m₂) : | |
| (m₁ \ m₂).getKey! k = m₁.getKey! k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey!_diff_of_not_mem_right h | |
| theorem getKey!_diff_of_mem_right [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {k : α} (mem : k ∈ m₂) : | |
| (m₁ \ m₂).getKey! k = default := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey!_diff_of_mem_right h | |
| theorem getKey!_diff_of_not_mem_left [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {k : α} (not_mem : k ∉ m₁) : | |
| (m₁ \ m₂).getKey! k = default := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.getKey!_diff_of_not_mem_left h | |
| /- size -/ | |
| theorem size_diff_le_size_left [EquivBEq α] [LawfulHashable α] : | |
| (m₁ \ m₂).size ≤ m₁.size := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.size_diff_le_size_left | |
| theorem size_diff_eq_size_left [EquivBEq α] [LawfulHashable α] | |
| (h : ∀ (a : α), a ∈ m₁ → a ∉ m₂) : | |
| (m₁ \ m₂).size = m₁.size := | |
| m₁.inductionOn₂ m₂ (fun _ _ => DHashMap.size_diff_eq_size_left) h | |
| theorem size_diff_add_size_inter_eq_size_left [EquivBEq α] [LawfulHashable α] : | |
| (m₁ \ m₂).size + (m₁ ∩ m₂).size = m₁.size := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.size_diff_add_size_inter_eq_size_left | |
| /- isEmpty -/ | |
| @[simp] | |
| theorem isEmpty_diff_left [EquivBEq α] [LawfulHashable α] (h : m₁.isEmpty) : | |
| (m₁ \ m₂).isEmpty = true := by | |
| revert h | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.isEmpty_diff_left h | |
| theorem isEmpty_diff_iff [EquivBEq α] [LawfulHashable α] : | |
| (m₁ \ m₂).isEmpty ↔ ∀ k, k ∈ m₁ → k ∈ m₂ := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.isEmpty_diff_iff | |
| end Diff | |
| namespace Const | |
| variable {β : Type v} {m₁ m₂ : ExtDHashMap α (fun _ => β)} | |
| /- get? -/ | |
| theorem get?_diff [EquivBEq α] [LawfulHashable α] {k : α} : | |
| Const.get? (m₁ \ m₂) k = | |
| if k ∈ m₂ then none else Const.get? m₁ k := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.Const.get?_diff | |
| theorem get?_diff_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : k ∉ m₂) : | |
| Const.get? (m₁ \ m₂) k = Const.get? m₁ k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get?_diff_of_not_mem_right h | |
| theorem get?_diff_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k : α} (not_mem : k ∉ m₁) : | |
| Const.get? (m₁ \ m₂) k = none := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get?_diff_of_not_mem_left h | |
| theorem get?_diff_of_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} (mem : k ∈ m₂) : | |
| Const.get? (m₁ \ m₂) k = none := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get?_diff_of_mem_right h | |
| /- get -/ | |
| @[simp] | |
| theorem get_diff [EquivBEq α] [LawfulHashable α] | |
| {k : α} {h_mem : k ∈ m₁ \ m₂} : | |
| Const.get (m₁ \ m₂) k h_mem = | |
| Const.get m₁ k (mem_diff_iff.1 h_mem).1 := by | |
| induction m₁ | |
| case mk a => | |
| induction m₂ | |
| case mk b => | |
| apply DHashMap.Const.get_diff | |
| /- getD -/ | |
| theorem getD_diff [EquivBEq α] [LawfulHashable α] {k : α} {fallback : β} : | |
| Const.getD (m₁ \ m₂) k fallback = | |
| if k ∈ m₂ then fallback else Const.getD m₁ k fallback := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.Const.getD_diff | |
| theorem getD_diff_of_not_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} {fallback : β} (not_mem : k ∉ m₂) : | |
| Const.getD (m₁ \ m₂) k fallback = Const.getD m₁ k fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.getD_diff_of_not_mem_right h | |
| theorem getD_diff_of_mem_right [EquivBEq α] [LawfulHashable α] | |
| {k : α} {fallback : β} (mem : k ∈ m₂) : | |
| Const.getD (m₁ \ m₂) k fallback = fallback := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.getD_diff_of_mem_right h | |
| theorem getD_diff_of_not_mem_left [EquivBEq α] [LawfulHashable α] | |
| {k : α} {fallback : β} (not_mem : k ∉ m₁) : | |
| Const.getD (m₁ \ m₂) k fallback = fallback := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.getD_diff_of_not_mem_left h | |
| /- get! -/ | |
| theorem get!_diff [EquivBEq α] [LawfulHashable α] [Inhabited β] {k : α} : | |
| Const.get! (m₁ \ m₂) k = | |
| if k ∈ m₂ then default else Const.get! m₁ k := | |
| m₁.inductionOn₂ m₂ fun _ _ => DHashMap.Const.get!_diff | |
| theorem get!_diff_of_not_mem_right [EquivBEq α] [LawfulHashable α] [Inhabited β] | |
| {k : α} (not_mem : k ∉ m₂) : | |
| Const.get! (m₁ \ m₂) k = Const.get! m₁ k := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get!_diff_of_not_mem_right h | |
| theorem get!_diff_of_mem_right [EquivBEq α] [LawfulHashable α] [Inhabited β] | |
| {k : α} (mem : k ∈ m₂) : | |
| Const.get! (m₁ \ m₂) k = default := by | |
| revert mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get!_diff_of_mem_right h | |
| theorem get!_diff_of_not_mem_left [EquivBEq α] [LawfulHashable α] [Inhabited β] | |
| {k : α} (not_mem : k ∉ m₁) : | |
| Const.get! (m₁ \ m₂) k = default := by | |
| revert not_mem | |
| exact m₁.inductionOn₂ m₂ fun _ _ h => DHashMap.Const.get!_diff_of_not_mem_left h | |
| end Const | |
| variable {m : ExtDHashMap α β} | |
| section Alter | |
| theorem alter_eq_empty_iff_erase_eq_empty [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} : | |
| m.alter k f = ∅ ↔ m.erase k = ∅ ∧ f (m.get? k) = none := by | |
| cases m with | mk m | |
| simpa only [← isEmpty_iff, ← Option.isNone_iff_eq_none, ← Bool.and_eq_true, Bool.coe_iff_coe] using | |
| DHashMap.isEmpty_alter_eq_isEmpty_erase | |
| @[simp] | |
| theorem alter_eq_empty_iff [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} : | |
| alter m k f = ∅ ↔ (m = ∅ ∨ (m.size = 1 ∧ k ∈ m)) ∧ f (get? m k) = none := by | |
| rw [alter_eq_empty_iff_erase_eq_empty, erase_eq_empty_iff] | |
| @[grind =] theorem contains_alter [LawfulBEq α] {k k' : α} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).contains k' = if k == k' then (f (m.get? k)).isSome else m.contains k' := | |
| m.inductionOn fun _ => DHashMap.contains_alter | |
| @[grind =] theorem mem_alter [LawfulBEq α] {k k' : α} {f : Option (β k) → Option (β k)} : | |
| k' ∈ m.alter k f ↔ if k == k' then (f (m.get? k)).isSome = true else k' ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_alter | |
| theorem mem_alter_of_beq [LawfulBEq α] {k k' : α} {f : Option (β k) → Option (β k)} (h : k == k') : | |
| k' ∈ m.alter k f ↔ (f (m.get? k)).isSome := | |
| m.inductionOn (fun _ h => DHashMap.mem_alter_of_beq h) h | |
| @[simp] | |
| theorem contains_alter_self [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).contains k = (f (m.get? k)).isSome := | |
| m.inductionOn fun _ => DHashMap.contains_alter_self | |
| @[simp] | |
| theorem mem_alter_self [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} : | |
| k ∈ m.alter k f ↔ (f (m.get? k)).isSome := | |
| m.inductionOn fun _ => DHashMap.mem_alter_self | |
| theorem contains_alter_of_beq_eq_false [LawfulBEq α] {k k' : α} {f : Option (β k) → Option (β k)} | |
| (h : (k == k') = false) : (m.alter k f).contains k' = m.contains k' := | |
| m.inductionOn (fun _ h => DHashMap.contains_alter_of_beq_eq_false h) h | |
| theorem mem_alter_of_beq_eq_false [LawfulBEq α] {k k' : α} {f : Option (β k) → Option (β k)} | |
| (h : (k == k') = false) : k' ∈ m.alter k f ↔ k' ∈ m := | |
| m.inductionOn (fun _ h => DHashMap.mem_alter_of_beq_eq_false h) h | |
| @[grind =] theorem size_alter [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).size = | |
| if k ∈ m ∧ (f (m.get? k)).isNone then | |
| m.size - 1 | |
| else if k ∉ m ∧ (f (m.get? k)).isSome then | |
| m.size + 1 | |
| else | |
| m.size := | |
| m.inductionOn fun _ => DHashMap.size_alter | |
| theorem size_alter_eq_add_one [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} | |
| (h : k ∉ m) (h' : (f (m.get? k)).isSome) : | |
| (m.alter k f).size = m.size + 1 := | |
| m.inductionOn (fun _ h h' => DHashMap.size_alter_eq_add_one h h') h h' | |
| theorem size_alter_eq_sub_one [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} | |
| (h : k ∈ m) (h' : (f (m.get? k)).isNone) : | |
| (m.alter k f).size = m.size - 1 := | |
| m.inductionOn (fun _ h h' => DHashMap.size_alter_eq_sub_one h h') h h' | |
| theorem size_alter_eq_self_of_not_mem [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} | |
| (h : k ∉ m) (h' : (f (m.get? k)).isNone) : (m.alter k f).size = m.size := | |
| m.inductionOn (fun _ h h' => DHashMap.size_alter_eq_self_of_not_mem h h') h h' | |
| theorem size_alter_eq_self_of_mem [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} | |
| (h : k ∈ m) (h' : (f (m.get? k)).isSome) : (m.alter k f).size = m.size := | |
| m.inductionOn (fun _ h h' => DHashMap.size_alter_eq_self_of_mem h h') h h' | |
| theorem size_alter_le_size [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).size ≤ m.size + 1 := | |
| m.inductionOn fun _ => DHashMap.size_alter_le_size | |
| theorem size_le_size_alter [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} : | |
| m.size - 1 ≤ (m.alter k f).size := | |
| m.inductionOn fun _ => DHashMap.size_le_size_alter | |
| @[grind =] theorem get?_alter [LawfulBEq α] {k k' : α} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).get? k' = | |
| if h : k == k' then | |
| (cast (congrArg (Option ∘ β) (eq_of_beq h)) (f (m.get? k))) | |
| else | |
| m.get? k' := | |
| m.inductionOn fun _ => DHashMap.get?_alter | |
| @[simp] | |
| theorem get?_alter_self [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).get? k = f (m.get? k) := | |
| m.inductionOn fun _ => DHashMap.get?_alter_self | |
| @[grind =] theorem get_alter [LawfulBEq α] {k k' : α} {f : Option (β k) → Option (β k)} | |
| {h : k' ∈ m.alter k f} : | |
| (m.alter k f).get k' h = | |
| if heq : k == k' then | |
| haveI h' : (f (m.get? k)).isSome := mem_alter_of_beq heq |>.mp h | |
| cast (congrArg β (eq_of_beq heq)) <| (f (m.get? k)).get <| h' | |
| else | |
| haveI h' : k' ∈ m := mem_alter_of_beq_eq_false (Bool.not_eq_true _ ▸ heq) |>.mp h | |
| m.get k' h' := | |
| m.inductionOn (fun _ _ => DHashMap.get_alter) h | |
| @[simp] | |
| theorem get_alter_self [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} | |
| {h : k ∈ m.alter k f} : | |
| haveI h' : (f (m.get? k)).isSome := mem_alter_self.mp h | |
| (m.alter k f).get k h = (f (m.get? k)).get h' := | |
| m.inductionOn (fun _ _ => DHashMap.get_alter_self) h | |
| @[grind =] theorem get!_alter [LawfulBEq α] {k k' : α} [hi : Inhabited (β k')] | |
| {f : Option (β k) → Option (β k)} : (m.alter k f).get! k' = | |
| if heq : k == k' then | |
| (f (m.get? k)).map (cast (congrArg β (eq_of_beq heq))) |>.get! | |
| else | |
| m.get! k' := | |
| m.inductionOn fun _ => DHashMap.get!_alter | |
| @[simp] | |
| theorem get!_alter_self [LawfulBEq α] {k : α} [Inhabited (β k)] {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).get! k = (f (m.get? k)).get! := | |
| m.inductionOn fun _ => DHashMap.get!_alter_self | |
| @[grind =] theorem getD_alter [LawfulBEq α] {k k' : α} {fallback : β k'} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).getD k' fallback = | |
| if heq : k == k' then | |
| f (m.get? k) |>.map (cast (congrArg β <| eq_of_beq heq)) |>.getD fallback | |
| else | |
| m.getD k' fallback := | |
| m.inductionOn fun _ => DHashMap.getD_alter | |
| @[simp] | |
| theorem getD_alter_self [LawfulBEq α] {k : α} {fallback : β k} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).getD k fallback = (f (m.get? k)).getD fallback := | |
| m.inductionOn fun _ => DHashMap.getD_alter_self | |
| @[grind =] theorem getKey?_alter [LawfulBEq α] {k k' : α} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).getKey? k' = | |
| if k == k' then | |
| if (f (m.get? k)).isSome then some k else none | |
| else | |
| m.getKey? k' := | |
| m.inductionOn fun _ => DHashMap.getKey?_alter | |
| theorem getKey?_alter_self [LawfulBEq α] {k : α} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).getKey? k = if (f (m.get? k)).isSome then some k else none := | |
| m.inductionOn fun _ => DHashMap.getKey?_alter_self | |
| @[grind =] theorem getKey!_alter [LawfulBEq α] [Inhabited α] {k k' : α} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).getKey! k' = | |
| if k == k' then | |
| if (f (m.get? k)).isSome then k else default | |
| else | |
| m.getKey! k' := | |
| m.inductionOn fun _ => DHashMap.getKey!_alter | |
| theorem getKey!_alter_self [LawfulBEq α] [Inhabited α] {k : α} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).getKey! k = if (f (m.get? k)).isSome then k else default := | |
| m.inductionOn fun _ => DHashMap.getKey!_alter_self | |
| @[simp] | |
| theorem getKey_alter_self [LawfulBEq α] [Inhabited α] {k : α} {f : Option (β k) → Option (β k)} | |
| {h : k ∈ m.alter k f} : (m.alter k f).getKey k h = k := | |
| m.inductionOn (fun _ _ => DHashMap.getKey_alter_self) h | |
| @[grind =] theorem getKeyD_alter [LawfulBEq α] {k k' fallback : α} {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).getKeyD k' fallback = | |
| if k == k' then | |
| if (f (m.get? k)).isSome then k else fallback | |
| else | |
| m.getKeyD k' fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_alter | |
| @[simp] | |
| theorem getKeyD_alter_self [LawfulBEq α] [Inhabited α] {k : α} {fallback : α} | |
| {f : Option (β k) → Option (β k)} : | |
| (m.alter k f).getKeyD k fallback = if (f (m.get? k)).isSome then k else fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_alter_self | |
| namespace Const | |
| variable {β : Type v} {m : ExtDHashMap α (fun _ => β)} | |
| theorem alter_eq_empty_iff_erase_eq_empty [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : | |
| alter m k f = ∅ ↔ m.erase k = ∅ ∧ f (get? m k) = none := by | |
| cases m with | mk m | |
| simpa only [← isEmpty_iff, ← Option.isNone_iff_eq_none, ← Bool.and_eq_true, Bool.coe_iff_coe] using | |
| DHashMap.Const.isEmpty_alter_eq_isEmpty_erase | |
| @[simp] | |
| theorem alter_eq_empty_iff [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : | |
| alter m k f = ∅ ↔ (m = ∅ ∨ (m.size = 1 ∧ k ∈ m)) ∧ f (get? m k) = none := by | |
| simp only [alter_eq_empty_iff_erase_eq_empty, erase_eq_empty_iff] | |
| @[grind =] theorem contains_alter [EquivBEq α] [LawfulHashable α] {k k': α} {f : Option β → Option β} : | |
| (Const.alter m k f).contains k' = | |
| if k == k' then (f (Const.get? m k)).isSome else m.contains k' := | |
| m.inductionOn fun _ => DHashMap.Const.contains_alter | |
| @[grind =] theorem mem_alter [EquivBEq α] [LawfulHashable α] {k k': α} {f : Option β → Option β} : | |
| k' ∈ Const.alter m k f ↔ if k == k' then (f (Const.get? m k)).isSome = true else k' ∈ m := | |
| m.inductionOn fun _ => DHashMap.Const.mem_alter | |
| theorem mem_alter_of_beq [EquivBEq α] [LawfulHashable α] {k k': α} {f : Option β → Option β} | |
| (h : k == k') : k' ∈ Const.alter m k f ↔ (f (Const.get? m k)).isSome := | |
| m.inductionOn (fun _ h => DHashMap.Const.mem_alter_of_beq h) h | |
| @[simp] | |
| theorem contains_alter_self [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : | |
| (Const.alter m k f).contains k = (f (Const.get? m k)).isSome := | |
| m.inductionOn fun _ => DHashMap.Const.contains_alter_self | |
| @[simp] | |
| theorem mem_alter_self [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : | |
| k ∈ Const.alter m k f ↔ (f (Const.get? m k)).isSome := | |
| m.inductionOn fun _ => DHashMap.Const.mem_alter_self | |
| theorem contains_alter_of_beq_eq_false [EquivBEq α] [LawfulHashable α] {k k' : α} | |
| {f : Option β → Option β} (h : (k == k') = false) : | |
| (Const.alter m k f).contains k' = m.contains k' := | |
| m.inductionOn (fun _ h => DHashMap.Const.contains_alter_of_beq_eq_false h) h | |
| theorem mem_alter_of_beq_eq_false [EquivBEq α] [LawfulHashable α] {k k' : α} | |
| {f : Option β → Option β} (h : (k == k') = false) : k' ∈ Const.alter m k f ↔ k' ∈ m := | |
| m.inductionOn (fun _ h => DHashMap.Const.mem_alter_of_beq_eq_false h) h | |
| @[grind =] theorem size_alter [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : | |
| (Const.alter m k f).size = | |
| if k ∈ m ∧ (f (Const.get? m k)).isNone then | |
| m.size - 1 | |
| else if k ∉ m ∧ (f (Const.get? m k)).isSome then | |
| m.size + 1 | |
| else | |
| m.size := | |
| m.inductionOn fun _ => DHashMap.Const.size_alter | |
| theorem size_alter_eq_add_one [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} | |
| (h : k ∉ m) (h' : (f (Const.get? m k)).isSome) : | |
| (Const.alter m k f).size = m.size + 1 := | |
| m.inductionOn (fun _ h h' => DHashMap.Const.size_alter_eq_add_one h h') h h' | |
| theorem size_alter_eq_sub_one [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} | |
| (h : k ∈ m) (h' : (f (Const.get? m k)).isNone) : | |
| (Const.alter m k f).size = m.size - 1 := | |
| m.inductionOn (fun _ h h' => DHashMap.Const.size_alter_eq_sub_one h h') h h' | |
| theorem size_alter_eq_self_of_not_mem [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} | |
| (h : k ∉ m) (h' : (f (Const.get? m k)).isNone) : (Const.alter m k f).size = m.size := | |
| m.inductionOn (fun _ h h' => DHashMap.Const.size_alter_eq_self_of_not_mem h h') h h' | |
| theorem size_alter_eq_self_of_mem [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} | |
| (h : k ∈ m) (h' : (f (Const.get? m k)).isSome) : (Const.alter m k f).size = m.size := | |
| m.inductionOn (fun _ h h' => DHashMap.Const.size_alter_eq_self_of_mem h h') h h' | |
| theorem size_alter_le_size [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : | |
| (Const.alter m k f).size ≤ m.size + 1 := | |
| m.inductionOn fun _ => DHashMap.Const.size_alter_le_size | |
| theorem size_le_size_alter [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : | |
| m.size - 1 ≤ (Const.alter m k f).size := | |
| m.inductionOn fun _ => DHashMap.Const.size_le_size_alter | |
| @[grind =] theorem get?_alter [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} : | |
| Const.get? (Const.alter m k f) k' = | |
| if k == k' then | |
| f (Const.get? m k) | |
| else | |
| Const.get? m k' := | |
| m.inductionOn fun _ => DHashMap.Const.get?_alter | |
| @[simp] | |
| theorem get?_alter_self [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : | |
| Const.get? (Const.alter m k f) k = f (Const.get? m k) := | |
| m.inductionOn fun _ => DHashMap.Const.get?_alter_self | |
| @[grind =] theorem get_alter [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} | |
| {h : k' ∈ Const.alter m k f} : | |
| Const.get (Const.alter m k f) k' h = | |
| if heq : k == k' then | |
| haveI h' : (f (Const.get? m k)).isSome := mem_alter_of_beq heq |>.mp h | |
| f (Const.get? m k) |>.get h' | |
| else | |
| haveI h' : k' ∈ m := mem_alter_of_beq_eq_false (Bool.not_eq_true _ ▸ heq) |>.mp h | |
| Const.get m k' h' := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_alter) h | |
| @[simp] | |
| theorem get_alter_self [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} | |
| {h : k ∈ Const.alter m k f} : | |
| haveI h' : (f (Const.get? m k)).isSome := mem_alter_self.mp h | |
| Const.get (Const.alter m k f) k h = (f (Const.get? m k)).get h' := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_alter_self) h | |
| @[grind =] theorem get!_alter [EquivBEq α] [LawfulHashable α] {k k' : α} [Inhabited β] | |
| {f : Option β → Option β} : Const.get! (Const.alter m k f) k' = | |
| if k == k' then | |
| f (Const.get? m k) |>.get! | |
| else | |
| Const.get! m k' := | |
| m.inductionOn fun _ => DHashMap.Const.get!_alter | |
| @[simp] | |
| theorem get!_alter_self [EquivBEq α] [LawfulHashable α] {k : α} [Inhabited β] | |
| {f : Option β → Option β} : Const.get! (Const.alter m k f) k = (f (Const.get? m k)).get! := | |
| m.inductionOn fun _ => DHashMap.Const.get!_alter_self | |
| @[grind =] theorem getD_alter [EquivBEq α] [LawfulHashable α] {k k' : α} {fallback : β} | |
| {f : Option β → Option β} : | |
| Const.getD (Const.alter m k f) k' fallback = | |
| if k == k' then | |
| f (Const.get? m k) |>.getD fallback | |
| else | |
| Const.getD m k' fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_alter | |
| @[simp] | |
| theorem getD_alter_self [EquivBEq α] [LawfulHashable α] {k : α} {fallback : β} | |
| {f : Option β → Option β} : | |
| Const.getD (Const.alter m k f) k fallback = (f (Const.get? m k)).getD fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_alter_self | |
| @[grind =] theorem getKey?_alter [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} : | |
| (Const.alter m k f).getKey? k' = | |
| if k == k' then | |
| if (f (Const.get? m k)).isSome then some k else none | |
| else | |
| m.getKey? k' := | |
| m.inductionOn fun _ => DHashMap.Const.getKey?_alter | |
| theorem getKey?_alter_self [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : | |
| (Const.alter m k f).getKey? k = if (f (Const.get? m k)).isSome then some k else none := | |
| m.inductionOn fun _ => DHashMap.Const.getKey?_alter_self | |
| @[grind =] theorem getKey!_alter [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} | |
| {f : Option β → Option β} : (Const.alter m k f).getKey! k' = | |
| if k == k' then | |
| if (f (Const.get? m k)).isSome then k else default | |
| else | |
| m.getKey! k' := | |
| m.inductionOn fun _ => DHashMap.Const.getKey!_alter | |
| theorem getKey!_alter_self [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} | |
| {f : Option β → Option β} : | |
| (Const.alter m k f).getKey! k = if (f (Const.get? m k)).isSome then k else default := | |
| m.inductionOn fun _ => DHashMap.Const.getKey!_alter_self | |
| @[grind =] theorem getKey_alter [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} | |
| {f : Option β → Option β} {h : k' ∈ Const.alter m k f} : | |
| (Const.alter m k f).getKey k' h = | |
| if heq : k == k' then | |
| k | |
| else | |
| haveI h' : k' ∈ m := mem_alter_of_beq_eq_false (Bool.not_eq_true _ ▸ heq) |>.mp h | |
| m.getKey k' h' := | |
| m.inductionOn (fun _ _ => DHashMap.Const.getKey_alter) h | |
| @[simp] | |
| theorem getKey_alter_self [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} | |
| {f : Option β → Option β} {h : k ∈ Const.alter m k f} : | |
| (Const.alter m k f).getKey k h = k := | |
| m.inductionOn (fun _ _ => DHashMap.Const.getKey_alter_self) h | |
| @[grind =] theorem getKeyD_alter [EquivBEq α] [LawfulHashable α] {k k' fallback : α} | |
| {f : Option β → Option β} : | |
| (Const.alter m k f).getKeyD k' fallback = | |
| if k == k' then | |
| if (f (Const.get? m k)).isSome then k else fallback | |
| else | |
| m.getKeyD k' fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getKeyD_alter | |
| theorem getKeyD_alter_self [EquivBEq α] [LawfulHashable α] [Inhabited α] {k fallback : α} | |
| {f : Option β → Option β} : | |
| (Const.alter m k f).getKeyD k fallback = | |
| if (f (Const.get? m k)).isSome then k else fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getKeyD_alter_self | |
| end Const | |
| end Alter | |
| section Modify | |
| @[simp] | |
| theorem modify_eq_empty_iff [LawfulBEq α] {k : α} {f : β k → β k} : | |
| m.modify k f = ∅ ↔ m = ∅ := by | |
| simp only [← isEmpty_iff, Bool.coe_iff_coe] | |
| exact m.inductionOn fun _ => DHashMap.isEmpty_modify | |
| @[simp, grind =] | |
| theorem contains_modify [LawfulBEq α] {k k': α} {f : β k → β k} : | |
| (m.modify k f).contains k' = m.contains k' := | |
| m.inductionOn fun _ => DHashMap.contains_modify | |
| @[simp, grind =] | |
| theorem mem_modify [LawfulBEq α] {k k': α} {f : β k → β k} : k' ∈ m.modify k f ↔ k' ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_modify | |
| @[simp, grind =] | |
| theorem size_modify [LawfulBEq α] {k : α} {f : β k → β k} : (m.modify k f).size = m.size := | |
| m.inductionOn fun _ => DHashMap.size_modify | |
| @[grind =] | |
| theorem get?_modify [LawfulBEq α] {k k' : α} {f : β k → β k} : | |
| (m.modify k f).get? k' = if h : k == k' then | |
| (cast (congrArg (Option ∘ β) (eq_of_beq h)) ((m.get? k).map f)) | |
| else | |
| m.get? k' := | |
| m.inductionOn fun _ => DHashMap.get?_modify | |
| @[simp] | |
| theorem get?_modify_self [LawfulBEq α] {k : α} {f : β k → β k} : | |
| (m.modify k f).get? k = (m.get? k).map f := | |
| m.inductionOn fun _ => DHashMap.get?_modify_self | |
| @[grind =] | |
| theorem get_modify [LawfulBEq α] {k k' : α} {f : β k → β k} | |
| (h : k' ∈ m.modify k f) : | |
| (m.modify k f).get k' h = | |
| if heq : k == k' then | |
| haveI h' : k ∈ m := mem_congr heq |>.mpr <| mem_modify.mp h | |
| cast (congrArg β (eq_of_beq heq)) <| f (m.get k h') | |
| else | |
| haveI h' : k' ∈ m := mem_modify.mp h | |
| m.get k' h' := | |
| m.inductionOn (fun _ h => DHashMap.get_modify h) h | |
| @[simp] | |
| theorem get_modify_self [LawfulBEq α] {k : α} {f : β k → β k} {h : k ∈ m.modify k f} : | |
| haveI h' : k ∈ m := mem_modify.mp h | |
| (m.modify k f).get k h = f (m.get k h') := | |
| m.inductionOn (fun _ _ => DHashMap.get_modify_self) h | |
| @[grind =] | |
| theorem get!_modify [LawfulBEq α] {k k' : α} [hi : Inhabited (β k')] {f : β k → β k} : | |
| (m.modify k f).get! k' = | |
| if heq : k == k' then | |
| m.get? k |>.map f |>.map (cast (congrArg β (eq_of_beq heq))) |>.get! | |
| else | |
| m.get! k' := | |
| m.inductionOn fun _ => DHashMap.get!_modify | |
| @[simp] | |
| theorem get!_modify_self [LawfulBEq α] {k : α} [Inhabited (β k)] {f : β k → β k} : | |
| (m.modify k f).get! k = ((m.get? k).map f).get! := | |
| m.inductionOn fun _ => DHashMap.get!_modify_self | |
| @[grind =] | |
| theorem getD_modify [LawfulBEq α] {k k' : α} {fallback : β k'} {f : β k → β k} : | |
| (m.modify k f).getD k' fallback = | |
| if heq : k == k' then | |
| m.get? k |>.map f |>.map (cast (congrArg β <| eq_of_beq heq)) |>.getD fallback | |
| else | |
| m.getD k' fallback := | |
| m.inductionOn fun _ => DHashMap.getD_modify | |
| @[simp] | |
| theorem getD_modify_self [LawfulBEq α] {k : α} {fallback : β k} {f : β k → β k} : | |
| (m.modify k f).getD k fallback = ((m.get? k).map f).getD fallback := | |
| m.inductionOn fun _ => DHashMap.getD_modify_self | |
| @[grind =] | |
| theorem getKey?_modify [LawfulBEq α] {k k' : α} {f : β k → β k} : | |
| (m.modify k f).getKey? k' = | |
| if k == k' then | |
| if k ∈ m then some k else none | |
| else | |
| m.getKey? k' := | |
| m.inductionOn fun _ => DHashMap.getKey?_modify | |
| theorem getKey?_modify_self [LawfulBEq α] {k : α} {f : β k → β k} : | |
| (m.modify k f).getKey? k = if k ∈ m then some k else none := | |
| m.inductionOn fun _ => DHashMap.getKey?_modify_self | |
| @[grind =] | |
| theorem getKey!_modify [LawfulBEq α] [Inhabited α] {k k' : α} {f : β k → β k} : | |
| (m.modify k f).getKey! k' = | |
| if k == k' then | |
| if k ∈ m then k else default | |
| else | |
| m.getKey! k' := | |
| m.inductionOn fun _ => DHashMap.getKey!_modify | |
| theorem getKey!_modify_self [LawfulBEq α] [Inhabited α] {k : α} {f : β k → β k} : | |
| (m.modify k f).getKey! k = if k ∈ m then k else default := | |
| m.inductionOn fun _ => DHashMap.getKey!_modify_self | |
| @[simp] | |
| theorem getKey_modify_self [LawfulBEq α] [Inhabited α] {k : α} {f : β k → β k} | |
| {h : k ∈ m.modify k f} : (m.modify k f).getKey k h = k := | |
| m.inductionOn (fun _ _ => DHashMap.getKey_modify_self) h | |
| @[grind =] | |
| theorem getKeyD_modify [LawfulBEq α] {k k' fallback : α} {f : β k → β k} : | |
| (m.modify k f).getKeyD k' fallback = | |
| if k == k' then | |
| if k ∈ m then k else fallback | |
| else | |
| m.getKeyD k' fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_modify | |
| theorem getKeyD_modify_self [LawfulBEq α] [Inhabited α] {k fallback : α} {f : β k → β k} : | |
| (m.modify k f).getKeyD k fallback = if k ∈ m then k else fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_modify_self | |
| namespace Const | |
| variable {β : Type v} {m : ExtDHashMap α (fun _ => β)} | |
| @[simp] | |
| theorem modify_eq_empty_iff [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} : | |
| Const.modify m k f = ∅ ↔ m = ∅ := by | |
| simp only [← isEmpty_iff, Bool.coe_iff_coe] | |
| exact m.inductionOn fun _ => DHashMap.Const.isEmpty_modify | |
| @[simp, grind =] | |
| theorem contains_modify [EquivBEq α] [LawfulHashable α] {k k': α} {f : β → β} : | |
| (Const.modify m k f).contains k' = m.contains k' := | |
| m.inductionOn fun _ => DHashMap.Const.contains_modify | |
| @[simp, grind =] | |
| theorem mem_modify [EquivBEq α] [LawfulHashable α] {k k': α} {f : β → β} : | |
| k' ∈ Const.modify m k f ↔ k' ∈ m := | |
| m.inductionOn fun _ => DHashMap.Const.mem_modify | |
| @[simp, grind =] | |
| theorem size_modify [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} : | |
| (Const.modify m k f).size = m.size := | |
| m.inductionOn fun _ => DHashMap.Const.size_modify | |
| @[grind =] | |
| theorem get?_modify [EquivBEq α] [LawfulHashable α] {k k' : α} {f : β → β} : | |
| Const.get? (Const.modify m k f) k' = if k == k' then | |
| Const.get? m k |>.map f | |
| else | |
| Const.get? m k' := | |
| m.inductionOn fun _ => DHashMap.Const.get?_modify | |
| @[simp] | |
| theorem get?_modify_self [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} : | |
| Const.get? (Const.modify m k f) k = (Const.get? m k).map f := | |
| m.inductionOn fun _ => DHashMap.Const.get?_modify_self | |
| @[grind =] | |
| theorem get_modify [EquivBEq α] [LawfulHashable α] {k k' : α} {f : β → β} | |
| {h : k' ∈ Const.modify m k f} : | |
| Const.get (Const.modify m k f) k' h = | |
| if heq : k == k' then | |
| haveI h' : k ∈ m := mem_congr heq |>.mpr <| mem_modify.mp h | |
| f (Const.get m k h') | |
| else | |
| haveI h' : k' ∈ m := mem_modify.mp h | |
| Const.get m k' h' := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_modify) h | |
| @[simp] | |
| theorem get_modify_self [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} | |
| {h : k ∈ Const.modify m k f} : | |
| haveI h' : k ∈ m := mem_modify.mp h | |
| Const.get (Const.modify m k f) k h = f (Const.get m k h') := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_modify_self) h | |
| @[grind =] | |
| theorem get!_modify [EquivBEq α] [LawfulHashable α] {k k' : α} [Inhabited β] {f : β → β} : | |
| Const.get! (Const.modify m k f) k' = | |
| if k == k' then | |
| Const.get? m k |>.map f |>.get! | |
| else | |
| Const.get! m k' := | |
| m.inductionOn fun _ => DHashMap.Const.get!_modify | |
| @[simp] | |
| theorem get!_modify_self [EquivBEq α] [LawfulHashable α] {k : α} [Inhabited β] {f : β → β} : | |
| Const.get! (Const.modify m k f) k = ((Const.get? m k).map f).get! := | |
| m.inductionOn fun _ => DHashMap.Const.get!_modify_self | |
| @[grind =] | |
| theorem getD_modify [EquivBEq α] [LawfulHashable α] {k k' : α} {fallback : β} {f : β → β} : | |
| Const.getD (Const.modify m k f) k' fallback = | |
| if k == k' then | |
| Const.get? m k |>.map f |>.getD fallback | |
| else | |
| Const.getD m k' fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_modify | |
| @[simp] | |
| theorem getD_modify_self [EquivBEq α] [LawfulHashable α] {k : α} {fallback : β} {f : β → β} : | |
| Const.getD (Const.modify m k f) k fallback = ((Const.get? m k).map f).getD fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_modify_self | |
| @[grind =] | |
| theorem getKey?_modify [EquivBEq α] [LawfulHashable α] {k k' : α} {f : β → β} : | |
| (Const.modify m k f).getKey? k' = | |
| if k == k' then | |
| if k ∈ m then some k else none | |
| else | |
| m.getKey? k' := | |
| m.inductionOn fun _ => DHashMap.Const.getKey?_modify | |
| theorem getKey?_modify_self [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} : | |
| (Const.modify m k f).getKey? k = if k ∈ m then some k else none := | |
| m.inductionOn fun _ => DHashMap.Const.getKey?_modify_self | |
| @[grind =] | |
| theorem getKey!_modify [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} {f : β → β} : | |
| (Const.modify m k f).getKey! k' = | |
| if k == k' then | |
| if k ∈ m then k else default | |
| else | |
| m.getKey! k' := | |
| m.inductionOn fun _ => DHashMap.Const.getKey!_modify | |
| theorem getKey!_modify_self [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} {f : β → β} : | |
| (Const.modify m k f).getKey! k = if k ∈ m then k else default := | |
| m.inductionOn fun _ => DHashMap.Const.getKey!_modify_self | |
| @[grind =] | |
| theorem getKey_modify [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} {f : β → β} | |
| {h : k' ∈ Const.modify m k f} : | |
| (Const.modify m k f).getKey k' h = | |
| if k == k' then | |
| k | |
| else | |
| haveI h' : k' ∈ m := mem_modify.mp h | |
| m.getKey k' h' := | |
| m.inductionOn (fun _ _ => DHashMap.Const.getKey_modify) h | |
| @[simp] | |
| theorem getKey_modify_self [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} {f : β → β} | |
| {h : k ∈ Const.modify m k f} : (Const.modify m k f).getKey k h = k := | |
| m.inductionOn (fun _ _ => DHashMap.Const.getKey_modify_self) h | |
| @[grind =] | |
| theorem getKeyD_modify [EquivBEq α] [LawfulHashable α] {k k' fallback : α} {f : β → β} : | |
| (Const.modify m k f).getKeyD k' fallback = | |
| if k == k' then | |
| if k ∈ m then k else fallback | |
| else | |
| m.getKeyD k' fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getKeyD_modify | |
| theorem getKeyD_modify_self [EquivBEq α] [LawfulHashable α] [Inhabited α] {k fallback : α} {f : β → β} : | |
| (Const.modify m k f).getKeyD k fallback = if k ∈ m then k else fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getKeyD_modify_self | |
| end Const | |
| end Modify | |
| section Ext | |
| variable {m₁ m₂ : Std.ExtDHashMap α β} | |
| @[ext, grind ext] | |
| theorem ext_get? [LawfulBEq α] {m₁ m₂ : Std.ExtDHashMap α β} (h : ∀ k, m₁.get? k = m₂.get? k) : m₁ = m₂ := | |
| m₁.inductionOn₂ m₂ (fun _ _ h => sound (.of_forall_get?_eq h)) h | |
| namespace Const | |
| variable {β : Type v} {m₁ m₂ : ExtDHashMap α fun _ => β} | |
| theorem ext_getKey_get? [EquivBEq α] [LawfulHashable α] | |
| (hk : ∀ k hk hk', m₁.getKey k hk = m₂.getKey k hk') | |
| (hv : ∀ k, Const.get? m₁ k = Const.get? m₂ k) : m₁ = m₂ := | |
| m₁.inductionOn₂ m₂ (fun _ _ hk hv => sound | |
| (.of_forall_getKey_eq_of_forall_constGet?_eq hk hv)) hk hv | |
| theorem ext_get? [LawfulBEq α] (h : ∀ k, get? m₁ k = get? m₂ k) : m₁ = m₂ := | |
| m₁.inductionOn₂ m₂ (fun _ _ h => sound (.of_forall_constGet?_eq h)) h | |
| theorem ext_getKey?_unit [EquivBEq α] [LawfulHashable α] {m₁ m₂ : ExtDHashMap α fun _ => Unit} | |
| (h : ∀ k, m₁.getKey? k = m₂.getKey? k) : m₁ = m₂ := | |
| m₁.inductionOn₂ m₂ (fun _ _ h => sound (.of_forall_getKey?_unit_eq h)) h | |
| theorem ext_contains_unit [LawfulBEq α] {m₁ m₂ : ExtDHashMap α fun _ => Unit} | |
| (h : ∀ k, m₁.contains k = m₂.contains k) : m₁ = m₂ := | |
| m₁.inductionOn₂ m₂ (fun _ _ h => sound (.of_forall_contains_unit_eq h)) h | |
| theorem ext_mem_unit [LawfulBEq α] {m₁ m₂ : ExtDHashMap α fun _ => Unit} | |
| (h : ∀ k, k ∈ m₁ ↔ k ∈ m₂) : m₁ = m₂ := | |
| m₁.inductionOn₂ m₂ (fun _ _ h => sound (.of_forall_mem_unit_iff h)) h | |
| end Const | |
| end Ext | |
| section filterMap | |
| variable {γ : α → Type w} | |
| theorem filterMap_eq_empty_iff [LawfulBEq α] | |
| {f : (a : α) → β a → Option (γ a)} : | |
| m.filterMap f = ∅ ↔ ∀ k h, f k (m.get k h) = none := | |
| isEmpty_iff.symm.trans <| m.inductionOn fun _ => DHashMap.isEmpty_filterMap_iff | |
| @[grind =] | |
| theorem contains_filterMap [LawfulBEq α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} : | |
| (m.filterMap f).contains k = (m.get? k).any (f k · |>.isSome) := | |
| m.inductionOn fun _ => DHashMap.contains_filterMap | |
| @[grind =] | |
| theorem mem_filterMap [LawfulBEq α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} : | |
| k ∈ m.filterMap f ↔ ∃ h, (f k (m.get k h)).isSome := | |
| m.inductionOn fun _ => DHashMap.mem_filterMap | |
| theorem contains_of_contains_filterMap [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} : | |
| (m.filterMap f).contains k = true → m.contains k = true := | |
| m.inductionOn fun _ => DHashMap.contains_of_contains_filterMap | |
| theorem mem_of_mem_filterMap [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} : | |
| k ∈ m.filterMap f → k ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_of_mem_filterMap | |
| theorem size_filterMap_le_size [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → Option (γ a)} : | |
| (m.filterMap f).size ≤ m.size := | |
| m.inductionOn fun _ => DHashMap.size_filterMap_le_size | |
| grind_pattern size_filterMap_le_size => (m.filterMap f).size | |
| theorem size_filterMap_eq_size_iff [LawfulBEq α] | |
| {f : (a : α) → β a → Option (γ a)} : | |
| (m.filterMap f).size = m.size ↔ ∀ (a : α) (h : a ∈ m), (f a (m.get a h)).isSome := | |
| m.inductionOn fun _ => DHashMap.size_filterMap_eq_size_iff | |
| @[simp, grind =] | |
| theorem get?_filterMap [LawfulBEq α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} : | |
| (m.filterMap f).get? k = (m.get? k).bind (f k) := | |
| m.inductionOn fun _ => DHashMap.get?_filterMap | |
| theorem isSome_apply_of_mem_filterMap [LawfulBEq α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} : | |
| ∀ (h' : k ∈ m.filterMap f), | |
| (f k (m.get k (mem_of_mem_filterMap h'))).isSome := | |
| m.inductionOn fun _ => DHashMap.isSome_apply_of_mem_filterMap | |
| @[simp, grind =] | |
| theorem get_filterMap [LawfulBEq α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} {h'} : | |
| (m.filterMap f).get k h' = | |
| (f k (m.get k (mem_of_mem_filterMap h'))).get | |
| (isSome_apply_of_mem_filterMap h') := | |
| m.inductionOn (fun _ _ => DHashMap.get_filterMap) h' | |
| @[grind =] | |
| theorem get!_filterMap [LawfulBEq α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} [Inhabited (γ k)] : | |
| (m.filterMap f).get! k = ((m.get? k).bind (f k)).get! := | |
| m.inductionOn fun _ => DHashMap.get!_filterMap | |
| @[grind =] | |
| theorem getD_filterMap [LawfulBEq α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} {fallback : γ k} : | |
| (m.filterMap f).getD k fallback = ((m.get? k).bind (f k)).getD fallback := | |
| m.inductionOn fun _ => DHashMap.getD_filterMap | |
| @[grind =] | |
| theorem getKey?_filterMap [LawfulBEq α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} : | |
| (m.filterMap f).getKey? k = | |
| (m.getKey? k).pfilter (fun x h' => | |
| (f x (m.get x (mem_of_getKey?_eq_some h'))).isSome) := | |
| m.inductionOn fun _ => DHashMap.getKey?_filterMap | |
| @[simp, grind =] | |
| theorem getKey_filterMap [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} {h'} : | |
| (m.filterMap f).getKey k h' = m.getKey k (mem_of_mem_filterMap h') := | |
| m.inductionOn (fun _ _ => DHashMap.getKey_filterMap) h' | |
| @[grind =] | |
| theorem getKey!_filterMap [LawfulBEq α] [Inhabited α] | |
| {f : (a : α) → β a → Option (γ a)} {k : α} : | |
| (m.filterMap f).getKey! k = | |
| ((m.getKey? k).pfilter (fun x h' => | |
| (f x (m.get x (mem_of_getKey?_eq_some h'))).isSome)).get! := | |
| m.inductionOn fun _ => DHashMap.getKey!_filterMap | |
| @[grind =] | |
| theorem getKeyD_filterMap [LawfulBEq α] | |
| {f : (a : α) → β a → Option (γ a)} {k fallback : α} : | |
| (m.filterMap f).getKeyD k fallback = | |
| ((m.getKey? k).pfilter (fun x h' => | |
| (f x (m.get x (mem_of_getKey?_eq_some h'))).isSome)).getD fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_filterMap | |
| namespace Const | |
| variable {β : Type v} {γ : Type w} {m : ExtDHashMap α (fun _ => β)} | |
| theorem filterMap_eq_empty_iff [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} : | |
| m.filterMap f = ∅ ↔ ∀ k h, f (m.getKey k h) (get m k h) = none := | |
| isEmpty_iff.symm.trans <| m.inductionOn fun _ => DHashMap.Const.isEmpty_filterMap_iff | |
| @[grind =] | |
| theorem mem_filterMap [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Option γ} {k : α} : | |
| k ∈ m.filterMap f ↔ ∃ h, (f (m.getKey k h) (Const.get m k h)).isSome := | |
| m.inductionOn fun _ => DHashMap.Const.mem_filterMap | |
| theorem size_filterMap_le_size [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β → Option γ} : | |
| (m.filterMap f).size ≤ m.size := | |
| m.inductionOn fun _ => DHashMap.size_filterMap_le_size | |
| grind_pattern size_filterMap_le_size => (m.filterMap f).size | |
| theorem size_filterMap_eq_size_iff [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Option γ} : | |
| (m.filterMap f).size = m.size ↔ ∀ k h, (f (m.getKey k h) (Const.get m k h)).isSome := | |
| m.inductionOn fun _ => DHashMap.Const.size_filterMap_eq_size_iff | |
| @[simp] | |
| theorem get?_filterMap [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Option γ} {k : α} : | |
| Const.get? (m.filterMap f) k = (Const.get? m k).pbind (fun x h' => | |
| f (m.getKey k (mem_iff_isSome_get?.mpr (Option.isSome_of_eq_some h'))) x) := | |
| m.inductionOn fun _ => DHashMap.Const.get?_filterMap | |
| /-- Simpler variant of `get?_filterMap` when `LawfulBEq` is available. -/ | |
| @[grind =] | |
| theorem get?_filterMap' [LawfulBEq α] | |
| {f : α → β → Option γ} {k : α} : | |
| Const.get? (m.filterMap f) k = (Const.get? m k).bind (f k) := by | |
| simp [get?_filterMap] | |
| theorem get?_filterMap_of_getKey?_eq_some [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Option γ} {k k' : α} (h : m.getKey? k = some k') : | |
| Const.get? (m.filterMap f) k = (Const.get? m k).bind (f k') := | |
| m.inductionOn (fun _ h => DHashMap.Const.get?_filterMap_of_getKey?_eq_some h) h | |
| theorem isSome_apply_of_mem_filterMap [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Option γ} {k : α} : | |
| ∀ (h : k ∈ m.filterMap f), | |
| (f (m.getKey k (mem_of_mem_filterMap h)) | |
| (Const.get m k (mem_of_mem_filterMap h))).isSome := | |
| m.inductionOn fun _ => DHashMap.Const.isSome_apply_of_mem_filterMap | |
| @[simp] | |
| theorem get_filterMap [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Option γ} {k : α} {h} : | |
| Const.get (m.filterMap f) k h = | |
| (f (m.getKey k (mem_of_mem_filterMap h)) | |
| (Const.get m k (mem_of_mem_filterMap h))).get | |
| (isSome_apply_of_mem_filterMap h) := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_filterMap) h | |
| /-- Simpler variant of `get_filterMap` when `LawfulBEq` is available. -/ | |
| @[grind =] | |
| theorem get_filterMap' [LawfulBEq α] | |
| {f : α → β → Option γ} {k : α} {h} : | |
| Const.get (m.filterMap f) k h = (f k (Const.get m k (mem_of_mem_filterMap h))).get (by simpa using isSome_apply_of_mem_filterMap h) := by | |
| simp [get_filterMap] | |
| theorem get!_filterMap [EquivBEq α] [LawfulHashable α] [Inhabited γ] | |
| {f : α → β → Option γ} {k : α} : | |
| Const.get! (m.filterMap f) k = | |
| ((Const.get? m k).pbind (fun x h' => | |
| f (m.getKey k (mem_iff_isSome_get?.mpr (Option.isSome_of_eq_some h'))) x)).get! := | |
| m.inductionOn fun _ => DHashMap.Const.get!_filterMap | |
| /-- Simpler variant of `get!_filterMap` when `LawfulBEq` is available. -/ | |
| @[grind =] | |
| theorem get!_filterMap' [LawfulBEq α] [Inhabited γ] | |
| {f : α → β → Option γ} {k : α} : | |
| Const.get! (m.filterMap f) k = ((Const.get? m k).bind (f k)).get! := by | |
| simp [get!_filterMap] | |
| theorem get!_filterMap_of_getKey?_eq_some [EquivBEq α] [LawfulHashable α] [Inhabited γ] | |
| {f : α → β → Option γ} {k k' : α} (h : m.getKey? k = some k') : | |
| Const.get! (m.filterMap f) k = ((Const.get? m k).bind (f k')).get! := | |
| m.inductionOn (fun _ h => DHashMap.Const.get!_filterMap_of_getKey?_eq_some h) h | |
| theorem getD_filterMap [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Option γ} {k : α} {fallback : γ} : | |
| Const.getD (m.filterMap f) k fallback = | |
| ((Const.get? m k).pbind (fun x h' => | |
| f (m.getKey k (mem_iff_isSome_get?.mpr (Option.isSome_of_eq_some h'))) x)).getD fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_filterMap | |
| /-- Simpler variant of `getD_filterMap` when `LawfulBEq` is available. -/ | |
| @[grind =] | |
| theorem getD_filterMap' [LawfulBEq α] | |
| {f : α → β → Option γ} {k : α} {fallback : γ} : | |
| Const.getD (m.filterMap f) k fallback = ((Const.get? m k).bind (f k)).getD fallback := by | |
| simp [getD_filterMap] | |
| theorem getD_filterMap_of_getKey?_eq_some [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Option γ} {k k' : α} {fallback : γ} (h : m.getKey? k = some k') : | |
| Const.getD (m.filterMap f) k fallback = ((Const.get? m k).bind (f k')).getD fallback := | |
| m.inductionOn (fun _ h => DHashMap.Const.getD_filterMap_of_getKey?_eq_some h) h | |
| @[grind =] | |
| theorem getKey?_filterMap [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Option γ} {k : α} : | |
| (m.filterMap f).getKey? k = | |
| (m.getKey? k).pfilter (fun x h' => | |
| (f x (Const.get m x (mem_of_getKey?_eq_some h'))).isSome) := | |
| m.inductionOn fun _ => DHashMap.Const.getKey?_filterMap | |
| @[grind =] | |
| theorem getKey!_filterMap [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {f : α → β → Option γ} {k : α} : | |
| (m.filterMap f).getKey! k = | |
| ((m.getKey? k).pfilter (fun x h' => | |
| (f x (Const.get m x (mem_of_getKey?_eq_some h'))).isSome)).get! := | |
| m.inductionOn fun _ => DHashMap.Const.getKey!_filterMap | |
| @[grind =] | |
| theorem getKeyD_filterMap [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Option γ} {k fallback : α} : | |
| (m.filterMap f).getKeyD k fallback = | |
| ((m.getKey? k).pfilter (fun x h' => | |
| (f x (Const.get m x (mem_of_getKey?_eq_some h'))).isSome)).getD fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getKeyD_filterMap | |
| end Const | |
| end filterMap | |
| section filter | |
| theorem filterMap_eq_filter [EquivBEq α] [LawfulHashable α] {f : (a : α) → β a → Bool} : | |
| m.filterMap (fun k => Option.guard (fun v => f k v)) = m.filter f := | |
| m.inductionOn fun _ => sound DHashMap.filterMap_equiv_filter | |
| theorem filter_eq_empty_iff [LawfulBEq α] | |
| {f : (a : α) → β a → Bool} : | |
| m.filter f = ∅ ↔ ∀ k h, f k (m.get k h) = false := | |
| isEmpty_iff.symm.trans <| m.inductionOn fun _ => DHashMap.isEmpty_filter_iff | |
| theorem filter_key_eq_empty_iff [EquivBEq α] [LawfulHashable α] {f : α → Bool} : | |
| m.filter (fun a _ => f a) = ∅ ↔ ∀ k h, f (m.getKey k h) = false := | |
| isEmpty_iff.symm.trans <| m.inductionOn fun _ => DHashMap.isEmpty_filter_key_iff | |
| @[grind =] theorem contains_filter [LawfulBEq α] {f : (a : α) → β a → Bool} {k : α} : | |
| (m.filter f).contains k = (m.get? k).any (f k) := | |
| m.inductionOn fun _ => DHashMap.contains_filter | |
| @[grind =] theorem mem_filter [LawfulBEq α] {f : (a : α) → β a → Bool} {k : α} : | |
| k ∈ m.filter f ↔ ∃ h, f k (m.get k h) := | |
| m.inductionOn fun _ => DHashMap.mem_filter | |
| theorem mem_filter_key [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} : | |
| k ∈ m.filter (fun a _ => f a) ↔ ∃ h, f (m.getKey k h) := | |
| m.inductionOn fun _ => DHashMap.mem_filter_key | |
| theorem contains_of_contains_filter [EquivBEq α] [LawfulHashable α] {f : (a : α) → β a → Bool} {k : α} : | |
| (m.filter f).contains k = true → m.contains k = true := | |
| m.inductionOn fun _ => DHashMap.contains_of_contains_filter | |
| theorem mem_of_mem_filter [EquivBEq α] [LawfulHashable α] {f : (a : α) → β a → Bool} {k : α} : | |
| k ∈ (m.filter f) → k ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_of_mem_filter | |
| theorem size_filter_le_size [EquivBEq α] [LawfulHashable α] {f : (a : α) → β a → Bool} : | |
| (m.filter f).size ≤ m.size := | |
| m.inductionOn fun _ => DHashMap.size_filter_le_size | |
| grind_pattern size_filter_le_size => (m.filter f).size | |
| theorem size_filter_eq_size_iff [LawfulBEq α] {f : (a : α) → β a → Bool} : | |
| (m.filter f).size = m.size ↔ ∀ k h, f k (m.get k h) := | |
| m.inductionOn fun _ => DHashMap.size_filter_eq_size_iff | |
| theorem filter_eq_self_iff [LawfulBEq α] {f : (a : α) → β a → Bool} : | |
| m.filter f = m ↔ ∀ k h, f k (m.get k h) := | |
| m.inductionOn fun _ => Iff.trans ⟨exact, sound⟩ DHashMap.filter_equiv_self_iff | |
| theorem filter_key_equiv_self_iff [EquivBEq α] [LawfulHashable α] {f : (a : α) → Bool} : | |
| m.filter (fun k _ => f k) = m ↔ ∀ k h, f (m.getKey k h) := | |
| m.inductionOn fun _ => Iff.trans ⟨exact, sound⟩ DHashMap.filter_key_equiv_self_iff | |
| theorem size_filter_key_eq_size_iff [EquivBEq α] [LawfulHashable α] {f : α → Bool} : | |
| (m.filter fun k _ => f k).size = m.size ↔ ∀ k h, f (m.getKey k h) := | |
| m.inductionOn fun _ => DHashMap.size_filter_key_eq_size_iff | |
| @[simp, grind =] | |
| theorem get?_filter [LawfulBEq α] | |
| {f : (a : α) → β a → Bool} {k : α} : | |
| (m.filter f).get? k = (m.get? k).filter (f k) := | |
| m.inductionOn fun _ => DHashMap.get?_filter | |
| @[simp, grind =] | |
| theorem get_filter [LawfulBEq α] | |
| {f : (a : α) → β a → Bool} {k : α} {h'} : | |
| (m.filter f).get k h' = m.get k (mem_of_mem_filter h') := | |
| m.inductionOn (fun _ _ => DHashMap.get_filter) h' | |
| @[grind =] | |
| theorem get!_filter [LawfulBEq α] | |
| {f : (a : α) → β a → Bool} {k : α} [Inhabited (β k)] : | |
| (m.filter f).get! k = ((m.get? k).filter (f k)).get! := | |
| m.inductionOn fun _ => DHashMap.get!_filter | |
| @[grind =] | |
| theorem getD_filter [LawfulBEq α] | |
| {f : (a : α) → β a → Bool} {k : α} {fallback : β k} : | |
| (m.filter f).getD k fallback = ((m.get? k).filter (f k)).getD fallback := | |
| m.inductionOn fun _ => DHashMap.getD_filter | |
| @[grind =] | |
| theorem getKey?_filter [LawfulBEq α] | |
| {f : (a : α) → β a → Bool} {k : α} : | |
| (m.filter f).getKey? k = | |
| (m.getKey? k).pfilter (fun x h' => | |
| f x (m.get x (mem_of_getKey?_eq_some h'))) := | |
| m.inductionOn fun _ => DHashMap.getKey?_filter | |
| theorem getKey?_filter_key [EquivBEq α] [LawfulHashable α] | |
| {f : α → Bool} {k : α} : | |
| (m.filter fun k _ => f k).getKey? k = (m.getKey? k).filter f := | |
| m.inductionOn fun _ => DHashMap.getKey?_filter_key | |
| @[simp, grind =] | |
| theorem getKey_filter [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → Bool} {k : α} {h'} : | |
| (m.filter f).getKey k h' = m.getKey k (mem_of_mem_filter h') := | |
| m.inductionOn (fun _ _ => DHashMap.getKey_filter) h' | |
| @[grind =] | |
| theorem getKey!_filter [LawfulBEq α] [Inhabited α] | |
| {f : (a : α) → β a → Bool} {k : α} : | |
| (m.filter f).getKey! k = | |
| ((m.getKey? k).pfilter (fun x h' => | |
| f x (m.get x (mem_of_getKey?_eq_some h')))).get! := | |
| m.inductionOn fun _ => DHashMap.getKey!_filter | |
| theorem getKey!_filter_key [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {f : α → Bool} {k : α} : | |
| (m.filter fun k _ => f k).getKey! k = ((m.getKey? k).filter f).get! := | |
| m.inductionOn fun _ => DHashMap.getKey!_filter_key | |
| @[grind =] | |
| theorem getKeyD_filter [LawfulBEq α] | |
| {f : (a : α) → β a → Bool} {k fallback : α} : | |
| (m.filter f).getKeyD k fallback = | |
| ((m.getKey? k).pfilter (fun x h' => | |
| f x (m.get x (mem_of_getKey?_eq_some h')))).getD fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_filter | |
| theorem getKeyD_filter_key [EquivBEq α] [LawfulHashable α] | |
| {f : α → Bool} {k fallback : α} : | |
| (m.filter fun k _ => f k).getKeyD k fallback = ((m.getKey? k).filter f).getD fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_filter_key | |
| namespace Const | |
| variable {β : Type v} {γ : Type w} {m : ExtDHashMap α (fun _ => β)} | |
| theorem filter_eq_empty_iff [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} : | |
| m.filter f = ∅ ↔ ∀ k h, f (m.getKey k h) (Const.get m k h) = false := | |
| isEmpty_iff.symm.trans <| m.inductionOn fun _ => DHashMap.Const.isEmpty_filter_iff | |
| @[grind =] theorem mem_filter [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Bool} {k : α} : | |
| k ∈ m.filter f ↔ ∃ (h' : k ∈ m), | |
| f (m.getKey k h') (Const.get m k h') := | |
| m.inductionOn fun _ => DHashMap.Const.mem_filter | |
| theorem size_filter_le_size [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Bool} : | |
| (m.filter f).size ≤ m.size := | |
| m.inductionOn fun _ => DHashMap.Const.size_filter_le_size | |
| grind_pattern size_filter_le_size => (m.filter f).size | |
| theorem size_filter_eq_size_iff [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Bool} : | |
| (m.filter f).size = m.size ↔ ∀ (a : α) (h : a ∈ m), | |
| f (m.getKey a h) (Const.get m a h) := | |
| m.inductionOn fun _ => DHashMap.Const.size_filter_eq_size_iff | |
| theorem filter_eq_self_iff [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} : | |
| m.filter f = m ↔ ∀ k h, f (m.getKey k h) (Const.get m k h) := | |
| m.inductionOn fun _ => Iff.trans ⟨exact, sound⟩ DHashMap.Const.filter_equiv_self_iff | |
| theorem get?_filter [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Bool} {k : α} : | |
| Const.get? (m.filter f) k = (Const.get? m k).pfilter (fun x h' => | |
| f (m.getKey k (mem_iff_isSome_get?.mpr (Option.isSome_of_eq_some h'))) x) := | |
| m.inductionOn fun _ => DHashMap.Const.get?_filter | |
| /-- Simpler variant of `get?_filter` when `LawfulBEq` is available. -/ | |
| @[grind =] | |
| theorem get?_filter' [LawfulBEq α] | |
| {f : α → β → Bool} {k : α} : | |
| Const.get? (m.filter f) k = (Const.get? m k).filter (f k) := by | |
| simp [get?_filter] | |
| theorem get?_filter_of_getKey?_eq_some [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Bool} {k k' : α} : | |
| m.getKey? k = some k' → | |
| Const.get? (m.filter f) k = (Const.get? m k).filter (fun x => f k' x) := | |
| m.inductionOn fun _ => DHashMap.Const.get?_filter_of_getKey?_eq_some | |
| @[simp, grind =] | |
| theorem get_filter [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Bool} {k : α} {h'} : | |
| Const.get (m.filter f) k h' = Const.get m k (mem_of_mem_filter h') := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_filter) h' | |
| theorem get!_filter [EquivBEq α] [LawfulHashable α] [Inhabited β] | |
| {f : α → β → Bool} {k : α} : | |
| Const.get! (m.filter f) k = | |
| ((Const.get? m k).pfilter (fun x h' => | |
| f (m.getKey k (mem_iff_isSome_get?.mpr (Option.isSome_of_eq_some h'))) x)).get! := | |
| m.inductionOn fun _ => DHashMap.Const.get!_filter | |
| /-- Simpler variant of `get!_filter` when `LawfulBEq` is available. -/ | |
| @[grind =] | |
| theorem get!_filter' [LawfulBEq α] [Inhabited β] | |
| {f : α → β → Bool} {k : α} : | |
| Const.get! (m.filter f) k = ((Const.get? m k).filter (f k)).get! := by | |
| simp [get!_filter] | |
| theorem get!_filter_of_getKey?_eq_some [EquivBEq α] [LawfulHashable α] [Inhabited β] | |
| {f : α → β → Bool} {k k' : α} : | |
| m.getKey? k = some k' → | |
| Const.get! (m.filter f) k = ((Const.get? m k).filter (fun x => f k' x)).get! := | |
| m.inductionOn fun _ => DHashMap.Const.get!_filter_of_getKey?_eq_some | |
| theorem getD_filter [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Bool} {k : α} {fallback : β} : | |
| Const.getD (m.filter f) k fallback = ((Const.get? m k).pfilter (fun x h' => | |
| f (m.getKey k (mem_iff_isSome_get?.mpr (Option.isSome_of_eq_some h'))) x)).getD fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_filter | |
| /-- Simpler variant of `getD_filter` when `LawfulBEq` is available. -/ | |
| @[grind =] | |
| theorem getD_filter' [LawfulBEq α] | |
| {f : α → β → Bool} {k : α} {fallback : β} : | |
| Const.getD (m.filter f) k fallback = ((Const.get? m k).filter (f k)).getD fallback := by | |
| simp [getD_filter] | |
| theorem getD_filter_of_getKey?_eq_some [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Bool} {k k' : α} {fallback : β} : | |
| m.getKey? k = some k' → | |
| Const.getD (m.filter f) k fallback = | |
| ((Const.get? m k).filter (fun x => f k' x)).getD fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_filter_of_getKey?_eq_some | |
| @[grind =] theorem getKey?_filter [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Bool} {k : α} : | |
| (m.filter f).getKey? k = | |
| (m.getKey? k).pfilter (fun x h' => | |
| (f x (Const.get m x (mem_of_getKey?_eq_some h')))) := | |
| m.inductionOn fun _ => DHashMap.Const.getKey?_filter | |
| @[grind =] theorem getKey!_filter [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {f : α → β → Bool} {k : α} : | |
| (m.filter f).getKey! k = | |
| ((m.getKey? k).pfilter (fun x h' => | |
| (f x (Const.get m x (mem_of_getKey?_eq_some h'))))).get! := | |
| m.inductionOn fun _ => DHashMap.Const.getKey!_filter | |
| @[grind =] theorem getKeyD_filter [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → Bool} {k fallback : α} : | |
| (m.filter f).getKeyD k fallback = | |
| ((m.getKey? k).pfilter (fun x h' => | |
| (f x (Const.get m x (mem_of_getKey?_eq_some h'))))).getD fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getKeyD_filter | |
| end Const | |
| end filter | |
| section map | |
| variable {γ : α → Type w} {δ : α → Type w'} | |
| @[simp] | |
| theorem map_id_fun [EquivBEq α] [LawfulHashable α] : m.map (fun _ v => v) = m := | |
| m.inductionOn fun _ => sound DHashMap.map_id_equiv | |
| @[simp] | |
| theorem map_map [EquivBEq α] [LawfulHashable α] {f : (a : α) → β a → γ a} {g : (a : α) → γ a → δ a} : | |
| (m.map f).map g = m.map fun k v => g k (f k v) := | |
| m.inductionOn fun _ => sound DHashMap.map_map_equiv | |
| theorem filterMap_eq_map [EquivBEq α] [LawfulHashable α] {f : (a : α) → β a → γ a} : | |
| (m.filterMap (fun k v => some (f k v))) = m.map f := | |
| m.inductionOn fun _ => sound DHashMap.filterMap_equiv_map | |
| @[simp] | |
| theorem map_eq_empty_iff [EquivBEq α] [LawfulHashable α] {f : (a : α) → β a → γ a} : | |
| m.map f = ∅ ↔ m = ∅ := by | |
| simp only [← isEmpty_iff, Bool.coe_iff_coe] | |
| exact m.inductionOn fun _ => DHashMap.isEmpty_map | |
| @[grind =] theorem contains_map [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → γ a} {k : α} : | |
| (m.map f).contains k = m.contains k := | |
| m.inductionOn fun _ => DHashMap.contains_map | |
| theorem contains_of_contains_map [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → γ a} {k : α} : | |
| (m.map f).contains k = true → m.contains k = true := | |
| m.inductionOn fun _ => DHashMap.contains_of_contains_map | |
| @[simp, grind =] | |
| theorem mem_map [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → γ a} {k : α} : | |
| k ∈ m.map f ↔ k ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_map | |
| theorem mem_of_mem_map [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → γ a} {k : α} : | |
| k ∈ m.map f → k ∈ m := | |
| m.inductionOn fun _ => DHashMap.mem_of_mem_map | |
| @[simp, grind =] | |
| theorem size_map [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → γ a} : | |
| (m.map f).size = m.size := | |
| m.inductionOn fun _ => DHashMap.size_map | |
| @[simp, grind =] | |
| theorem get?_map [LawfulBEq α] | |
| {f : (a : α) → β a → γ a} {k : α} : | |
| (m.map f).get? k = (m.get? k).map (f k) := | |
| m.inductionOn fun _ => DHashMap.get?_map | |
| @[simp, grind =] | |
| theorem get_map [LawfulBEq α] | |
| {f : (a : α) → β a → γ a} {k : α} {h'} : | |
| (m.map f).get k h' = f k (m.get k (mem_of_mem_map h')) := | |
| m.inductionOn (fun _ _ => DHashMap.get_map) h' | |
| @[grind =] | |
| theorem get!_map [LawfulBEq α] | |
| {f : (a : α) → β a → γ a} {k : α} [Inhabited (γ k)] : | |
| (m.map f).get! k = ((m.get? k).map (f k)).get! := | |
| m.inductionOn fun _ => DHashMap.get!_map | |
| @[grind =] | |
| theorem getD_map [LawfulBEq α] | |
| {f : (a : α) → β a → γ a} {k : α} {fallback : γ k} : | |
| (m.map f).getD k fallback = ((m.get? k).map (f k)).getD fallback := | |
| m.inductionOn fun _ => DHashMap.getD_map | |
| @[simp, grind =] | |
| theorem getKey?_map [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → γ a} {k : α} : | |
| (m.map f).getKey? k = m.getKey? k := | |
| m.inductionOn fun _ => DHashMap.getKey?_map | |
| @[simp, grind =] | |
| theorem getKey_map [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → γ a} {k : α} {h'} : | |
| (m.map f).getKey k h' = m.getKey k (mem_of_mem_map h') := | |
| m.inductionOn (fun _ _ => DHashMap.getKey_map) h' | |
| @[simp, grind =] | |
| theorem getKey!_map [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {f : (a : α) → β a → γ a} {k : α} : | |
| (m.map f).getKey! k = m.getKey! k := | |
| m.inductionOn fun _ => DHashMap.getKey!_map | |
| @[simp, grind =] | |
| theorem getKeyD_map [EquivBEq α] [LawfulHashable α] | |
| {f : (a : α) → β a → γ a} {k fallback : α} : | |
| (m.map f).getKeyD k fallback = m.getKeyD k fallback := | |
| m.inductionOn fun _ => DHashMap.getKeyD_map | |
| namespace Const | |
| variable {β : Type v} {γ : Type w} {m : ExtDHashMap α fun _ => β} | |
| @[simp, grind =] | |
| theorem get?_map [LawfulBEq α] | |
| {f : α → β → γ} {k : α} : | |
| Const.get? (m.map f) k = (Const.get? m k).map (f k) := | |
| m.inductionOn fun _ => DHashMap.Const.get?_map | |
| /-- Variant of `get?_map` that holds with `EquivBEq` (i.e. without `LawfulBEq`). -/ | |
| @[simp (low)] | |
| theorem get?_map' [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → γ} {k : α} : | |
| Const.get? (m.map f) k = (Const.get? m k).pmap (fun v h' => f (m.getKey k h') v) | |
| (fun _ h' => mem_iff_isSome_get?.mpr (Option.isSome_of_eq_some h')) := | |
| m.inductionOn fun _ => DHashMap.Const.get?_map' | |
| theorem get?_map_of_getKey?_eq_some [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → γ} {k k' : α} (h : m.getKey? k = some k') : | |
| Const.get? (m.map f) k = (Const.get? m k).map (f k') := | |
| m.inductionOn (fun _ h => DHashMap.Const.get?_map_of_getKey?_eq_some h) h | |
| @[simp, grind =] | |
| theorem get_map [LawfulBEq α] | |
| {f : α → β → γ} {k : α} {h'} : | |
| Const.get (m.map f) k h' = f k (Const.get m k (mem_of_mem_map h')) := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_map) h' | |
| /-- Variant of `get_map` that holds with `EquivBEq` (i.e. without `LawfulBEq`). -/ | |
| @[simp (low)] | |
| theorem get_map' [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → γ} {k : α} {h'} : | |
| Const.get (m.map f) k h' = | |
| f (m.getKey k (mem_of_mem_map h')) (Const.get m k (mem_of_mem_map h')) := | |
| m.inductionOn (fun _ _ => DHashMap.Const.get_map') h' | |
| @[grind =] theorem get!_map [LawfulBEq α] [Inhabited γ] | |
| {f : α → β → γ} {k : α} : | |
| Const.get! (m.map f) k = ((Const.get? m k).map (f k)).get! := | |
| m.inductionOn fun _ => DHashMap.Const.get!_map | |
| /-- Variant of `get!_map` that holds with `EquivBEq` (i.e. without `LawfulBEq`). -/ | |
| theorem get!_map' [EquivBEq α] [LawfulHashable α] [Inhabited γ] | |
| {f : α → β → γ} {k : α} : | |
| Const.get! (m.map f) k = | |
| ((get? m k).pmap (fun v h => f (m.getKey k h) v) | |
| (fun _ h' => mem_iff_isSome_get?.mpr (Option.isSome_of_mem h'))).get! := | |
| m.inductionOn fun _ => DHashMap.Const.get!_map' | |
| theorem get!_map_of_getKey?_eq_some [EquivBEq α] [LawfulHashable α] [Inhabited γ] | |
| {f : α → β → γ} {k k' : α} (h : m.getKey? k = some k') : | |
| Const.get! (m.map f) k = ((Const.get? m k).map (f k')).get! := | |
| m.inductionOn (fun _ h => DHashMap.Const.get!_map_of_getKey?_eq_some h) h | |
| @[grind =] theorem getD_map [LawfulBEq α] | |
| {f : α → β → γ} {k : α} {fallback : γ} : | |
| Const.getD (m.map f) k fallback = ((Const.get? m k).map (f k)).getD fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_map | |
| /-- Variant of `getD_map` that holds with `EquivBEq` (i.e. without `LawfulBEq`). -/ | |
| theorem getD_map' [EquivBEq α] [LawfulHashable α] | |
| {f : α → β → γ} {k : α} {fallback : γ} : | |
| Const.getD (m.map f) k fallback = | |
| ((get? m k).pmap (fun v h => f (m.getKey k h) v) | |
| (fun _ h' => mem_iff_isSome_get?.mpr (Option.isSome_of_eq_some h'))).getD fallback := | |
| m.inductionOn fun _ => DHashMap.Const.getD_map' | |
| theorem getD_map_of_getKey?_eq_some [EquivBEq α] [LawfulHashable α] [Inhabited γ] | |
| {f : α → β → γ} {k k' : α} {fallback : γ} (h : m.getKey? k = some k') : | |
| Const.getD (m.map f) k fallback = ((Const.get? m k).map (f k')).getD fallback := | |
| m.inductionOn (fun _ h => DHashMap.Const.getD_map_of_getKey?_eq_some h) h | |
| end Const | |
| end map | |
| end Std.ExtDHashMap |