{-# 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

{- |
modulo @2^61-1@

@b@ should be a primitive root of @2^61-1@
-}
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

{- |
>>> fromString @(RollingHash 2047) "abc"
406650978
>>> fromString @(RollingHash 2047) "cba"
415031394
>>> fromString @(RollingHash 100) "abc"
979899
-}
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

{- |
>>> rht = buildRollingHashTable @2047 $ U.fromList "abcdef"
>>> rollingHashTo rht 3
406650978
>>> fromString @(RollingHash 2047) "abc"
406650978
-}
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

{- |
>>> rht = buildRollingHashTable @2047 $ U.fromList "abcdef"
>>> rollingHashFromTo rht 1 4
410843235
>>> fromString @(RollingHash 2047) "bcd"
410843235
-}
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)

{- |
>>> rht = buildRollingHashTable @2047 $ U.fromList "abcdef"
>>> rollingHashReverseTo rht 3
415031394
>>> fromString @(RollingHash 2047) "cba"
415031394
-}
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

{- |
>>> rht = buildRollingHashTable @2047 $ U.fromList "abcdef"
>>> rollingHashReverseFromTo rht 1 4
419223651
>>> fromString @(RollingHash 2047) "dcb"
419223651
-}
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

{- |
/O(1)/

>>> rht = buildRollingHashTable @2047 $ U.fromList "mississippi"
>>> isPalindromeFromTo rht 0 11
False
>>> isPalindromeFromTo rht 1 5
True
>>> isPalindromeFromTo rht 1 8
True
>>> isPalindromeFromTo rht 0 0
True
>>> isPalindromeFromTo rht 11 11
True
-}
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

{- |
>>> cacheSize = 10
>>> rht = buildRollingHashTable @2047 $ U.replicate cacheSize 'x'
>>> ab = "ab"
>>> cde = "cde"
>>> appendRH rht (length ab) (fromString ab) (length cde) (fromString cde)
1703952588079203
>>> fromString @(RollingHash 2047) "abcde"
1703952588079203

>>> rht = buildRollingHashTable @2047 U.empty
>>> ab = "ab"
>>> cde = "cde"
>>> appendRH rht (length ab) (fromString ab) (length cde) (fromString cde)
1703952588079203
>>> fromString @(RollingHash 2047) "abcde"
1703952588079203
-}
appendRH ::
  forall (b :: Nat).
  (KnownNat b) =>
  RollingHashTable b ->
  -- | length
  Int ->
  RollingHash b ->
  -- | length
  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

{- |
LCP(Longet Common Prefix) of @s[i..n)@ and @s[j..n)@

/O(log n)/

>>> rht = buildRollingHashTable @2047 $ U.fromList "abcxxxabc"
>>> longestCommonPrefixRH rht 0 6
3
>>> longestCommonPrefixRH rht 0 0
9
>>> longestCommonPrefixRH rht 8 8
1
>>> longestCommonPrefixRH rht 0 1
0
-}
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

{- |
/O(log n)/

>>> import Data.List
>>> rht = buildRollingHashTable @2047 $ U.fromList "mississippi"
>>> sortBy (compareSuffixRH rht) [0..11]
[11,10,7,4,1,0,9,8,6,3,5,2]
>>> rht = buildRollingHashTable @2047 $ U.fromList "abracadabra"
>>> sortBy (compareSuffixRH rht) [0..11]
[11,10,7,0,3,5,8,1,4,6,9,2]
>>> rht = buildRollingHashTable @2047 $ U.fromList "ababab"
>>> sortBy (compareSuffixRH rht) [0..6]
[6,4,2,0,5,3,1]
-}
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

{- |
Rabin–Karp

/O(n)/

>>> rht = buildRollingHashTable @2047 $ U.fromList "xxxabcxxx"
>>> abc = "abc"
>>> findSubstringIndexRH rht (length abc) (fromString abc)
Just 3
>>> zzz = "zzz"
>>> findSubstringIndexRH rht (length zzz) (fromString zzz)
Nothing
-}
findSubstringIndexRH ::
  (KnownNat b) =>
  RollingHashTable b ->
  -- | length
  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

{- |
Rabin–Karp

/O(n)/

>>> rht = buildRollingHashTable @2047 $ U.fromList "xxxabcxxx"
>>> abc = "abc"
>>> findSubstringIndicesRH rht (length abc) (fromString abc)
[3]
>>> xxx = "xxx"
>>> findSubstringIndicesRH rht (length xxx) (fromString xxx)
[0,6]
>>> zzz = "zzz"
>>> findSubstringIndicesRH rht (length zzz) (fromString zzz)
[]
-}
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

{- |
>>> F.foldl' (snocRH @2047) emptyRH "abc"
406650978
-}
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#))

{- |
check if @g@ is a primitive root of @2^61-1@.

>>> isPrimitiveRootRH 2047
True
>>> take 10 $ filter isPrimitiveRootRH [2..]
[37,43,55,69,74,86,110,123,133,138]
-}
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)

{- |
Generate a primitive root of @2^61-1@.

>>> genPrimitiveRootRH (mkStdGen 123)
1600615663002506808
>>> isPrimitiveRootRH 1600615663002506808
True
-}
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 (mkStdGen 123) $ \proxy -> getRollingHash $ 456 `asRollingHashOf` proxy
456
-}
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 #-}