libghc-stringsearch-doc 0.3.6.4-3 / usr / share / doc / libghc-stringsearch-doc / html / stringsearch.txt

-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Fast searching, splitting and replacing of ByteStrings
--   
--   This package provides several functions to quickly search for
--   substrings in strict or lazy ByteStrings. It also provides functions
--   for breaking or splitting on substrings and replacing all occurrences
--   of a substring (the first in case of overlaps) with another. GHC
--   before 6.10 are no longer supported, other compilers only if they
--   support BangPatterns. If you need it to work with other compilers,
--   send a feature request.
@package stringsearch
@version 0.3.6.4


-- | Simultaneous search for multiple patterns in a lazy <a>ByteString</a>
--   using the Karp-Rabin algorithm.
--   
--   A description of the algorithm for a single pattern can be found at
--   <a>http://www-igm.univ-mlv.fr/~lecroq/string/node5.html#SECTION0050</a>.
module Data.ByteString.Lazy.Search.KarpRabin

-- | <tt><a>indicesOfAny</a></tt> finds all occurrences of any of several
--   non-empty strict patterns in a lazy target string. If no non-empty
--   patterns are given, the result is an empty list. Otherwise the result
--   list contains the pairs of all indices where any of the (non-empty)
--   patterns start and the list of all patterns starting at that index,
--   the patterns being represented by their (zero-based) position in the
--   pattern list. Empty patterns are filtered out before processing
--   begins.
indicesOfAny :: [ByteString] -> ByteString -> [(Int64, [Int])]


-- | Simultaneous search for multiple patterns in a strict
--   <a>ByteString</a> using the Karp-Rabin algorithm.
--   
--   A description of the algorithm for a single pattern can be found at
--   <a>http://www-igm.univ-mlv.fr/~lecroq/string/node5.html#SECTION0050</a>.
module Data.ByteString.Search.KarpRabin

-- | <tt><a>indicesOfAny</a></tt> finds all occurrences of any of several
--   non-empty patterns in a strict target string. If no non-empty patterns
--   are given, the result is an empty list. Otherwise the result list
--   contains the pairs of all indices where any of the (non-empty)
--   patterns start and the list of all patterns starting at that index,
--   the patterns being represented by their (zero-based) position in the
--   pattern list. Empty patterns are filtered out before processing
--   begins.
indicesOfAny :: [ByteString] -> ByteString -> [(Int, [Int])]


-- | Fast search of strict <a>ByteString</a> values using the
--   Knuth-Morris-Pratt algorithm.
--   
--   A description of the algorithm can be found at
--   <a>http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm</a>.
--   
--   Original authors: Justin Bailey (jgbailey at gmail.com) and Chris
--   Kuklewicz (haskell at list.mightyreason.com).
module Data.ByteString.Search.KMP

-- | <tt><a>indices</a></tt> finds the starting indices of all possibly
--   overlapping occurrences of the pattern in the target string. If the
--   pattern is empty, the result is <tt>[0 .. <a>length</a> target]</tt>.
indices :: ByteString -> ByteString -> [Int]

-- | <tt><a>nonOverlappingIndices</a></tt> finds the starting indices of
--   all non-overlapping occurrences of the pattern in the target string.
--   It is more efficient than removing indices from the list produced by
--   <a>indices</a>.
nonOverlappingIndices :: ByteString -> ByteString -> [Int]


-- | Fast non-overlapping Knuth-Morris-Pratt search of both strict and lazy
--   <a>ByteString</a> values.
--   
--   A description of the algorithm can be found at
--   <a>http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm</a>.
--   
--   Original authors: Justin Bailey (jgbailey at gmail.com) and Chris
--   Kuklewicz (haskell at list.mightyreason.com).

-- | <i>Deprecated: Use the new interface instead </i>
module Data.ByteString.Search.KnuthMorrisPratt

-- | <tt><a>matchLL</a></tt> finds the starting indices of all
--   <i>non-overlapping</i> occurrences of the pattern in the target
--   string. It is a simple wrapper around <a>nonOverlappingIndices</a>
--   strictifying the pattern.
matchLL :: ByteString -> ByteString -> [Int64]

