git.iko.soy/text
on 3cf8564 help sign in
text/Data/Text/Search.hs
90 lines 3.3 kB history raw
1{-# LANGUAGE BangPatterns, ScopedTypeVariables #-}
3-- |
4-- Module : Data.Text.Search
5-- Copyright : (c) Bryan O'Sullivan 2009
6--
7-- License : BSD-style
8-- Maintainer : bos@serpentine.com, rtomharper@googlemail.com,
9-- duncan@haskell.org
10-- Stability : experimental
11-- Portability : GHC
12--
13-- Fast substring search for 'Text', based on work by Boyer, Moore,
14-- Horspool, Sunday, and Lundh.
15--
16-- References:
17--
18-- * R. S. Boyer, J. S. Moore: A Fast String Searching Algorithm.
19-- Communications of the ACM, 20, 10, 762-772 (1977)
20--
21-- * R. N. Horspool: Practical Fast Searching in Strings. Software -
22-- Practice and Experience 10, 501-506 (1980)
23--
24-- * D. M. Sunday: A Very Fast Substring Search Algorithm.
25-- Communications of the ACM, 33, 8, 132-142 (1990)
26--
27-- * F. Lundh: The Fast Search Algorithm.
28-- <http://effbot.org/zone/stringlib.htm> (2006)
30module Data.Text.Search
31 (
32 indices
33 ) where
35import qualified Data.Text.Array as A
36import Data.Word (Word64)
37import Data.Text.Internal (Text(..))
38import Data.Bits ((.|.), (.&.))
39import Data.Text.UnsafeShift (shiftL)
41data T = {-# UNPACK #-} !Word64 :* {-# UNPACK #-} !Int
43-- | /O(n+m)/ Find the offsets of all non-overlapping indices of
44-- @needle@ within @haystack@. The offsets returned represent
45-- uncorrected indices in the low-level \"needle\" array, to which its
46-- offset must be added.
47--
48-- In (unlikely) bad cases, this algorithm's complexity degrades
49-- towards /O(n*m)/.
50indices :: Text -- ^ Substring to search for (@needle@)
51 -> Text -- ^ Text to search in (@haystack@)
52 -> [Int]
53indices _needle@(Text narr noff nlen) _haystack@(Text harr hoff hlen)
54 | nlen == 1 = scanOne (nindex 0)
55 | nlen <= 0 || ldiff < 0 = []
56 | otherwise = scan 0
57 where
58 ldiff = hlen - nlen
59 nlast = nlen - 1
60 z = nindex nlast
61 nindex k = A.unsafeIndex narr (noff+k)
62 hindex k = A.unsafeIndex harr (hoff+k)
63 hindex' k | k == hlen = 0
64 | otherwise = A.unsafeIndex harr (hoff+k)
65 buildTable !i !msk !skp
66 | i >= nlast = (msk .|. swizzle z) :* skp
67 | otherwise = buildTable (i+1) (msk .|. swizzle c) skp'
68 where c = nindex i
69 skp' | c == z = nlen - i - 2
70 | otherwise = skp
71 swizzle k = 1 `shiftL` (fromIntegral k .&. 0x3f)
72 scan !i
73 | i > ldiff = []
74 | c == z && candidateMatch 0 = i : scan (i + nlen)
75 | otherwise = scan (i + delta)
76 where c = hindex (i + nlast)
77 candidateMatch !j
78 | j >= nlast = True
79 | hindex (i+j) /= nindex j = False
80 | otherwise = candidateMatch (j+1)
81 delta | nextInPattern = nlen + 1
82 | c == z = skip + 1
83 | otherwise = 1
84 where nextInPattern = mask .&. swizzle (hindex' (i+nlen)) == 0
85 !(mask :* skip) = buildTable 0 0 (nlen-2)
86 scanOne c = loop 0
87 where loop !i | i >= hlen = []
88 | hindex i == c = i : loop (i+1)
89 | otherwise = loop (i+1)
90{-# INLINE indices #-}