data-hash 0.1.0.0 → 0.2.0.0

raw patch · 8 files changed

+179/−14 lines, 8 filesdep +QuickCheckdep +containersdep +data-hashdep ~basesetup-changedPVP ok

version bump matches the API change (PVP)

Dependencies added: QuickCheck, containers, data-hash, test-framework, test-framework-quickcheck2

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• AUTHORS +3/−0
• Setup.lhs +1/−1
• data-hash.cabal +19/−5
• src/Data/Hash.hs +4/−1
• src/Data/Hash/Base.hs +5/−6
• src/Data/Hash/Instances.hs +0/−1
• src/Data/Hash/Rolling.hs +90/−0
• tests/Main.hs +57/−0

@@ -0,0 +1,3 @@+Daniel Gorin++The Rolling hash implementation was contributed by Boris Sukholitko.

@@ -2,4 +2,4 @@ > module Main where > import Distribution.Simple > main :: IO ()-> main = defaultMainWithHooks defaultUserHooks+> main = defaultMain

@@ -1,5 +1,5 @@ name:               data-hash-version:            0.1.0.0+version:            0.2.0.0 description:                     Combinators for building fast hashing functions. Includes                     hashing functions for all basic Haskell98 types.@@ -10,18 +10,32 @@ license:            BSD3 license-file:       LICENSE maintainer:         jcpetruzza@gmail.com-homepage:           http://code.haskell.org/~jcpetruzza/data-hash -cabal-version:      >= 1.2+cabal-version:      >= 1.8 build-type:         Simple tested-with:        GHC==6.10 +extra-source-files: AUTHORS++source-repository   head+  type:             darcs+  location:         http://darcsden.com/jcpetruzza/data-hash+ Library-  build-depends:    base >= 3, array+  build-depends:    base >= 3 && <= 5, array, containers   ghc-options:      -Wall -O2   hs-source-dirs:   src -  exposed-modules:  Data.Hash+  exposed-modules:  Data.Hash, Data.Hash.Rolling   other-modules:    Data.Hash.Base, Data.Hash.Instances    extensions:       CPP+++test-suite Main+  type:            exitcode-stdio-1.0+  x-uses-tf:       true+  build-depends:   base, QuickCheck, test-framework, test-framework-quickcheck2, data-hash+  ghc-options:     -Wall+  hs-source-dirs:  tests+  main-is:         Main.hs

@@ -21,9 +21,12 @@                    hashWord16, hashWord32, hashWord64, hashInt,                    hashStorable, hashFoldable,                    -- * The @Hashable@ class-                   Hashable(..) )+                   Hashable(..),+                   -- * Rolling hashes+                   module Data.Hash.Rolling )  where  import Data.Hash.Base import Data.Hash.Instances+import Data.Hash.Rolling

@@ -1,11 +1,10 @@-module Data.Hash.Base ( Hash, asWord64, combine,-                        hashWord8, hashWord16, hashWord32, hashWord64, hashInt,-                        hashStorable,-                        h0, hT, hF )-where+module Data.Hash.Base where  import Data.Array-import Foreign+import Foreign (Storable, with, sizeOf, castPtr, Ptr, peek, plusPtr)+import System.IO.Unsafe (unsafePerformIO)+import Data.Word+import Data.Bits  #ifdef __GLASGOW_HASKELL__ import GHC.Arr ( unsafeAt )

@@ -7,7 +7,6 @@ import Data.Word import Data.Int import Data.Ratio-import Data.Char import Data.Foldable  class Hashable a where