-- | <tt><a>matchLS</a></tt> finds the starting indices of all
--   <i>non-overlapping</i> occurrences of the pattern in the target
--   string. It is a simple wrapper around <a>nonOverlappingIndices</a>
--   strictifying the pattern.
matchLS :: ByteString -> ByteString -> [Int]

-- | <tt><a>matchSS</a></tt> finds the starting indices of all
--   <i>non-overlapping</i> occurrences of the pattern in the target
--   string. It is an alias for <a>nonOverlappingIndices</a>.
matchSS :: ByteString -> ByteString -> [Int]

-- | <tt><a>matchSL</a></tt> finds the starting indices of all
--   <i>non-overlapping</i> occurrences of the pattern in the target
--   string. It is an alias for <a>nonOverlappingIndices</a>.
matchSL :: ByteString -> ByteString -> [Int64]


-- | Fast search of lazy <a>ByteString</a> values using the
--   Knuth-Morris-Pratt algorithm.
--   
--   A description of the algorithm can be found at
--   <a>http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm</a>.
--   
--   Original authors: Justin Bailey (jgbailey at gmail.com) and Chris
--   Kuklewicz (haskell at list.mightyreason.com).
module Data.ByteString.Lazy.Search.KMP

-- | <tt><a>indices</a></tt> finds the starting indices of all possibly
--   overlapping occurrences of the pattern in the target string. If the
--   pattern is empty, the result is <tt>[0 .. <a>length</a> target]</tt>.
indices :: ByteString -> ByteString -> [Int64]

-- | <tt><a>nonOverlappingIndices</a></tt> finds the starting indices of
--   all non-overlapping occurrences of the pattern in the target string.
--   It is more efficient than removing indices from the list produced by
--   <a>indices</a>.
nonOverlappingIndices :: ByteString -> ByteString -> [Int64]

-- | <tt><a>strictify</a></tt> transforms a lazy <a>ByteString</a> into a
--   strict <a>ByteString</a>, to make it a suitable pattern for the
--   searching functions.
strictify :: ByteString -> ByteString


-- | Class for values to be substituted into strict and lazy
--   <a>ByteString</a>s by the <tt>replace</tt> functions defined in this
--   package.
module Data.ByteString.Search.Substitution

-- | Type class of meaningful substitutions for replace functions on
--   ByteStrings. Instances for strict and lazy ByteStrings are provided
--   here.
class Substitution a
substitution :: Substitution a => a -> ([ByteString] -> [ByteString])
prependCycle :: Substitution a => a -> (ByteString -> ByteString)
instance Substitution ByteString
instance Substitution ByteString


-- | Fast search of strict <a>ByteString</a> values. Breaking, splitting
--   and replacing using a deterministic finite automaton.
module Data.ByteString.Search.DFA

-- | <tt><a>indices</a></tt> finds the starting indices of all possibly
--   overlapping occurrences of the pattern in the target string. If the
--   pattern is empty, the result is <tt>[0 .. <a>length</a> target]</tt>.
indices :: ByteString -> ByteString -> [Int]

-- | <tt><a>nonOverlappingIndices</a></tt> finds the starting indices of
--   all non-overlapping occurrences of the pattern in the target string.
--   It is more efficient than removing indices from the list produced by
--   <a>indices</a>.
nonOverlappingIndices :: ByteString -> ByteString -> [Int]

-- | <tt><a>breakOn</a> pattern target</tt> splits <tt>target</tt> at the
--   first occurrence of <tt>pattern</tt>. If the pattern does not occur in
--   the target, the second component of the result is empty, otherwise it
--   starts with <tt>pattern</tt>. If the pattern is empty, the first
--   component is empty.
--   
--   <pre>
--   <a>uncurry</a> <a>append</a> . <a>breakOn</a> pattern = <a>id</a>
--   </pre>
breakOn :: ByteString -> ByteString -> (ByteString, ByteString)

