{-# LANGUAGE DataKinds #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UnboxedTuples #-}
module Data.RollingHash where
import Data.Char
import qualified Data.Foldable as F
import Data.Proxy
import qualified Data.Vector.Generic as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed as U
import GHC.Exts
import GHC.Real (Ratio (..))
import GHC.TypeLits
import System.Random.Stateful
import My.Prelude
newtype RollingHash (b :: Nat) = RollingHash {forall (b :: Nat). RollingHash b -> Int
getRollingHash :: Int}
deriving newtype (RollingHash b -> RollingHash b -> Bool
(RollingHash b -> RollingHash b -> Bool)
-> (RollingHash b -> RollingHash b -> Bool) -> Eq (RollingHash b)
forall (b :: Nat). RollingHash b -> RollingHash b -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall (b :: Nat). RollingHash b -> RollingHash b -> Bool
== :: RollingHash b -> RollingHash b -> Bool
$c/= :: forall (b :: Nat). RollingHash b -> RollingHash b -> Bool
/= :: RollingHash b -> RollingHash b -> Bool
Eq, Eq (RollingHash b)
Eq (RollingHash b) =>
(RollingHash b -> RollingHash b -> Ordering)
-> (RollingHash b -> RollingHash b -> Bool)
-> (RollingHash b -> RollingHash b -> Bool)
-> (RollingHash b -> RollingHash b -> Bool)
-> (RollingHash b -> RollingHash b -> Bool)
-> (RollingHash b -> RollingHash b -> RollingHash b)
-> (RollingHash b -> RollingHash b -> RollingHash b)
-> Ord (RollingHash b)
RollingHash b -> RollingHash b -> Bool
RollingHash b -> RollingHash b -> Ordering
RollingHash b -> RollingHash b -> RollingHash b
forall (b :: Nat). Eq (RollingHash b)
forall (b :: Nat). RollingHash b -> RollingHash b -> Bool
forall (b :: Nat). RollingHash b -> RollingHash b -> Ordering
forall (b :: Nat). RollingHash b -> RollingHash b -> RollingHash b
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: forall (b :: Nat). RollingHash b -> RollingHash b -> Ordering
compare :: RollingHash b -> RollingHash b -> Ordering
$c< :: forall (b :: Nat). RollingHash b -> RollingHash b -> Bool
< :: RollingHash b -> RollingHash b -> Bool
$c<= :: forall (b :: Nat). RollingHash b -> RollingHash b -> Bool
<= :: RollingHash b -> RollingHash b -> Bool
$c> :: forall (b :: Nat). RollingHash b -> RollingHash b -> Bool
> :: RollingHash b -> RollingHash b -> Bool
$c>= :: forall (b :: Nat). RollingHash b -> RollingHash b -> Bool
>= :: RollingHash b -> RollingHash b -> Bool
$cmax :: forall (b :: Nat). RollingHash b -> RollingHash b -> RollingHash b
max :: RollingHash b -> RollingHash b -> RollingHash b
$cmin :: forall (b :: Nat). RollingHash b -> RollingHash b -> RollingHash b
min :: RollingHash b -> RollingHash b -> RollingHash b
Ord, Int -> RollingHash b -> ShowS
[RollingHash b] -> ShowS
RollingHash b -> String
(Int -> RollingHash b -> ShowS)
-> (RollingHash b -> String)
-> ([RollingHash b] -> ShowS)
-> Show (RollingHash b)
forall (b :: Nat). Int -> RollingHash b -> ShowS
forall (b :: Nat). [RollingHash b] -> ShowS
forall (b :: Nat). RollingHash b -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall (b :: Nat). Int -> RollingHash b -> ShowS
showsPrec :: Int -> RollingHash b -> ShowS
$cshow :: forall (b :: Nat). RollingHash b -> String
show :: RollingHash b -> String
$cshowList :: forall (b :: Nat). [RollingHash b] -> ShowS
showList :: [RollingHash b] -> ShowS
Show)
instance Num (RollingHash b) where
(RollingHash (I# Int#
x#)) + :: RollingHash b -> RollingHash b -> RollingHash b
+ (RollingHash (I# Int#
y#)) = case Int#
x# Int# -> Int# -> Int#
+# Int#
y# of
Int#
xy# -> case Int#
xy# Int# -> Int# -> Int#
>=# Int#
0x1fffffffffffffff# of
Int#
b# -> Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Int# -> Int
I# (Int#
xy# Int# -> Int# -> Int#
+# Int#
b# Int# -> Int# -> Int#
-# Int# -> Int# -> Int#
uncheckedIShiftL# Int#
b# Int#
61#))
{-# INLINE (+) #-}
(RollingHash (I# Int#
x#)) - :: RollingHash b -> RollingHash b -> RollingHash b
- (RollingHash (I# Int#
y#)) = case Int#
x# Int# -> Int# -> Int#
-# Int#
y# of
Int#
xy# -> case Int#
xy# Int# -> Int# -> Int#
<# Int#
0# of
Int#
b# -> Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Int# -> Int
I# (Int#
xy# Int# -> Int# -> Int#
-# Int#
b# Int# -> Int# -> Int#
+# Int# -> Int# -> Int#
uncheckedIShiftL# Int#
b# Int#
61#))
{-# INLINE (-) #-}
(RollingHash (I# Int#
x#)) * :: RollingHash b -> RollingHash b -> RollingHash b
* (RollingHash (I# Int#
y#)) = case Word# -> Word# -> (# Word#, Word# #)
timesWord2# (Int# -> Word#
int2Word# Int#
x#) (Int# -> Word#
int2Word# Int#
y#) of
(# Word#
hi#, Word#
lo# #) ->
case Int# -> Int# -> Int#
uncheckedIShiftL# (Word# -> Int#
word2Int# Word#
hi#) Int#
3#
Int# -> Int# -> Int#
+# Int# -> Int# -> Int#
uncheckedIShiftRL# (Word# -> Int#
word2Int# Word#
lo#) Int#
61#
Int# -> Int# -> Int#
+# Int# -> Int# -> Int#
andI# (Word# -> Int#
word2Int# Word#
lo#) Int#
0x1fffffffffffffff# of
Int#
qr# -> case Int#
qr# Int# -> Int# -> Int#
># Int#
0x1fffffffffffffff# of
Int#
b# -> Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Int# -> Int
I# (Int#
qr# Int# -> Int# -> Int#
+# Int#
b# Int# -> Int# -> Int#
-# Int# -> Int# -> Int#
uncheckedIShiftL# Int#
b# Int#
61#))
{-# INLINE (*) #-}
abs :: RollingHash b -> RollingHash b
abs = RollingHash b -> RollingHash b
forall a. a -> a
id
{-# INLINE abs #-}
signum :: RollingHash b -> RollingHash b
signum = RollingHash b -> RollingHash b -> RollingHash b
forall a b. a -> b -> a
const (Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash Int
1)
{-# INLINE signum #-}
fromInteger :: Integer -> RollingHash b
fromInteger Integer
x = Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Int -> RollingHash b) -> Int -> RollingHash b
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
mod Integer
x Integer
0x1fffffffffffffff)
{-# INLINE fromInteger #-}
instance (KnownNat b) => Fractional (RollingHash b) where
recip :: RollingHash b -> RollingHash b
recip = (RollingHash b -> Int -> RollingHash b
forall a b. (Num a, Integral b) => a -> b -> a
^ (Int
0x1ffffffffffffffd :: Int))
{-# INLINE recip #-}
fromRational :: Rational -> RollingHash b
fromRational (Integer
p :% Integer
q) = Integer -> RollingHash b
forall a. Num a => Integer -> a
fromInteger Integer
p RollingHash b -> RollingHash b -> RollingHash b
forall a. Fractional a => a -> a -> a
/ Integer -> RollingHash b
forall a. Num a => Integer -> a
fromInteger Integer
q
instance (KnownNat b) => IsString (RollingHash b) where
fromString :: String -> RollingHash b
fromString = (RollingHash b -> Char -> RollingHash b)
-> RollingHash b -> String -> RollingHash b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' RollingHash b -> Char -> RollingHash b
forall (b :: Nat).
KnownNat b =>
RollingHash b -> Char -> RollingHash b
snocRH RollingHash b
forall (b :: Nat). RollingHash b
emptyRH
newtype instance U.MVector s (RollingHash b) = MV_RollingHash (U.MVector s Int)
newtype instance U.Vector (RollingHash b) = V_RollingHash (U.Vector Int)
deriving newtype instance GM.MVector U.MVector (RollingHash b)
deriving newtype instance G.Vector U.Vector (RollingHash b)
instance U.Unbox (RollingHash b)
data RollingHashTable (b :: Nat) = RollingHashTable
{ forall (b :: Nat). RollingHashTable b -> Vector Char
originalRH :: !(U.Vector Char)
, forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
hashForwardRH :: !(U.Vector (RollingHash b))
, forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
hashReverseRH :: !(U.Vector (RollingHash b))
, forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
powCacheRH :: !(U.Vector (RollingHash b))
, forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
recipPowCacheRH :: !(U.Vector (RollingHash b))
}
buildRollingHashTable ::
forall (b :: Nat).
(KnownNat b) =>
U.Vector Char ->
RollingHashTable b
buildRollingHashTable :: forall (b :: Nat). KnownNat b => Vector Char -> RollingHashTable b
buildRollingHashTable Vector Char
originalRH =
RollingHashTable
{ Vector Char
originalRH :: Vector Char
originalRH :: Vector Char
originalRH
, Vector (RollingHash b)
hashForwardRH :: Vector (RollingHash b)
hashForwardRH :: Vector (RollingHash b)
hashForwardRH
, Vector (RollingHash b)
hashReverseRH :: Vector (RollingHash b)
hashReverseRH :: Vector (RollingHash b)
hashReverseRH
, Vector (RollingHash b)
powCacheRH :: Vector (RollingHash b)
powCacheRH :: Vector (RollingHash b)
powCacheRH
, Vector (RollingHash b)
recipPowCacheRH :: Vector (RollingHash b)
recipPowCacheRH :: Vector (RollingHash b)
recipPowCacheRH
}
where
!b :: RollingHash b
b = Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Integer -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall (n :: Nat). KnownNat n => Proxy# n -> Integer
natVal' @b Proxy# b
forall {k} (a :: k). Proxy# a
proxy#))
!b' :: RollingHash b
b' = RollingHash b -> RollingHash b
forall a. Fractional a => a -> a
recip RollingHash b
b
hashForwardRH :: Vector (RollingHash b)
hashForwardRH = (RollingHash b -> Char -> RollingHash b)
-> RollingHash b -> Vector Char -> Vector (RollingHash b)
forall a b.
(Unbox a, Unbox b) =>
(a -> b -> a) -> a -> Vector b -> Vector a
U.scanl' (\RollingHash b
h Char
c -> RollingHash b
h RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* RollingHash b
b RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
+ Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Char -> Int
ord Char
c)) RollingHash b
0 Vector Char
originalRH
(Vector (RollingHash b)
hashReverseRH, Vector (RollingHash b)
powCacheRH) =
Vector (RollingHash b, RollingHash b)
-> (Vector (RollingHash b), Vector (RollingHash b))
forall a b.
(Unbox a, Unbox b) =>
Vector (a, b) -> (Vector a, Vector b)
U.unzip (Vector (RollingHash b, RollingHash b)
-> (Vector (RollingHash b), Vector (RollingHash b)))
-> Vector (RollingHash b, RollingHash b)
-> (Vector (RollingHash b), Vector (RollingHash b))
forall a b. (a -> b) -> a -> b
$
((RollingHash b, RollingHash b)
-> Char -> (RollingHash b, RollingHash b))
-> (RollingHash b, RollingHash b)
-> Vector Char
-> Vector (RollingHash b, RollingHash b)
forall a b.
(Unbox a, Unbox b) =>
(a -> b -> a) -> a -> Vector b -> Vector a
U.scanl'
( \(!RollingHash b
h, !RollingHash b
powb) Char
c ->
(Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Char -> Int
ord Char
c) RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* RollingHash b
powb RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
+ RollingHash b
h, RollingHash b
powb RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* RollingHash b
b)
)
(RollingHash b
0, RollingHash b
1)
Vector Char
originalRH
recipPowCacheRH :: Vector (RollingHash b)
recipPowCacheRH = (RollingHash b -> Char -> RollingHash b)
-> RollingHash b -> Vector Char -> Vector (RollingHash b)
forall a b.
(Unbox a, Unbox b) =>
(a -> b -> a) -> a -> Vector b -> Vector a
U.scanl' (\RollingHash b
powb' Char
_ -> RollingHash b
powb' RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* RollingHash b
b') RollingHash b
1 Vector Char
originalRH
rollingHashTo :: (KnownNat b) => RollingHashTable b -> Int -> RollingHash b
rollingHashTo :: forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> RollingHash b
rollingHashTo RollingHashTable{Vector (RollingHash b)
hashForwardRH :: forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
hashForwardRH :: Vector (RollingHash b)
hashForwardRH} Int
i = Vector (RollingHash b) -> Int -> RollingHash b
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector (RollingHash b)
hashForwardRH Int
i
rollingHashFromTo ::
(KnownNat b) =>
RollingHashTable b ->
Int ->
Int ->
RollingHash b
rollingHashFromTo :: forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> Int -> RollingHash b
rollingHashFromTo RollingHashTable{Vector (RollingHash b)
hashForwardRH :: forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
hashForwardRH :: Vector (RollingHash b)
hashForwardRH, Vector (RollingHash b)
powCacheRH :: forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
powCacheRH :: Vector (RollingHash b)
powCacheRH} Int
l Int
r =
RollingHash b
hr RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
- RollingHash b
hl RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* RollingHash b
brl
where
hl :: RollingHash b
hl = Vector (RollingHash b) -> Int -> RollingHash b
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector (RollingHash b)
hashForwardRH Int
l
hr :: RollingHash b
hr = Vector (RollingHash b) -> Int -> RollingHash b
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector (RollingHash b)
hashForwardRH Int
r
brl :: RollingHash b
brl = Vector (RollingHash b) -> Int -> RollingHash b
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector (RollingHash b)
powCacheRH (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l)
rollingHashReverseTo :: (KnownNat b) => RollingHashTable b -> Int -> RollingHash b
rollingHashReverseTo :: forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> RollingHash b
rollingHashReverseTo RollingHashTable{Vector (RollingHash b)
hashReverseRH :: forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
hashReverseRH :: Vector (RollingHash b)
hashReverseRH} Int
i = Vector (RollingHash b) -> Int -> RollingHash b
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector (RollingHash b)
hashReverseRH Int
i
rollingHashReverseFromTo ::
(KnownNat b) =>
RollingHashTable b ->
Int ->
Int ->
RollingHash b
rollingHashReverseFromTo :: forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> Int -> RollingHash b
rollingHashReverseFromTo RollingHashTable{Vector (RollingHash b)
hashReverseRH :: forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
hashReverseRH :: Vector (RollingHash b)
hashReverseRH, Vector (RollingHash b)
recipPowCacheRH :: forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
recipPowCacheRH :: Vector (RollingHash b)
recipPowCacheRH} Int
l Int
r =
(RollingHash b
hr RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
- RollingHash b
hl) RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* RollingHash b
bl'
where
hl :: RollingHash b
hl = Vector (RollingHash b) -> Int -> RollingHash b
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector (RollingHash b)
hashReverseRH Int
l
hr :: RollingHash b
hr = Vector (RollingHash b) -> Int -> RollingHash b
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector (RollingHash b)
hashReverseRH Int
r
bl' :: RollingHash b
bl' = Vector (RollingHash b) -> Int -> RollingHash b
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector (RollingHash b)
recipPowCacheRH Int
l
isPalindromeFromTo :: (KnownNat b) => RollingHashTable b -> Int -> Int -> Bool
isPalindromeFromTo :: forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> Int -> Bool
isPalindromeFromTo RollingHashTable b
rht Int
l Int
r =
RollingHashTable b -> Int -> Int -> RollingHash b
forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> Int -> RollingHash b
rollingHashFromTo RollingHashTable b
rht Int
l Int
r RollingHash b -> RollingHash b -> Bool
forall a. Eq a => a -> a -> Bool
== RollingHashTable b -> Int -> Int -> RollingHash b
forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> Int -> RollingHash b
rollingHashReverseFromTo RollingHashTable b
rht Int
l Int
r
appendRH ::
forall (b :: Nat).
(KnownNat b) =>
RollingHashTable b ->
Int ->
RollingHash b ->
Int ->
RollingHash b ->
RollingHash b
appendRH :: forall (b :: Nat).
KnownNat b =>
RollingHashTable b
-> Int -> RollingHash b -> Int -> RollingHash b -> RollingHash b
appendRH RollingHashTable{Vector (RollingHash b)
powCacheRH :: forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
powCacheRH :: Vector (RollingHash b)
powCacheRH} Int
_lx RollingHash b
hx Int
ly RollingHash b
hy
| Int
ly Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Vector (RollingHash b) -> Int
forall a. Unbox a => Vector a -> Int
U.length Vector (RollingHash b)
powCacheRH = RollingHash b
hx RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* Vector (RollingHash b) -> Int -> RollingHash b
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector (RollingHash b)
powCacheRH Int
ly RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
+ RollingHash b
hy
| Bool
otherwise =
let !b :: RollingHash b
b = Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Integer -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall (n :: Nat). KnownNat n => Proxy# n -> Integer
natVal' @b Proxy# b
forall {k} (a :: k). Proxy# a
proxy#))
in RollingHash b
hx RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* (RollingHash b
b RollingHash b -> Int -> RollingHash b
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
ly) RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
+ RollingHash b
hy
longestCommonPrefixRH :: (KnownNat b) => RollingHashTable b -> Int -> Int -> Int
longestCommonPrefixRH :: forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> Int -> Int
longestCommonPrefixRH RollingHashTable b
rht Int
i Int
j | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
j = RollingHashTable b -> Int -> Int -> Int
forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> Int -> Int
longestCommonPrefixRH RollingHashTable b
rht Int
i Int
j
longestCommonPrefixRH rht :: RollingHashTable b
rht@RollingHashTable{Vector Char
originalRH :: forall (b :: Nat). RollingHashTable b -> Vector Char
originalRH :: Vector Char
originalRH} Int
i Int
j =
Int -> Int -> (Int -> Bool) -> Int
binarySearch Int
0 (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
j) ((Int -> Bool) -> Int) -> (Int -> Bool) -> Int
forall a b. (a -> b) -> a -> b
$ \Int
k ->
RollingHashTable b -> Int -> Int -> RollingHash b
forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> Int -> RollingHash b
rollingHashFromTo RollingHashTable b
rht Int
i (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) RollingHash b -> RollingHash b -> Bool
forall a. Eq a => a -> a -> Bool
/= RollingHashTable b -> Int -> Int -> RollingHash b
forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> Int -> RollingHash b
rollingHashFromTo RollingHashTable b
rht Int
j (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
where
!n :: Int
n = Vector Char -> Int
forall a. Unbox a => Vector a -> Int
U.length Vector Char
originalRH
compareSuffixRH ::
(KnownNat b) =>
RollingHashTable b ->
Int ->
Int ->
Ordering
compareSuffixRH :: forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> Int -> Ordering
compareSuffixRH !rht :: RollingHashTable b
rht@RollingHashTable{Vector Char
originalRH :: forall (b :: Nat). RollingHashTable b -> Vector Char
originalRH :: Vector Char
originalRH} Int
i Int
j
| Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n
, Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n =
Char -> Char -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
(Vector Char -> Int -> Char
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector Char
originalRH (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
k))
(Vector Char -> Int -> Char
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector Char
originalRH (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
k))
| Bool
otherwise = Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
j Int
i
where
!k :: Int
k = RollingHashTable b -> Int -> Int -> Int
forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> Int -> Int
longestCommonPrefixRH RollingHashTable b
rht Int
i Int
j
!n :: Int
n = Vector Char -> Int
forall a. Unbox a => Vector a -> Int
U.length Vector Char
originalRH
findSubstringIndexRH ::
(KnownNat b) =>
RollingHashTable b ->
Int ->
RollingHash b ->
Maybe Int
findSubstringIndexRH :: forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> RollingHash b -> Maybe Int
findSubstringIndexRH
RollingHashTable
{ Vector (RollingHash b)
hashForwardRH :: forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
hashForwardRH :: Vector (RollingHash b)
hashForwardRH
, Vector (RollingHash b)
powCacheRH :: forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
powCacheRH :: Vector (RollingHash b)
powCacheRH
}
!Int
len
!RollingHash b
hash =
(RollingHash b -> Bool) -> Vector (RollingHash b) -> Maybe Int
forall a. Unbox a => (a -> Bool) -> Vector a -> Maybe Int
U.findIndex (RollingHash b -> RollingHash b -> Bool
forall a. Eq a => a -> a -> Bool
== RollingHash b
hash) (Vector (RollingHash b) -> Maybe Int)
-> Vector (RollingHash b) -> Maybe Int
forall a b. (a -> b) -> a -> b
$
(RollingHash b -> RollingHash b -> RollingHash b)
-> Vector (RollingHash b)
-> Vector (RollingHash b)
-> Vector (RollingHash b)
forall a b c.
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector a -> Vector b -> Vector c
U.zipWith (\RollingHash b
hr RollingHash b
hl -> RollingHash b
hr RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
- RollingHash b
hl RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* RollingHash b
b) (Int -> Vector (RollingHash b) -> Vector (RollingHash b)
forall a. Unbox a => Int -> Vector a -> Vector a
U.drop Int
len Vector (RollingHash b)
hashForwardRH) Vector (RollingHash b)
hashForwardRH
where
!b :: RollingHash b
b = Vector (RollingHash b) -> Int -> RollingHash b
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector (RollingHash b)
powCacheRH Int
len
findSubstringIndicesRH ::
(KnownNat b) =>
RollingHashTable b ->
Int ->
RollingHash b ->
U.Vector Int
findSubstringIndicesRH :: forall (b :: Nat).
KnownNat b =>
RollingHashTable b -> Int -> RollingHash b -> Vector Int
findSubstringIndicesRH
RollingHashTable
{ Vector (RollingHash b)
hashForwardRH :: forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
hashForwardRH :: Vector (RollingHash b)
hashForwardRH
, Vector (RollingHash b)
powCacheRH :: forall (b :: Nat). RollingHashTable b -> Vector (RollingHash b)
powCacheRH :: Vector (RollingHash b)
powCacheRH
}
!Int
len
!RollingHash b
hash =
(RollingHash b -> Bool) -> Vector (RollingHash b) -> Vector Int
forall a. Unbox a => (a -> Bool) -> Vector a -> Vector Int
U.findIndices (RollingHash b -> RollingHash b -> Bool
forall a. Eq a => a -> a -> Bool
== RollingHash b
hash) (Vector (RollingHash b) -> Vector Int)
-> Vector (RollingHash b) -> Vector Int
forall a b. (a -> b) -> a -> b
$
(RollingHash b -> RollingHash b -> RollingHash b)
-> Vector (RollingHash b)
-> Vector (RollingHash b)
-> Vector (RollingHash b)
forall a b c.
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector a -> Vector b -> Vector c
U.zipWith (\RollingHash b
hr RollingHash b
hl -> RollingHash b
hr RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
- RollingHash b
hl RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* RollingHash b
b) (Int -> Vector (RollingHash b) -> Vector (RollingHash b)
forall a. Unbox a => Int -> Vector a -> Vector a
U.drop Int
len Vector (RollingHash b)
hashForwardRH) Vector (RollingHash b)
hashForwardRH
where
!b :: RollingHash b
b = Vector (RollingHash b) -> Int -> RollingHash b
forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndex Vector (RollingHash b)
powCacheRH Int
len
asRollingHashOf :: RollingHash b -> Proxy b -> RollingHash b
asRollingHashOf :: forall (b :: Nat). RollingHash b -> Proxy b -> RollingHash b
asRollingHashOf = RollingHash b -> Proxy b -> RollingHash b
forall a b. a -> b -> a
const
emptyRH :: RollingHash b
emptyRH :: forall (b :: Nat). RollingHash b
emptyRH = Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash Int
0
singletonRH :: Int -> RollingHash b
singletonRH :: forall (b :: Nat). Int -> RollingHash b
singletonRH = Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash
snocRH ::
forall (b :: Nat).
(KnownNat b) =>
RollingHash b ->
Char ->
RollingHash b
snocRH :: forall (b :: Nat).
KnownNat b =>
RollingHash b -> Char -> RollingHash b
snocRH RollingHash b
h Char
c = RollingHash b
h RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* RollingHash b
base RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
+ Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Char -> Int
ord Char
c)
where
base :: RollingHash b
base = Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Integer -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall (n :: Nat). KnownNat n => Proxy# n -> Integer
natVal' @b Proxy# b
forall {k} (a :: k). Proxy# a
proxy#))
isPrimitiveRootRH :: Int -> Bool
isPrimitiveRootRH :: Int -> Bool
isPrimitiveRootRH Int
g = (Int -> Bool) -> [Int] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Int -> Bool
ok [Int
2, Int
3, Int
5, Int
7, Int
11, Int
13, Int
31, Int
41, Int
61, Int
151, Int
331, Int
1321]
where
ok :: Int -> Bool
ok :: Int -> Bool
ok Int
p = Int -> RollingHash 2047
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
g RollingHash 2047 -> Int -> RollingHash 2047
forall a b. (Num a, Integral b) => a -> b -> a
^ Int -> Int -> Int
forall a. Integral a => a -> a -> a
quot Int
0x1ffffffffffffffe Int
p RollingHash 2047 -> RollingHash 2047 -> Bool
forall a. Eq a => a -> a -> Bool
/= (RollingHash 2047
1 :: RollingHash 2047)
genPrimitiveRootRH :: (RandomGen g) => g -> Int
genPrimitiveRootRH :: forall g. RandomGen g => g -> Int
genPrimitiveRootRH = g -> Int
forall g. RandomGen g => g -> Int
go
where
go :: t -> Int
go !t
g
| Int -> Bool
isPrimitiveRootRH Int
x = Int
x
| Bool
otherwise = t -> Int
go t
g'
where
(Int
x, t
g') = (Int, Int) -> t -> (Int, t)
forall a g. (Random a, RandomGen g) => (a, a) -> g -> (a, g)
forall g. RandomGen g => (Int, Int) -> g -> (Int, g)
randomR (Int
2, Int
0x1ffffffffffffffe) t
g
withPrimitiveRootRH ::
(RandomGen g) =>
g ->
(forall b. (KnownNat b) => Proxy b -> a) ->
a
withPrimitiveRootRH :: forall g a.
RandomGen g =>
g -> (forall (b :: Nat). KnownNat b => Proxy b -> a) -> a
withPrimitiveRootRH g
gen forall (b :: Nat). KnownNat b => Proxy b -> a
f =
case Integer -> Maybe SomeNat
someNatVal (Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Integer) -> Int -> Integer
forall a b. (a -> b) -> a -> b
$ g -> Int
forall g. RandomGen g => g -> Int
genPrimitiveRootRH g
gen) of
Just (SomeNat Proxy n
proxy) -> Proxy n -> a
forall (b :: Nat). KnownNat b => Proxy b -> a
f Proxy n
proxy
Maybe SomeNat
Nothing -> String -> a
forall a. HasCallStack => String -> a
error String
"withPrimitiveRootRH failed"
{-# INLINE withPrimitiveRootRH #-}