static-hash (empty) → 0.0.0

raw patch · 4 files changed

+120/−0 lines, 4 filesdep +arraydep +basedep +hashablesetup-changed

Dependencies added: array, base, hashable, primes

Files

• Data/StaticHash.hs +68/−0
• LICENSE +29/−0
• Setup.hs +2/−0
• static-hash.cabal +21/−0

@@ -0,0 +1,68 @@+{-|+  Pure immutable hash whose lookup is O(1).+-}++module Data.StaticHash (+    StaticHash+  , fromList, lookup+  ) where++import Data.Array+import Data.Hashable+import Data.List (groupBy,sortBy)+import Data.Numbers.Primes+import qualified Prelude as P (lookup)+import Prelude hiding (lookup)++----------------------------------------------------------------++{-|+  Data type for immutable hashes.+-}+newtype StaticHash k v = StaticHash (Array Int (Maybe [(k,v)]))++----------------------------------------------------------------++{-| +  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+  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++fil :: Int -> Int -> [(Int, v)] -> [(Int, Maybe v)]+fil i lim []+  | i < lim   = (i,Nothing) : 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++----------------------------------------------------------------++{-|+  Looking up 'StaticHash'.+-}+lookup :: (Eq k,Hashable k) => k -> StaticHash k v -> Maybe v+lookup k (StaticHash hs) = hs ! i >>= P.lookup k+  where+    (_,p') = bounds hs+    p = p' + 1+    i = k `hashBy` p++----------------------------------------------------------------++hashBy :: Hashable k => k -> Int -> Int+hashBy k p = hash k `mod` p

@@ -0,0 +1,29 @@+Copyright (c) 2009, IIJ Innovation Institute Inc.+All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions+are met:++  * Redistributions of source code must retain the above copyright+    notice, this list of conditions and the following disclaimer.+  * Redistributions in binary form must reproduce the above copyright+    notice, this list of conditions and the following disclaimer in+    the documentation and/or other materials provided with the+    distribution.+  * Neither the name of the copyright holders nor the names of its+    contributors may be used to endorse or promote products derived+    from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS+FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE+COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,+INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,+BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER+CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT+LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN+ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE+POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,21 @@+Name:                   static-hash+Version:                0.0.0+Author:                 Kazu Yamamoto <kazu@iij.ad.jp>+Maintainer:             Kazu Yamamoto <kazu@iij.ad.jp>+License:                BSD3+License-File:           LICENSE+Synopsis:               Immutable hash+Description:            Pure immutable hash whose lookup is O(1)+Category:               Data Structures+Cabal-Version:          >= 1.6+Build-Type:             Simple+library+  if impl(ghc >= 6.12)+    GHC-Options:        -Wall -fno-warn-unused-do-bind+  else+    GHC-Options:        -Wall+  Exposed-Modules:      Data.StaticHash+  Build-Depends:        base >= 4 && < 5, primes, hashable, array+Source-Repository head+  Type:                 git+  Location:             git://github.com/kazu-yamamoto/static-hash.git