module Data.HashMap.Lazy.Internal
( collisions
, collisionHistogram
) where
import Prelude hiding (lookup)
import qualified Data.FullList.Lazy as FL
import Data.HashMap.Common (HashMap(..))
import Data.HashMap.Lazy (insert, lookup)
collisions :: HashMap k v -> Int
collisions t = go t 0
where
go (Bin _ l r) !sz = go r (go l sz)
go (Tip _ l) !sz
| fl_sz <= 1 = sz
| otherwise = sz + fl_sz
where fl_sz = FL.size l
go Nil !sz = sz
collisionHistogram :: HashMap k v -> HashMap Int Int
collisionHistogram t = go t Nil
where
go (Bin _ l r) h = go r (go l h)
go (Tip _ l) h = (insert sz $! maybe 1 (1+) (lookup sz h)) h
where sz = FL.size l
go Nil h = h