-- | <tt><a>breakAfter</a> pattern target</tt> splits <tt>target</tt>
--   behind the first occurrence of <tt>pattern</tt>. An empty second
--   component means that either the pattern does not occur in the target
--   or the first occurrence of pattern is at the very end of target. To
--   discriminate between those cases, use e.g. <a>isSuffixOf</a>.
--   
--   <pre>
--   <a>uncurry</a> <a>append</a> . <a>breakAfter</a> pattern = <a>id</a>
--   </pre>
breakAfter :: ByteString -> ByteString -> (ByteString, ByteString)

-- | <tt><a>replace</a> pat sub text</tt> replaces all (non-overlapping)
--   occurrences of <tt>pat</tt> in <tt>text</tt> with <tt>sub</tt>. If
--   occurrences of <tt>pat</tt> overlap, the first occurrence that does
--   not overlap with a replaced previous occurrence is substituted.
--   Occurrences of <tt>pat</tt> arising from a substitution will not be
--   substituted. For example:
--   
--   <pre>
--   <a>replace</a> "ana" "olog" "banana" = "bologna"
--   <a>replace</a> "ana" "o" "bananana" = "bono"
--   <a>replace</a> "aab" "abaa" "aaabb" = "aabaab"
--   </pre>
--   
--   The result is a <i>lazy</i> <a>ByteString</a>, which is lazily
--   produced, without copying. Equality of pattern and substitution is not
--   checked, but
--   
--   <pre>
--   <a>concat</a> . <a>toChunks</a> $ <a>replace</a> pat pat text == text
--   </pre>
--   
--   holds. If the pattern is empty but not the substitution, the result is
--   equivalent to (were they <a>String</a>s) <tt><a>cycle</a> sub</tt>.
--   
--   For non-empty <tt>pat</tt> and <tt>sub</tt> a strict
--   <a>ByteString</a>,
--   
--   <pre>
--   <a>fromChunks</a> . <a>intersperse</a> sub . <a>split</a> pat = <a>replace</a> pat sub
--   </pre>
--   
--   and analogous relations hold for other types of <tt>sub</tt>.
replace :: Substitution rep => ByteString -> rep -> ByteString -> ByteString

-- | <tt><a>split</a> pattern target</tt> splits <tt>target</tt> at each
--   (non-overlapping) occurrence of <tt>pattern</tt>, removing
--   <tt>pattern</tt>. If <tt>pattern</tt> is empty, the result is an
--   infinite list of empty <a>ByteString</a>s, if <tt>target</tt> is empty
--   but not <tt>pattern</tt>, the result is an empty list, otherwise the
--   following relations hold:
--   
--   <pre>
--   <a>concat</a> . <a>intersperse</a> pat . <a>split</a> pat = <a>id</a>,
--   <a>length</a> (<a>split</a> pattern target) ==
--               <a>length</a> (<a>nonOverlappingIndices</a> pattern target) + 1,
--   </pre>
--   
--   no fragment in the result contains an occurrence of <tt>pattern</tt>.
split :: ByteString -> ByteString -> [ByteString]

-- | <tt><a>splitKeepEnd</a> pattern target</tt> splits <tt>target</tt>
--   after each (non-overlapping) occurrence of <tt>pattern</tt>. If
--   <tt>pattern</tt> is empty, the result is an infinite list of empty
--   <a>ByteString</a>s, otherwise the following relations hold:
--   
--   <pre>
--   <a>concat</a> . <a>splitKeepEnd</a> pattern = <a>id</a>,
--   </pre>
--   
--   all fragments in the result except possibly the last end with
--   <tt>pattern</tt>, no fragment contains more than one occurrence of
--   <tt>pattern</tt>.
splitKeepEnd :: ByteString -> ByteString -> [ByteString]

-- | <tt><a>splitKeepFront</a></tt> is like <a>splitKeepEnd</a>, except
--   that <tt>target</tt> is split before each occurrence of
--   <tt>pattern</tt> and hence all fragments with the possible exception
--   of the first begin with <tt>pattern</tt>. No fragment contains more
--   than one non-overlapping occurrence of <tt>pattern</tt>.
splitKeepFront :: ByteString -> ByteString -> [ByteString]


