Bryan O'Sullivan avatar Bryan O'Sullivan committed 4230af0

Implement split in terms of indices and splitAtWord.

Comments (0)

Files changed (1)

Data/Text/Lazy.hs

 -- copies to create substrings; they just construct new 'Text's that
 -- are slices of the original.
 
--- | /O(m)*O(n)/ Break a 'Text' into pieces separated by the first
--- 'Text' argument, consuming the delimiter.  An empty delimiter is
+-- | /O(m+n)/ Break a 'Text' into pieces separated by the first
+-- 'Text' argument, consuming the delimiter. An empty delimiter is
 -- invalid, and will cause an error to be raised.
 --
 -- Examples:
 --
 -- > intercalate s . split s         == id
 -- > split (singleton c)             == splitBy (==c)
+--
+-- In (unlikely) bad cases, this function's time complexity degrades
+-- towards /O(n*m)/.
 split :: Text                   -- ^ Text to split on
       -> Text                   -- ^ Input text
       -> [Text]
-split pat src0
-    | l == 0    = emptyError "split"
-    | l == 1    = splitBy (== (head pat)) src0
-    | otherwise = go src0
+split pat src
+    | null pat        = emptyError "split"
+    | isSingleton pat = splitBy (== head pat) src
+    | otherwise       = go 0 (indices pat src) src
   where
-    l      = length pat
-    go src = search 0 src
-      where
-        search !n !s
-            | null s             = [src]      -- not found
-            | pat `isPrefixOf` s = take n src : go (drop l s)
-            | otherwise          = search (n+1) (tail s)
+    go  _ []     cs = [cs]
+    go !s (x:xs) cs = let h :*: t = splitAtWord (x-s) cs
+                      in  h : go (s+x) xs t
 {-# INLINE [1] split #-}
 
 {-# RULES
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.