-- | Radix operations on `String`.
module MCSP.Data.String.Extra.Radix (
    -- * Prefix
    stripPrefix,
    isPrefixOf,
    commonPrefix,
    splitCommonPrefix,

    -- * Infix
    stripInfix,
    isInfixOf,

    -- * Suffix
    stripSuffix,
    isSuffixOf,
    suffixes,
) where

import Data.Bool (Bool (..), otherwise)
import Data.Eq (Eq, (/=), (==))
import Data.Function ((.))
import Data.Int (Int)
import Data.List.Extra (find, firstJust)
import Data.Maybe (Maybe (Just, Nothing), fromMaybe, isJust)
import Data.Ord (min)
import Data.Tuple.Extra (fst3)
import GHC.Num ((+), (-))

import MCSP.Data.String (String (..), drop, length, splitAt, take, unsafeIndex, unsafeSlice)

-- ---------------------- --
-- String prefix analysis --

-- | /O(min(m,n))/ Removes the given prefix from a string.
--
-- Returns `Nothing` if the string does not start with the prefix given, or `Just` the string after
-- the prefix.
--
-- >>> stripPrefix "foo" "foobar"
-- Just bar
--
-- >>> stripPrefix "foo" "foo"
-- Just
--
-- >>> stripPrefix "foo" "barfoo"
-- Nothing
stripPrefix :: Eq a => String a -> String a -> Maybe (String a)
stripPrefix :: forall a. Eq a => String a -> String a -> Maybe (String a)
stripPrefix String a
p String a
str
    | String a
s0 String a -> String a -> Bool
forall a. Eq a => a -> a -> Bool
== String a
p = String a -> Maybe (String a)
forall a. a -> Maybe a
Just String a
s1
    | Bool