-- | Fast overlapping Boyer-Moore search of lazy <a>ByteString</a> values.
--   Breaking, splitting and replacing using the Boyer-Moore algorithm.
--   
--   Descriptions of the algorithm can be found at
--   <a>http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140</a>
--   and
--   <a>http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm</a>
--   
--   Original authors: Daniel Fischer (daniel.is.fischer at googlemail.com)
--   and Chris Kuklewicz (haskell at list.mightyreason.com).
module Data.ByteString.Lazy.Search

-- | <tt><a>indices</a></tt> finds the starting indices of all possibly
--   overlapping occurrences of the pattern in the target string. If the
--   pattern is empty, the result is <tt>[0 .. <a>length</a> target]</tt>.
indices :: ByteString -> ByteString -> [Int64]

-- | <tt><a>nonOverlappingIndices</a></tt> finds the starting indices of
--   all non-overlapping occurrences of the pattern in the target string.
--   It is more efficient than removing indices from the list produced by
--   <a>indices</a>.
nonOverlappingIndices :: ByteString -> ByteString -> [Int64]

-- | <tt><a>breakOn</a> pattern target</tt> splits <tt>target</tt> at the
--   first occurrence of <tt>pattern</tt>. If the pattern does not occur in
--   the target, the second component of the result is empty, otherwise it
--   starts with <tt>pattern</tt>. If the pattern is empty, the first
--   component is empty. For a non-empty pattern, the first component is
--   generated lazily, thus the first parts of it can be available before
--   the pattern has been found or determined to be absent.
--   
--   <pre>
--   <a>uncurry</a> <a>append</a> . <a>breakOn</a> pattern = <a>id</a>
--   </pre>
breakOn :: ByteString -> ByteString -> (ByteString, ByteString)

-- | <tt><a>breakAfter</a> pattern target</tt> splits <tt>target</tt>
--   behind the first occurrence of <tt>pattern</tt>. An empty second
--   component means that either the pattern does not occur in the target
--   or the first occurrence of pattern is at the very end of target. If
--   you need to discriminate between those cases, use breakFindAfter. If
--   the pattern is empty, the first component is empty. For a non-empty
--   pattern, the first component is generated lazily, thus the first parts
--   of it can be available before the pattern has been found or determined
--   to be absent.
--   
--   <pre>
--   <a>uncurry</a> <a>append</a> . <a>breakAfter</a> pattern = <a>id</a>
--   </pre>
breakAfter :: ByteString -> ByteString -> (ByteString, ByteString)

-- | <tt><a>breakFindAfter</a></tt> does the same as <a>breakAfter</a> but
--   additionally indicates whether the pattern is present in the target.
--   
--   <pre>
--   <a>fst</a> . <a>breakFindAfter</a> pat = <a>breakAfter</a> pat
--   </pre>
breakFindAfter :: ByteString -> ByteString -> ((ByteString, ByteString), Bool)

-- | <tt><a>replace</a> pat sub text</tt> replaces all (non-overlapping)
--   occurrences of <tt>pat</tt> in <tt>text</tt> with <tt>sub</tt>. If
--   occurrences of <tt>pat</tt> overlap, the first occurrence that does
--   not overlap with a replaced previous occurrence is substituted.
--   Occurrences of <tt>pat</tt> arising from a substitution will not be
--   substituted. For example:
--   
--   <pre>
--   <a>replace</a> "ana" "olog" "banana" = "bologna"
--   <a>replace</a> "ana" "o" "bananana" = "bono"
--   <a>replace</a> "aab" "abaa" "aaabb" = "aabaab"
--   </pre>
--   
--   The result is a lazy <a>ByteString</a>, which is lazily produced,
--   without copying. Equality of pattern and substitution is not checked,
--   but
--   
--   <pre>
--   <a>replace</a> pat pat text == text
--   </pre>
--   
--   holds (the internal structure is generally different). If the pattern
--   is empty but not the substitution, the result is equivalent to (were
--   they <a>String</a>s) <tt>cycle sub</tt>.
--   
--   For non-empty <tt>pat</tt> and <tt>sub</tt> a lazy <a>ByteString</a>,
--   
--   <pre>
--   <a>concat</a> . <a>intersperse</a> sub . <a>split</a> pat = <a>replace</a> pat sub
--   </pre>
--   
--   and analogous relations hold for other types of <tt>sub</tt>.
replace :: Substitution rep => ByteString -> rep -> ByteString -> ByteString

