blob: 254694ed065f99b7d46e899dc0ab5b895144e9f5 [file]
/-
Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Markus Himmel
-/
module
prelude
public import Std.Data.DHashMap.Basic
import all Std.Data.DHashMap.Basic
public section
/-!
This is an internal implementation file of the hash map. Users of the hash map should not rely on
the contents of this file.
File contents: relating operations on `Raw` to operations on `Raw₀`
-/
set_option linter.missingDocs true
set_option autoImplicit false
universe u v w
variable {α : Type u} {β : α → Type v} {γ : Type w} {δ : α → Type w}
namespace Std.DHashMap.Internal
namespace Raw
-- TODO: the next two lemmas need to be renamed, but there is a bootstrapping obstacle.
theorem empty_eq {c : Nat} : (Raw.emptyWithCapacity c : Raw α β) = (Raw₀.emptyWithCapacity c).1 := (rfl)
theorem emptyc_eq : (∅ : Raw α β) = Raw₀.emptyWithCapacity.1 := (rfl)
theorem insert_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {a : α} {b : β a} :
m.insert a b = (Raw₀.insert ⟨m, h.size_buckets_pos⟩ a b).1 := by
simp [Raw.insert, h.size_buckets_pos]
theorem insertIfNew_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {a : α} {b : β a} :
m.insertIfNew a b = (Raw₀.insertIfNew ⟨m, h.size_buckets_pos⟩ a b).1 := by
simp [Raw.insertIfNew, h.size_buckets_pos]
theorem containsThenInsert_snd_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {a : α} {b : β a} :
(m.containsThenInsert a b).2 = (Raw₀.containsThenInsert ⟨m, h.size_buckets_pos⟩ a b).2.1 := by
simp [Raw.containsThenInsert, h.size_buckets_pos]
theorem containsThenInsert_fst_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {a : α} {b : β a} :
(m.containsThenInsert a b).1 = (Raw₀.containsThenInsert ⟨m, h.size_buckets_pos⟩ a b).1 := by
simp [Raw.containsThenInsert, h.size_buckets_pos]
theorem containsThenInsertIfNew_snd_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {a : α}
{b : β a} : (m.containsThenInsertIfNew a b).2 =
(Raw₀.containsThenInsertIfNew ⟨m, h.size_buckets_pos⟩ a b).2.1 := by
simp [Raw.containsThenInsertIfNew, h.size_buckets_pos]
theorem containsThenInsertIfNew_fst_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {a : α}
{b : β a} : (m.containsThenInsertIfNew a b).1 =
(Raw₀.containsThenInsertIfNew ⟨m, h.size_buckets_pos⟩ a b).1 := by
simp [Raw.containsThenInsertIfNew, h.size_buckets_pos]
theorem getThenInsertIfNew?_snd_eq [BEq α] [Hashable α] [LawfulBEq α] {m : Raw α β} (h : m.WF)
{a : α} {b : β a} : (m.getThenInsertIfNew? a b).2 =
(Raw₀.getThenInsertIfNew? ⟨m, h.size_buckets_pos⟩ a b).2.1 := by
simp [Raw.getThenInsertIfNew?, h.size_buckets_pos]
theorem getThenInsertIfNew?_fst_eq [BEq α] [Hashable α] [LawfulBEq α] {m : Raw α β} (h : m.WF)
{a : α} {b : β a} : (m.getThenInsertIfNew? a b).1 =
(Raw₀.getThenInsertIfNew? ⟨m, h.size_buckets_pos⟩ a b).1 := by
simp [Raw.getThenInsertIfNew?, h.size_buckets_pos]
theorem get?_eq [BEq α] [Hashable α] [LawfulBEq α] {m : Raw α β} (h : m.WF) {a : α} :
m.get? a = Raw₀.get? ⟨m, h.size_buckets_pos⟩ a := by
simp [Raw.get?, h.size_buckets_pos]
theorem contains_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {a : α} :
m.contains a = Raw₀.contains ⟨m, h.size_buckets_pos⟩ a := by
simp [Raw.contains, h.size_buckets_pos]
theorem get_eq [BEq α] [Hashable α] [LawfulBEq α] {m : Raw α β} {a : α} {h : a ∈ m} :
m.get a h = Raw₀.get ⟨m, by change dite .. = true at h; split at h <;> simp_all⟩ a
(by change dite .. = true at h; split at h <;> simp_all) := (rfl)
theorem getD_eq [BEq α] [Hashable α] [LawfulBEq α] {m : Raw α β} (h : m.WF) {a : α}
{fallback : β a} : m.getD a fallback = Raw₀.getD ⟨m, h.size_buckets_pos⟩ a fallback := by
simp [Raw.getD, h.size_buckets_pos]
theorem get!_eq [BEq α] [Hashable α] [LawfulBEq α] {m : Raw α β} (h : m.WF) {a : α}
[Inhabited (β a)] : m.get! a = Raw₀.get! ⟨m, h.size_buckets_pos⟩ a := by
simp [Raw.get!, h.size_buckets_pos]
theorem getKey?_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {a : α} :
m.getKey? a = Raw₀.getKey? ⟨m, h.size_buckets_pos⟩ a := by
simp [Raw.getKey?, h.size_buckets_pos]
theorem getKey_eq [BEq α] [Hashable α] {m : Raw α β} {a : α} {h : a ∈ m} :
m.getKey a h = Raw₀.getKey ⟨m, by change dite .. = true at h; split at h <;> simp_all⟩ a
(by change dite .. = true at h; split at h <;> simp_all) := (rfl)
theorem getKeyD_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {a fallback : α} :
m.getKeyD a fallback = Raw₀.getKeyD ⟨m, h.size_buckets_pos⟩ a fallback := by
simp [Raw.getKeyD, h.size_buckets_pos]
theorem getKey!_eq [BEq α] [Hashable α] [Inhabited α] {m : Raw α β} (h : m.WF) {a : α} :
m.getKey! a = Raw₀.getKey! ⟨m, h.size_buckets_pos⟩ a := by
simp [Raw.getKey!, h.size_buckets_pos]
theorem erase_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {a : α} :
m.erase a = Raw₀.erase ⟨m, h.size_buckets_pos⟩ a := by
simp [Raw.erase, h.size_buckets_pos]
theorem filterMap_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF)
{f : (a : α) → β a → Option (δ a)} : m.filterMap f =
Raw₀.filterMap f ⟨m, h.size_buckets_pos⟩ := by
simp [Raw.filterMap, h.size_buckets_pos]
theorem map_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {f : (a : α) → β a → δ a} :
m.map f = Raw₀.map f ⟨m, h.size_buckets_pos⟩ := by
simp [Raw.map, h.size_buckets_pos]
theorem filter_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {f : (a : α) → β a → Bool} :
m.filter f = Raw₀.filter f ⟨m, h.size_buckets_pos⟩ := by
simp [Raw.filter, h.size_buckets_pos]
theorem insertMany_eq [BEq α] [Hashable α] {m : Raw α β} (h : m.WF) {ρ : Type w} [ForIn Id ρ ((a : α) × β a)] {l : ρ} :
m.insertMany l = Raw₀.insertMany ⟨m, h.size_buckets_pos⟩ l := by
simp [Raw.insertMany, h.size_buckets_pos]
theorem ofList_eq [BEq α] [Hashable α] {l : List ((a : α) × β a)} :
Raw.ofList l = Raw₀.insertMany Raw₀.emptyWithCapacity l := by
simp only [Raw.ofList, Raw.insertMany, (Raw.WF.empty).size_buckets_pos ∅, ↓reduceDIte]
congr
theorem ofArray_eq [BEq α] [Hashable α] {a : Array ((a : α) × β a)} :
Raw.ofArray a = Raw₀.insertMany Raw₀.emptyWithCapacity a := by
simp only [Raw.ofArray, Raw.insertMany, (Raw.WF.empty).size_buckets_pos ∅, ↓reduceDIte]
congr
theorem alter_eq [BEq α] [LawfulBEq α] [Hashable α] {m : Raw α β} (h : m.WF) {k : α} {f : Option (β k) → Option (β k)} :
m.alter k f = Raw₀.alter ⟨m, h.size_buckets_pos⟩ k f := by
simp [Raw.alter, h.size_buckets_pos]
theorem modify_eq [BEq α] [LawfulBEq α] [Hashable α] {m : Raw α β} (h : m.WF) {k : α} {f : β k → β k} :
m.modify k f = Raw₀.modify ⟨m, h.size_buckets_pos⟩ k f := by
simp [Raw.modify, h.size_buckets_pos]
theorem union_eq [BEq α] [Hashable α] {m₁ m₂ : Raw α β} (h₁ : m₁.WF) (h₂ : m₂.WF) :
m₁.union m₂ = Raw₀.union ⟨m₁, h₁.size_buckets_pos⟩ ⟨m₂, h₂.size_buckets_pos⟩ := by
simp [Raw.union, h₁.size_buckets_pos, h₂.size_buckets_pos]
theorem inter_eq [BEq α] [Hashable α] {m₁ m₂ : Raw α β} (h₁ : m₁.WF) (h₂ : m₂.WF) :
m₁.inter m₂ = Raw₀.inter ⟨m₁, h₁.size_buckets_pos⟩ ⟨m₂, h₂.size_buckets_pos⟩ := by
simp [Raw.inter, h₁.size_buckets_pos, h₂.size_buckets_pos]
theorem beq_eq [BEq α] [Hashable α] [LawfulBEq α] [∀ k, BEq (β k)] {m₁ m₂ : Raw α β} (h₁ : m₁.WF) (h₂ : m₂.WF) :
m₁.beq m₂ = Raw₀.beq ⟨m₁, h₁.size_buckets_pos⟩ ⟨m₂, h₂.size_buckets_pos⟩ := by
simp [Raw.beq, h₁.size_buckets_pos, h₂.size_buckets_pos]
theorem Const.beq_eq {β : Type v} [BEq α] [Hashable α] [BEq β] {m₁ m₂ : Raw α (fun _ => β)} (h₁ : m₁.WF) (h₂ : m₂.WF) :
Raw.Const.beq m₁ m₂ = Raw₀.Const.beq ⟨m₁, h₁.size_buckets_pos⟩ ⟨m₂, h₂.size_buckets_pos⟩ := by
simp [Raw.Const.beq, h₁.size_buckets_pos, h₂.size_buckets_pos]
theorem diff_eq [BEq α] [Hashable α] {m₁ m₂ : Raw α β} (h₁ : m₁.WF) (h₂ : m₂.WF) :
m₁.diff m₂ = Raw₀.diff ⟨m₁, h₁.size_buckets_pos⟩ ⟨m₂, h₂.size_buckets_pos⟩ := by
simp [Raw.diff, h₁.size_buckets_pos, h₂.size_buckets_pos]
section
variable {β : Type v}
theorem Const.insertMany_eq [BEq α] [Hashable α] {m : Raw α (fun _ => β)} (h : m.WF) {ρ : Type w} [ForIn Id ρ (α × β)] {l : ρ} :
Raw.Const.insertMany m l = Raw₀.Const.insertMany ⟨m, h.size_buckets_pos⟩ l := by
simp [Raw.Const.insertMany, h.size_buckets_pos]
theorem Const.ofList_eq [BEq α] [Hashable α] {l : List (α × β)} :
Raw.Const.ofList l = Raw₀.Const.insertMany Raw₀.emptyWithCapacity l := by
simp only [Raw.Const.ofList, Raw.Const.insertMany, (Raw.WF.empty).size_buckets_pos ∅, ↓reduceDIte]
congr
theorem Const.ofArray_eq [BEq α] [Hashable α] {a : Array (α × β)} :
Raw.Const.ofArray a = Raw₀.Const.insertMany Raw₀.emptyWithCapacity a := by
simp only [Raw.Const.ofArray, Raw.Const.insertMany, (Raw.WF.empty).size_buckets_pos ∅, ↓reduceDIte]
congr
theorem Const.insertManyIfNewUnit_eq {ρ : Type w} [ForIn Id ρ α] [BEq α] [Hashable α]
{m : Raw α (fun _ => Unit)} {l : ρ} (h : m.WF):
Raw.Const.insertManyIfNewUnit m l = Raw₀.Const.insertManyIfNewUnit ⟨m, h.size_buckets_pos⟩ l := by
simp [Raw.Const.insertManyIfNewUnit, h.size_buckets_pos]
theorem Const.unitOfList_eq [BEq α] [Hashable α] {l : List α} :
Raw.Const.unitOfList l = Raw₀.Const.insertManyIfNewUnit Raw₀.emptyWithCapacity l := by
simp only [Raw.Const.unitOfList, Raw.Const.insertManyIfNewUnit, (Raw.WF.empty).size_buckets_pos ∅,
↓reduceDIte]
congr
theorem Const.unitOfArray_eq [BEq α] [Hashable α] {a : Array α} :
Raw.Const.unitOfArray a = Raw₀.Const.insertManyIfNewUnit Raw₀.emptyWithCapacity a := by
simp only [Raw.Const.unitOfArray, Raw.Const.insertManyIfNewUnit, (Raw.WF.empty).size_buckets_pos ∅,
↓reduceDIte]
congr
theorem Const.get?_eq [BEq α] [Hashable α] {m : Raw α (fun _ => β)} (h : m.WF) {a : α} :
Raw.Const.get? m a = Raw₀.Const.get? ⟨m, h.size_buckets_pos⟩ a := by
simp [Raw.Const.get?, h.size_buckets_pos]
theorem Const.get_eq [BEq α] [Hashable α] {m : Raw α (fun _ => β)} {a : α} {h : a ∈ m} :
Raw.Const.get m a h = Raw₀.Const.get
⟨m, by change dite .. = true at h; split at h <;> simp_all⟩ a
(by change dite .. = true at h; split at h <;> simp_all) :=
(rfl)
theorem Const.getD_eq [BEq α] [Hashable α] {m : Raw α (fun _ => β)} (h : m.WF) {a : α}
{fallback : β} : Raw.Const.getD m a fallback =
Raw₀.Const.getD ⟨m, h.size_buckets_pos⟩ a fallback := by
simp [Raw.Const.getD, h.size_buckets_pos]
theorem Const.get!_eq [BEq α] [Hashable α] [Inhabited β] {m : Raw α (fun _ => β)} (h : m.WF)
{a : α} : Raw.Const.get! m a = Raw₀.Const.get! ⟨m, h.size_buckets_pos⟩ a := by
simp [Raw.Const.get!, h.size_buckets_pos]
theorem Const.getThenInsertIfNew?_snd_eq [BEq α] [Hashable α] {m : Raw α (fun _ => β)} (h : m.WF)
{a : α} {b : β} : (Raw.Const.getThenInsertIfNew? m a b).2 =
(Raw₀.Const.getThenInsertIfNew? ⟨m, h.size_buckets_pos⟩ a b).2.1 := by
simp [Raw.Const.getThenInsertIfNew?, h.size_buckets_pos]
theorem Const.getThenInsertIfNew?_fst_eq [BEq α] [Hashable α] {m : Raw α (fun _ => β)} (h : m.WF)
{a : α} {b : β} : (Raw.Const.getThenInsertIfNew? m a b).1 =
(Raw₀.Const.getThenInsertIfNew? ⟨m, h.size_buckets_pos⟩ a b).1 := by
simp [Raw.Const.getThenInsertIfNew?, h.size_buckets_pos]
theorem Const.alter_eq [BEq α] [EquivBEq α] [Hashable α] {m : Raw α (fun _ => β)} (h : m.WF) {k : α} {f : Option β → Option β} :
Raw.Const.alter m k f = Raw₀.Const.alter ⟨m, h.size_buckets_pos⟩ k f := by
simp [Raw.Const.alter, h.size_buckets_pos]
theorem Const.modify_eq [BEq α] [EquivBEq α] [Hashable α] {m : Raw α (fun _ => β)} (h : m.WF) {k : α} {f : β → β} :
Raw.Const.modify m k f = Raw₀.Const.modify ⟨m, h.size_buckets_pos⟩ k f := by
simp [Raw.Const.modify, h.size_buckets_pos]
end
end Raw
end Std.DHashMap.Internal