{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE StandaloneDeriving #-}

-- | Strict variants of 'FingerTree' operations.
module Data.FingerTree.Strict
  ( StrictFingerTree,
    fromStrict,
    forceToStrict,

    -- * Construction
    empty,
    singleton,
    (<|),
    (|>),
    (><),
    fromList,

    -- * Deconstruction
    null,

    -- ** Examining the ends
    viewl,
    viewr,

    -- ** Search
    SearchResult (..),
    search,

    -- ** Splitting

    -- | These functions are special cases of 'search'.
    split,
    takeUntil,
    dropUntil,

    -- * Transformation
    reverse,

    -- ** Maps
    fmap',
    unsafeFmap,
    -- Re-export from "Data.FingerTree"
    Measured (..),
    ViewL (..),
    ViewR (..),
  )
where

import Data.FingerTree (Measured (..), ViewL (..), ViewR (..))
import qualified Data.FingerTree as FT
import Data.Foldable (foldl', toList)
import Data.Unit.Strict (forceElemsToWHNF)
import GHC.Generics (Generic)
import NoThunks.Class (NoThunks (..), noThunksInValues)
import Prelude hiding (null, reverse)

infixr 5 ><

infixr 5 <|

infixl 5 |>

-- | A @newtype@ wrapper around a 'FT.FingerTree', representing a finger tree
-- that is strict in its values.
--
-- This strictness is not enforced at the type level, but rather by the
-- construction functions in this module. These functions essentially just
-- wrap the original "Data.FingerTree" functions while forcing the provided
-- value to WHNF.
newtype StrictFingerTree v a = SFT {StrictFingerTree v a -> FingerTree v a
fromStrict :: FT.FingerTree v a}
  deriving (StrictFingerTree v a -> StrictFingerTree v a -> Bool
(StrictFingerTree v a -> StrictFingerTree v a -> Bool)
-> (StrictFingerTree v a -> StrictFingerTree v a -> Bool)
-> Eq (StrictFingerTree v a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall v a.
Eq a =>
StrictFingerTree v a -> StrictFingerTree v a -> Bool
/= :: StrictFingerTree v a -> StrictFingerTree v a -> Bool
$c/= :: forall v a.
Eq a =>
StrictFingerTree v a -> StrictFingerTree v a -> Bool
== :: StrictFingerTree v a -> StrictFingerTree v a -> Bool
$c== :: forall v a.
Eq a =>
StrictFingerTree v a -> StrictFingerTree v a -> Bool
Eq, Eq (StrictFingerTree v a)
Eq (StrictFingerTree v a)
-> (StrictFingerTree v a -> StrictFingerTree v a -> Ordering)
-> (StrictFingerTree v a -> StrictFingerTree v a -> Bool)
-> (StrictFingerTree v a -> StrictFingerTree v a -> Bool)
-> (StrictFingerTree v a -> StrictFingerTree v a -> Bool)
-> (StrictFingerTree v a -> StrictFingerTree v a -> Bool)
-> (StrictFingerTree v a
    -> StrictFingerTree v a -> StrictFingerTree v a)
-> (StrictFingerTree v a
    -> StrictFingerTree v a -> StrictFingerTree v a)
-> Ord (StrictFingerTree v a)
StrictFingerTree v a -> StrictFingerTree v a -> Bool
StrictFingerTree v a -> StrictFingerTree v a -> Ordering
StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall v a. Ord a => Eq (StrictFingerTree v a)
forall v a.
Ord a =>
StrictFingerTree v a -> StrictFingerTree v a -> Bool
forall v a.
Ord a =>
StrictFingerTree v a -> StrictFingerTree v a -> Ordering
forall v a.
Ord a =>
StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
min :: StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
$cmin :: forall v a.
Ord a =>
StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
max :: StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
$cmax :: forall v a.
Ord a =>
StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
>= :: StrictFingerTree v a -> StrictFingerTree v a -> Bool
$c>= :: forall v a.
Ord a =>
StrictFingerTree v a -> StrictFingerTree v a -> Bool
> :: StrictFingerTree v a -> StrictFingerTree v a -> Bool
$c> :: forall v a.
Ord a =>
StrictFingerTree v a -> StrictFingerTree v a -> Bool
<= :: StrictFingerTree v a -> StrictFingerTree v a -> Bool
$c<= :: forall v a.
Ord a =>
StrictFingerTree v a -> StrictFingerTree v a -> Bool
< :: StrictFingerTree v a -> StrictFingerTree v a -> Bool
$c< :: forall v a.
Ord a =>
StrictFingerTree v a -> StrictFingerTree v a -> Bool
compare :: StrictFingerTree v a -> StrictFingerTree v a -> Ordering
$ccompare :: forall v a.
Ord a =>
StrictFingerTree v a -> StrictFingerTree v a -> Ordering
$cp1Ord :: forall v a. Ord a => Eq (StrictFingerTree v a)
Ord, Int -> StrictFingerTree v a -> ShowS
[StrictFingerTree v a] -> ShowS
StrictFingerTree v a -> String
(Int -> StrictFingerTree v a -> ShowS)
-> (StrictFingerTree v a -> String)
-> ([StrictFingerTree v a] -> ShowS)
-> Show (StrictFingerTree v a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall v a. Show a => Int -> StrictFingerTree v a -> ShowS
forall v a. Show a => [StrictFingerTree v a] -> ShowS
forall v a. Show a => StrictFingerTree v a -> String
showList :: [StrictFingerTree v a] -> ShowS
$cshowList :: forall v a. Show a => [StrictFingerTree v a] -> ShowS
show :: StrictFingerTree v a -> String
$cshow :: forall v a. Show a => StrictFingerTree v a -> String
showsPrec :: Int -> StrictFingerTree v a -> ShowS
$cshowsPrec :: forall v a. Show a => Int -> StrictFingerTree v a -> ShowS
Show)

deriving newtype instance Foldable (StrictFingerTree v)

deriving newtype instance (Measured v a) => Measured v (StrictFingerTree v a)

instance NoThunks a => NoThunks (StrictFingerTree v a) where
  showTypeOf :: Proxy (StrictFingerTree v a) -> String
showTypeOf Proxy (StrictFingerTree v a)
_ = String
"StrictFingerTree"
  wNoThunks :: Context -> StrictFingerTree v a -> IO (Maybe ThunkInfo)
wNoThunks Context
ctxt = Context -> [a] -> IO (Maybe ThunkInfo)
forall a. NoThunks a => Context -> [a] -> IO (Maybe ThunkInfo)
noThunksInValues Context
ctxt ([a] -> IO (Maybe ThunkInfo))
-> (StrictFingerTree v a -> [a])
-> StrictFingerTree v a
-> IO (Maybe ThunkInfo)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StrictFingerTree v a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList

{-------------------------------------------------------------------------------
  Construction
-------------------------------------------------------------------------------}

-- | /O(1)/. The empty sequence.
empty :: Measured v a => StrictFingerTree v a
empty :: StrictFingerTree v a
empty = FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
forall v a. Measured v a => FingerTree v a
FT.empty

-- | /O(1)/. A singleton sequence.
singleton :: Measured v a => a -> StrictFingerTree v a
singleton :: a -> StrictFingerTree v a
singleton !a
a = FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT (a -> FingerTree v a
forall v a. Measured v a => a -> FingerTree v a
FT.singleton a
a)

-- | /O(n)/. Create a sequence from a finite list of elements.
-- The opposite operation 'toList' is supplied by the 'Foldable' instance.
fromList :: (Measured v a) => [a] -> StrictFingerTree v a
fromList :: [a] -> StrictFingerTree v a
fromList ![a]
xs = (StrictFingerTree v a -> a -> StrictFingerTree v a)
-> StrictFingerTree v a -> [a] -> StrictFingerTree v a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' StrictFingerTree v a -> a -> StrictFingerTree v a
forall v a.
Measured v a =>
StrictFingerTree v a -> a -> StrictFingerTree v a
(|>) (FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
forall v a. Measured v a => FingerTree v a
FT.empty) [a]
xs

-- | /O(1)/. Add an element to the left end of a sequence.
-- Mnemonic: a triangle with the single element at the pointy end.
(<|) :: (Measured v a) => a -> StrictFingerTree v a -> StrictFingerTree v a
(!a
a) <| :: a -> StrictFingerTree v a -> StrictFingerTree v a
<| SFT FingerTree v a
ft = FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT (a
a a -> FingerTree v a -> FingerTree v a
forall v a. Measured v a => a -> FingerTree v a -> FingerTree v a
FT.<| FingerTree v a
ft)

-- | /O(1)/. Add an element to the right end of a sequence.
-- Mnemonic: a triangle with the single element at the pointy end.
(|>) :: (Measured v a) => StrictFingerTree v a -> a -> StrictFingerTree v a
SFT FingerTree v a
ft |> :: StrictFingerTree v a -> a -> StrictFingerTree v a
|> (!a
a) = FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT (FingerTree v a
ft FingerTree v a -> a -> FingerTree v a
forall v a. Measured v a => FingerTree v a -> a -> FingerTree v a
FT.|> a
a)

-- | /O(log(min(n1,n2)))/. Concatenate two sequences.
(><) ::
  (Measured v a) =>
  StrictFingerTree v a ->
  StrictFingerTree v a ->
  StrictFingerTree v a
SFT FingerTree v a
ft >< :: StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
>< SFT FingerTree v a
ft' = FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT (FingerTree v a
ft FingerTree v a -> FingerTree v a -> FingerTree v a
forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
FT.>< FingerTree v a
ft')

-- | Convert a 'FT.FingerTree' into a 'StrictFingerTree' by forcing each element
-- to WHNF.
forceToStrict :: FT.FingerTree v a -> StrictFingerTree v a
forceToStrict :: FingerTree v a -> StrictFingerTree v a
forceToStrict FingerTree v a
xs = FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT (FingerTree v a -> FingerTree v a
forall (t :: * -> *) a. Foldable t => t a -> t a
forceElemsToWHNF FingerTree v a
xs)

{-------------------------------------------------------------------------------
  Deconstruction
-------------------------------------------------------------------------------}

-- | /O(1)/. Is this the empty sequence?
null :: StrictFingerTree v a -> Bool
null :: StrictFingerTree v a -> Bool
null (SFT FingerTree v a
ft) = FingerTree v a -> Bool
forall v a. FingerTree v a -> Bool
FT.null FingerTree v a
ft

{-------------------------------------------------------------------------------
  Examining the ends
-------------------------------------------------------------------------------}

-- | /O(1)/. Analyse the left end of a sequence.
viewl ::
  (Measured v a) =>
  StrictFingerTree v a ->
  ViewL (StrictFingerTree v) a
viewl :: StrictFingerTree v a -> ViewL (StrictFingerTree v) a
viewl (SFT FingerTree v a
ft) = case FingerTree v a -> ViewL (FingerTree v) a
forall v a.
Measured v a =>
FingerTree v a -> ViewL (FingerTree v) a
FT.viewl FingerTree v a
ft of
  ViewL (FingerTree v) a
EmptyL -> ViewL (StrictFingerTree v) a
forall (s :: * -> *) a. ViewL s a
EmptyL
  a
a :< FingerTree v a
ft' -> a
a a -> StrictFingerTree v a -> ViewL (StrictFingerTree v) a
forall (s :: * -> *) a. a -> s a -> ViewL s a
:< FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
ft'

-- | /O(1)/. Analyse the right end of a sequence.
viewr ::
  (Measured v a) =>
  StrictFingerTree v a ->
  ViewR (StrictFingerTree v) a
viewr :: StrictFingerTree v a -> ViewR (StrictFingerTree v) a
viewr (SFT FingerTree v a
ft) = case FingerTree v a -> ViewR (FingerTree v) a
forall v a.
Measured v a =>
FingerTree v a -> ViewR (FingerTree v) a
FT.viewr FingerTree v a
ft of
  ViewR (FingerTree v) a
EmptyR -> ViewR (StrictFingerTree v) a
forall (s :: * -> *) a. ViewR s a
EmptyR
  FingerTree v a
ft' :> a
a -> FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
ft' StrictFingerTree v a -> a -> ViewR (StrictFingerTree v) a
forall (s :: * -> *) a. s a -> a -> ViewR s a
:> a
a

{-------------------------------------------------------------------------------
  Search
-------------------------------------------------------------------------------}

-- | A result of 'search', attempting to find a point where a predicate
-- on splits of the sequence changes from 'False' to 'True'.
--
-- @since 0.1.2.0
data SearchResult v a
  = -- | A tree opened at a particular element: the prefix to the
    -- left, the element, and the suffix to the right.
    Position !(StrictFingerTree v a) !a !(StrictFingerTree v a)
  | -- | A position to the left of the sequence, indicating that the
    -- predicate is 'True' at both ends.
    OnLeft
  | -- | A position to the right of the sequence, indicating that the
    -- predicate is 'False' at both ends.
    OnRight
  | -- | No position in the tree, returned if the predicate is 'True'
    -- at the left end and 'False' at the right end.  This will not
    -- occur if the predicate in monotonic on the tree.
    Nowhere
  deriving (SearchResult v a -> SearchResult v a -> Bool
(SearchResult v a -> SearchResult v a -> Bool)
-> (SearchResult v a -> SearchResult v a -> Bool)
-> Eq (SearchResult v a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall v a. Eq a => SearchResult v a -> SearchResult v a -> Bool
/= :: SearchResult v a -> SearchResult v a -> Bool
$c/= :: forall v a. Eq a => SearchResult v a -> SearchResult v a -> Bool
== :: SearchResult v a -> SearchResult v a -> Bool
$c== :: forall v a. Eq a => SearchResult v a -> SearchResult v a -> Bool
Eq, Eq (SearchResult v a)
Eq (SearchResult v a)
-> (SearchResult v a -> SearchResult v a -> Ordering)
-> (SearchResult v a -> SearchResult v a -> Bool)
-> (SearchResult v a -> SearchResult v a -> Bool)
-> (SearchResult v a -> SearchResult v a -> Bool)
-> (SearchResult v a -> SearchResult v a -> Bool)
-> (SearchResult v a -> SearchResult v a -> SearchResult v a)
-> (SearchResult v a -> SearchResult v a -> SearchResult v a)
-> Ord (SearchResult v a)
SearchResult v a -> SearchResult v a -> Bool
SearchResult v a -> SearchResult v a -> Ordering
SearchResult v a -> SearchResult v a -> SearchResult v a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall v a. Ord a => Eq (SearchResult v a)
forall v a. Ord a => SearchResult v a -> SearchResult v a -> Bool
forall v a.
Ord a =>
SearchResult v a -> SearchResult v a -> Ordering
forall v a.
Ord a =>
SearchResult v a -> SearchResult v a -> SearchResult v a
min :: SearchResult v a -> SearchResult v a -> SearchResult v a
$cmin :: forall v a.
Ord a =>
SearchResult v a -> SearchResult v a -> SearchResult v a
max :: SearchResult v a -> SearchResult v a -> SearchResult v a
$cmax :: forall v a.
Ord a =>
SearchResult v a -> SearchResult v a -> SearchResult v a
>= :: SearchResult v a -> SearchResult v a -> Bool
$c>= :: forall v a. Ord a => SearchResult v a -> SearchResult v a -> Bool
> :: SearchResult v a -> SearchResult v a -> Bool
$c> :: forall v a. Ord a => SearchResult v a -> SearchResult v a -> Bool
<= :: SearchResult v a -> SearchResult v a -> Bool
$c<= :: forall v a. Ord a => SearchResult v a -> SearchResult v a -> Bool
< :: SearchResult v a -> SearchResult v a -> Bool
$c< :: forall v a. Ord a => SearchResult v a -> SearchResult v a -> Bool
compare :: SearchResult v a -> SearchResult v a -> Ordering
$ccompare :: forall v a.
Ord a =>
SearchResult v a -> SearchResult v a -> Ordering
$cp1Ord :: forall v a. Ord a => Eq (SearchResult v a)
Ord, Int -> SearchResult v a -> ShowS
[SearchResult v a] -> ShowS
SearchResult v a -> String
(Int -> SearchResult v a -> ShowS)
-> (SearchResult v a -> String)
-> ([SearchResult v a] -> ShowS)
-> Show (SearchResult v a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall v a. Show a => Int -> SearchResult v a -> ShowS
forall v a. Show a => [SearchResult v a] -> ShowS
forall v a. Show a => SearchResult v a -> String
showList :: [SearchResult v a] -> ShowS
$cshowList :: forall v a. Show a => [SearchResult v a] -> ShowS
show :: SearchResult v a -> String
$cshow :: forall v a. Show a => SearchResult v a -> String
showsPrec :: Int -> SearchResult v a -> ShowS
$cshowsPrec :: forall v a. Show a => Int -> SearchResult v a -> ShowS
Show, (forall x. SearchResult v a -> Rep (SearchResult v a) x)
-> (forall x. Rep (SearchResult v a) x -> SearchResult v a)
-> Generic (SearchResult v a)
forall x. Rep (SearchResult v a) x -> SearchResult v a
forall x. SearchResult v a -> Rep (SearchResult v a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall v a x. Rep (SearchResult v a) x -> SearchResult v a
forall v a x. SearchResult v a -> Rep (SearchResult v a) x
$cto :: forall v a x. Rep (SearchResult v a) x -> SearchResult v a
$cfrom :: forall v a x. SearchResult v a -> Rep (SearchResult v a) x
Generic)

-- | Convert from an 'FT.SearchResult' (the data type from "Data.FingerTree")
-- to a 'SearchResult' (the data type from this module).
fromOriginalSearchResult :: FT.SearchResult v a -> SearchResult v a
fromOriginalSearchResult :: SearchResult v a -> SearchResult v a
fromOriginalSearchResult (FT.Position FingerTree v a
left a
a FingerTree v a
right) =
  StrictFingerTree v a
-> a -> StrictFingerTree v a -> SearchResult v a
forall v a.
StrictFingerTree v a
-> a -> StrictFingerTree v a -> SearchResult v a
Position (FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
left) a
a (FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
right)
fromOriginalSearchResult SearchResult v a
FT.OnLeft = SearchResult v a
forall v a. SearchResult v a
OnLeft
fromOriginalSearchResult SearchResult v a
FT.OnRight = SearchResult v a
forall v a. SearchResult v a
OnRight
fromOriginalSearchResult SearchResult v a
FT.Nowhere = SearchResult v a
forall v a. SearchResult v a
Nowhere

-- | /O(log(min(i,n-i)))/. Search a sequence for a point where a predicate
-- on splits of the sequence changes from 'False' to 'True'.
--
-- The argument @p@ is a relation between the measures of the two
-- sequences that could be appended together to form the sequence @t@.
-- If the relation is 'False' at the leftmost split and 'True' at the
-- rightmost split, i.e.
--
-- @not (p 'mempty' ('measure' t)) && p ('measure' t) 'mempty'@
--
-- then there must exist an element @x@ in the sequence such that @p@
-- is 'False' for the split immediately before @x@ and 'True' for the
-- split just after it:
--
-- <<images/search.svg>>
--
-- In this situation, @'search' p t@ returns such an element @x@ and the
-- pieces @l@ and @r@ of the sequence to its left and right respectively.
-- That is, it returns @'Position' l x r@ such that
--
-- * @l >< (x <| r) = t@
--
-- * @not (p (measure l) (measure (x <| r))@
--
-- * @p (measure (l |> x)) (measure r)@
--
-- For predictable results, one should ensure that there is only one such
-- point, i.e. that the predicate is /monotonic/ on @t@.
--
-- @since 0.1.2.0
search ::
  (Measured v a) =>
  (v -> v -> Bool) ->
  StrictFingerTree v a ->
  SearchResult v a
search :: (v -> v -> Bool) -> StrictFingerTree v a -> SearchResult v a
search v -> v -> Bool
p (SFT FingerTree v a
ft) = SearchResult v a -> SearchResult v a
forall v a. SearchResult v a -> SearchResult v a
fromOriginalSearchResult ((v -> v -> Bool) -> FingerTree v a -> SearchResult v a
forall v a.
Measured v a =>
(v -> v -> Bool) -> FingerTree v a -> SearchResult v a
FT.search v -> v -> Bool
p FingerTree v a
ft)

{-------------------------------------------------------------------------------
  Splitting
-------------------------------------------------------------------------------}

-- | /O(log(min(i,n-i)))/. Split a sequence at a point where the predicate
-- on the accumulated measure of the prefix changes from 'False' to 'True'.
--
-- For predictable results, one should ensure that there is only one such
-- point, i.e. that the predicate is /monotonic/.
split ::
  (Measured v a) =>
  (v -> Bool) ->
  StrictFingerTree v a ->
  (StrictFingerTree v a, StrictFingerTree v a)
split :: (v -> Bool)
-> StrictFingerTree v a
-> (StrictFingerTree v a, StrictFingerTree v a)
split v -> Bool
p (SFT FingerTree v a
ft) = (FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
left, FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
right)
  where
    (FingerTree v a
left, FingerTree v a
right) = (v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a)
forall v a.
Measured v a =>
(v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a)
FT.split v -> Bool
p FingerTree v a
ft

-- | /O(log(min(i,n-i)))/.
-- Given a monotonic predicate @p@, @'takeUntil' p t@ is the largest
-- prefix of @t@ whose measure does not satisfy @p@.
--
-- *  @'takeUntil' p t = 'fst' ('split' p t)@
takeUntil ::
  (Measured v a) =>
  (v -> Bool) ->
  StrictFingerTree v a ->
  StrictFingerTree v a
takeUntil :: (v -> Bool) -> StrictFingerTree v a -> StrictFingerTree v a
takeUntil v -> Bool
p (SFT FingerTree v a
ft) = FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT ((v -> Bool) -> FingerTree v a -> FingerTree v a
forall v a.
Measured v a =>
(v -> Bool) -> FingerTree v a -> FingerTree v a
FT.takeUntil v -> Bool
p FingerTree v a
ft)

-- | /O(log(min(i,n-i)))/.
-- Given a monotonic predicate @p@, @'dropUntil' p t@ is the rest of @t@
-- after removing the largest prefix whose measure does not satisfy @p@.
--
-- * @'dropUntil' p t = 'snd' ('split' p t)@
dropUntil ::
  (Measured v a) =>
  (v -> Bool) ->
  StrictFingerTree v a ->
  StrictFingerTree v a
dropUntil :: (v -> Bool) -> StrictFingerTree v a -> StrictFingerTree v a
dropUntil v -> Bool
p (SFT FingerTree v a
ft) = FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT ((v -> Bool) -> FingerTree v a -> FingerTree v a
forall v a.
Measured v a =>
(v -> Bool) -> FingerTree v a -> FingerTree v a
FT.dropUntil v -> Bool
p FingerTree v a
ft)

{-------------------------------------------------------------------------------
  Transformation
-------------------------------------------------------------------------------}

-- | /O(n)/. The reverse of a sequence.
reverse :: (Measured v a) => StrictFingerTree v a -> StrictFingerTree v a
reverse :: StrictFingerTree v a -> StrictFingerTree v a
reverse (SFT FingerTree v a
ft) = FingerTree v a -> StrictFingerTree v a
forall v a. FingerTree v a -> StrictFingerTree v a
SFT (FingerTree v a -> FingerTree v a
forall v a. Measured v a => FingerTree v a -> FingerTree v a
FT.reverse FingerTree v a
ft)

{-------------------------------------------------------------------------------
  Maps
-------------------------------------------------------------------------------}

-- | Like 'fmap', but with constraints on the element types.
fmap' ::
  (Measured v1 a1, Measured v2 a2) =>
  (a1 -> a2) ->
  StrictFingerTree v1 a1 ->
  StrictFingerTree v2 a2
fmap' :: (a1 -> a2) -> StrictFingerTree v1 a1 -> StrictFingerTree v2 a2
fmap' a1 -> a2
f (SFT FingerTree v1 a1
ft) = FingerTree v2 a2 -> StrictFingerTree v2 a2
forall v a. FingerTree v a -> StrictFingerTree v a
forceToStrict ((a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2
forall v1 a1 v2 a2.
(Measured v1 a1, Measured v2 a2) =>
(a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2
FT.fmap' a1 -> a2
f FingerTree v1 a1
ft)

-- | Like 'fmap', but safe only if the function preserves the measure.
unsafeFmap :: (a -> b) -> StrictFingerTree v a -> StrictFingerTree v b
unsafeFmap :: (a -> b) -> StrictFingerTree v a -> StrictFingerTree v b
unsafeFmap a -> b
f (SFT FingerTree v a
ft) = FingerTree v b -> StrictFingerTree v b
forall v a. FingerTree v a -> StrictFingerTree v a
forceToStrict ((a -> b) -> FingerTree v a -> FingerTree v b
forall a b v. (a -> b) -> FingerTree v a -> FingerTree v b
FT.unsafeFmap a -> b
f FingerTree v a
ft)