-- | <tt><a>split</a> pattern target</tt> splits <tt>target</tt> at each
--   (non-overlapping) occurrence of <tt>pattern</tt>, removing
--   <tt>pattern</tt>. If <tt>pattern</tt> is empty, the result is an
--   infinite list of empty <a>ByteString</a>s, if <tt>target</tt> is empty
--   but not <tt>pattern</tt>, the result is an empty list, otherwise the
--   following relations hold (where <tt>patL</tt> is the lazy
--   <a>ByteString</a> corresponding to <tt>pat</tt>):
--   
--   <pre>
--   <a>concat</a> . <a>intersperse</a> patL . <a>split</a> pat = <a>id</a>,
--   <a>length</a> (<a>split</a> pattern target) ==
--               <a>length</a> (<a>nonOverlappingIndices</a> pattern target) + 1,
--   </pre>
--   
--   no fragment in the result contains an occurrence of <tt>pattern</tt>.
split :: ByteString -> ByteString -> [ByteString]

-- | <tt><a>splitKeepEnd</a> pattern target</tt> splits <tt>target</tt>
--   after each (non-overlapping) occurrence of <tt>pattern</tt>. If
--   <tt>pattern</tt> is empty, the result is an infinite list of empty
--   <a>ByteString</a>s, otherwise the following relations hold:
--   
--   <pre>
--   <a>concat</a> . <a>splitKeepEnd</a> pattern = <a>id</a>,
--   </pre>
--   
--   all fragments in the result except possibly the last end with
--   <tt>pattern</tt>, no fragment contains more than one occurrence of
--   <tt>pattern</tt>.
splitKeepEnd :: ByteString -> ByteString -> [ByteString]

-- | <tt><a>splitKeepFront</a></tt> is like <a>splitKeepEnd</a>, except
--   that <tt>target</tt> is split before each occurrence of
--   <tt>pattern</tt> and hence all fragments with the possible exception
--   of the first begin with <tt>pattern</tt>. No fragment contains more
--   than one non-overlapping occurrence of <tt>pattern</tt>.
splitKeepFront :: ByteString -> ByteString -> [ByteString]

-- | <tt><a>strictify</a></tt> converts a lazy <a>ByteString</a> to a
--   strict <a>ByteString</a> to make it a suitable pattern.
strictify :: ByteString -> ByteString


-- | Fast search of lazy <a>ByteString</a> values. Breaking, splitting and
--   replacing using a deterministic finite automaton.
module Data.ByteString.Lazy.Search.DFA

-- | <tt><a>indices</a></tt> finds the starting indices of all possibly
--   overlapping occurrences of the pattern in the target string. If the
--   pattern is empty, the result is <tt>[0 .. <a>length</a> target]</tt>.
indices :: ByteString -> ByteString -> [Int64]

-- | <tt><a>nonOverlappingIndices</a></tt> finds the starting indices of
--   all non-overlapping occurrences of the pattern in the target string.
--   It is more efficient than removing indices from the list produced by
--   <a>indices</a>.
nonOverlappingIndices :: ByteString -> ByteString -> [Int64]

-- | <tt><a>breakOn</a> pattern target</tt> splits <tt>target</tt> at the
--   first occurrence of <tt>pattern</tt>. If the pattern does not occur in
--   the target, the second component of the result is empty, otherwise it
--   starts with <tt>pattern</tt>. If the pattern is empty, the first
--   component is empty. For a non-empty pattern, the first component is
--   generated lazily, thus the first parts of it can be available before
--   the pattern has been found or determined to be absent.
--   
--   <pre>
--   <a>uncurry</a> <a>append</a> . <a>breakOn</a> pattern = <a>id</a>
--   </pre>
breakOn :: ByteString -> ByteString -> (ByteString, ByteString)

