static-hash 0.0.0 → 0.0.1

raw patch · 2 files changed

+62/−24 lines, 2 filesdep +containers

Dependencies added: containers

Files

• Data/StaticHash.hs +60/−22
• static-hash.cabal +2/−2

@@ -1,17 +1,21 @@ {-|-  Pure immutable hash whose lookup is O(1).+  Pure immutable hash whose lookup is O(1) on the average,+  but O(N) in the worst case. -}  module Data.StaticHash (     StaticHash-  , fromList, lookup+  , fromList, fromList', lookup   ) where  import Data.Array+import Data.Function import Data.Hashable import Data.List (groupBy,sortBy)+import Data.Map (Map)+import qualified Data.Map as M import Data.Numbers.Primes-import qualified Prelude as P (lookup)+import Data.Ord import Prelude hiding (lookup)  ----------------------------------------------------------------@@ -19,48 +23,82 @@ {-|   Data type for immutable hashes. -}-newtype StaticHash k v = StaticHash (Array Int (Maybe [(k,v)])) +newtype StaticHash k v = StaticHash (Array Int (Some k v)) deriving Show++data Some k v = None | One k v | More (Map k v) deriving Show++type Hash = Int+ ---------------------------------------------------------------- -{-| +{-|   Creating 'StaticHash' from a list. A prime around the length of   the list x 2 is chosen for the size of array. This may prevent   collisions. -} -fromList :: (Eq k,Hashable k) => [(k,v)] -> StaticHash k v-fromList xs = StaticHash $ array (0,p-1) ls+fromList :: (Eq k, Ord k, Hashable k) => [(k,v)] -> StaticHash k v+fromList xs = fromList' (length xs) xs++{-|+  Creating 'StaticHash' from a list and its size.+-}++fromList' :: (Eq k, Ord k, Hashable k) => Int -> [(k,v)] -> StaticHash k v+fromList' len xs = StaticHash $ array (0,p-1) $ toIxKV xs   where-    len = length xs     threshold = len * 2 -- hoping collision free-    p = head $ filter (>= threshold) primes-    hs = map (\xy -> (fst xy `hashBy` p, xy)) xs-    x <=> y = fst x`compare` fst y-    x === y = fst x == fst y-    gs = groupBy (===) $ sortBy (<=>) hs-    unify ys = (fst (head ys), map snd ys)-    ls = fil 0 p $ map unify gs+    p = findPrime threshold+    hashfunc = (`hashBy` p)+    toIxKV = fil 0 p . unify . hashGroup hashfunc -fil :: Int -> Int -> [(Int, v)] -> [(Int, Maybe v)]+findPrime :: Int -> Int+findPrime threshold = head $ filter (>= threshold) primes++hashGroup :: (Eq k, Ord k, Hashable k) => (k -> Hash) -> [(k,v)] -> [[(Hash,(k,v))]]+hashGroup hashfunc xs = gs+  where+    hs = map (\kv@(k,_) -> (hashfunc k, kv)) xs+    gs = groupBy ((==) `on` fst) $ sortBy (comparing fst) hs++unify :: Ord k => [[(Hash, (k, v))]] -> [(Hash, Some k v)]+unify = map hashKeyVal++hashKeyVal :: Ord k => [(Hash,(k,v))] -> (Hash,Some k v)+hashKeyVal xs = (h, toSome kvs)+  where+    (h:_,kvs) = unzip xs++toSome :: Ord k => [(k,v)] -> Some k v+toSome []      = None+toSome [(k,v)] = One k v+toSome kvs     = More (M.fromList kvs)++fil :: Int -> Int -> [(Hash, Some k v)] -> [(Hash, Some k v)] fil i lim []-  | i < lim   = (i,Nothing) : fil (i+1) lim []+  | i < lim   = (i,None) : fil (i+1) lim []   | otherwise = [] fil i lim kvs@((k,v):rest)-  | i < k     = (i,Nothing) : fil (i+1) lim kvs-  | otherwise = (k,Just v)  : fil (k+1) lim rest+  | i < k     = (i,None) : fil (i+1) lim kvs+  | otherwise = (k,v)    : fil (k+1) lim rest  ----------------------------------------------------------------  {-|   Looking up 'StaticHash'. -}-lookup :: (Eq k,Hashable k) => k -> StaticHash k v -> Maybe v-lookup k (StaticHash hs) = hs ! i >>= P.lookup k+lookup :: (Eq k, Ord k, Hashable k) => k -> StaticHash k v -> Maybe v+lookup key (StaticHash hs) = case hs ! i of+    None    -> Nothing+    One k v+      | key == k  -> Just v+      | otherwise -> Nothing+    More m  -> M.lookup key m   where     (_,p') = bounds hs     p = p' + 1-    i = k `hashBy` p+    i = key `hashBy` p  ---------------------------------------------------------------- 

@@ -1,5 +1,5 @@ Name:                   static-hash-Version:                0.0.0+Version:                0.0.1 Author:                 Kazu Yamamoto <kazu@iij.ad.jp> Maintainer:             Kazu Yamamoto <kazu@iij.ad.jp> License:                BSD3@@ -15,7 +15,7 @@   else     GHC-Options:        -Wall   Exposed-Modules:      Data.StaticHash-  Build-Depends:        base >= 4 && < 5, primes, hashable, array+  Build-Depends:        base >= 4 && < 5, primes, hashable, array, containers Source-Repository head   Type:                 git   Location:             git://github.com/kazu-yamamoto/static-hash.git