otherwise = Maybe (String a)
forall a. Maybe a
Nothing
  where
    (String a
s0, String a
s1) = Int -> String a -> (String a, String a)
forall a. Int -> String a -> (String a, String a)
splitAt (String a -> Int
forall a. String a -> Int
length String a
p) String a
str
{-# INLINEABLE stripPrefix #-}

-- | /O(min(m,n))/ Returns `True` iff the first string is a prefix of the second.
--
-- >>> "Hello" `isPrefixOf` "Hello World!"
-- True
--
-- >>> "Hello" `isPrefixOf` "Wello Horld!"
-- False
isPrefixOf :: Eq a => String a -> String a -> Bool
String a
p isPrefixOf :: forall a. Eq a => String a -> String a -> Bool
`isPrefixOf` String a
str = Int -> String a -> String a
forall a. Int -> String a -> String a
take (String a -> Int
forall a. String a -> Int
length String a
p) String a
str String a -> String a -> Bool
forall a. Eq a => a -> a -> Bool
== String a
p

-- | /O(min(m,n))/ The length of maximum common prefix of two string.
--
-- >>> commonPrefixLength "abc" "abd"
-- 2
commonPrefixLength :: Eq a => String a -> String a -> Int
commonPrefixLength :: forall a. Eq a => String a -> String a -> Int
commonPrefixLength String a
lhs String a
rhs = Int -> Maybe Int -> Int
forall a. a -> Maybe a -> a
fromMaybe Int
n (forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a
find @[] Int -> Bool
notMatching [Int]
indices)
  where
    n :: Int
n = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min (String a -> Int
forall a. String a -> Int
length String a
lhs) (String a -> Int
forall a. String a -> Int
length String a
rhs)
    indices :: [Int]
indices = [Int
Item [Int]
0 .. Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1]
    -- SAFETY: index i is in range [0, n = min(lhs, rhs)) and is guaranteed to be in bounds for
    -- both strings
    notMatching :: Int -> Bool
notMatching Int
i = String a -> Int -> a
forall a. String a -> Int -> a
unsafeIndex String a
lhs Int
i a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= String a -> Int -> a
forall a. String a -> Int -> a
unsafeIndex String a
rhs Int
i
{-# INLINEABLE commonPrefixLength #-}

-- | /O(min(m,n))/ The maximum common prefix of two strings.
--
-- >>> commonPrefix "abc" "abd"
-- ab
--
-- >>> commonPrefix "xyz" "xyz"
-- xyz
--
-- >>> commonPrefix "def" "ghi"
-- <BLANKLINE>
commonPrefix :: Eq a => String a -> String a -> String a
commonPrefix :: forall a. Eq a => String a -> String a -> String a
commonPrefix String a
lhs String a
rhs = (String a, String a, String a) -> String a
forall a b c. (a, b, c) -> a
fst3 (String a -> String a -> (String a, String a, String a)
forall a.
Eq a =>
String a -> String a -> (String a, String a, String a)
splitCommonPrefix String a
lhs String a
rhs)
{-# INLINE commonPrefix #-}

-- | /O(min(m,n))/ Returns the maximum common prefix of two strings and the remainder of each string.
--
-- Note that @splitCommonPrefix a b@ is equivalent to
-- @let p = commonPrefix a b in (p, fromJust (splitPrefix p a), fromJust (splitPrefix p b))@, but
-- slightly more efficient and cannot fail.
--
-- >>> splitCommonPrefix "abc" "abd"
-- (ab,c,d)
--
-- >>> splitCommonPrefix "xyz" "xyz"
-- (xyz,,)
--
-- >>> splitCommonPrefix "def" "ghi"
-- (,def,ghi)
splitCommonPrefix :: Eq a => String a -> String a -> (String a, String a, String a)
splitCommonPrefix :: forall a.
Eq a =>
String a -> String a -> (String a, String a, String a)
splitCommonPrefix String a
lhs String a
rhs =
    -- SAFETY: commonPrefixLength is guaranteed to resolve to a length not bigger than
    -- any of the strings
    ( Int -> Int -> String a -> String a
forall a. Int -> Int -> String a -> String a
unsafeSlice Int
0 Int
prefix String a
lhs,
      -- SAFETY: again, '0 <= prefix <= length lhs' and '0 <= prefix <= length rhs'
      Int -> Int -> String a -> String a
forall a. Int -> Int -> String a -> String a
unsafeSlice Int
prefix (String a -> Int
forall a. String a -> Int
length String a
lhs Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
prefix) String a
lhs,
      Int -> Int -> String a -> String a
forall a. Int -> Int -> String a -> String a
unsafeSlice Int
prefix (String a -> Int
forall a. String a -> Int
length String a
rhs Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
prefix) String a
rhs
    )
  where
    prefix :: Int
prefix = String a -> String a -> Int
forall a. Eq a => String a -> String a -> Int
commonPrefixLength String a
lhs String a
rhs
{-# INLINE splitCommonPrefix #-}

-- --------------------- --
-- String infix analysis --

-- | /O(n m)/ Return the the string before (prefix) and after (suffix) the search string, or
-- `Nothing` if the search string is not present.
--
-- A result of @`Just` (s1, s2) = `stripInfix` s r@ means that
-- @s1 `Strings.Data.String.++` r `Strings.Data.String.++` s2 `==` s@.
--
-- >>> stripInfix "el" "Hello"
-- Just (H,lo)
--
-- >>> stripInfix "World!" "Hello"
-- Nothing
--
-- >>> stripInfix "si" "mississipi"
-- Just (mis,ssipi)
--
-- >>> stripInfix "chat" "hat"
-- Nothing
--
-- >>> stripInfix "word" "word"
-- Just (,)
stripInfix :: Eq a => String a -> String a -> Maybe (String a, String a)
stripInfix :: forall a.
Eq a =>
String a -> String a -> Maybe (String a, String a)
stripInfix String a
needle String a
haystack = (Int -> Maybe (String a, String a))
-> [Int] -> Maybe (String a, String a)
forall a b. (a -> Maybe b) -> [a] -> Maybe b
firstJust ((String a, String a, String a) -> Maybe (String a, String a)
matchingNeedle ((String a, String a, String a) -> Maybe (String a, String a))
-> (Int -> (String a, String a, String a))
-> Int
-> Maybe (String a, String a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> (String a, String a, String a)
split) [Int
Item [Int]
0 .. Int
Item [Int]
n]
  where
    r :: Int
r = String a -> Int
forall a. String a -> Int
length String a
needle
    n :: Int
n = String a -> Int
forall a. String a -> Int
length String a
haystack Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
r
    matchingNeedle :: (String a, String a, String a) -> Maybe (String a, String a)
matchingNeedle (String a
a, String a
candidate, String a
c)
        | String a
candidate String a -> String a -> Bool
forall a. Eq a => a -> a -> Bool
== String a
needle = (String a, String a) -> Maybe (String a, String a)
forall a. a -> Maybe a
Just (String a
a, String a
c)
        | Bool
otherwise = Maybe (String a, String a)
forall a. Maybe a
Nothing
    -- SAFETY: given '0 <= i <= n` and `n = length str - length radix`, we'll have that always
    -- `0 <= i + r <= length str` and `n - i = length str - r - i`, both being inbounds
    split :: Int -> (String a, String a, String a)
split Int
i =
        ( Int -> Int -> String a -> String a
forall a. Int -> Int -> String a -> String a
unsafeSlice Int
0 Int
i String a
haystack, -- part before infix (prefix)
          Int -> Int -> String a -> String a
forall a. Int -> Int -> String a -> String a
unsafeSlice Int
i Int
r String a
haystack, -- candidate for infix
          Int -> Int -> String a -> String a
forall a. Int -> Int -> String a -> String a
unsafeSlice (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
r) (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i) String a
haystack -- after matched infix (suffix)
        )

-- | /O(n m)/  Check if the first string is contained anywhere within the second string.
--
-- >>> isInfixOf "Haskell" "I really like Haskell."
-- True
--
-- >>> isInfixOf "Ial" "I really like Haskell."
-- False
isInfixOf :: Eq a => String a -> String a -> Bool
String a
r isInfixOf :: forall a. Eq a => String a -> String a -> Bool
`isInfixOf` String a
str = Maybe (String a, String a) -> Bool
forall a. Maybe a -> Bool
isJust (String a -> String a -> Maybe (String a, String a)
forall a.
Eq a =>
String a -> String a -> Maybe (String a, String a)
stripInfix String a
r String a
str)
{-# INLINEABLE isInfixOf #-}

-- ---------------------- --
-- String suffix analysis --

-- | /O(min(m,n))/ Returns the prefix of the second string if its suffix matches the first string.
--
-- Returns `Nothing` if the string does not end with the suffix given, or `Just` the string before
-- the suffix.
--
-- >>> stripSuffix "bar" "foobar"
-- Just foo
--
-- >>> stripSuffix "" "baz"
-- Just baz
--
-- >>> stripSuffix "foo" "quux"
-- Nothing
stripSuffix :: Eq a => String a -> String a -> Maybe (String a)
stripSuffix :: forall a. Eq a => String a -> String a -> Maybe (String a)
stripSuffix String a
s String a
str
    | String a
s1 String a -> String a -> Bool
forall a. Eq a => a -> a -> Bool
== String a
s = String a -> Maybe (String a)
forall a. a -> Maybe a
Just String a
s0
    | Bool
otherwise = Maybe (String a)
forall a. Maybe a
Nothing
  where
    (String a
s0, String a
s1) = Int -> String a -> (String a, String a)
forall a. Int -> String a -> (String a, String a)
splitAt (String a -> Int
forall a. String a -> Int
length String a
str Int -> Int -> Int
forall a. Num a => a -> a -> a
- String a -> Int
forall a. String a -> Int
length String a
s) String a
str
{-# INLINEABLE stripSuffix #-}

-- | /O(min(m,n))/ Returns `True` iff the first string is a prefix of the second.
--
-- >>> "ld!" `isSuffixOf` "Hello World!"
-- True
--
-- >>> "World" `isSuffixOf` "Hello World!"
-- False
isSuffixOf :: Eq a => String a -> String a -> Bool
String a
s isSuffixOf :: forall a. Eq a => String a -> String a -> Bool
`isSuffixOf` String a
str = Int -> String a -> String a
forall a. Int -> String a -> String a
drop (String a -> Int
forall a. String a -> Int
length String a
str Int -> Int -> Int
forall a. Num a => a -> a -> a
- String a -> Int
forall a. String a -> Int
length String a
s) String a
str String a -> String a -> Bool
forall a. Eq a => a -> a -> Bool
== String a
s

-- | /O(n)/ Extract all non-empty suffixes of a string.
--
-- >>> suffixes "Hello"
-- [Hello,ello,llo,lo,o]
suffixes :: String a -> [String a]
suffixes :: forall a. String a -> [String a]
suffixes s :: String a
s@(a
_ :< String a
rest) = String a
s String a -> [String a] -> [String a]
forall a. a -> [a] -> [a]
: String a -> [String a]
forall a. String a -> [String a]
suffixes String a
rest
suffixes String a
Null = []
{-# INLINE suffixes #-}