-- | <tt><a>breakAfter</a> pattern target</tt> splits <tt>target</tt>
--   behind the first occurrence of <tt>pattern</tt>. An empty second
--   component means that either the pattern does not occur in the target
--   or the first occurrence of pattern is at the very end of target. If
--   you need to discriminate between those cases, use breakFindAfter. If
--   the pattern is empty, the first component is empty. For a non-empty
--   pattern, the first component is generated lazily, thus the first parts
--   of it can be available before the pattern has been found or determined
--   to be absent. <tt> <a>uncurry</a> <a>append</a> . <a>breakAfter</a>
--   pattern = <a>id</a> </tt>
breakAfter :: ByteString -> ByteString -> (ByteString, ByteString)

-- | <tt><a>breakFindAfter</a></tt> does the same as <a>breakAfter</a> but
--   additionally indicates whether the pattern is present in the target.
--   
--   <pre>
--   <a>fst</a> . <a>breakFindAfter</a> pat = <a>breakAfter</a> pat
--   </pre>
breakFindAfter :: ByteString -> ByteString -> ((ByteString, ByteString), Bool)

-- | <tt><a>replace</a> pat sub text</tt> replaces all (non-overlapping)
--   occurrences of <tt>pat</tt> in <tt>text</tt> with <tt>sub</tt>. If
--   occurrences of <tt>pat</tt> overlap, the first occurrence that does
--   not overlap with a replaced previous occurrence is substituted.
--   Occurrences of <tt>pat</tt> arising from a substitution will not be
--   substituted. For example:
--   
--   <pre>
--   <a>replace</a> "ana" "olog" "banana" = "bologna"
--   <a>replace</a> "ana" "o" "bananana" = "bono"
--   <a>replace</a> "aab" "abaa" "aaabb" = "aabaab"
--   </pre>
--   
--   The result is a lazy <a>ByteString</a>, which is lazily produced,
--   without copying. Equality of pattern and substitution is not checked,
--   but
--   
--   <pre>
--   <a>replace</a> pat pat text == text
--   </pre>
--   
--   holds (the internal structure is generally different). If the pattern
--   is empty but not the substitution, the result is equivalent to (were
--   they <a>String</a>s) <tt>cycle sub</tt>.
--   
--   For non-empty <tt>pat</tt> and <tt>sub</tt> a lazy <a>ByteString</a>,
--   
--   <pre>
--   <a>concat</a> . <a>intersperse</a> sub . <a>split</a> pat = <a>replace</a> pat sub
--   </pre>
--   
--   and analogous relations hold for other types of <tt>sub</tt>.
replace :: Substitution rep => ByteString -> rep -> ByteString -> ByteString

-- | <tt><a>split</a> pattern target</tt> splits <tt>target</tt> at each
--   (non-overlapping) occurrence of <tt>pattern</tt>, removing
--   <tt>pattern</tt>. If <tt>pattern</tt> is empty, the result is an
--   infinite list of empty <a>ByteString</a>s, if <tt>target</tt> is empty
--   but not <tt>pattern</tt>, the result is an empty list, otherwise the
--   following relations hold (where <tt>patL</tt> is the lazy
--   <a>ByteString</a> corresponding to <tt>pat</tt>):
--   
--   <pre>
--   <a>concat</a> . <a>intersperse</a> patL . <a>split</a> pat = <a>id</a>,
--   <a>length</a> (<a>split</a> pattern target) ==
--               <a>length</a> (<a>nonOverlappingIndices</a> pattern target) + 1,
--   </pre>
--   
--   no fragment in the result contains an occurrence of <tt>pattern</tt>.
split :: ByteString -> ByteString -> [ByteString]

-- | <tt><a>splitKeepEnd</a> pattern target</tt> splits <tt>target</tt>
--   after each (non-overlapping) occurrence of <tt>pattern</tt>. If
--   <tt>pattern</tt> is empty, the result is an infinite list of empty
--   <a>ByteString</a>s, otherwise the following relations hold:
--   
--   <pre>
--   <a>concat</a> . <a>splitKeepEnd</a> pattern = 'id,'
--   </pre>
--   
--   all fragments in the result except possibly the last end with
--   <tt>pattern</tt>, no fragment contains more than one occurrence of
--   <tt>pattern</tt>.
splitKeepEnd :: ByteString -> ByteString -> [ByteString]

