{-# 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 (toList)
import qualified Data.Foldable as F (foldl')
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 {forall v a. StrictFingerTree v a -> FingerTree v a
fromStrict :: FT.FingerTree v a}
  deriving stock (StrictFingerTree v a -> StrictFingerTree v a -> Bool
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, StrictFingerTree v a -> StrictFingerTree v a -> Bool
StrictFingerTree v a -> StrictFingerTree v a -> Ordering
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
Ord, Int -> StrictFingerTree v a -> ShowS
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 (forall a. Eq a => a -> StrictFingerTree v a -> Bool
forall a. Num a => StrictFingerTree v a -> a
forall a. Ord a => StrictFingerTree v a -> a
forall m. Monoid m => StrictFingerTree v m -> m
forall a. StrictFingerTree v a -> Bool
forall a. StrictFingerTree v a -> Int
forall a. StrictFingerTree v a -> [a]
forall a. (a -> a -> a) -> StrictFingerTree v a -> a
forall v a. Eq a => a -> StrictFingerTree v a -> Bool
forall v a. Num a => StrictFingerTree v a -> a
forall v a. Ord a => StrictFingerTree v a -> a
forall m a. Monoid m => (a -> m) -> StrictFingerTree v a -> m
forall v m. Monoid m => StrictFingerTree v m -> m
forall v a. StrictFingerTree v a -> Bool
forall v a. StrictFingerTree v a -> Int
forall v a. StrictFingerTree v a -> [a]
forall b a. (b -> a -> b) -> b -> StrictFingerTree v a -> b
forall a b. (a -> b -> b) -> b -> StrictFingerTree v a -> b
forall v a. (a -> a -> a) -> StrictFingerTree v a -> a
forall v m a. Monoid m => (a -> m) -> StrictFingerTree v a -> m
forall v b a. (b -> a -> b) -> b -> StrictFingerTree v a -> b
forall v a b. (a -> b -> b) -> b -> StrictFingerTree v a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: forall a. Num a => StrictFingerTree v a -> a
$cproduct :: forall v a. Num a => StrictFingerTree v a -> a
sum :: forall a. Num a => StrictFingerTree v a -> a
$csum :: forall v a. Num a => StrictFingerTree v a -> a
minimum :: forall a. Ord a => StrictFingerTree v a -> a
$cminimum :: forall v a. Ord a => StrictFingerTree v a -> a
maximum :: forall a. Ord a => StrictFingerTree v a -> a
$cmaximum :: forall v a. Ord a => StrictFingerTree v a -> a
elem :: forall a. Eq a => a -> StrictFingerTree v a -> Bool
$celem :: forall v a. Eq a => a -> StrictFingerTree v a -> Bool
length :: forall a. StrictFingerTree v a -> Int
$clength :: forall v a. StrictFingerTree v a -> Int
null :: forall a. StrictFingerTree v a -> Bool
$cnull :: forall v a. StrictFingerTree v a -> Bool
toList :: forall a. StrictFingerTree v a -> [a]
$ctoList :: forall v a. StrictFingerTree v a -> [a]
foldl1 :: forall a. (a -> a -> a) -> StrictFingerTree v a -> a
$cfoldl1 :: forall v a. (a -> a -> a) -> StrictFingerTree v a -> a
foldr1 :: forall a. (a -> a -> a) -> StrictFingerTree v a -> a
$cfoldr1 :: forall v a. (a -> a -> a) -> StrictFingerTree v a -> a
foldl' :: forall b a. (b -> a -> b) -> b -> StrictFingerTree v a -> b
$cfoldl' :: forall v b a. (b -> a -> b) -> b -> StrictFingerTree v a -> b
foldl :: forall b a. (b -> a -> b) -> b -> StrictFingerTree v a -> b
$cfoldl :: forall v b a. (b -> a -> b) -> b -> StrictFingerTree v a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> StrictFingerTree v a -> b
$cfoldr' :: forall v a b. (a -> b -> b) -> b -> StrictFingerTree v a -> b
foldr :: forall a b. (a -> b -> b) -> b -> StrictFingerTree v a -> b
$cfoldr :: forall v a b. (a -> b -> b) -> b -> StrictFingerTree v a -> b
foldMap' :: forall m a. Monoid m => (a -> m) -> StrictFingerTree v a -> m
$cfoldMap' :: forall v m a. Monoid m => (a -> m) -> StrictFingerTree v a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> StrictFingerTree v a -> m
$cfoldMap :: forall v m a. Monoid m => (a -> m) -> StrictFingerTree v a -> m
fold :: forall m. Monoid m => StrictFingerTree v m -> m
$cfold :: forall v m. Monoid m => StrictFingerTree v m -> m
Foldable, NonEmpty (StrictFingerTree v a) -> StrictFingerTree v a
StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
forall b.
Integral b =>
b -> StrictFingerTree v a -> StrictFingerTree v a
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
forall v a.
Measured v a =>
NonEmpty (StrictFingerTree v a) -> StrictFingerTree v a
forall v a.
Measured v a =>
StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
forall v a b.
(Measured v a, Integral b) =>
b -> StrictFingerTree v a -> StrictFingerTree v a
stimes :: forall b.
Integral b =>
b -> StrictFingerTree v a -> StrictFingerTree v a
$cstimes :: forall v a b.
(Measured v a, Integral b) =>
b -> StrictFingerTree v a -> StrictFingerTree v a
sconcat :: NonEmpty (StrictFingerTree v a) -> StrictFingerTree v a
$csconcat :: forall v a.
Measured v a =>
NonEmpty (StrictFingerTree v a) -> StrictFingerTree v a
<> :: StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
$c<> :: forall v a.
Measured v a =>
StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
Semigroup, StrictFingerTree v a
[StrictFingerTree v a] -> StrictFingerTree v a
StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
forall a.
Semigroup a -> a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
forall v a. Measured v a => Semigroup (StrictFingerTree v a)
forall v a. Measured v a => StrictFingerTree v a
forall v a.
Measured v a =>
[StrictFingerTree v a] -> StrictFingerTree v a
forall v a.
Measured v a =>
StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
mconcat :: [StrictFingerTree v a] -> StrictFingerTree v a
$cmconcat :: forall v a.
Measured v a =>
[StrictFingerTree v a] -> StrictFingerTree v a
mappend :: StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
$cmappend :: forall v a.
Measured v a =>
StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
mempty :: StrictFingerTree v a
$cmempty :: forall v a. Measured v a => StrictFingerTree v a
Monoid, Measured v)

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 = forall a. NoThunks a => Context -> [a] -> IO (Maybe ThunkInfo)
noThunksInValues Context
ctxt forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) a. Foldable t => t a -> [a]
toList

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

-- | /O(1)/. The empty sequence.
empty :: Measured v a => StrictFingerTree v a
empty :: forall v a. Measured v a => StrictFingerTree v a
empty = forall v a. FingerTree v a -> StrictFingerTree v a
SFT 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 :: forall v a. Measured v a => a -> StrictFingerTree v a
singleton !a
a = forall v a. FingerTree v a -> StrictFingerTree v a
SFT (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 :: forall v a. Measured v a => [a] -> StrictFingerTree v a
fromList ![a]
xs = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' forall v a.
Measured v a =>
StrictFingerTree v a -> a -> StrictFingerTree v a
(|>) (forall v a. FingerTree v a -> StrictFingerTree v a
SFT 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) <| :: forall v a.
Measured v a =>
a -> StrictFingerTree v a -> StrictFingerTree v a
<| SFT FingerTree v a
ft = forall v a. FingerTree v a -> StrictFingerTree v a
SFT (a
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 |> :: forall v a.
Measured v a =>
StrictFingerTree v a -> a -> StrictFingerTree v a
|> (!a
a) = forall v a. FingerTree v a -> StrictFingerTree v a
SFT (FingerTree v a
ft 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 >< :: forall v a.
Measured v a =>
StrictFingerTree v a
-> StrictFingerTree v a -> StrictFingerTree v a
>< SFT FingerTree v a
ft' = forall v a. FingerTree v a -> StrictFingerTree v a
SFT (FingerTree v a
ft 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 :: forall v a. FingerTree v a -> StrictFingerTree v a
forceToStrict FingerTree v a
xs = forall v a. FingerTree v a -> StrictFingerTree v a
SFT (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 :: forall v a. StrictFingerTree v a -> Bool
null (SFT FingerTree v a
ft) = 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 :: forall v a.
Measured v a =>
StrictFingerTree v a -> ViewL (StrictFingerTree v) a
viewl (SFT FingerTree v a
ft) = case 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 -> forall (s :: * -> *) a. ViewL s a
EmptyL
  a
a :< FingerTree v a
ft' -> a
a forall (s :: * -> *) a. a -> s a -> ViewL s 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 :: forall v a.
Measured v a =>
StrictFingerTree v a -> ViewR (StrictFingerTree v) a
viewr (SFT FingerTree v a
ft) = case 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 -> forall (s :: * -> *) a. ViewR s a
EmptyR
  FingerTree v a
ft' :> a
a -> forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
ft' 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
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, SearchResult v a -> SearchResult v a -> Ordering
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
Ord, Int -> SearchResult v a -> ShowS
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 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 :: forall v a. SearchResult v a -> SearchResult v a
fromOriginalSearchResult (FT.Position FingerTree v a
left a
a FingerTree v a
right) =
  forall v a.
StrictFingerTree v a
-> a -> StrictFingerTree v a -> SearchResult v a
Position (forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
left) a
a (forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
right)
fromOriginalSearchResult SearchResult v a
FT.OnLeft = forall v a. SearchResult v a
OnLeft
fromOriginalSearchResult SearchResult v a
FT.OnRight = forall v a. SearchResult v a
OnRight
fromOriginalSearchResult SearchResult v a
FT.Nowhere = 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 :: forall v a.
Measured v a =>
(v -> v -> Bool) -> StrictFingerTree v a -> SearchResult v a
search v -> v -> Bool
p (SFT FingerTree v a
ft) = forall v a. SearchResult v a -> SearchResult v a
fromOriginalSearchResult (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 :: forall v a.
Measured v a =>
(v -> Bool)
-> StrictFingerTree v a
-> (StrictFingerTree v a, StrictFingerTree v a)
split v -> Bool
p (SFT FingerTree v a
ft) = (forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
left, forall v a. FingerTree v a -> StrictFingerTree v a
SFT FingerTree v a
right)
  where
    (FingerTree v a
left, FingerTree v a
right) = 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 :: forall v a.
Measured v a =>
(v -> Bool) -> StrictFingerTree v a -> StrictFingerTree v a
takeUntil v -> Bool
p (SFT FingerTree v a
ft) = forall v a. FingerTree v a -> StrictFingerTree v a
SFT (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 :: forall v a.
Measured v a =>
(v -> Bool) -> StrictFingerTree v a -> StrictFingerTree v a
dropUntil v -> Bool
p (SFT FingerTree v a
ft) = forall v a. FingerTree v a -> StrictFingerTree v a
SFT (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 :: forall v a.
Measured v a =>
StrictFingerTree v a -> StrictFingerTree v a
reverse (SFT FingerTree v a
ft) = forall v a. FingerTree v a -> StrictFingerTree v a
SFT (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' :: forall v1 a1 v2 a2.
(Measured v1 a1, Measured v2 a2) =>
(a1 -> a2) -> StrictFingerTree v1 a1 -> StrictFingerTree v2 a2
fmap' a1 -> a2
f (SFT FingerTree v1 a1
ft) = forall v a. FingerTree v a -> StrictFingerTree v a
forceToStrict (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 :: forall a b v.
(a -> b) -> StrictFingerTree v a -> StrictFingerTree v b
unsafeFmap a -> b
f (SFT FingerTree v a
ft) = forall v a. FingerTree v a -> StrictFingerTree v a
forceToStrict (forall a b v. (a -> b) -> FingerTree v a -> FingerTree v b
FT.unsafeFmap a -> b
f FingerTree v a
ft)