stringsearch 0.1.1 → 0.2
raw patch · 3 files changed
+43/−26 lines, 3 filesdep +arraydep +bytestringdep ~base
Dependencies added: array, bytestring
Dependency ranges changed: base
Files
- Data/ByteString/Search/BoyerMoore.hs +13/−9
- Data/ByteString/Search/KnuthMorrisPratt.hs +7/−3
- stringsearch.cabal +23/−14
Data/ByteString/Search/BoyerMoore.hs view
@@ -51,7 +51,11 @@ import qualified Data.ByteString as S (ByteString,null,length,concat) import qualified Data.ByteString.Lazy as L (ByteString,toChunks)-import qualified Data.ByteString.Base as B (unsafeIndex)+#if __GLASGOW_HASKELL__ >= 608+import qualified Data.ByteString.Unsafe as U (unsafeIndex)+#else+import qualified Data.ByteString.Base as U (unsafeIndex)+#endif import Data.Array.Base (unsafeAt,unsafeRead,unsafeWrite) import Data.Array.ST (newArray,newArray_,runSTUArray)@@ -166,7 +170,7 @@ {-# INLINE patAt #-} patAt :: Int -> Word8- patAt !i = B.unsafeIndex pat i+ patAt !i = U.unsafeIndex pat i searcher str | maxStrLen <= S.length str = error "Overflow error in BoyerMoore.matchSSd" | otherwise =@@ -174,7 +178,7 @@ !maxDiff = strLen-patLen {-# INLINE strAt #-} strAt :: Int -> Word8- strAt !i = B.unsafeIndex str i+ strAt !i = U.unsafeIndex str i findMatch !diff !patI = case strAt (diff+patI) of@@ -226,7 +230,7 @@ {-# INLINE patAt #-} patAt :: Int -> Word8- patAt !i = B.unsafeIndex pat i+ patAt !i = U.unsafeIndex pat i searcher string = let -- seek is used to position the "zipper" of@@ -321,7 +325,7 @@ !maxStrLen = pred ((maxBound::Int) - patLen) {-# INLINE strAt #-} strAt :: Int -> Word8- strAt !i = B.unsafeIndex str i+ strAt !i = U.unsafeIndex str i in case string of [] -> [] [str] -> -- Steal the quick findMatch from matchSSd for this case:@@ -349,7 +353,7 @@ !maxStrLen = ((maxBound::Int) - patLen) {-# INLINE strAt #-} strAt :: Int -> Word8- strAt !i = B.unsafeIndex str i+ strAt !i = U.unsafeIndex str i in if maxStrLen <= strLen then error "Overflow in BoyerMoore.matchSSsd" else findMatch 0 patEnd@@ -376,7 +380,7 @@ | otherwise = runSTUArray (do ar <- newArray (minBound,maxBound) (-1) let loop !i | i == patEnd = return ar- | otherwise = do unsafeWrite ar (fromEnum $ pat `B.unsafeIndex` i) i+ | otherwise = do unsafeWrite ar (fromEnum $ pat `U.unsafeIndex` i) i loop (succ i) loop 0) where@@ -390,7 +394,7 @@ occurs' :: S.ByteString -> UArray Word8 Int occurs' !pat = accumArray (flip const) (-1) (0,255)- [ (pat `B.unsafeIndex` i, i) | i <- [0..pred (S.length pat)] ]+ [ (pat `U.unsafeIndex` i, i) | i <- [0..pred (S.length pat)] ] occurs'' :: S.ByteString -> UArray Word8 Int occurs'' !pat = accumArray (flip const) (-1) (minBound,maxBound) $ zip (init $ S.unpack pat) [0..]@@ -434,7 +438,7 @@ let {-# INLINE matchSuffix #-} matchSuffix !idx !from = do let !d = patEnd - idx- helper !i | i < 0 || (pat `B.unsafeIndex` i) /= (pat `B.unsafeIndex` (i+d)) = i+ helper !i | i < 0 || (pat `U.unsafeIndex` i) /= (pat `U.unsafeIndex` (i+d)) = i | otherwise = helper (pred i) pre' = helper from unsafeWrite ar idx (idx-pre')
Data/ByteString/Search/KnuthMorrisPratt.hs view
@@ -40,7 +40,11 @@ import qualified Data.Array.IArray as IArray (array) import qualified Data.ByteString.Lazy as L import qualified Data.ByteString as S-import qualified Data.ByteString.Base as B (unsafeIndex)+#if __GLASGOW_HASKELL__ >= 608+import qualified Data.ByteString.Unsafe as U (unsafeIndex)+#else+import qualified Data.ByteString.Base as U (unsafeIndex)+#endif import Data.Int (Int64) -- $overview@@ -114,7 +118,7 @@ findMatch !strIndex !patIndex | patIndex == patLen = (prior + fromIntegral strIndex - fromIntegral patLen) : findMatch strIndex 0 | strIndex == strLen = searcher (prior + fromIntegral strLen) patIndex strRest | otherwise =- if (B.unsafeIndex str strIndex) == (B.unsafeIndex pat patIndex)+ if (U.unsafeIndex str strIndex) == (U.unsafeIndex pat patIndex) then findMatch (succ strIndex) (succ patIndex) else if patIndex == 0 then findMatch (succ strIndex) 0@@ -152,7 +156,7 @@ | shiftPrefix == patIdx = 0 -- No match | shiftPrefix + prefixIdx == patIdx = prefixIdx -- Suffix found. -- Compare pattern to itself, but shifted, here.- | B.unsafeIndex pat (shiftPrefix + prefixIdx) == B.unsafeIndex pat prefixIdx = longestSuffix' shiftPrefix (prefixIdx + 1)+ | U.unsafeIndex pat (shiftPrefix + prefixIdx) == U.unsafeIndex pat prefixIdx = longestSuffix' shiftPrefix (prefixIdx + 1) | otherwise = longestSuffix' (shiftPrefix + 1) 0 in longestSuffix' 1 0
stringsearch.cabal view
@@ -1,14 +1,23 @@-Name: stringsearch-Category: Text, Data, Search-Version: 0.1.1-Description: Fast search of ByteStrings-License: BSD3-License-file: LICENSE-Author: Daniel Fischer, Chris Kuklewicz-Maintainer: bos@serpentine.com-Build-Depends: base-Exposed-modules: Data.ByteString.Search.BoyerMoore- Data.ByteString.Search.KnuthMorrisPratt-Extensions: CPP-ghc-options: -O2 -Wall -Werror-nhc98-options: -K4M+Name: stringsearch+Version: 0.2+Description: Fast search of ByteStrings+Category: Text, Data, Search+License: BSD3+License-file: LICENSE+Author: Daniel Fischer, Chris Kuklewicz+Maintainer: bos@serpentine.com+Cabal-version: >= 1.2++Flag splitBase+ Description: Choose the new, split-up base package.++Library+ if flag(splitBase)+ Build-depends: base, array, bytestring+ else+ Build-depends: base+ Exposed-modules: Data.ByteString.Search.BoyerMoore+ Data.ByteString.Search.KnuthMorrisPratt+ Extensions: CPP+ ghc-options: -O2 -Wall -Werror+ nhc98-options: -K4M