module Data.Hash.Rolling (
RollingHash,
rollingHash, addAndRoll,
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 {
forall a. RollingHash a -> Hash
currentHash :: Hash
,forall a. RollingHash a -> Int
windowSize :: Int
,forall a. RollingHash a -> Seq Hash
hseq :: S.Seq Hash
,forall a. RollingHash a -> RollingHash a -> Hash -> RollingHash a
addHashImpl :: RollingHash a -> Hash -> RollingHash a
} deriving Int -> RollingHash a -> ShowS
forall a. Int -> RollingHash a -> ShowS
forall a. [RollingHash a] -> ShowS
forall a. RollingHash a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [RollingHash a] -> ShowS
$cshowList :: forall a. [RollingHash a] -> ShowS
show :: RollingHash a -> String
$cshow :: forall a. RollingHash a -> String
showsPrec :: Int -> RollingHash a -> ShowS
$cshowsPrec :: forall a. Int -> RollingHash a -> ShowS
Show
rollingHash :: Int -> RollingHash a
rollingHash :: forall a. Int -> RollingHash a
rollingHash Int
n
| Int
n forall a. Eq a => a -> a -> Bool
== Int
0 = forall a. HasCallStack => String -> a
error forall a b. (a -> b) -> a -> b
$ String
"rollingHash: invalid window size " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Int
n
| Bool
otherwise = RH {
currentHash :: Hash
currentHash = Hash
initial_hash
,windowSize :: Int
windowSize = Int
n
,hseq :: Seq Hash
hseq = forall a. a -> Seq a
S.singleton Hash
initial_hash
,addHashImpl :: RollingHash a -> Hash -> RollingHash a
addHashImpl = forall a. Int -> RollingHash a -> Hash -> RollingHash a
accumulateNext (Int
n forall a. Num a => a -> a -> a
- Int
1)
}
where initial_hash :: Hash
initial_hash = forall a. Hashable a => a -> Hash
hash () Hash -> Hash -> Hash
`combine` forall a. Hashable a => a -> Hash
hash Int
n
defaultAddHash :: RollingHash a -> Hash -> RollingHash a
defaultAddHash :: forall a. RollingHash a -> Hash -> RollingHash a
defaultAddHash RollingHash a
rh Hash
hv = RollingHash a
rh { currentHash :: Hash
currentHash = (forall a. RollingHash a -> Hash
currentHash RollingHash a
rh) Hash -> Hash -> Hash
`combine` (Word64 -> Hash
Hash forall a b. (a -> b) -> a -> b
$ forall a. Bits a => a -> Int -> a
rotate Word64
c1 Int
k forall a. Bits a => a -> a -> a
`xor` Word64
ck)
, hseq :: Seq Hash
hseq = (forall a. Int -> Seq a -> Seq a
S.drop Int
1 forall a b. (a -> b) -> a -> b
$ forall a. RollingHash a -> Seq Hash
hseq RollingHash a
rh) forall a. Seq a -> a -> Seq a
S.|> Hash
hv
}
where ck :: Word64
ck = Hash -> Word64
asWord64 Hash
hv
c1 :: Word64
c1 = Hash -> Word64
asWord64 forall a b. (a -> b) -> a -> b
$ forall a. Seq a -> Int -> a
S.index (forall a. RollingHash a -> Seq Hash
hseq RollingHash a
rh) Int
0
k :: Int
k = forall a. Seq a -> Int
S.length forall a b. (a -> b) -> a -> b
$ forall a. RollingHash a -> Seq Hash
hseq RollingHash a
rh
addAndRoll :: Hashable a => RollingHash a -> a -> RollingHash a
addAndRoll :: forall a. Hashable a => RollingHash a -> a -> RollingHash a
addAndRoll RollingHash a
r a
a = (forall a. RollingHash a -> RollingHash a -> Hash -> RollingHash a
addHashImpl RollingHash a
r) RollingHash a
r (forall a. Hashable a => a -> Hash
hash a
a)
accumulateNext :: Int -> RollingHash a -> Hash -> RollingHash a
accumulateNext :: forall a. Int -> RollingHash a -> Hash -> RollingHash a
accumulateNext Int
n | Int
n forall a. Ord a => a -> a -> Bool
> Int
0 = \RollingHash a
rh Hash
h -> RollingHash a
rh {
currentHash :: Hash
currentHash = forall a. RollingHash a -> Hash
currentHash RollingHash a
rh Hash -> Hash -> Hash
`combine` Hash
h,
hseq :: Seq Hash
hseq = (forall a. RollingHash a -> Seq Hash
hseq RollingHash a
rh) forall a. Seq a -> a -> Seq a
S.|> Hash
h,
addHashImpl :: RollingHash a -> Hash -> RollingHash a
addHashImpl = forall a. Int -> RollingHash a -> Hash -> RollingHash a
accumulateNext (Int
n forall a. Num a => a -> a -> a
- Int
1)
}
| Bool
otherwise = forall a. RollingHash a -> Hash -> RollingHash a
defaultAddHash
lastHashes :: RollingHash a -> [Hash]
lastHashes :: forall a. RollingHash a -> [Hash]
lastHashes = forall (t :: * -> *) a. Foldable t => t a -> [a]
toList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. RollingHash a -> Seq Hash
hseq