ac-library-hs 1.3.0.1 → 1.3.1.0
raw patch · 4 files changed
+45/−11 lines, 4 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- README.md +3/−1
- ac-library-hs.cabal +1/−1
- src/AtCoder/Extra/Monoid/RollingHash.hs +26/−9
- test/Tests/Extra/Monoid.hs +15/−0
README.md view
@@ -2,6 +2,8 @@ Haskell port of [ac-library](https://github.com/atcoder/ac-library), a library for competitive programming on [AtCoder](https://atcoder.jp/). +The `main` branch is the version avaiable on AtCoder. See `dev` branch for upcoming updates.+ ## Notes - The library is mainly for AtCoder and only GHC 9.8.4 is guaranteed to be supported.@@ -10,5 +12,5 @@ ## Usage -See the API documentation for more information.+See the [API documentation on Hackage](https://hackage.haskell.org/package/ac-library-hs) for more information.
ac-library-hs.cabal view
@@ -4,7 +4,7 @@ -- PVP summary: +-+------- breaking API changes -- | | +----- non-breaking API additions -- | | | +--- code changes with no API change-version: 1.3.0.1+version: 1.3.1.0 synopsis: Data structures and algorithms description: Haskell port of [ac-library](https://github.com/atcoder/ac-library), a library for competitive
src/AtCoder/Extra/Monoid/RollingHash.hs view
@@ -25,6 +25,7 @@ import Data.Vector.Generic.Mutable qualified as VGM import Data.Vector.Unboxed qualified as VU import Data.Vector.Unboxed.Mutable qualified as VUM+import Data.WideWord.Word128 import GHC.Exts (proxy#) import GHC.TypeNats (KnownNat, natVal') @@ -34,7 +35,6 @@ -- Combining `RollingHash` with `SegTree` enables \(O(\log |s|)\) string slice creation and -- \(O(1)\) slice comparison. ----- -- ==== __Example__ -- It's convenient to define a type alias of `RollingHash`: --@@ -42,7 +42,7 @@ -- >>> import AtCoder.SegTree qualified as ST -- >>> import Data.Char (ord) -- >>> import Data.Semigroup (Dual (..))--- >>> type RH = RH.RollingHash 100 998244353+-- >>> type RH = RH.RollingHash 100 2305843009213693951 -- -- Let's test whether "abcba" is a palindrome: --@@ -76,7 +76,7 @@ -- @since 1.1.0.0 {-# INLINE new #-} new :: forall b p. (KnownNat b, KnownNat p) => Int -> RollingHash b p-new h = RollingHash (h `mod` fromIntegral (natVal' (proxy# @p))) (fromIntegral (natVal' (proxy# @b)))+new h = RollingHash (h `rem` fromIntegral (natVal' (proxy# @p))) (fromIntegral (natVal' (proxy# @b))) -- | \(O(1)\) Creates a one-length `RollingHash` from an integer without taking the mod. --@@ -85,15 +85,32 @@ unsafeNew :: forall b p. (KnownNat b, KnownNat p) => Int -> RollingHash b p unsafeNew h = RollingHash h (fromIntegral (natVal' (proxy# @b))) +-- | \(O(1)\)+{-# INLINE calc #-}+calc :: forall b p. (KnownNat b, KnownNat p) => RollingHash b p -> RollingHash b p -> RollingHash b p+calc (RollingHash !digit1 !hash1) (RollingHash !digit2 !hash2)+ | p < 3037000499 =+ let !digit' = digit1 * digit2 `rem` p+ !hash' = addMod p (hash1 * digit2 `rem` p) hash2+ in RollingHash digit' hash'+ | otherwise =+ -- TODO: This is slow+ let !digit' = fromIntegral $! to128 digit1 * to128 digit2 `rem` to128 p+ !hash' = fromIntegral $! (to128 hash1 * to128 digit2 + to128 hash2) `rem` to128 p+ in RollingHash digit' hash'+ where+ !p = fromIntegral $ natVal' (proxy# @p)+ to128 :: Int -> Word128+ to128 = fromIntegral+ addMod :: Int -> Int -> Int -> Int+ addMod m x y+ | x + y >= m = x + y - m+ | otherwise = x + y+ -- | @since 1.1.0.0 instance (KnownNat b, KnownNat p) => Semigroup (RollingHash b p) where- -- \| \(O(1)\) {-# INLINE (<>) #-}- (RollingHash !digit1 !hash1) <> (RollingHash !digit2 !hash2) = RollingHash digit' hash'- where- !p = fromIntegral $ natVal' (proxy# @p)- !digit' = digit1 * digit2 `mod` p- !hash' = (hash1 * digit2 + hash2) `mod` p+ (<>) = calc -- | @since 1.1.0.0 instance (KnownNat b, KnownNat p) => Monoid (RollingHash b p) where
test/Tests/Extra/Monoid.hs view
@@ -100,6 +100,13 @@ pure $ RollingHash hash next -- orphan instance+instance QC.Arbitrary (RollingHash b 2305843009213693951) where+ arbitrary = do+ hash <- QC.chooseInt (0, 2305843009213693951 - 1)+ next <- QC.chooseInt (0, 2305843009213693951 - 1)+ pure $ RollingHash hash next++-- orphan instance instance QC.Arbitrary (Max Int) where arbitrary = Max <$> QC.arbitrary @@ -249,6 +256,14 @@ testGroup "RollingHash" [ laws @(RollingHash 100 998244353)+ [ QCC.semigroupLaws,+ QCC.monoidLaws,+ QCC.semigroupMonoidLaws+ ]+ ],+ testGroup+ "RollingHash"+ [ laws @(RollingHash 100 2305843009213693951) [ QCC.semigroupLaws, QCC.monoidLaws, QCC.semigroupMonoidLaws