-- | <tt><a>splitKeepFront</a></tt> is like <a>splitKeepEnd</a>, except
--   that <tt>target</tt> is split before each occurrence of
--   <tt>pattern</tt> and hence all fragments with the possible exception
--   of the first begin with <tt>pattern</tt>. No fragment contains more
--   than one non-overlapping occurrence of <tt>pattern</tt>.
splitKeepFront :: ByteString -> ByteString -> [ByteString]


-- | Fast overlapping Boyer-Moore search of both strict and lazy
--   <tt>ByteString</tt> values.
--   
--   Descriptions of the algorithm can be found at
--   <a>http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140</a>
--   and
--   <a>http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm</a>
--   
--   Original authors: Daniel Fischer (daniel.is.fischer at googlemail.com)
--   and Chris Kuklewicz (haskell at list.mightyreason.com).

-- | <i>Deprecated: Use the new interface instead </i>
module Data.ByteString.Search.BoyerMoore

-- | <tt><a>matchLL</a></tt> finds the starting indices of all possibly
--   overlapping occurrences of the pattern in the target string. It is a
--   simple wrapper for <a>indices</a>. If the pattern is empty, the result
--   is <tt>[0 .. <a>length</a> target]</tt>.
matchLL :: ByteString -> ByteString -> [Int64]

-- | <tt><a>matchLS</a></tt> finds the starting indices of all possibly
--   overlapping occurrences of the pattern in the target string. It is a
--   simple wrapper for <a>indices</a>. If the pattern is empty, the result
--   is <tt>[0 .. <a>length</a> target]</tt>.
matchLS :: ByteString -> ByteString -> [Int]

-- | <tt><a>matchSL</a></tt> finds the starting indices of all possibly
--   overlapping occurrences of the pattern in the target string. It is an
--   alias for <a>indices</a>. If the pattern is empty, the result is
--   <tt>[0 .. <a>length</a> target]</tt>.
matchSL :: ByteString -> ByteString -> [Int64]

-- | <tt><a>matchSS</a></tt> finds the starting indices of all possibly
--   overlapping occurrences of the pattern in the target string. It is an
--   alias for <a>indices</a>. If the pattern is empty, the result is
--   <tt>[0 .. <a>length</a> target]</tt>.
matchSS :: ByteString -> ByteString -> [Int]


-- | Fast overlapping Boyer-Moore search of strict <a>ByteString</a>
--   values. Breaking, splitting and replacing using the Boyer-Moore
--   algorithm.
--   
--   Descriptions of the algorithm can be found at
--   <a>http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140</a>
--   and
--   <a>http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm</a>
--   
--   Original authors: Daniel Fischer (daniel.is.fischer at googlemail.com)
--   and Chris Kuklewicz (haskell at list.mightyreason.com).
module Data.ByteString.Search

-- | <tt><a>indices</a></tt> finds the starting indices of all possibly
--   overlapping occurrences of the pattern in the target string. If the
--   pattern is empty, the result is <tt>[0 .. <a>length</a> target]</tt>.
--   
--   In general, <tt><a>not</a> . <a>null</a> $ <a>indices</a> pat
--   target</tt> is a much more efficient version of <a>isInfixOf</a>.
indices :: ByteString -> ByteString -> [Int]

-- | <tt><a>nonOverlappingIndices</a></tt> finds the starting indices of
--   all non-overlapping occurrences of the pattern in the target string.
--   It is more efficient than removing indices from the list produced by
--   <a>indices</a>.
nonOverlappingIndices :: ByteString -> ByteString -> [Int]

-- | <tt><a>breakOn</a> pattern target</tt> splits <tt>target</tt> at the
--   first occurrence of <tt>pattern</tt>. If the pattern does not occur in
--   the target, the second component of the result is empty, otherwise it
--   starts with <tt>pattern</tt>. If the pattern is empty, the first
--   component is empty.
--   
--   <pre>
--   <a>uncurry</a> <a>append</a> . <a>breakOn</a> pattern = <a>id</a>
--   </pre>
breakOn :: ByteString -> ByteString -> (ByteString, ByteString)