@@ -0,0 +1,90 @@+------------------------------------------------------------------------------+-- |+-- Module       : Data.Hash.Rolling+-- License      : BSD-style+--+-- Maintainer   : jcpetruzza@gmail.com+-- Stability    : experimental+-- Portability  : portable+--+-- Efficient implementation of a rolling hash, i.e., the computation of a hash through+-- a moving window of a fixed size @n@ over some stream. All operations are O(1) (in+-- particular, they do not depend on the size of the window).+--+-- Some laws that this type satisfies:+--+-- * @currentHash rh == foldl1 combine (lastHashes rh)@+--+-- * @length (lastHashes rh) <= windowSize rh@+--+-- * @length (lastHashes $ addAndRoll rh a) == windowSize rh -- whenever length (lastHashes rh) == windowSize rh@+--+-- * @last (lastHashes $ addAndRoll rh x) == hash a@+--+-- * @init (lastHashes $ addAndRoll rh a) `isSuffixOf` (lastHashes rh)@+-------------------------------------------------------------------------------+module Data.Hash.Rolling (+    -- * The @RollingHash@ type+    RollingHash,+    -- ** Construction and manipulation+    rollingHash, addAndRoll,+    -- ** Querying+    currentHash, lastHashes, windowSize+)++where++import Data.Hash.Base+import Data.Hash.Instances+import Data.Bits+import qualified Data.Sequence as S+import Data.Foldable+import Text.Show.Functions ()+++data RollingHash a = RH {+     currentHash :: Hash+    ,windowSize  :: Int+    ,hseq        :: S.Seq Hash+    ,addHashImpl :: RollingHash a -> Hash -> RollingHash a+    } deriving Show++-- | @rollingHash n@ creates a @RollingHash@ of window+--   size @n@ (for @n > 0@)+rollingHash :: Int -> RollingHash a+rollingHash n+  | n == 0    = error $ "rollingHash: invalid window size " ++ show n+  | otherwise = RH {+       currentHash = initial_hash+      ,windowSize  = n+      ,hseq        = S.singleton initial_hash+      ,addHashImpl = accumulateNext (n - 1)+    }+    where initial_hash = hash () `combine` hash n++defaultAddHash :: RollingHash a -> Hash -> RollingHash a+defaultAddHash rh hv = rh { currentHash = (currentHash rh) `combine` (Hash $ rotate c1 k `xor` ck)+                          ,        hseq = (S.drop 1 $ hseq rh) S.|> hv+                          }+    where ck = asWord64 hv+          c1 = asWord64 $ S.index (hseq rh) 0+          k = S.length $ hseq rh+++-- | @addAndRoll x rh@ adds a new input element and rolls the window+--   one place through the input (if at least @n@ elements were+--   already consumed).+addAndRoll ::  Hashable a => RollingHash a -> a -> RollingHash a+addAndRoll r a = (addHashImpl r) r (hash a)++accumulateNext :: Int -> RollingHash a -> Hash -> RollingHash a+accumulateNext n | n > 0 = \rh h -> rh {+                            currentHash = currentHash rh `combine` h,+                            hseq = (hseq rh) S.|> h,+                            addHashImpl = accumulateNext (n - 1)+                        }+             | otherwise = defaultAddHash++-- | @lastHashes rh@ returns the last @n@ hashes.+lastHashes :: RollingHash a -> [Hash]+lastHashes = toList . hseq

@@ -0,0 +1,57 @@+module Main where++import Control.Applicative+import Test.QuickCheck+import Data.List++import Test.Framework as TF (defaultMain, testGroup, Test)+import Test.Framework.Providers.QuickCheck2 (testProperty)+import Data.Hash++main :: IO ()+main = defaultMain tests++instance (Arbitrary a, Hashable a) => Arbitrary (RollingHash a) where+  arbitrary = do Positive n <- arbitrary+                 foldl' addAndRoll (rollingHash n) <$> arbitrary++foldH :: [Int] -> Hash+foldH (i:xs) = foldl combine (hash i) $ map hash xs+foldH _ = error "Cannot happen"++rhArr :: Int -> [Int] -> RollingHash Int+rhArr x xs = foldl addAndRoll (rollingHash (length (x:xs))) (x:xs)++prop_cycle :: Int -> [Int] -> Bool+prop_cycle x xs = (currentHash rh) == (currentHash $ foldl addAndRoll rh $ x:x:xs)+    where rh = rhArr x xs++prop_curr :: RollingHash Int -> Bool+prop_curr rh = currentHash rh == foldl1' combine (lastHashes rh)++prop_len1 :: RollingHash Int -> Bool+prop_len1 rh = length (lastHashes rh) <= windowSize rh++prop_len2 :: RollingHash Int -> Int -> Bool+prop_len2 rh x+  | length (lastHashes rh) == n = length (lastHashes $ addAndRoll rh x) == n+  | otherwise                   = length (lastHashes $ addAndRoll rh x) == length (lastHashes rh) + 1+  where n = windowSize rh++prop_last :: RollingHash Int -> Int -> Bool+prop_last rh x = last (lastHashes $ addAndRoll rh x) == hash x++prop_suff :: RollingHash Int -> Int -> Bool+prop_suff rh x = init (lastHashes $ addAndRoll rh x) `isSuffixOf` (lastHashes rh)+++tests :: [TF.Test]+tests = [ testGroup "QuickCheck tests" [+              testProperty "curr" prop_curr+            , testProperty "len1" prop_len1+            , testProperty "len2" prop_len2+            , testProperty "last" prop_last+            , testProperty "suff" prop_suff+            , testProperty "cycle" prop_cycle+          ]+        ]