{-# LANGUAGE BangPatterns #-}
------------------------------------------------------------------------
-- |
-- Module : Data.HashMap.Lazy.Internal
-- Copyright : 2010-2011 Johan Tibell
-- License : BSD-style
-- Maintainer : johan.tibell@gmail.com
-- Stability : provisional
-- Portability : portable
--
-- Semi-public internals.
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)
-------------------------------------------------------------------
-- Metadata about map behavior
-- | /O(n)/ Return the number of hash collisions in this map.
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
-- | /O(n)/ Return histogram of hash collisions in this map.
-- Keys are number of entries in bucket, values are number of buckets
-- of that size.
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