-- | <tt><a>breakAfter</a> pattern target</tt> splits <tt>target</tt>
--   behind the first occurrence of <tt>pattern</tt>. An empty second
--   component means that either the pattern does not occur in the target
--   or the first occurrence of pattern is at the very end of target. To
--   discriminate between those cases, use e.g. <a>isSuffixOf</a>.
--   
--   <pre>
--   <a>uncurry</a> <a>append</a> . <a>breakAfter</a> pattern = <a>id</a>
--   </pre>
breakAfter :: ByteString -> ByteString -> (ByteString, ByteString)

-- | <tt><a>replace</a> pat sub text</tt> replaces all (non-overlapping)
--   occurrences of <tt>pat</tt> in <tt>text</tt> with <tt>sub</tt>. If
--   occurrences of <tt>pat</tt> overlap, the first occurrence that does
--   not overlap with a replaced previous occurrence is substituted.
--   Occurrences of <tt>pat</tt> arising from a substitution will not be
--   substituted. For example:
--   
--   <pre>
--   <a>replace</a> "ana" "olog" "banana" = "bologna"
--   <a>replace</a> "ana" "o" "bananana" = "bono"
--   <a>replace</a> "aab" "abaa" "aaabb" = "aabaab"
--   </pre>
--   
--   The result is a <i>lazy</i> <a>ByteString</a>, which is lazily
--   produced, without copying. Equality of pattern and substitution is not
--   checked, but
--   
--   <pre>
--   (<a>concat</a> . <a>toChunks</a> $ <a>replace</a> pat pat text) == text
--   </pre>
--   
--   holds. If the pattern is empty but not the substitution, the result is
--   equivalent to (were they <a>String</a>s) <tt><a>cycle</a> sub</tt>.
--   
--   For non-empty <tt>pat</tt> and <tt>sub</tt> a strict
--   <a>ByteString</a>,
--   
--   <pre>
--   <a>fromChunks</a> . <a>intersperse</a> sub . <a>split</a> pat = <a>replace</a> pat sub
--   </pre>
--   
--   and analogous relations hold for other types of <tt>sub</tt>.
replace :: Substitution rep => ByteString -> rep -> ByteString -> ByteString

-- | <tt><a>split</a> pattern target</tt> splits <tt>target</tt> at each
--   (non-overlapping) occurrence of <tt>pattern</tt>, removing
--   <tt>pattern</tt>. If <tt>pattern</tt> is empty, the result is an
--   infinite list of empty <a>ByteString</a>s, if <tt>target</tt> is empty
--   but not <tt>pattern</tt>, the result is an empty list, otherwise the
--   following relations hold:
--   
--   <pre>
--   <a>concat</a> . <a>intersperse</a> pat . <a>split</a> pat = <a>id</a>,
--   <a>length</a> (<a>split</a> pattern target) ==
--               <a>length</a> (<a>nonOverlappingIndices</a> pattern target) + 1,
--   </pre>
--   
--   no fragment in the result contains an occurrence of <tt>pattern</tt>.
split :: ByteString -> ByteString -> [ByteString]

-- | <tt><a>splitKeepEnd</a> pattern target</tt> splits <tt>target</tt>
--   after each (non-overlapping) occurrence of <tt>pattern</tt>. If
--   <tt>pattern</tt> is empty, the result is an infinite list of empty
--   <a>ByteString</a>s, otherwise the following relations hold:
--   
--   <pre>
--   <a>concat</a> . <a>splitKeepEnd</a> pattern = <a>id</a>,
--   </pre>
--   
--   all fragments in the result except possibly the last end with
--   <tt>pattern</tt>, no fragment contains more than one occurrence of
--   <tt>pattern</tt>.
splitKeepEnd :: ByteString -> ByteString -> [ByteString]

-- | <tt><a>splitKeepFront</a></tt> is like <a>splitKeepEnd</a>, except
--   that <tt>target</tt> is split before each occurrence of
--   <tt>pattern</tt> and hence all fragments with the possible exception
--   of the first begin with <tt>pattern</tt>. No fragment contains more
--   than one non-overlapping occurrence of <tt>pattern</tt>.
splitKeepFront :: ByteString -> ByteString -> [ByteString]