blob: bcc27616c9db2cee0acd5ccadb5f636d8624260f [file]
/-
Copyright (c) 2018 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Author: Leonardo de Moura
-/
prelude
import Init.Data.Array.Basic
import Init.Data.AssocList
import Init.Data.Option.Basic
import Init.Data.Hashable
universes u v w
def HashMapBucket (α : Type u) (β : Type v) :=
{ b : Array (AssocList α β) // b.size > 0 }
def HashMapBucket.update {α : Type u} {β : Type v} (data : HashMapBucket α β) (i : USize) (d : AssocList α β) (h : i.toNat < data.val.size) : HashMapBucket α β :=
⟨ data.val.uset i d h,
transRelRight Greater (Array.szFSetEq data.val ⟨USize.toNat i, h⟩ d) data.property ⟩
structure HashMapImp (α : Type u) (β : Type v) :=
(size : Nat)
(buckets : HashMapBucket α β)
def mkHashMapImp {α : Type u} {β : Type v} (nbuckets := 8) : HashMapImp α β :=
let n := if nbuckets = 0 then 8 else nbuckets;
{ size := 0,
buckets :=
⟨ mkArray n AssocList.nil,
have p₁ : (mkArray n (@AssocList.nil α β)).size = n from Array.szMkArrayEq _ _;
have p₂ : n = if nbuckets = 0 then 8 else nbuckets from rfl;
have p₃ : (if nbuckets = 0 then 8 else nbuckets) > 0 from
match nbuckets with
| 0 => Nat.zeroLtSucc _
| Nat.succ x => Nat.zeroLtSucc _;
transRelRight Greater (Eq.trans p₁ p₂) p₃ ⟩ }
namespace HashMapImp
variables {α : Type u} {β : Type v}
def mkIdx {n : Nat} (h : n > 0) (u : USize) : { u : USize // u.toNat < n } :=
⟨u %ₙ n, USize.modnLt _ h⟩
@[inline] def reinsertAux (hashFn : α → USize) (data : HashMapBucket α β) (a : α) (b : β) : HashMapBucket α β :=
let ⟨i, h⟩ := mkIdx data.property (hashFn a);
data.update i (AssocList.cons a b (data.val.uget i h)) h
@[inline] def foldBucketsM {δ : Type w} {m : Type w → Type w} [Monad m] (data : HashMapBucket α β) (d : δ) (f : δ → α → β → m δ) : m δ :=
data.val.foldlM (fun d b => b.foldlM f d) d
@[inline] def foldBuckets {δ : Type w} (data : HashMapBucket α β) (d : δ) (f : δ → α → β → δ) : δ :=
Id.run $ foldBucketsM data d f
@[inline] def foldM {δ : Type w} {m : Type w → Type w} [Monad m] (f : δ → α → β → m δ) (d : δ) (h : HashMapImp α β) : m δ :=
foldBucketsM h.buckets d f
@[inline] def fold {δ : Type w} (f : δ → α → β → δ) (d : δ) (m : HashMapImp α β) : δ :=
foldBuckets m.buckets d f
def findEntry? [HasBeq α] [Hashable α] (m : HashMapImp α β) (a : α) : Option (α × β) :=
match m with
| ⟨_, buckets⟩ =>
let ⟨i, h⟩ := mkIdx buckets.property (hash a);
(buckets.val.uget i h).findEntry? a
def find? [HasBeq α] [Hashable α] (m : HashMapImp α β) (a : α) : Option β :=
match m with
| ⟨_, buckets⟩ =>
let ⟨i, h⟩ := mkIdx buckets.property (hash a);
(buckets.val.uget i h).find? a
def contains [HasBeq α] [Hashable α] (m : HashMapImp α β) (a : α) : Bool :=
match m with
| ⟨_, buckets⟩ =>
let ⟨i, h⟩ := mkIdx buckets.property (hash a);
(buckets.val.uget i h).contains a
-- TODO: remove `partial` by using well-founded recursion
partial def moveEntries [Hashable α] : Nat → Array (AssocList α β) → HashMapBucket α β → HashMapBucket α β
| i, source, target =>
if h : i < source.size then
let idx : Fin source.size := ⟨i, h⟩;
let es : AssocList α β := source.get idx;
-- We remove `es` from `source` to make sure we can reuse its memory cells when performing es.foldl
let source := source.set idx AssocList.nil;
let target := es.foldl (reinsertAux hash) target;
moveEntries (i+1) source target
else target
def expand [Hashable α] (size : Nat) (buckets : HashMapBucket α β) : HashMapImp α β :=
let nbuckets := buckets.val.size * 2;
have aux₁ : nbuckets > 0 from Nat.mulPos buckets.property (Nat.zeroLtBit0 Nat.oneNeZero);
have aux₂ : (mkArray nbuckets (@AssocList.nil α β)).size = nbuckets from Array.szMkArrayEq _ _;
let new_buckets : HashMapBucket α β := ⟨mkArray nbuckets AssocList.nil, aux₂.symm ▸ aux₁⟩;
{ size := size,
buckets := moveEntries 0 buckets.val new_buckets }
def insert [HasBeq α] [Hashable α] (m : HashMapImp α β) (a : α) (b : β) : HashMapImp α β :=
match m with
| ⟨size, buckets⟩ =>
let ⟨i, h⟩ := mkIdx buckets.property (hash a);
let bkt := buckets.val.uget i h;
if bkt.contains a
then ⟨size, buckets.update i (bkt.replace a b) h⟩
else
let size' := size + 1;
let buckets' := buckets.update i (AssocList.cons a b bkt) h;
if size' ≤ buckets.val.size
then { size := size', buckets := buckets' }
else expand size' buckets'
def erase [HasBeq α] [Hashable α] (m : HashMapImp α β) (a : α) : HashMapImp α β :=
match m with
| ⟨ size, buckets ⟩ =>
let ⟨i, h⟩ := mkIdx buckets.property (hash a);
let bkt := buckets.val.uget i h;
if bkt.contains a then ⟨size - 1, buckets.update i (bkt.erase a) h⟩
else m
inductive WellFormed [HasBeq α] [Hashable α] : HashMapImp α β → Prop
| mkWff : ∀ n, WellFormed (mkHashMapImp n)
| insertWff : ∀ m a b, WellFormed m → WellFormed (insert m a b)
| eraseWff : ∀ m a, WellFormed m → WellFormed (erase m a)
end HashMapImp
def HashMap (α : Type u) (β : Type v) [HasBeq α] [Hashable α] :=
{ m : HashMapImp α β // m.WellFormed }
open HashMapImp
def mkHashMap {α : Type u} {β : Type v} [HasBeq α] [Hashable α] (nbuckets := 8) : HashMap α β :=
⟨ mkHashMapImp nbuckets, WellFormed.mkWff nbuckets ⟩
namespace HashMap
variables {α : Type u} {β : Type v} [HasBeq α] [Hashable α]
instance : Inhabited (HashMap α β) :=
⟨mkHashMap⟩
instance : HasEmptyc (HashMap α β) :=
⟨mkHashMap⟩
@[inline] def insert (m : HashMap α β) (a : α) (b : β) : HashMap α β :=
match m with
| ⟨ m, hw ⟩ => ⟨ m.insert a b, WellFormed.insertWff m a b hw ⟩
@[inline] def erase (m : HashMap α β) (a : α) : HashMap α β :=
match m with
| ⟨ m, hw ⟩ => ⟨ m.erase a, WellFormed.eraseWff m a hw ⟩
@[inline] def findEntry? (m : HashMap α β) (a : α) : Option (α × β) :=
match m with
| ⟨ m, _ ⟩ => m.findEntry? a
@[inline] def find? (m : HashMap α β) (a : α) : Option β :=
match m with
| ⟨ m, _ ⟩ => m.find? a
@[inline] def findD (m : HashMap α β) (a : α) (b₀ : β) : β :=
(m.find? a).getD b₀
@[inline] def find! [Inhabited β] (m : HashMap α β) (a : α) : β :=
match m.find? a with
| some b => b
| none => panic! "key is not in the map"
@[inline] def getOp (self : HashMap α β) (idx : α) : Option β :=
self.find? idx
@[inline] def contains (m : HashMap α β) (a : α) : Bool :=
match m with
| ⟨ m, _ ⟩ => m.contains a
@[inline] def foldM {δ : Type w} {m : Type w → Type w} [Monad m] (f : δ → α → β → m δ) (d : δ) (h : HashMap α β) : m δ :=
match h with
| ⟨ h, _ ⟩ => h.foldM f d
@[inline] def fold {δ : Type w} (f : δ → α → β → δ) (d : δ) (m : HashMap α β) : δ :=
match m with
| ⟨ m, _ ⟩ => m.fold f d
@[inline] def size (m : HashMap α β) : Nat :=
match m with
| ⟨ {size := sz, ..}, _ ⟩ => sz
@[inline] def isEmpty (m : HashMap α β) : Bool :=
m.size = 0
@[inline] def empty : HashMap α β :=
mkHashMap
def toList (m : HashMap α β) : List (α × β) :=
m.fold (fun r k v => (k, v)::r) []
def toArray (m : HashMap α β) : Array (α × β) :=
m.fold (fun r k v => r.push (k, v)) #[]
def numBuckets (m : HashMap α β) : Nat :=
m.val.buckets.val.size
end HashMap