{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FlexibleContexts #-}
{-# LANGUAGE TypeFamilies, DeriveDataTypeable, DeriveGeneric #-}
{-# LANGUAGE Trustworthy, UndecidableInstances, BangPatterns #-}

{- |
    Module      :  SDP.Templates.AnyChunks
    Copyright   :  (c) Andrey Mulik 2020
    License     :  BSD-style
    Maintainer  :  work.a.mulik@gmail.com
    Portability :  non-portable (GHC extensions)
    
    "SDP.Templates.AnyChunks" provides 'AnyChunks' - list of data chunks.
-}
module SDP.Templates.AnyChunks
(
  -- * Export
  module SDP.IndexedM,
  module SDP.Scan,
  
  -- * Chunk list
  AnyChunks, fromChunks, fromChunksM, toChunks
)
where

import Prelude ()
import SDP.SafePrelude
import SDP.IndexedM
import SDP.SortM
import SDP.Scan

import qualified GHC.Exts as E

import GHC.Generics

import Data.Default.Class
import Data.Typeable
import Data.String
import Data.Data

import Text.Read.SDP
import Text.Show.SDP

import SDP.SortM.Tim

import Control.Exception.SDP

default ()

--------------------------------------------------------------------------------

{- |
  'AnyChunks' is list of data chunks. AnyChunks shouldn't contain empty chunks,
  so the 'AnyChunks' constructor is made private (see 'fromChunks' and
  'fromChunksM').
  
  * Efficiency of operations on @'AnyChunks' rep e@ are very sensitive in the
  efficiency of 'Bordered', 'Linear' and 'Split' on @rep e@.
  * @'AnyChunks' rep e@ is only defined for Int-indexed @rep e@.
  * 'Eq', 'Ord', 'Eq1' and 'Ord1' instances compare @'AnyChunks' rep e@ as
  streams of equal size chunks. To do this, the comparison @rep e@ must also be
  lexicographic, also for @rep e@ must implement 'Bordered' and 'Split'.
  * 'Freeze' and 'Thaw' for @'AnyChunks' rep e@ are defined for all @rep e@ that
  already have 'Freeze' and 'Thaw' instances.
-}
newtype AnyChunks rep e = AnyChunks [rep e] deriving ( Typeable, Typeable (AnyChunks rep e)
DataType
Constr
Typeable (AnyChunks rep e)
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> AnyChunks rep e -> c (AnyChunks rep e))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (AnyChunks rep e))
-> (AnyChunks rep e -> Constr)
-> (AnyChunks rep e -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (AnyChunks rep e)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (AnyChunks rep e)))
-> ((forall b. Data b => b -> b)
    -> AnyChunks rep e -> AnyChunks rep e)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> AnyChunks rep e -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> AnyChunks rep e -> r)
-> (forall u.
    (forall d. Data d => d -> u) -> AnyChunks rep e -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> AnyChunks rep e -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d)
    -> AnyChunks rep e -> m (AnyChunks rep e))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> AnyChunks rep e -> m (AnyChunks rep e))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> AnyChunks rep e -> m (AnyChunks rep e))
-> Data (AnyChunks rep e)
AnyChunks rep e -> DataType
AnyChunks rep e -> Constr
(forall b. Data b => b -> b) -> AnyChunks rep e -> AnyChunks rep e
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> AnyChunks rep e -> c (AnyChunks rep e)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (AnyChunks rep e)
forall a.
Typeable a
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u.
Int -> (forall d. Data d => d -> u) -> AnyChunks rep e -> u
forall u. (forall d. Data d => d -> u) -> AnyChunks rep e -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> AnyChunks rep e -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> AnyChunks rep e -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> AnyChunks rep e -> m (AnyChunks rep e)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (AnyChunks rep e)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> AnyChunks rep e -> c (AnyChunks rep e)
forall (rep :: * -> *) e.
(Typeable rep, Typeable e, Data (rep e)) =>
Typeable (AnyChunks rep e)
forall (rep :: * -> *) e.
(Typeable rep, Typeable e, Data (rep e)) =>
AnyChunks rep e -> DataType
forall (rep :: * -> *) e.
(Typeable rep, Typeable e, Data (rep e)) =>
AnyChunks rep e -> Constr
forall (rep :: * -> *) e.
(Typeable rep, Typeable e, Data (rep e)) =>
(forall b. Data b => b -> b) -> AnyChunks rep e -> AnyChunks rep e
forall (rep :: * -> *) e u.
(Typeable rep, Typeable e, Data (rep e)) =>
Int -> (forall d. Data d => d -> u) -> AnyChunks rep e -> u
forall (rep :: * -> *) e u.
(Typeable rep, Typeable e, Data (rep e)) =>
(forall d. Data d => d -> u) -> AnyChunks rep e -> [u]
forall (rep :: * -> *) e r r'.
(Typeable rep, Typeable e, Data (rep e)) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> AnyChunks rep e -> r
forall (rep :: * -> *) e r r'.
(Typeable rep, Typeable e, Data (rep e)) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> AnyChunks rep e -> r
forall (rep :: * -> *) e (m :: * -> *).
(Typeable rep, Typeable e, Data (rep e), Monad m) =>
(forall d. Data d => d -> m d)
-> AnyChunks rep e -> m (AnyChunks rep e)
forall (rep :: * -> *) e (m :: * -> *).
(Typeable rep, Typeable e, Data (rep e), MonadPlus m) =>
(forall d. Data d => d -> m d)
-> AnyChunks rep e -> m (AnyChunks rep e)
forall (rep :: * -> *) e (c :: * -> *).
(Typeable rep, Typeable e, Data (rep e)) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (AnyChunks rep e)
forall (rep :: * -> *) e (c :: * -> *).
(Typeable rep, Typeable e, Data (rep e)) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> AnyChunks rep e -> c (AnyChunks rep e)
forall (rep :: * -> *) e (t :: * -> *) (c :: * -> *).
(Typeable rep, Typeable e, Data (rep e), Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (AnyChunks rep e))
forall (rep :: * -> *) e (t :: * -> * -> *) (c :: * -> *).
(Typeable rep, Typeable e, Data (rep e), Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (AnyChunks rep e))
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (AnyChunks rep e))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (AnyChunks rep e))
$cAnyChunks :: Constr
$tAnyChunks :: DataType
gmapMo :: (forall d. Data d => d -> m d)
-> AnyChunks rep e -> m (AnyChunks rep e)
$cgmapMo :: forall (rep :: * -> *) e (m :: * -> *).
(Typeable rep, Typeable e, Data (rep e), MonadPlus m) =>
(forall d. Data d => d -> m d)
-> AnyChunks rep e -> m (AnyChunks rep e)
gmapMp :: (forall d. Data d => d -> m d)
-> AnyChunks rep e -> m (AnyChunks rep e)
$cgmapMp :: forall (rep :: * -> *) e (m :: * -> *).
(Typeable rep, Typeable e, Data (rep e), MonadPlus m) =>
(forall d. Data d => d -> m d)
-> AnyChunks rep e -> m (AnyChunks rep e)
gmapM :: (forall d. Data d => d -> m d)
-> AnyChunks rep e -> m (AnyChunks rep e)
$cgmapM :: forall (rep :: * -> *) e (m :: * -> *).
(Typeable rep, Typeable e, Data (rep e), Monad m) =>
(forall d. Data d => d -> m d)
-> AnyChunks rep e -> m (AnyChunks rep e)
gmapQi :: Int -> (forall d. Data d => d -> u) -> AnyChunks rep e -> u
$cgmapQi :: forall (rep :: * -> *) e u.
(Typeable rep, Typeable e, Data (rep e)) =>
Int -> (forall d. Data d => d -> u) -> AnyChunks rep e -> u
gmapQ :: (forall d. Data d => d -> u) -> AnyChunks rep e -> [u]
$cgmapQ :: forall (rep :: * -> *) e u.
(Typeable rep, Typeable e, Data (rep e)) =>
(forall d. Data d => d -> u) -> AnyChunks rep e -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> AnyChunks rep e -> r
$cgmapQr :: forall (rep :: * -> *) e r r'.
(Typeable rep, Typeable e, Data (rep e)) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> AnyChunks rep e -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> AnyChunks rep e -> r
$cgmapQl :: forall (rep :: * -> *) e r r'.
(Typeable rep, Typeable e, Data (rep e)) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> AnyChunks rep e -> r
gmapT :: (forall b. Data b => b -> b) -> AnyChunks rep e -> AnyChunks rep e
$cgmapT :: forall (rep :: * -> *) e.
(Typeable rep, Typeable e, Data (rep e)) =>
(forall b. Data b => b -> b) -> AnyChunks rep e -> AnyChunks rep e
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (AnyChunks rep e))
$cdataCast2 :: forall (rep :: * -> *) e (t :: * -> * -> *) (c :: * -> *).
(Typeable rep, Typeable e, Data (rep e), Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (AnyChunks rep e))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (AnyChunks rep e))
$cdataCast1 :: forall (rep :: * -> *) e (t :: * -> *) (c :: * -> *).
(Typeable rep, Typeable e, Data (rep e), Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (AnyChunks rep e))
dataTypeOf :: AnyChunks rep e -> DataType
$cdataTypeOf :: forall (rep :: * -> *) e.
(Typeable rep, Typeable e, Data (rep e)) =>
AnyChunks rep e -> DataType
toConstr :: AnyChunks rep e -> Constr
$ctoConstr :: forall (rep :: * -> *) e.
(Typeable rep, Typeable e, Data (rep e)) =>
AnyChunks rep e -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (AnyChunks rep e)
$cgunfold :: forall (rep :: * -> *) e (c :: * -> *).
(Typeable rep, Typeable e, Data (rep e)) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (AnyChunks rep e)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> AnyChunks rep e -> c (AnyChunks rep e)
$cgfoldl :: forall (rep :: * -> *) e (c :: * -> *).
(Typeable rep, Typeable e, Data (rep e)) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> AnyChunks rep e -> c (AnyChunks rep e)
$cp1Data :: forall (rep :: * -> *) e.
(Typeable rep, Typeable e, Data (rep e)) =>
Typeable (AnyChunks rep e)
Data, (forall x. AnyChunks rep e -> Rep (AnyChunks rep e) x)
-> (forall x. Rep (AnyChunks rep e) x -> AnyChunks rep e)
-> Generic (AnyChunks rep e)
forall x. Rep (AnyChunks rep e) x -> AnyChunks rep e
forall x. AnyChunks rep e -> Rep (AnyChunks rep e) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall (rep :: * -> *) e x.
Rep (AnyChunks rep e) x -> AnyChunks rep e
forall (rep :: * -> *) e x.
AnyChunks rep e -> Rep (AnyChunks rep e) x
$cto :: forall (rep :: * -> *) e x.
Rep (AnyChunks rep e) x -> AnyChunks rep e
$cfrom :: forall (rep :: * -> *) e x.
AnyChunks rep e -> Rep (AnyChunks rep e) x
Generic )

-- | Construct immutable 'AnyChunks' safely.
fromChunks :: (Nullable (rep e)) => [rep e] -> AnyChunks rep e
fromChunks :: [rep e] -> AnyChunks rep e
fromChunks =  [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e)
-> ([rep e] -> [rep e]) -> [rep e] -> AnyChunks rep e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (rep e -> Bool) -> [rep e] -> [rep e]
forall l e. Linear l e => (e -> Bool) -> l -> l
except rep e -> Bool
forall e. Nullable e => e -> Bool
isNull

-- | Construct mutable 'AnyChunks' safely.
fromChunksM :: (BorderedM1 m rep Int e) => [rep e] -> m (AnyChunks rep e)
fromChunksM :: [rep e] -> m (AnyChunks rep e)
fromChunksM =  ([rep e] -> AnyChunks rep e) -> m [rep e] -> m (AnyChunks rep e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks (m [rep e] -> m (AnyChunks rep e))
-> ([rep e] -> m [rep e]) -> [rep e] -> m (AnyChunks rep e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [rep e] -> m [rep e]
forall (m :: * -> *) a i. BorderedM m a i => [a] -> m [a]
go
  where
    go :: [a] -> m [a]
go (a
x : [a]
xs) = do Int
n <- a -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf a
x; Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 Bool -> m [a] -> m [a] -> m [a]
forall a. Bool -> a -> a -> a
? [a] -> m [a]
go [a]
xs (m [a] -> m [a]) -> m [a] -> m [a]
forall a b. (a -> b) -> a -> b
$ (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> m [a] -> m [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> m [a]
go [a]
xs
    go    []    = [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return []

-- | Extract immutable 'AnyChunks' chunks safely.
toChunks :: AnyChunks rep e -> [rep e]
toChunks :: AnyChunks rep e -> [rep e]
toChunks =  AnyChunks rep e -> [rep e]
E.coerce

--------------------------------------------------------------------------------

{- Eq and Ord instances. -}

instance (Eq (rep e), Bordered1 rep Int e, Split1 rep e) => Eq (AnyChunks rep e)
  where
    AnyChunks rep e
Z == :: AnyChunks rep e -> AnyChunks rep e -> Bool
== AnyChunks rep e
Z = Bool
True
    xs :: AnyChunks rep e
xs@(AnyChunks (rep e
x : [rep e]
xs')) == ys :: AnyChunks rep e
ys@(AnyChunks (rep e
y : [rep e]
ys')) = if Int
n1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
n2
        then Int -> rep e -> rep e
forall s e. Split s e => Int -> s -> s
take Int
n2 rep e
x rep e -> rep e -> Bool
forall a. Eq a => a -> a -> Bool
== rep e
y Bool -> Bool -> Bool
&& Int -> AnyChunks rep e -> AnyChunks rep e
forall s e. Split s e => Int -> s -> s
drop Int
n2 AnyChunks rep e
xs AnyChunks rep e -> AnyChunks rep e -> Bool
forall a. Eq a => a -> a -> Bool
== [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
ys'
        else Int -> rep e -> rep e
forall s e. Split s e => Int -> s -> s
take Int
n1 rep e
y rep e -> rep e -> Bool
forall a. Eq a => a -> a -> Bool
== rep e
x Bool -> Bool -> Bool
&& Int -> AnyChunks rep e -> AnyChunks rep e
forall s e. Split s e => Int -> s -> s
drop Int
n1 AnyChunks rep e
ys AnyChunks rep e -> AnyChunks rep e -> Bool
forall a. Eq a => a -> a -> Bool
== [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
xs'
      where
        n1 :: Int
n1 = rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
x
        n2 :: Int
n2 = rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
y
    AnyChunks rep e
_ == AnyChunks rep e
_ = Bool
False

instance (Ord (rep e), Bordered1 rep Int e, Split1 rep e) => Ord (AnyChunks rep e)
  where
    compare :: AnyChunks rep e -> AnyChunks rep e -> Ordering
compare AnyChunks rep e
Z AnyChunks rep e
Z = Ordering
EQ
    compare xs :: AnyChunks rep e
xs@(AnyChunks (rep e
x : [rep e]
xs')) ys :: AnyChunks rep e
ys@(AnyChunks (rep e
y : [rep e]
ys')) = if Int
n1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
n2
        then (Int -> rep e -> rep e
forall s e. Split s e => Int -> s -> s
take Int
n2 rep e
x Compare (rep e)
forall o. Ord o => Compare o
<=> rep e
y) Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> (Int -> AnyChunks rep e -> AnyChunks rep e
forall s e. Split s e => Int -> s -> s
drop Int
n2 AnyChunks rep e
xs AnyChunks rep e -> AnyChunks rep e -> Ordering
forall o. Ord o => Compare o
<=> [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
ys')
        else (rep e
x Compare (rep e)
forall o. Ord o => Compare o
<=> Int -> rep e -> rep e
forall s e. Split s e => Int -> s -> s
take Int
n1 rep e
y) Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> ([rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
xs' AnyChunks rep e -> AnyChunks rep e -> Ordering
forall o. Ord o => Compare o
<=> Int -> AnyChunks rep e -> AnyChunks rep e
forall s e. Split s e => Int -> s -> s
drop Int
n1 AnyChunks rep e
ys)
      where
        n1 :: Int
n1 = rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
x
        n2 :: Int
n2 = rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
y
    compare AnyChunks rep e
Z AnyChunks rep e
_ = Ordering
LT
    compare AnyChunks rep e
_ AnyChunks rep e
_ = Ordering
GT

--------------------------------------------------------------------------------

{- Show and Read instances. -}

instance {-# OVERLAPPABLE #-} (Indexed1 rep Int e, Show e) => Show (AnyChunks rep e)
  where
    showsPrec :: Int -> AnyChunks rep e -> ShowS
showsPrec = String -> Int -> AnyChunks rep e -> ShowS
forall v i e.
(Indexed v i e, Show i, Show e) =>
String -> Int -> v -> ShowS
assocsPrec String
"unlist "

instance (Indexed1 rep Int Char) => Show (AnyChunks rep Char)
  where
    showsPrec :: Int -> AnyChunks rep Char -> ShowS
showsPrec = String -> ShowS
forall a. Show a => a -> ShowS
shows (String -> ShowS)
-> (Int -> AnyChunks rep Char -> String)
-> Int
-> AnyChunks rep Char
-> ShowS
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
... (AnyChunks rep Char -> String)
-> Int -> AnyChunks rep Char -> String
forall a b. a -> b -> a
const AnyChunks rep Char -> String
forall l e. Linear l e => l -> [e]
listL

instance (Indexed1 rep Int e, Read e) => Read (AnyChunks rep e)
  where
    readPrec :: ReadPrec (AnyChunks rep e)
readPrec = String -> ReadPrec (AnyChunks rep e)
forall v i e.
(Indexed v i e, Read i, Read e) =>
String -> ReadPrec v
indexedPrec' String
"ublist"
    readList :: ReadS [AnyChunks rep e]
readList = ReadS [AnyChunks rep e]
forall a. Read a => ReadS [a]
readListDefault

--------------------------------------------------------------------------------

{- Semigroup, Monoid, Nullable, Default and Estimate instances. -}

instance Nullable (AnyChunks rep e)
  where
    isNull :: AnyChunks rep e -> Bool
isNull = \ (AnyChunks [rep e]
es) -> [rep e] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [rep e]
es
    lzero :: AnyChunks rep e
lzero  = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks []

instance Semigroup (AnyChunks rep e)
  where
    AnyChunks [rep e]
xs <> :: AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e
<> AnyChunks [rep e]
ys = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e]
xs [rep e] -> [rep e] -> [rep e]
forall l e. Linear l e => l -> l -> l
++ [rep e]
ys)

instance Monoid  (AnyChunks rep e) where mempty :: AnyChunks rep e
mempty = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks []
instance Default (AnyChunks rep e) where def :: AnyChunks rep e
def    = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks []

instance (Bordered1 rep Int e) => Estimate (AnyChunks rep e)
  where
    <==> :: Compare (AnyChunks rep e)
(<==>) = Int -> Compare (AnyChunks rep e)
forall (rep :: * -> *) e (rep :: * -> *) e.
(Bordered (rep e) Int, Bordered (rep e) Int) =>
Int -> AnyChunks rep e -> AnyChunks rep e -> Ordering
go Int
0
      where
        go :: Int -> AnyChunks rep e -> AnyChunks rep e -> Ordering
go Int
o (AnyChunks [])   (AnyChunks []) = Int
o Compare Int
forall o. Ord o => Compare o
<=> Int
0
        go Int
o (AnyChunks [])               AnyChunks rep e
ys = Int
o Int -> AnyChunks rep e -> Ordering
forall e. Estimate e => Int -> e -> Ordering
<=.> AnyChunks rep e
ys
        go Int
o AnyChunks rep e
xs               (AnyChunks []) = AnyChunks rep e
xs AnyChunks rep e -> Int -> Ordering
forall e. Estimate e => e -> Int -> Ordering
<.=> (-Int
o)
        go Int
o (AnyChunks (rep e
x : [rep e]
xs)) (AnyChunks (rep e
y : [rep e]
ys)) =
          Int -> AnyChunks rep e -> AnyChunks rep e -> Ordering
go (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+ rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
y) ([rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
xs) ([rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
ys)
    
    (AnyChunks       []) <.=> :: AnyChunks rep e -> Int -> Ordering
<.=> Int
n = Int
0 Compare Int
forall o. Ord o => Compare o
<=> Int
n
    (AnyChunks (rep e
x : [rep e]
xs)) <.=> Int
n = Int
c Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
n Bool -> Ordering -> Ordering -> Ordering
forall a. Bool -> a -> a -> a
? Ordering
GT (Ordering -> Ordering) -> Ordering -> Ordering
forall a b. (a -> b) -> a -> b
$ [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
xs AnyChunks rep e -> Int -> Ordering
forall e. Estimate e => e -> Int -> Ordering
<.=> (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
c)
      where
        c :: Int
c = rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
x

--------------------------------------------------------------------------------

{- Overloaded Lists and Strings support. -}

instance (Linear1 (AnyChunks rep) Char) => IsString (AnyChunks rep Char)
  where
    fromString :: String -> AnyChunks rep Char
fromString = String -> AnyChunks rep Char
forall l e. Linear l e => [e] -> l
fromList

instance (Linear1 (AnyChunks rep) e) => E.IsList (AnyChunks rep e)
  where
    type Item (AnyChunks rep e) = e
    
    fromListN :: Int -> [Item (AnyChunks rep e)] -> AnyChunks rep e
fromListN = Int -> [Item (AnyChunks rep e)] -> AnyChunks rep e
forall l e. Linear l e => Int -> [e] -> l
fromListN
    fromList :: [Item (AnyChunks rep e)] -> AnyChunks rep e
fromList  = [Item (AnyChunks rep e)] -> AnyChunks rep e
forall l e. Linear l e => [e] -> l
fromList
    toList :: AnyChunks rep e -> [Item (AnyChunks rep e)]
toList    = AnyChunks rep e -> [Item (AnyChunks rep e)]
forall l e. Linear l e => l -> [e]
listL

--------------------------------------------------------------------------------

{- Functor and Applicative instances. -}

instance (Functor rep) => Functor (AnyChunks rep)
  where
    fmap :: (a -> b) -> AnyChunks rep a -> AnyChunks rep b
fmap a -> b
f (AnyChunks [rep a]
es) = [rep b] -> AnyChunks rep b
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ((a -> b) -> rep a -> rep b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f (rep a -> rep b) -> [rep a] -> [rep b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [rep a]
es)

instance (Applicative rep) => Applicative (AnyChunks rep)
  where
    AnyChunks [rep (a -> b)]
fs <*> :: AnyChunks rep (a -> b) -> AnyChunks rep a -> AnyChunks rep b
<*> AnyChunks [rep a]
es = [rep b] -> AnyChunks rep b
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep b] -> AnyChunks rep b) -> [rep b] -> AnyChunks rep b
forall a b. (a -> b) -> a -> b
$ (rep (a -> b) -> rep a -> rep b)
-> [rep (a -> b)] -> [rep a] -> [rep b]
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 rep (a -> b) -> rep a -> rep b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
(<*>) [rep (a -> b)]
fs [rep a]
es
    pure :: a -> AnyChunks rep a
pure a
e = [rep a] -> AnyChunks rep a
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [a -> rep a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
e]

--------------------------------------------------------------------------------

{- Foldable and Traversable instances. -}

instance (Foldable rep) => Foldable (AnyChunks rep)
  where
    foldr :: (a -> b -> b) -> b -> AnyChunks rep a -> b
foldr a -> b -> b
f b
base (AnyChunks [rep a]
es) = (b -> rep a -> b) -> rep a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> b -> b) -> b -> rep a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f) (rep a -> b -> b) -> b -> [rep a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
`foldr` b
base ([rep a] -> b) -> [rep a] -> b
forall a b. (a -> b) -> a -> b
$ [rep a]
es
    foldl :: (b -> a -> b) -> b -> AnyChunks rep a -> b
foldl b -> a -> b
f b
base (AnyChunks [rep a]
es) = (b -> rep a -> b) -> b -> [rep a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ((b -> a -> b) -> b -> rep a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl b -> a -> b
f) b
base [rep a]
es
    
    elem :: a -> AnyChunks rep a -> Bool
elem a
e (AnyChunks [rep a]
es) = (rep a -> Bool -> Bool) -> Bool -> [rep a] -> Bool
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Bool -> Bool -> Bool
(||) (Bool -> Bool -> Bool) -> (rep a -> Bool) -> rep a -> Bool -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> rep a -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
elem a
e) Bool
False [rep a]
es
    length :: AnyChunks rep a -> Int
length (AnyChunks [rep a]
es) = (rep a -> Int -> Int) -> Int -> [rep a] -> Int
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' (Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Int -> Int -> Int) -> (rep a -> Int) -> rep a -> Int -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. rep a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length) Int
0 [rep a]
es
    null :: AnyChunks rep a -> Bool
null   (AnyChunks [rep a]
es) = [rep a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [rep a]
es

instance (Traversable rep) => Traversable (AnyChunks rep)
  where
    traverse :: (a -> f b) -> AnyChunks rep a -> f (AnyChunks rep b)
traverse a -> f b
f (AnyChunks [rep a]
es) = [rep b] -> AnyChunks rep b
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep b] -> AnyChunks rep b) -> f [rep b] -> f (AnyChunks rep b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (rep a -> f (rep b)) -> [rep a] -> f [rep b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((a -> f b) -> rep a -> f (rep b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f) [rep a]
es

--------------------------------------------------------------------------------

{- Bordered, Linear and Split instances. -}

instance (Bordered1 rep Int e) => Bordered (AnyChunks rep e) Int
  where
    sizeOf :: AnyChunks rep e -> Int
sizeOf (AnyChunks [rep e]
es) = (rep e -> Int -> Int) -> Int -> [rep e] -> Int
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' (Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Int -> Int -> Int) -> (rep e -> Int) -> rep e -> Int -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf) Int
0 [rep e]
es
    
    indexIn :: AnyChunks rep e -> Int -> Bool
indexIn AnyChunks rep e
es = \ Int
i -> Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 Bool -> Bool -> Bool
&& Int
i Int -> AnyChunks rep e -> Bool
forall e. Estimate e => Int -> e -> Bool
<. AnyChunks rep e
es
    
    -- | Quick unchecked offset.
    offsetOf :: AnyChunks rep e -> Int -> Int
offsetOf = (Int -> Int) -> AnyChunks rep e -> Int -> Int
forall a b. a -> b -> a
const Int -> Int
forall a. a -> a
id
    
    -- | Quick unchecked index.
    indexOf :: AnyChunks rep e -> Int -> Int
indexOf  = (Int -> Int) -> AnyChunks rep e -> Int -> Int
forall a b. a -> b -> a
const Int -> Int
forall a. a -> a
id
    
    lower :: AnyChunks rep e -> Int
lower   AnyChunks rep e
_ = Int
0
    upper :: AnyChunks rep e -> Int
upper  AnyChunks rep e
es = AnyChunks rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf AnyChunks rep e
es Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
    bounds :: AnyChunks rep e -> (Int, Int)
bounds AnyChunks rep e
es = (Int
0, AnyChunks rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf AnyChunks rep e
es Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)

instance (Bordered1 rep Int e, Linear1 rep e) => Linear (AnyChunks rep e) e
  where
    single :: e -> AnyChunks rep e
single e
e = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [e -> rep e
forall l e. Linear l e => e -> l
single e
e]
    
    toHead :: e -> AnyChunks rep e -> AnyChunks rep e
toHead e
e (AnyChunks es :: [rep e]
es@(rep e
x : [rep e]
xs)) = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e) -> [rep e] -> AnyChunks rep e
forall a b. (a -> b) -> a -> b
$ rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
lim Bool -> [rep e] -> [rep e] -> [rep e]
forall a. Bool -> a -> a -> a
? (e
e e -> rep e -> rep e
forall l e. Linear l e => e -> l -> l
:> rep e
x) rep e -> [rep e] -> [rep e]
forall a. a -> [a] -> [a]
: [rep e]
xs ([rep e] -> [rep e]) -> [rep e] -> [rep e]
forall a b. (a -> b) -> a -> b
$ e -> rep e
forall l e. Linear l e => e -> l
single e
e rep e -> [rep e] -> [rep e]
forall a. a -> [a] -> [a]
: [rep e]
es
    toHead e
e                       AnyChunks rep e
_ = e -> AnyChunks rep e
forall l e. Linear l e => e -> l
single e
e
    
    toLast :: AnyChunks rep e -> e -> AnyChunks rep e
toLast (AnyChunks ([rep e]
xs :< rep e
x)) e
e = rep e -> Bool
forall e. Nullable e => e -> Bool
isNull rep e
x Bool -> AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e
forall a. Bool -> a -> a -> a
? [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
xs AnyChunks rep e -> e -> AnyChunks rep e
forall l e. Linear l e => l -> e -> l
:< e
e (AnyChunks rep e -> AnyChunks rep e)
-> AnyChunks rep e -> AnyChunks rep e
forall a b. (a -> b) -> a -> b
$ [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e]
xs [rep e] -> rep e -> [rep e]
forall l e. Linear l e => l -> e -> l
:< (rep e
x rep e -> e -> rep e
forall l e. Linear l e => l -> e -> l
:< e
e))
    toLast AnyChunks rep e
_                     e
e = e -> AnyChunks rep e
forall l e. Linear l e => e -> l
single e
e
    
    uncons :: AnyChunks rep e -> (e, AnyChunks rep e)
uncons = [rep e] -> (e, AnyChunks rep e)
forall (rep :: * -> *) e a.
Linear (rep e) a =>
[rep e] -> (a, AnyChunks rep e)
go ([rep e] -> (e, AnyChunks rep e))
-> (AnyChunks rep e -> [rep e])
-> AnyChunks rep e
-> (e, AnyChunks rep e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        go :: [rep e] -> (a, AnyChunks rep e)
go ((a
x :> rep e
xs) : [rep e]
xss) = (a
x, [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks (rep e
xs rep e -> [rep e] -> [rep e]
forall a. a -> [a] -> [a]
: [rep e]
xss))
        go                 [rep e]
_ = String -> (a, AnyChunks rep e)
forall a. String -> a
pfailEx String
"(:>)"
    
    unsnoc :: AnyChunks rep e -> (AnyChunks rep e, e)
unsnoc = [rep e] -> (AnyChunks rep e, e)
forall (rep :: * -> *) e b.
Linear (rep e) b =>
[rep e] -> (AnyChunks rep e, b)
go ([rep e] -> (AnyChunks rep e, e))
-> (AnyChunks rep e -> [rep e])
-> AnyChunks rep e
-> (AnyChunks rep e, e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        go :: [rep e] -> (AnyChunks rep e, b)
go ([rep e]
xss :< (rep e
xs :< b
x)) = ([rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e]
xss [rep e] -> rep e -> [rep e]
forall l e. Linear l e => l -> e -> l
:< rep e
xs), b
x)
        go                  [rep e]
_ = String -> (AnyChunks rep e, b)
forall a. String -> a
pfailEx String
"(:<)"
    
    fromList :: [e] -> AnyChunks rep e
fromList = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e)
-> ([e] -> [rep e]) -> [e] -> AnyChunks rep e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([e] -> rep e) -> [[e]] -> [rep e]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [e] -> rep e
forall l e. Linear l e => [e] -> l
fromList ([[e]] -> [rep e]) -> ([e] -> [[e]]) -> [e] -> [rep e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [e] -> [[e]]
forall s e. Split s e => Int -> s -> [s]
chunks Int
lim
    listL :: AnyChunks rep e -> [e]
listL    = (rep e -> [e] -> [e]) -> [e] -> [rep e] -> [e]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ([e] -> [e] -> [e]
forall l e. Linear l e => l -> l -> l
(++) ([e] -> [e] -> [e]) -> (rep e -> [e]) -> rep e -> [e] -> [e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. rep e -> [e]
forall l e. Linear l e => l -> [e]
listL) [] ([rep e] -> [e])
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> [e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    
    (AnyChunks (rep e
x : [rep e]
xs)) !^ :: AnyChunks rep e -> Int -> e
!^ Int
i = let n :: Int
n = rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
x in Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n Bool -> e -> e -> e
forall a. Bool -> a -> a -> a
? rep e
x rep e -> Int -> e
forall l e. Linear l e => l -> Int -> e
!^ Int
i (e -> e) -> e -> e
forall a b. (a -> b) -> a -> b
$ [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
xs AnyChunks rep e -> Int -> e
forall l e. Linear l e => l -> Int -> e
!^ (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n)
    AnyChunks rep e
_                    !^ Int
_ = String -> e
forall a. HasCallStack => String -> a
error String
"in SDP.Unrolled.Unlist.(!^)"
    
    write :: AnyChunks rep e -> Int -> e -> AnyChunks rep e
write es' :: AnyChunks rep e
es'@(AnyChunks [rep e]
es) Int
n e
e =
      let
        go :: Int -> [rep e] -> [rep e]
go Int
i (rep e
x : [rep e]
xs) = let c :: Int
c = rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
x in Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
c Bool -> [rep e] -> [rep e] -> [rep e]
forall a. Bool -> a -> a -> a
? rep e -> Int -> e -> rep e
forall l e. Linear l e => l -> Int -> e -> l
write rep e
x Int
i e
e rep e -> [rep e] -> [rep e]
forall a. a -> [a] -> [a]
: [rep e]
xs ([rep e] -> [rep e]) -> [rep e] -> [rep e]
forall a b. (a -> b) -> a -> b
$ rep e
x rep e -> [rep e] -> [rep e]
forall a. a -> [a] -> [a]
: Int -> [rep e] -> [rep e]
go (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
c) [rep e]
xs
        go Int
_       [rep e]
xs = [rep e]
xs
      in  Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e
forall a. Bool -> a -> a -> a
? AnyChunks rep e
es' (AnyChunks rep e -> AnyChunks rep e)
-> AnyChunks rep e -> AnyChunks rep e
forall a b. (a -> b) -> a -> b
$ [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks (Int -> [rep e] -> [rep e]
go Int
n [rep e]
es)
    
    -- | Deduplicated chunks.
    replicate :: Int -> e -> AnyChunks rep e
replicate Int
n e
e = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e) -> [rep e] -> AnyChunks rep e
forall a b. (a -> b) -> a -> b
$ Int -> rep e -> [rep e]
forall l e. Linear l e => Int -> e -> l
replicate Int
count rep e
chunk [rep e] -> rep e -> [rep e]
forall l e. Linear l e => l -> e -> l
:< rep e
rest
      where
        (Int
count, Int
rst) = Int
n Int -> Int -> (Int, Int)
forall a. Integral a => a -> a -> (a, a)
`divMod` Int
lim
        
        chunk :: rep e
chunk = Int -> e -> rep e
forall l e. Linear l e => Int -> e -> l
replicate Int
lim e
e
        rest :: rep e
rest  = Int -> e -> rep e
forall l e. Linear l e => Int -> e -> l
replicate Int
rst e
e
    
    reverse :: AnyChunks rep e -> AnyChunks rep e
reverse (AnyChunks [rep e]
es) = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks (rep e -> rep e
forall l e. Linear l e => l -> l
reverse (rep e -> rep e) -> [rep e] -> [rep e]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [rep e] -> [rep e]
forall l e. Linear l e => l -> l
reverse [rep e]
es)
    force :: AnyChunks rep e -> AnyChunks rep e
force   (AnyChunks [rep e]
es) = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks (rep e -> rep e
forall l e. Linear l e => l -> l
force (rep e -> rep e) -> [rep e] -> [rep e]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [rep e]
es)
    
    partition :: (e -> Bool)
-> AnyChunks rep e -> (AnyChunks rep e, AnyChunks rep e)
partition e -> Bool
p = ([e] -> AnyChunks rep e)
-> ([e], [e]) -> (AnyChunks rep e, AnyChunks rep e)
forall a b. (a -> b) -> (a, a) -> (b, b)
both [e] -> AnyChunks rep e
forall l e. Linear l e => [e] -> l
fromList (([e], [e]) -> (AnyChunks rep e, AnyChunks rep e))
-> (AnyChunks rep e -> ([e], [e]))
-> AnyChunks rep e
-> (AnyChunks rep e, AnyChunks rep e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (e -> Bool) -> [e] -> ([e], [e])
forall l e. Linear l e => (e -> Bool) -> l -> (l, l)
partition e -> Bool
p ([e] -> ([e], [e]))
-> (AnyChunks rep e -> [e]) -> AnyChunks rep e -> ([e], [e])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [e]
forall l e. Linear l e => l -> [e]
listL
    
    select :: (e -> Maybe a) -> AnyChunks rep e -> [a]
select  e -> Maybe a
f (AnyChunks [rep e]
es) = (rep e -> [a]) -> [rep e] -> [a]
forall l e (f :: * -> *) a.
(Linear l e, Foldable f) =>
(a -> l) -> f a -> l
concatMap ((e -> Maybe a) -> rep e -> [a]
forall l e a. Linear l e => (e -> Maybe a) -> l -> [a]
select e -> Maybe a
f) [rep e]
es
    extract :: (e -> Maybe a) -> AnyChunks rep e -> ([a], AnyChunks rep e)
extract e -> Maybe a
f (AnyChunks [rep e]
es) = ([[a]] -> [a])
-> ([rep e] -> AnyChunks rep e)
-> ([[a]], [rep e])
-> ([a], AnyChunks rep e)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [[a]] -> [a]
forall l e (f :: * -> *). (Linear l e, Foldable f) => f l -> l
concat [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks (([[a]], [rep e]) -> ([a], AnyChunks rep e))
-> ([([a], rep e)] -> ([[a]], [rep e]))
-> [([a], rep e)]
-> ([a], AnyChunks rep e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [([a], rep e)] -> ([[a]], [rep e])
forall a b. [(a, b)] -> ([a], [b])
unzip ([([a], rep e)] -> ([a], AnyChunks rep e))
-> [([a], rep e)] -> ([a], AnyChunks rep e)
forall a b. (a -> b) -> a -> b
$ (e -> Maybe a) -> rep e -> ([a], rep e)
forall l e a. Linear l e => (e -> Maybe a) -> l -> ([a], l)
extract e -> Maybe a
f (rep e -> ([a], rep e)) -> [rep e] -> [([a], rep e)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [rep e]
es
    
    selects :: f (e -> Maybe a) -> AnyChunks rep e -> ([[a]], AnyChunks rep e)
selects f (e -> Maybe a)
fs = ([e] -> AnyChunks rep e)
-> ([[a]], [e]) -> ([[a]], AnyChunks rep e)
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second [e] -> AnyChunks rep e
forall l e. Linear l e => [e] -> l
fromList (([[a]], [e]) -> ([[a]], AnyChunks rep e))
-> (AnyChunks rep e -> ([[a]], [e]))
-> AnyChunks rep e
-> ([[a]], AnyChunks rep e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f (e -> Maybe a) -> [e] -> ([[a]], [e])
forall l e (f :: * -> *) a.
(Linear l e, Foldable f) =>
f (e -> Maybe a) -> l -> ([[a]], l)
selects f (e -> Maybe a)
fs ([e] -> ([[a]], [e]))
-> (AnyChunks rep e -> [e]) -> AnyChunks rep e -> ([[a]], [e])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [e]
forall l e. Linear l e => l -> [e]
listL
    
    ofoldr :: (Int -> e -> b -> b) -> b -> AnyChunks rep e -> b
ofoldr Int -> e -> b -> b
f' b
base' = Int -> (Int -> e -> b -> b) -> b -> [rep e] -> b
forall l e i p.
(Linear l e, Bordered l i) =>
Int -> (Int -> e -> p -> p) -> p -> [l] -> p
go Int
0 Int -> e -> b -> b
f' b
base' ([rep e] -> b)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        go :: Int -> (Int -> e -> p -> p) -> p -> [l] -> p
go Int
o Int -> e -> p -> p
f p
base (l
x : [l]
xs) = (Int -> e -> p -> p) -> p -> l -> p
forall l e b. Linear l e => (Int -> e -> b -> b) -> b -> l -> b
ofoldr (Int -> e -> p -> p
f (Int -> e -> p -> p) -> (Int -> Int) -> Int -> e -> p -> p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+)) (Int -> (Int -> e -> p -> p) -> p -> [l] -> p
go (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+ l -> Int
forall b i. Bordered b i => b -> Int
sizeOf l
x) Int -> e -> p -> p
f p
base [l]
xs) l
x
        go Int
_ Int -> e -> p -> p
_ p
base [l]
_ = p
base
    
    ofoldl :: (Int -> b -> e -> b) -> b -> AnyChunks rep e -> b
ofoldl Int -> b -> e -> b
f' b
base' = Int -> (Int -> b -> e -> b) -> b -> [rep e] -> b
forall l i e p.
(Bordered l i, Linear l e) =>
Int -> (Int -> p -> e -> p) -> p -> [l] -> p
go Int
0 Int -> b -> e -> b
f' b
base' ([rep e] -> b)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        go :: Int -> (Int -> p -> e -> p) -> p -> [l] -> p
go Int
o Int -> p -> e -> p
f p
base (l
x : [l]
xs) = Int -> (Int -> p -> e -> p) -> p -> [l] -> p
go (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+ l -> Int
forall b i. Bordered b i => b -> Int
sizeOf l
x) Int -> p -> e -> p
f ((Int -> p -> e -> p) -> p -> l -> p
forall l e b. Linear l e => (Int -> b -> e -> b) -> b -> l -> b
ofoldl (Int -> p -> e -> p
f (Int -> p -> e -> p) -> (Int -> Int) -> Int -> p -> e -> p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+)) p
base l
x) [l]
xs
        go Int
_ Int -> p -> e -> p
_ p
base [l]
_ = p
base
    
    o_foldr :: (e -> b -> b) -> b -> AnyChunks rep e -> b
o_foldr e -> b -> b
f b
base = (rep e -> b -> b) -> b -> [rep e] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((b -> rep e -> b) -> rep e -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((b -> rep e -> b) -> rep e -> b -> b)
-> (b -> rep e -> b) -> rep e -> b -> b
forall a b. (a -> b) -> a -> b
$ (e -> b -> b) -> b -> rep e -> b
forall l e b. Linear l e => (e -> b -> b) -> b -> l -> b
o_foldr e -> b -> b
f) b
base ([rep e] -> b)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    o_foldl :: (b -> e -> b) -> b -> AnyChunks rep e -> b
o_foldl b -> e -> b
f b
base = (b -> rep e -> b) -> b -> [rep e] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ((b -> e -> b) -> b -> rep e -> b
forall l e b. Linear l e => (b -> e -> b) -> b -> l -> b
o_foldl b -> e -> b
f) b
base ([rep e] -> b)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks

instance (Bordered1 rep Int e, Split1 rep e) => Split (AnyChunks rep e) e
  where
    take :: Int -> AnyChunks rep e -> AnyChunks rep e
take Int
n = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e)
-> (AnyChunks rep e -> [rep e])
-> AnyChunks rep e
-> AnyChunks rep e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [rep e] -> [rep e]
forall s i e. (Bordered s i, Split s e) => Int -> [s] -> [s]
go Int
n ([rep e] -> [rep e])
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> [rep e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        go :: Int -> [s] -> [s]
go Int
c (s
x : [s]
xs) = let s :: Int
s = s -> Int
forall b i. Bordered b i => b -> Int
sizeOf s
x in case Int
c Compare Int
forall o. Ord o => Compare o
<=> Int
s of
          Ordering
GT -> s
x s -> [s] -> [s]
forall a. a -> [a] -> [a]
: Int -> [s] -> [s]
go (Int
c Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
s) [s]
xs
          Ordering
LT -> [Int -> s -> s
forall s e. Split s e => Int -> s -> s
take Int
c s
x]
          Ordering
EQ -> [s
x]
        go Int
_    []    = []

    drop :: Int -> AnyChunks rep e -> AnyChunks rep e
drop Int
n = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e)
-> (AnyChunks rep e -> [rep e])
-> AnyChunks rep e
-> AnyChunks rep e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [rep e] -> [rep e]
forall s i e. (Bordered s i, Split s e) => Int -> [s] -> [s]
go Int
n ([rep e] -> [rep e])
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> [rep e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        go :: Int -> [a] -> [a]
go Int
c (a
x : [a]
xs) = let s :: Int
s = a -> Int
forall b i. Bordered b i => b -> Int
sizeOf a
x in case Int
c Compare Int
forall o. Ord o => Compare o
<=> Int
s of
          Ordering
GT -> Int -> [a] -> [a]
go (Int
c Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
s) [a]
xs
          Ordering
LT -> Int -> a -> a
forall s e. Split s e => Int -> s -> s
drop Int
c a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs
          Ordering
EQ -> [a]
xs
        go Int
_    []    = []
    
    prefix :: (e -> Bool) -> AnyChunks rep e -> Int
prefix e -> Bool
f = (rep e -> Int -> Int) -> Int -> [rep e] -> Int
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' (\ rep e
e Int
n -> let p :: Int
p = (e -> Bool) -> rep e -> Int
forall s e. Split s e => (e -> Bool) -> s -> Int
prefix e -> Bool
f rep e
e in Int
p Int -> rep e -> Bool
forall e. Estimate e => Int -> e -> Bool
==. rep e
e Bool -> Int -> Int -> Int
forall a. Bool -> a -> a -> a
? Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Int
p) Int
0 ([rep e] -> Int)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    suffix :: (e -> Bool) -> AnyChunks rep e -> Int
suffix e -> Bool
f = (Int -> rep e -> Int) -> Int -> [rep e] -> Int
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\ Int
n rep e
e -> let s :: Int
s = (e -> Bool) -> rep e -> Int
forall s e. Split s e => (e -> Bool) -> s -> Int
suffix e -> Bool
f rep e
e in Int
s Int -> rep e -> Bool
forall e. Estimate e => Int -> e -> Bool
==. rep e
e Bool -> Int -> Int -> Int
forall a. Bool -> a -> a -> a
? Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Int
s) Int
0 ([rep e] -> Int)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    combo :: Equal e -> AnyChunks rep e -> Int
combo  Equal e
f = (rep e -> Int -> Int) -> Int -> [rep e] -> Int
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' (\ rep e
e Int
n -> let c :: Int
c = Equal e -> rep e -> Int
forall s e. Split s e => Equal e -> s -> Int
combo  Equal e
f rep e
e in Int
c Int -> rep e -> Bool
forall e. Estimate e => Int -> e -> Bool
==. rep e
e Bool -> Int -> Int -> Int
forall a. Bool -> a -> a -> a
? Int
c Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Int
c) Int
0 ([rep e] -> Int)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks

--------------------------------------------------------------------------------

{- BorderedM, LinearM and SplitM instances. -}

instance (BorderedM1 m rep Int e) => BorderedM m (AnyChunks rep e) Int
  where
    getLower :: AnyChunks rep e -> m Int
getLower  AnyChunks rep e
_ = Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return Int
0
    getUpper :: AnyChunks rep e -> m Int
getUpper AnyChunks rep e
es = do Int
n <- AnyChunks rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf AnyChunks rep e
es; Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
    
    getSizeOf :: AnyChunks rep e -> m Int
getSizeOf = (rep e -> m Int -> m Int) -> m Int -> [rep e] -> m Int
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((Int -> Int -> Int) -> m Int -> m Int -> m Int
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (m Int -> m Int -> m Int)
-> (rep e -> m Int) -> rep e -> m Int -> m Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf) (Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return Int
0) ([rep e] -> m Int)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> m Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    
    getIndices :: AnyChunks rep e -> m [Int]
getIndices AnyChunks rep e
es = do Int
n <- AnyChunks rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf AnyChunks rep e
es; [Int] -> m [Int]
forall (m :: * -> *) a. Monad m => a -> m a
return [Int
0 .. Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1]
    nowIndexIn :: AnyChunks rep e -> Int -> m Bool
nowIndexIn AnyChunks rep e
es = \ Int
i -> Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> m Bool -> m Bool -> m Bool
forall a. Bool -> a -> a -> a
? Bool -> m Bool
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False (m Bool -> m Bool) -> m Bool -> m Bool
forall a b. (a -> b) -> a -> b
$ do Int
n <- AnyChunks rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf AnyChunks rep e
es; Bool -> m Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n)

instance (BorderedM1 m rep Int e, SplitM1 m rep e) => LinearM m (AnyChunks rep e) e
  where
    nowNull :: AnyChunks rep e -> m Bool
nowNull = ([Bool] -> Bool) -> m [Bool] -> m Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and (m [Bool] -> m Bool)
-> (AnyChunks rep e -> m [Bool]) -> AnyChunks rep e -> m Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (rep e -> m Bool) -> [rep e] -> m [Bool]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM rep e -> m Bool
forall (m :: * -> *) l e. LinearM m l e => l -> m Bool
nowNull ([rep e] -> m [Bool])
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> m [Bool]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    getHead :: AnyChunks rep e -> m e
getHead = rep e -> m e
forall (m :: * -> *) l e. LinearM m l e => l -> m e
getHead (rep e -> m e)
-> (AnyChunks rep e -> rep e) -> AnyChunks rep e -> m e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [rep e] -> rep e
forall l e. Linear l e => l -> e
head ([rep e] -> rep e)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> rep e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    getLast :: AnyChunks rep e -> m e
getLast = rep e -> m e
forall (m :: * -> *) l e. LinearM m l e => l -> m e
getLast (rep e -> m e)
-> (AnyChunks rep e -> rep e) -> AnyChunks rep e -> m e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [rep e] -> rep e
forall l e. Linear l e => l -> e
last ([rep e] -> rep e)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> rep e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    newNull :: m (AnyChunks rep e)
newNull = AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) a. Monad m => a -> m a
return ([rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [])
    
    prepend :: e -> AnyChunks rep e -> m (AnyChunks rep e)
prepend e
e' AnyChunks rep e
es' = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e) -> m [rep e] -> m (AnyChunks rep e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> e -> [rep e] -> m [rep e]
forall (m :: * -> *) a i e.
(BorderedM m a i, LinearM m a e) =>
e -> [a] -> m [a]
go e
e' (AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks AnyChunks rep e
es')
      where
        go :: e -> [a] -> m [a]
go e
e es :: [a]
es@(a
x : [a]
xs) = do Int
n <- a -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf a
x; Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
lim Bool -> m [a] -> m [a] -> m [a]
forall a. Bool -> a -> a -> a
? (a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs) (a -> [a]) -> m a -> m [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> e -> a -> m a
forall (m :: * -> *) l e. LinearM m l e => e -> l -> m l
prepend e
e a
x (m [a] -> m [a]) -> m [a] -> m [a]
forall a b. (a -> b) -> a -> b
$ (a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
es) (a -> [a]) -> m a -> m [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [e] -> m a
forall (m :: * -> *) l e. LinearM m l e => [e] -> m l
newLinear [e
e]
        go e
e           [a]
_ = a -> [a]
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> [a]) -> m a -> m [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [e] -> m a
forall (m :: * -> *) l e. LinearM m l e => [e] -> m l
newLinear [e
e]
    
    append :: AnyChunks rep e -> e -> m (AnyChunks rep e)
append AnyChunks rep e
es' e
e' = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e) -> m [rep e] -> m (AnyChunks rep e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> e -> [rep e] -> m [rep e]
forall (f :: * -> *) a e (m :: * -> *) i e.
(Linear (f a) e, BorderedM m e i, LinearM m e e, LinearM m a e,
 Applicative f) =>
e -> f a -> m (f a)
go e
e' (AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks AnyChunks rep e
es')
      where
        go :: e -> f a -> m (f a)
go e
e es :: f a
es@(f a
xs :< e
x) = do Int
n <- e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf e
x; Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
lim Bool -> m (f a) -> m (f a) -> m (f a)
forall a. Bool -> a -> a -> a
? (f a
xs f a -> e -> f a
forall l e. Linear l e => l -> e -> l
:<) (e -> f a) -> m e -> m (f a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> e -> e -> m e
forall (m :: * -> *) l e. LinearM m l e => l -> e -> m l
append e
x e
e (m (f a) -> m (f a)) -> m (f a) -> m (f a)
forall a b. (a -> b) -> a -> b
$ (f a
es f a -> e -> f a
forall l e. Linear l e => l -> e -> l
:<) (e -> f a) -> m e -> m (f a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [e] -> m e
forall (m :: * -> *) l e. LinearM m l e => [e] -> m l
newLinear [e
e]
        go e
e            f a
_ = a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> f a) -> m a -> m (f a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [e] -> m a
forall (m :: * -> *) l e. LinearM m l e => [e] -> m l
newLinear [e
e]
    
    newLinear :: [e] -> m (AnyChunks rep e)
newLinear = ([rep e] -> AnyChunks rep e) -> m [rep e] -> m (AnyChunks rep e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks (m [rep e] -> m (AnyChunks rep e))
-> ([e] -> m [rep e]) -> [e] -> m (AnyChunks rep e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([e] -> m (rep e)) -> [[e]] -> m [rep e]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM [e] -> m (rep e)
forall (m :: * -> *) l e. LinearM m l e => [e] -> m l
newLinear ([[e]] -> m [rep e]) -> ([e] -> [[e]]) -> [e] -> m [rep e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [e] -> [[e]]
forall s e. Split s e => Int -> s -> [s]
chunks Int
lim
    
    !#> :: AnyChunks rep e -> Int -> m e
(!#>) (AnyChunks [rep e]
es) = [rep e] -> Int -> m e
forall (m :: * -> *) l i b.
(BorderedM m l i, LinearM m l b) =>
[l] -> Int -> m b
go [rep e]
es
      where
        go :: [l] -> Int -> m b
go (l
x : [l]
xs) Int
i = do Int
n <- l -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf l
x; Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n Bool -> m b -> m b -> m b
forall a. Bool -> a -> a -> a
? l
x l -> Int -> m b
forall (m :: * -> *) l e. LinearM m l e => l -> Int -> m e
!#> Int
i (m b -> m b) -> m b -> m b
forall a b. (a -> b) -> a -> b
$ [l] -> Int -> m b
go [l]
xs (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n)
        go [l]
_        Int
_ = String -> m b
forall a. String -> a
overEx String
"(>!)"
    
    {-# INLINE writeM #-}
    writeM :: AnyChunks rep e -> Int -> e -> m ()
writeM = [rep e] -> Int -> e -> m ()
forall (m :: * -> *) l i t.
(BorderedM m l i, LinearM m l t) =>
[l] -> Int -> t -> m ()
go ([rep e] -> Int -> e -> m ())
-> (AnyChunks rep e -> [rep e])
-> AnyChunks rep e
-> Int
-> e
-> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        go :: [l] -> Int -> t -> m ()
go (l
x : [l]
xs) Int
i t
e = do Int
n <- l -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf l
x; Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n Bool -> m () -> m () -> m ()
forall a. Bool -> a -> a -> a
? l -> Int -> t -> m ()
forall (m :: * -> *) l e. LinearM m l e => l -> Int -> e -> m ()
writeM l
x Int
i t
e (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ [l] -> Int -> t -> m ()
go [l]
xs (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n) t
e
        go [l]
_        Int
_ t
_ = () -> m ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
    
    getLeft :: AnyChunks rep e -> m [e]
getLeft  (AnyChunks [rep e]
es) = [[e]] -> [e]
forall l e (f :: * -> *). (Linear l e, Foldable f) => f l -> l
concat ([[e]] -> [e]) -> m [[e]] -> m [e]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (rep e -> m [e]) -> [rep e] -> m [[e]]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM rep e -> m [e]
forall (m :: * -> *) l e. LinearM m l e => l -> m [e]
getLeft [rep e]
es
    getRight :: AnyChunks rep e -> m [e]
getRight (AnyChunks [rep e]
es) = ([[e]] -> [e]
forall l e (f :: * -> *). (Linear l e, Foldable f) => f l -> l
concat ([[e]] -> [e]) -> ([[e]] -> [[e]]) -> [[e]] -> [e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[e]] -> [[e]]
forall l e. Linear l e => l -> l
reverse) ([[e]] -> [e]) -> m [[e]] -> m [e]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (rep e -> m [e]) -> [rep e] -> m [[e]]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM rep e -> m [e]
forall (m :: * -> *) l e. LinearM m l e => l -> m [e]
getRight [rep e]
es
    reversed :: AnyChunks rep e -> m (AnyChunks rep e)
reversed (AnyChunks [rep e]
es) = ([rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e)
-> ([rep e] -> [rep e]) -> [rep e] -> AnyChunks rep e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [rep e] -> [rep e]
forall l e. Linear l e => l -> l
reverse) ([rep e] -> AnyChunks rep e) -> m [rep e] -> m (AnyChunks rep e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (rep e -> m (rep e)) -> [rep e] -> m [rep e]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM rep e -> m (rep e)
forall (m :: * -> *) l e. LinearM m l e => l -> m l
reversed [rep e]
es
    
    filled :: Int -> e -> m (AnyChunks rep e)
filled Int
c e
e = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e) -> m [rep e] -> m (AnyChunks rep e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [m (rep e)] -> m [rep e]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence (Int -> m (rep e) -> [m (rep e)]
forall l e. Linear l e => Int -> e -> l
replicate Int
d (Int -> e -> m (rep e)
forall (m :: * -> *) l e. LinearM m l e => Int -> e -> m l
filled Int
lim e
e) [m (rep e)] -> m (rep e) -> [m (rep e)]
forall l e. Linear l e => l -> e -> l
:< Int -> e -> m (rep e)
forall (m :: * -> *) l e. LinearM m l e => Int -> e -> m l
filled Int
n e
e)
      where
        (Int
d, Int
n) = Int
c Int -> Int -> (Int, Int)
forall a. Integral a => a -> a -> (a, a)
`divMod` Int
lim
    
    -- TODO: rewrite without SplitM
    copyTo :: AnyChunks rep e -> Int -> AnyChunks rep e -> Int -> Int -> m ()
copyTo AnyChunks rep e
src Int
os AnyChunks rep e
trg Int
ot Int
c = Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
c Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
        Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
os Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
ot Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ String -> m ()
forall a. String -> a
underEx String
"copyTo"
        AnyChunks rep e
src' <- Int -> AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) s e. SplitM m s e => Int -> s -> m s
dropM Int
os AnyChunks rep e
src
        AnyChunks rep e
trg' <- Int -> AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) s e. SplitM m s e => Int -> s -> m s
dropM Int
ot AnyChunks rep e
trg
        Int -> AnyChunks rep e -> AnyChunks rep e -> m ()
forall (m :: * -> *) (rep :: * -> *) e.
(SplitM m (rep e) e, BorderedM m (rep e) Int) =>
Int -> AnyChunks rep e -> AnyChunks rep e -> m ()
go Int
c AnyChunks rep e
src' AnyChunks rep e
trg'
      where
        go :: Int -> AnyChunks rep e -> AnyChunks rep e -> m ()
go Int
n xs :: AnyChunks rep e
xs@(AnyChunks (rep e
x : [rep e]
_)) ys :: AnyChunks rep e
ys@(AnyChunks (rep e
y : [rep e]
_)) = do
          Int
n1 <- rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf rep e
x
          Int
n2 <- rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf rep e
y
          let n' :: Int
n' = [Int] -> Int
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Int
n1, Int
n2, Int
n]
          
          rep e -> Int -> rep e -> Int -> Int -> m ()
forall (m :: * -> *) l e.
LinearM m l e =>
l -> Int -> l -> Int -> Int -> m ()
copyTo rep e
x Int
0 rep e
y Int
0 Int
n'
          Int -> AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) s e. SplitM m s e => Int -> s -> m s
dropM Int
n' AnyChunks rep e
xs m (AnyChunks rep e)
-> m (AnyChunks rep e)
-> (AnyChunks rep e -> AnyChunks rep e -> m ())
-> m ()
forall (m :: * -> *) a b c.
Monad m =>
m a -> m b -> (a -> b -> m c) -> m c
>>=<< Int -> AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) s e. SplitM m s e => Int -> s -> m s
dropM Int
n' AnyChunks rep e
ys ((AnyChunks rep e -> AnyChunks rep e -> m ()) -> m ())
-> (AnyChunks rep e -> AnyChunks rep e -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ Int -> AnyChunks rep e -> AnyChunks rep e -> m ()
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n')
        go Int
n AnyChunks rep e
_ AnyChunks rep e
_ = Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ String -> m ()
forall a. String -> a
overEx String
"copyTo"
    
    -- | Unsafe, returns joined stream of existing chunks.
    merged :: f (AnyChunks rep e) -> m (AnyChunks rep e)
merged = AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) a. Monad m => a -> m a
return (AnyChunks rep e -> m (AnyChunks rep e))
-> (f (AnyChunks rep e) -> AnyChunks rep e)
-> f (AnyChunks rep e)
-> m (AnyChunks rep e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e)
-> (f (AnyChunks rep e) -> [rep e])
-> f (AnyChunks rep e)
-> AnyChunks rep e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (AnyChunks rep e -> [rep e] -> [rep e])
-> [rep e] -> f (AnyChunks rep e) -> [rep e]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ([rep e] -> [rep e] -> [rep e]
forall l e. Linear l e => l -> l -> l
(++) ([rep e] -> [rep e] -> [rep e])
-> (AnyChunks rep e -> [rep e])
-> AnyChunks rep e
-> [rep e]
-> [rep e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks) []
    
    ofoldrM :: (Int -> e -> r -> m r) -> r -> AnyChunks rep e -> m r
ofoldrM Int -> e -> r -> m r
f r
base' = Int -> r -> [rep e] -> m r
ofoldrCh Int
0 r
base' ([rep e] -> m r)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> m r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        ofoldrCh :: Int -> r -> [rep e] -> m r
ofoldrCh !Int
o r
base (rep e
x : [rep e]
xs) = do
          Int
n   <- rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf rep e
x
          r
xs' <- Int -> r -> [rep e] -> m r
ofoldrCh (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n) r
base [rep e]
xs
          (Int -> e -> r -> m r) -> r -> rep e -> m r
forall (m :: * -> *) l e r.
LinearM m l e =>
(Int -> e -> r -> m r) -> r -> l -> m r
ofoldrM (Int -> e -> r -> m r
f (Int -> e -> r -> m r) -> (Int -> Int) -> Int -> e -> r -> m r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+)) r
xs' rep e
x
        ofoldrCh Int
_ r
base [rep e]
_ = r -> m r
forall (m :: * -> *) a. Monad m => a -> m a
return r
base
    
    ofoldlM :: (Int -> r -> e -> m r) -> r -> AnyChunks rep e -> m r
ofoldlM Int -> r -> e -> m r
f r
base' = Int -> r -> [rep e] -> m r
ofoldlCh Int
0 r
base' ([rep e] -> m r)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> m r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        ofoldlCh :: Int -> r -> [rep e] -> m r
ofoldlCh !Int
o r
base (rep e
x : [rep e]
xs) = do
          Int
n  <- rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf rep e
x
          r
x' <- (Int -> r -> e -> m r) -> r -> rep e -> m r
forall (m :: * -> *) l e r.
LinearM m l e =>
(Int -> r -> e -> m r) -> r -> l -> m r
ofoldlM (Int -> r -> e -> m r
f (Int -> r -> e -> m r) -> (Int -> Int) -> Int -> r -> e -> m r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+)) r
base rep e
x
          Int -> r -> [rep e] -> m r
ofoldlCh (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n) r
x' [rep e]
xs
        ofoldlCh Int
_ r
base [rep e]
_ = r -> m r
forall (m :: * -> *) a. Monad m => a -> m a
return r
base
    
    foldrM :: (e -> r -> m r) -> r -> AnyChunks rep e -> m r
foldrM e -> r -> m r
f r
base = (rep e -> m r -> m r) -> m r -> [rep e] -> m r
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((r -> m r) -> m r -> m r
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
(=<<) ((r -> m r) -> m r -> m r)
-> (rep e -> r -> m r) -> rep e -> m r -> m r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (r -> rep e -> m r) -> rep e -> r -> m r
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((e -> r -> m r) -> r -> rep e -> m r
forall (m :: * -> *) l e r.
LinearM m l e =>
(e -> r -> m r) -> r -> l -> m r
foldrM e -> r -> m r
f)) (r -> m r
forall (m :: * -> *) a. Monad m => a -> m a
return r
base) ([rep e] -> m r)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> m r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    foldlM :: (r -> e -> m r) -> r -> AnyChunks rep e -> m r
foldlM r -> e -> m r
f r
base = (m r -> rep e -> m r) -> m r -> [rep e] -> m r
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ((rep e -> m r -> m r) -> m r -> rep e -> m r
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((rep e -> m r -> m r) -> m r -> rep e -> m r)
-> (rep e -> m r -> m r) -> m r -> rep e -> m r
forall a b. (a -> b) -> a -> b
$ (r -> m r) -> m r -> m r
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
(=<<) ((r -> m r) -> m r -> m r)
-> (rep e -> r -> m r) -> rep e -> m r -> m r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (r -> rep e -> m r) -> rep e -> r -> m r
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((r -> e -> m r) -> r -> rep e -> m r
forall (m :: * -> *) l e r.
LinearM m l e =>
(r -> e -> m r) -> r -> l -> m r
foldlM r -> e -> m r
f)) (r -> m r
forall (m :: * -> *) a. Monad m => a -> m a
return r
base) ([rep e] -> m r)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> m r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks

instance (BorderedM1 m rep Int e, SplitM1 m rep e) => SplitM m (AnyChunks rep e) e
  where
    takeM :: Int -> AnyChunks rep e -> m (AnyChunks rep e)
takeM Int
n (AnyChunks (rep e
e : [rep e]
es)) = Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Bool
-> m (AnyChunks rep e)
-> m (AnyChunks rep e)
-> m (AnyChunks rep e)
forall a. Bool -> a -> a -> a
? m (AnyChunks rep e)
forall (m :: * -> *) l e. LinearM m l e => m l
newNull (m (AnyChunks rep e) -> m (AnyChunks rep e))
-> m (AnyChunks rep e) -> m (AnyChunks rep e)
forall a b. (a -> b) -> a -> b
$ do
      Int
c <- rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf rep e
e
      case Int
n Compare Int
forall o. Ord o => Compare o
<=> Int
c of
        Ordering
EQ -> AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) a. Monad m => a -> m a
return ([rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e
e])
        Ordering
LT -> do rep e
t <- Int -> rep e -> m (rep e)
forall (m :: * -> *) s e. SplitM m s e => Int -> s -> m s
takeM Int
n rep e
e; AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) a. Monad m => a -> m a
return ([rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e
t])
        Ordering
GT -> do (AnyChunks [rep e]
ts) <- Int -> AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) s e. SplitM m s e => Int -> s -> m s
takeM (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
c) ([rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
es); AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) a. Monad m => a -> m a
return (AnyChunks rep e -> m (AnyChunks rep e))
-> AnyChunks rep e -> m (AnyChunks rep e)
forall a b. (a -> b) -> a -> b
$ [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks (rep e
e rep e -> [rep e] -> [rep e]
forall a. a -> [a] -> [a]
: [rep e]
ts)
    takeM Int
_ AnyChunks rep e
es = AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) a. Monad m => a -> m a
return AnyChunks rep e
es
    
    dropM :: Int -> AnyChunks rep e -> m (AnyChunks rep e)
dropM Int
n es' :: AnyChunks rep e
es'@(AnyChunks (rep e
e : [rep e]
es)) = Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Bool
-> m (AnyChunks rep e)
-> m (AnyChunks rep e)
-> m (AnyChunks rep e)
forall a. Bool -> a -> a -> a
? AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) a. Monad m => a -> m a
return AnyChunks rep e
es' (m (AnyChunks rep e) -> m (AnyChunks rep e))
-> m (AnyChunks rep e) -> m (AnyChunks rep e)
forall a b. (a -> b) -> a -> b
$ do
      Int
c <- rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf rep e
e
      case Int
n Compare Int
forall o. Ord o => Compare o
<=> Int
c of
        Ordering
EQ -> AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) a. Monad m => a -> m a
return ([rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
es)
        Ordering
GT -> Int -> AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) s e. SplitM m s e => Int -> s -> m s
dropM (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
c) ([rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
es)
        Ordering
LT -> do rep e
d <- Int -> rep e -> m (rep e)
forall (m :: * -> *) s e. SplitM m s e => Int -> s -> m s
dropM Int
n rep e
e; AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) a. Monad m => a -> m a
return (AnyChunks rep e -> m (AnyChunks rep e))
-> AnyChunks rep e -> m (AnyChunks rep e)
forall a b. (a -> b) -> a -> b
$ [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks (rep e
d rep e -> [rep e] -> [rep e]
forall a. a -> [a] -> [a]
: [rep e]
es)
    dropM Int
_ AnyChunks rep e
es = AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) a. Monad m => a -> m a
return AnyChunks rep e
es
    
    prefixM :: (e -> Bool) -> AnyChunks rep e -> m Int
prefixM e -> Bool
f (AnyChunks [rep e]
es) = (rep e -> m Int -> m Int) -> m Int -> [rep e] -> m Int
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\ rep e
e m Int
p -> do Int
n <- rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf rep e
e; Int
c <- (e -> Bool) -> rep e -> m Int
forall (m :: * -> *) s e. SplitM m s e => (e -> Bool) -> s -> m Int
prefixM e -> Bool
f rep e
e; Int
c Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n Bool -> m Int -> m Int -> m Int
forall a. Bool -> a -> a -> a
? (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
c) (Int -> Int) -> m Int -> m Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> m Int
p (m Int -> m Int) -> m Int -> m Int
forall a b. (a -> b) -> a -> b
$ Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return Int
c) (Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return Int
0) [rep e]
es
    suffixM :: (e -> Bool) -> AnyChunks rep e -> m Int
suffixM e -> Bool
f (AnyChunks [rep e]
es) = (m Int -> rep e -> m Int) -> m Int -> [rep e] -> m Int
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (\ m Int
p rep e
e -> do Int
n <- rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf rep e
e; Int
c <- (e -> Bool) -> rep e -> m Int
forall (m :: * -> *) s e. SplitM m s e => (e -> Bool) -> s -> m Int
suffixM e -> Bool
f rep e
e; Int
c Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n Bool -> m Int -> m Int -> m Int
forall a. Bool -> a -> a -> a
? (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
c) (Int -> Int) -> m Int -> m Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> m Int
p (m Int -> m Int) -> m Int -> m Int
forall a b. (a -> b) -> a -> b
$ Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return Int
c) (Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return Int
0) [rep e]
es
    mprefix :: (e -> m Bool) -> AnyChunks rep e -> m Int
mprefix e -> m Bool
f (AnyChunks [rep e]
es) = (rep e -> m Int -> m Int) -> m Int -> [rep e] -> m Int
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\ rep e
e m Int
p -> do Int
n <- rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf rep e
e; Int
c <- (e -> m Bool) -> rep e -> m Int
forall (m :: * -> *) s e.
SplitM m s e =>
(e -> m Bool) -> s -> m Int
mprefix e -> m Bool
f rep e
e; Int
c Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n Bool -> m Int -> m Int -> m Int
forall a. Bool -> a -> a -> a
? (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
c) (Int -> Int) -> m Int -> m Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> m Int
p (m Int -> m Int) -> m Int -> m Int
forall a b. (a -> b) -> a -> b
$ Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return Int
c) (Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return Int
0) [rep e]
es
    msuffix :: (e -> m Bool) -> AnyChunks rep e -> m Int
msuffix e -> m Bool
f (AnyChunks [rep e]
es) = (m Int -> rep e -> m Int) -> m Int -> [rep e] -> m Int
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (\ m Int
p rep e
e -> do Int
n <- rep e -> m Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf rep e
e; Int
c <- (e -> m Bool) -> rep e -> m Int
forall (m :: * -> *) s e.
SplitM m s e =>
(e -> m Bool) -> s -> m Int
msuffix e -> m Bool
f rep e
e; Int
c Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n Bool -> m Int -> m Int -> m Int
forall a. Bool -> a -> a -> a
? (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
c) (Int -> Int) -> m Int -> m Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> m Int
p (m Int -> m Int) -> m Int -> m Int
forall a b. (a -> b) -> a -> b
$ Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return Int
c) (Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return Int
0) [rep e]
es

--------------------------------------------------------------------------------

{- Set and Scan instances. -}

instance (Nullable (AnyChunks rep e), SetWith1 (AnyChunks rep) e, Ord e) => Set (AnyChunks rep e) e

instance (SetWith1 rep e, Linear1 rep e, Ord (rep e), Bordered1 rep Int e) => SetWith (AnyChunks rep e) e
  where
    insertWith :: Compare e -> e -> AnyChunks rep e -> AnyChunks rep e
insertWith Compare e
f' e
e' = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e)
-> (AnyChunks rep e -> [rep e])
-> AnyChunks rep e
-> AnyChunks rep e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Compare e -> e -> [rep e] -> [rep e]
forall a e.
(SetWith a e, Linear a e) =>
Compare e -> e -> [a] -> [a]
go Compare e
f' e
e' ([rep e] -> [rep e])
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> [rep e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        go :: Compare e -> e -> [a] -> [a]
go Compare e
f e
e (a
x : [a]
xs) = Compare e -> e -> a -> Bool
forall s o. SetWith s o => Compare o -> o -> s -> Bool
memberWith Compare e
f e
e a
x Bool -> [a] -> [a] -> [a]
forall a. Bool -> a -> a -> a
? Compare e -> e -> a -> a
forall s o. SetWith s o => Compare o -> o -> s -> s
insertWith Compare e
f e
e a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: Compare e -> e -> [a] -> [a]
go Compare e
f e
e [a]
xs
        go Compare e
_ e
e        [a]
_ = [e -> a
forall l e. Linear l e => e -> l
single e
e]
    
    deleteWith :: Compare e -> e -> AnyChunks rep e -> AnyChunks rep e
deleteWith Compare e
f' e
e' = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e)
-> (AnyChunks rep e -> [rep e])
-> AnyChunks rep e
-> AnyChunks rep e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Compare e -> e -> [rep e] -> [rep e]
forall a t. SetWith a t => Compare t -> t -> [a] -> [a]
go Compare e
f' e
e' ([rep e] -> [rep e])
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> [rep e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        go :: Compare t -> t -> [a] -> [a]
go Compare t
f t
e (a
x : [a]
xs) = Compare t -> t -> a -> Bool
forall s o. SetWith s o => Compare o -> o -> s -> Bool
memberWith Compare t
f t
e a
x Bool -> [a] -> [a] -> [a]
forall a. Bool -> a -> a -> a
? Compare t -> t -> a -> a
forall s o. SetWith s o => Compare o -> o -> s -> s
deleteWith Compare t
f t
e a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: Compare t -> t -> [a] -> [a]
go Compare t
f t
e [a]
xs
        go Compare t
_ t
_        [a]
_ = []
    
    intersectionWith :: Compare e -> AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e
intersectionWith Compare e
f = [e] -> AnyChunks rep e
forall l e. Linear l e => [e] -> l
fromList ([e] -> AnyChunks rep e)
-> (AnyChunks rep e -> AnyChunks rep e -> [e])
-> AnyChunks rep e
-> AnyChunks rep e
-> AnyChunks rep e
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
... ([e] -> [e] -> [e])
-> (AnyChunks rep e -> [e])
-> AnyChunks rep e
-> AnyChunks rep e
-> [e]
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
on (Compare e -> [e] -> [e] -> [e]
forall s o. SetWith s o => Compare o -> s -> s -> s
intersectionWith Compare e
f) AnyChunks rep e -> [e]
forall l e. Linear l e => l -> [e]
listL
    differenceWith :: Compare e -> AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e
differenceWith   Compare e
f = [e] -> AnyChunks rep e
forall l e. Linear l e => [e] -> l
fromList ([e] -> AnyChunks rep e)
-> (AnyChunks rep e -> AnyChunks rep e -> [e])
-> AnyChunks rep e
-> AnyChunks rep e
-> AnyChunks rep e
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
... ([e] -> [e] -> [e])
-> (AnyChunks rep e -> [e])
-> AnyChunks rep e
-> AnyChunks rep e
-> [e]
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
on (Compare e -> [e] -> [e] -> [e]
forall s o. SetWith s o => Compare o -> s -> s -> s
differenceWith   Compare e
f) AnyChunks rep e -> [e]
forall l e. Linear l e => l -> [e]
listL
    symdiffWith :: Compare e -> AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e
symdiffWith      Compare e
f = [e] -> AnyChunks rep e
forall l e. Linear l e => [e] -> l
fromList ([e] -> AnyChunks rep e)
-> (AnyChunks rep e -> AnyChunks rep e -> [e])
-> AnyChunks rep e
-> AnyChunks rep e
-> AnyChunks rep e
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
... ([e] -> [e] -> [e])
-> (AnyChunks rep e -> [e])
-> AnyChunks rep e
-> AnyChunks rep e
-> [e]
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
on (Compare e -> [e] -> [e] -> [e]
forall s o. SetWith s o => Compare o -> s -> s -> s
symdiffWith      Compare e
f) AnyChunks rep e -> [e]
forall l e. Linear l e => l -> [e]
listL
    unionWith :: Compare e -> AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e
unionWith        Compare e
f = [e] -> AnyChunks rep e
forall l e. Linear l e => [e] -> l
fromList ([e] -> AnyChunks rep e)
-> (AnyChunks rep e -> AnyChunks rep e -> [e])
-> AnyChunks rep e
-> AnyChunks rep e
-> AnyChunks rep e
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
... ([e] -> [e] -> [e])
-> (AnyChunks rep e -> [e])
-> AnyChunks rep e
-> AnyChunks rep e
-> [e]
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
on (Compare e -> [e] -> [e] -> [e]
forall s o. SetWith s o => Compare o -> s -> s -> s
unionWith        Compare e
f) AnyChunks rep e -> [e]
forall l e. Linear l e => l -> [e]
listL
    
    lookupLTWith :: Compare e -> e -> AnyChunks rep e -> Maybe e
lookupLTWith Compare e
f e
o = (rep e -> Maybe e -> Maybe e) -> Maybe e -> [rep e] -> Maybe e
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Maybe e -> Maybe e -> Maybe e
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>) (Maybe e -> Maybe e -> Maybe e)
-> (rep e -> Maybe e) -> rep e -> Maybe e -> Maybe e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Compare e -> e -> rep e -> Maybe e
forall s o. SetWith s o => Compare o -> o -> s -> Maybe o
lookupLTWith Compare e
f e
o) Maybe e
forall a. Maybe a
Nothing ([rep e] -> Maybe e)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> Maybe e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    lookupLEWith :: Compare e -> e -> AnyChunks rep e -> Maybe e
lookupLEWith Compare e
f e
o = (rep e -> Maybe e -> Maybe e) -> Maybe e -> [rep e] -> Maybe e
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Maybe e -> Maybe e -> Maybe e
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>) (Maybe e -> Maybe e -> Maybe e)
-> (rep e -> Maybe e) -> rep e -> Maybe e -> Maybe e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Compare e -> e -> rep e -> Maybe e
forall s o. SetWith s o => Compare o -> o -> s -> Maybe o
lookupLEWith Compare e
f e
o) Maybe e
forall a. Maybe a
Nothing ([rep e] -> Maybe e)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> Maybe e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    lookupGTWith :: Compare e -> e -> AnyChunks rep e -> Maybe e
lookupGTWith Compare e
f e
o = (rep e -> Maybe e -> Maybe e) -> Maybe e -> [rep e] -> Maybe e
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Maybe e -> Maybe e -> Maybe e
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>) (Maybe e -> Maybe e -> Maybe e)
-> (rep e -> Maybe e) -> rep e -> Maybe e -> Maybe e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Compare e -> e -> rep e -> Maybe e
forall s o. SetWith s o => Compare o -> o -> s -> Maybe o
lookupGTWith Compare e
f e
o) Maybe e
forall a. Maybe a
Nothing ([rep e] -> Maybe e)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> Maybe e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    lookupGEWith :: Compare e -> e -> AnyChunks rep e -> Maybe e
lookupGEWith Compare e
f e
o = (rep e -> Maybe e -> Maybe e) -> Maybe e -> [rep e] -> Maybe e
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Maybe e -> Maybe e -> Maybe e
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>) (Maybe e -> Maybe e -> Maybe e)
-> (rep e -> Maybe e) -> rep e -> Maybe e -> Maybe e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Compare e -> e -> rep e -> Maybe e
forall s o. SetWith s o => Compare o -> o -> s -> Maybe o
lookupGEWith Compare e
f e
o) Maybe e
forall a. Maybe a
Nothing ([rep e] -> Maybe e)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> Maybe e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
    
    memberWith :: Compare e -> e -> AnyChunks rep e -> Bool
memberWith Compare e
f e
x (AnyChunks [rep e]
es) = Compare e -> e -> rep e -> Bool
forall s o. SetWith s o => Compare o -> o -> s -> Bool
memberWith Compare e
f e
x (rep e -> Bool) -> [rep e] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
`any` [rep e]
es
    
    isSubsetWith :: Compare e -> AnyChunks rep e -> AnyChunks rep e -> Bool
isSubsetWith Compare e
f AnyChunks rep e
xs AnyChunks rep e
ys = (e -> Bool -> Bool) -> Bool -> AnyChunks rep e -> Bool
forall l e b. Linear l e => (e -> b -> b) -> b -> l -> b
o_foldr (\ e
e Bool
b -> Compare e -> e -> AnyChunks rep e -> Bool
forall s o. SetWith s o => Compare o -> o -> s -> Bool
memberWith Compare e
f e
e AnyChunks rep e
ys Bool -> Bool -> Bool
&& Bool
b) Bool
True AnyChunks rep e
xs

instance (Linear1 (AnyChunks rep) e) => Scan (AnyChunks rep e) e

--------------------------------------------------------------------------------

{- Indexed instance. -}

instance (Indexed1 rep Int e) => Map (AnyChunks rep e) Int e
  where
    toMap :: [(Int, e)] -> AnyChunks rep e
toMap [(Int, e)]
ascs = [(Int, e)] -> Bool
forall e. Nullable e => e -> Bool
isNull [(Int, e)]
ascs Bool -> AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e
forall a. Bool -> a -> a -> a
? AnyChunks rep e
forall e. Nullable e => e
Z (AnyChunks rep e -> AnyChunks rep e)
-> AnyChunks rep e -> AnyChunks rep e
forall a b. (a -> b) -> a -> b
$ (Int, Int) -> [(Int, e)] -> AnyChunks rep e
forall v i e. Indexed v i e => (i, i) -> [(i, e)] -> v
assoc ([(Int, e)] -> (Int, Int)
forall a b. Ord a => [(a, b)] -> (a, a)
ascsBounds [(Int, e)]
ascs) [(Int, e)]
ascs
    
    toMap' :: e -> [(Int, e)] -> AnyChunks rep e
toMap' e
defvalue [(Int, e)]
ascs = [(Int, e)] -> Bool
forall e. Nullable e => e -> Bool
isNull [(Int, e)]
ascs Bool -> AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e
forall a. Bool -> a -> a -> a
? AnyChunks rep e
forall e. Nullable e => e
Z (AnyChunks rep e -> AnyChunks rep e)
-> AnyChunks rep e -> AnyChunks rep e
forall a b. (a -> b) -> a -> b
$ (Int, Int) -> e -> [(Int, e)] -> AnyChunks rep e
forall v i e. Indexed v i e => (i, i) -> e -> [(i, e)] -> v
assoc' ([(Int, e)] -> (Int, Int)
forall a b. Ord a => [(a, b)] -> (a, a)
ascsBounds [(Int, e)]
ascs) e
defvalue [(Int, e)]
ascs
    
    .! :: AnyChunks rep e -> Int -> e
(.!) = AnyChunks rep e -> Int -> e
forall l e. Linear l e => l -> Int -> e
(!^)
    
    AnyChunks rep e
Z            // :: AnyChunks rep e -> [(Int, e)] -> AnyChunks rep e
// [(Int, e)]
ascs = [(Int, e)] -> AnyChunks rep e
forall map key e. Map map key e => [(key, e)] -> map
toMap [(Int, e)]
ascs
    AnyChunks [rep e]
es // [(Int, e)]
ascs = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks (Int -> [rep e] -> [(Int, e)] -> [rep e]
go Int
0 [rep e]
es [(Int, e)]
ascs)
      where
        go :: Int -> [rep e] -> [(Int, e)] -> [rep e]
go Int
_    []     [(Int, e)]
_  = []
        go Int
_    [rep e]
xs    [ ] = [rep e]
xs
        go Int
l (rep e
x : [rep e]
xs) [(Int, e)]
ies = rep e
x rep e -> [(Int, e)] -> rep e
forall map key e. Map map key e => map -> [(key, e)] -> map
// [(Int, e)]
as rep e -> [rep e] -> [rep e]
forall a. a -> [a] -> [a]
: Int -> [rep e] -> [(Int, e)] -> [rep e]
go Int
n [rep e]
xs [(Int, e)]
bs
          where
            ([(Int, e)]
as, [(Int, e)]
bs) = ((Int, e) -> Bool) -> [(Int, e)] -> ([(Int, e)], [(Int, e)])
forall l e. Linear l e => (e -> Bool) -> l -> (l, l)
partition ((Int, Int) -> Int -> Bool
forall i. Index i => (i, i) -> i -> Bool
inRange (Int
l, Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (Int -> Bool) -> ((Int, e) -> Int) -> (Int, e) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, e) -> Int
forall a b. (a, b) -> a
fst) [(Int, e)]
ies
            n :: Int
n = Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ [rep e] -> Int
forall b i. Bordered b i => b -> Int
sizeOf [rep e]
es
    
    e -> Bool
p .$ :: (e -> Bool) -> AnyChunks rep e -> Maybe Int
.$ AnyChunks (rep e
x : [rep e]
xs) = e -> Bool
p (e -> Bool) -> rep e -> Maybe Int
forall map key e. Map map key e => (e -> Bool) -> map -> Maybe key
.$ rep e
x Maybe Int -> Maybe Int -> Maybe Int
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
x) (Int -> Int) -> Maybe Int -> Maybe Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> e -> Bool
p (e -> Bool) -> AnyChunks rep e -> Maybe Int
forall map key e. Map map key e => (e -> Bool) -> map -> Maybe key
.$ [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
xs
    e -> Bool
_ .$                  AnyChunks rep e
_ = Maybe Int
forall a. Maybe a
Nothing
    
    e -> Bool
p *$ :: (e -> Bool) -> AnyChunks rep e -> [Int]
*$ AnyChunks (rep e
x : [rep e]
xs) = e -> Bool
p (e -> Bool) -> rep e -> [Int]
forall map key e. Map map key e => (e -> Bool) -> map -> [key]
*$ rep e
x [Int] -> [Int] -> [Int]
forall l e. Linear l e => l -> l -> l
++ (Int -> Int) -> [Int] -> [Int]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ rep e -> Int
forall b i. Bordered b i => b -> Int
sizeOf rep e
x) (e -> Bool
p (e -> Bool) -> AnyChunks rep e -> [Int]
forall map key e. Map map key e => (e -> Bool) -> map -> [key]
*$ [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [rep e]
xs)
    e -> Bool
_ *$                  AnyChunks rep e
_ = []
    
    kfoldr :: (Int -> e -> b -> b) -> b -> AnyChunks rep e -> b
kfoldr Int -> e -> b -> b
f b
base AnyChunks rep e
es = let bnds :: (Int, Int)
bnds = AnyChunks rep e -> (Int, Int)
forall b i. Bordered b i => b -> (i, i)
bounds AnyChunks rep e
es in (Int -> e -> b -> b) -> b -> AnyChunks rep e -> b
forall map key e b.
Map map key e =>
(key -> e -> b -> b) -> b -> map -> b
kfoldr (Int -> e -> b -> b
f (Int -> e -> b -> b) -> (Int -> Int) -> Int -> e -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, Int) -> Int -> Int
forall i. Index i => (i, i) -> Int -> i
index (Int, Int)
bnds) b
base AnyChunks rep e
es
    kfoldl :: (Int -> b -> e -> b) -> b -> AnyChunks rep e -> b
kfoldl Int -> b -> e -> b
f b
base AnyChunks rep e
es = let bnds :: (Int, Int)
bnds = AnyChunks rep e -> (Int, Int)
forall b i. Bordered b i => b -> (i, i)
bounds AnyChunks rep e
es in (Int -> b -> e -> b) -> b -> AnyChunks rep e -> b
forall map key e b.
Map map key e =>
(key -> b -> e -> b) -> b -> map -> b
kfoldl (Int -> b -> e -> b
f (Int -> b -> e -> b) -> (Int -> Int) -> Int -> b -> e -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, Int) -> Int -> Int
forall i. Index i => (i, i) -> Int -> i
index (Int, Int)
bnds) b
base AnyChunks rep e
es

instance (Indexed1 rep Int e) => Indexed (AnyChunks rep e) Int e
  where
    assoc :: (Int, Int) -> [(Int, e)] -> AnyChunks rep e
assoc (Int, Int)
bnds [(Int, e)]
ascs = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ((Int, Int) -> [(Int, e)] -> [rep e]
forall a b. Indexed a Int b => (Int, Int) -> [(Int, b)] -> [a]
go (Int, Int)
bnds [(Int, e)]
ascs)
      where
        go :: (Int, Int) -> [(Int, b)] -> [a]
go (Int
l, Int
u) [(Int, b)]
ies = (Int, Int) -> Bool
forall i. Index i => (i, i) -> Bool
isEmpty (Int
l, Int
u) Bool -> [a] -> [a] -> [a]
forall a. Bool -> a -> a -> a
? [] ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ (Int, Int) -> [(Int, b)] -> a
forall v i e. Indexed v i e => (i, i) -> [(i, e)] -> v
assoc (Int
l, Int
n) [(Int, b)]
as a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (Int, Int) -> [(Int, b)] -> [a]
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, Int
u) [(Int, b)]
bs
          where
            ([(Int, b)]
as, [(Int, b)]
bs) = ((Int, b) -> Bool) -> [(Int, b)] -> ([(Int, b)], [(Int, b)])
forall l e. Linear l e => (e -> Bool) -> l -> (l, l)
partition ((Int, Int) -> Int -> Bool
forall i. Index i => (i, i) -> i -> Bool
inRange (Int
l, Int
n) (Int -> Bool) -> ((Int, b) -> Int) -> (Int, b) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, b) -> Int
forall a b. (a, b) -> a
fst) [(Int, b)]
ies
            n :: Int
n = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
u (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lim)
    
    assoc' :: (Int, Int) -> e -> [(Int, e)] -> AnyChunks rep e
assoc' (Int, Int)
bnds e
defvalue [(Int, e)]
ascs = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ((Int, Int) -> [(Int, e)] -> [rep e]
go (Int, Int)
bnds [(Int, e)]
ascs)
      where
        go :: (Int, Int) -> [(Int, e)] -> [rep e]
go (Int
l, Int
u) [(Int, e)]
ies = (Int, Int) -> Bool
forall i. Index i => (i, i) -> Bool
isEmpty (Int
l, Int
u) Bool -> [rep e] -> [rep e] -> [rep e]
forall a. Bool -> a -> a -> a
? [] ([rep e] -> [rep e]) -> [rep e] -> [rep e]
forall a b. (a -> b) -> a -> b
$ (Int, Int) -> e -> [(Int, e)] -> rep e
forall v i e. Indexed v i e => (i, i) -> e -> [(i, e)] -> v
assoc' (Int
l, Int
n) e
defvalue [(Int, e)]
as rep e -> [rep e] -> [rep e]
forall a. a -> [a] -> [a]
: (Int, Int) -> [(Int, e)] -> [rep e]
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, Int
u) [(Int, e)]
bs
          where
            ([(Int, e)]
as, [(Int, e)]
bs) = ((Int, e) -> Bool) -> [(Int, e)] -> ([(Int, e)], [(Int, e)])
forall l e. Linear l e => (e -> Bool) -> l -> (l, l)
partition ((Int, Int) -> Int -> Bool
forall i. Index i => (i, i) -> i -> Bool
inRange (Int
l, Int
n) (Int -> Bool) -> ((Int, e) -> Int) -> (Int, e) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, e) -> Int
forall a b. (a, b) -> a
fst) [(Int, e)]
ies
            n :: Int
n = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
u (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lim)
    
    fromIndexed :: m -> AnyChunks rep e
fromIndexed m
es = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks [m -> rep e
forall v i e m j. (Indexed v i e, Indexed m j e) => m -> v
fromIndexed m
es]

--------------------------------------------------------------------------------

{- MapM, IndexedM and SortM instances. -}

instance (SplitM1 m rep e, MapM1 m rep Int e, BorderedM1 m rep Int e) => MapM m (AnyChunks rep e) Int e
  where
    newMap :: [(Int, e)] -> m (AnyChunks rep e)
newMap [(Int, e)]
ascs = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e) -> m [rep e] -> m (AnyChunks rep e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [m (rep e)] -> m [rep e]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence ((Int, Int) -> [(Int, e)] -> [m (rep e)]
forall (m :: * -> *) map b.
MapM m map Int b =>
(Int, Int) -> [(Int, b)] -> [m map]
go ([(Int, e)] -> (Int, Int)
forall a b. Ord a => [(a, b)] -> (a, a)
ascsBounds [(Int, e)]
ascs) [(Int, e)]
ascs)
      where
        go :: (Int, Int) -> [(Int, b)] -> [m map]
go (Int
l, Int
u) [(Int, b)]
ies = (Int, Int) -> Bool
forall i. Index i => (i, i) -> Bool
isEmpty (Int
l, Int
u) Bool -> [m map] -> [m map] -> [m map]
forall a. Bool -> a -> a -> a
? [] ([m map] -> [m map]) -> [m map] -> [m map]
forall a b. (a -> b) -> a -> b
$ [(Int, b)] -> m map
forall (m :: * -> *) map key e.
MapM m map key e =>
[(key, e)] -> m map
newMap [(Int, b)]
as m map -> [m map] -> [m map]
forall a. a -> [a] -> [a]
: (Int, Int) -> [(Int, b)] -> [m map]
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, Int
u) [(Int, b)]
bs
          where
            ([(Int, b)]
as, [(Int, b)]
bs) = ((Int, b) -> Bool) -> [(Int, b)] -> ([(Int, b)], [(Int, b)])
forall l e. Linear l e => (e -> Bool) -> l -> (l, l)
partition ((Int, Int) -> Int -> Bool
forall i. Index i => (i, i) -> i -> Bool
inRange (Int
l, Int
n) (Int -> Bool) -> ((Int, b) -> Int) -> (Int, b) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, b) -> Int
forall a b. (a, b) -> a
fst) [(Int, b)]
ies
            n :: Int
n = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
u (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lim)
    
    newMap' :: e -> [(Int, e)] -> m (AnyChunks rep e)
newMap' e
defvalue [(Int, e)]
ascs = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e) -> m [rep e] -> m (AnyChunks rep e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [m (rep e)] -> m [rep e]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence ((Int, Int) -> [(Int, e)] -> [m (rep e)]
go ([(Int, e)] -> (Int, Int)
forall a b. Ord a => [(a, b)] -> (a, a)
ascsBounds [(Int, e)]
ascs) [(Int, e)]
ascs)
      where
        go :: (Int, Int) -> [(Int, e)] -> [m (rep e)]
go (Int
l, Int
u) [(Int, e)]
ies = e -> [(Int, e)] -> m (rep e)
forall (m :: * -> *) map key e.
MapM m map key e =>
e -> [(key, e)] -> m map
newMap' e
defvalue [(Int, e)]
as m (rep e) -> [m (rep e)] -> [m (rep e)]
forall a. a -> [a] -> [a]
: (Int, Int) -> [(Int, e)] -> [m (rep e)]
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, Int
u) [(Int, e)]
bs
          where
            ([(Int, e)]
as, [(Int, e)]
bs) = ((Int, e) -> Bool) -> [(Int, e)] -> ([(Int, e)], [(Int, e)])
forall l e. Linear l e => (e -> Bool) -> l -> (l, l)
partition ((Int, Int) -> Int -> Bool
forall i. Index i => (i, i) -> i -> Bool
inRange (Int
l, Int
n) (Int -> Bool) -> ((Int, e) -> Int) -> (Int, e) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, e) -> Int
forall a b. (a, b) -> a
fst) [(Int, e)]
ies
            n :: Int
n = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
u (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lim)
    
    {-# INLINE (>!) #-}
    AnyChunks rep e
es >! :: AnyChunks rep e -> Int -> m e
>! Int
i = Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> m e -> m e -> m e
forall a. Bool -> a -> a -> a
? String -> m e
forall a. String -> a
overEx String
"(>!)" (m e -> m e) -> m e -> m e
forall a b. (a -> b) -> a -> b
$ AnyChunks rep e
es AnyChunks rep e -> Int -> m e
forall (m :: * -> *) l e. LinearM m l e => l -> Int -> m e
!#> Int
i
    
    overwrite :: AnyChunks rep e -> [(Int, e)] -> m (AnyChunks rep e)
overwrite es' :: AnyChunks rep e
es'@(AnyChunks []) [(Int, e)]
ascs = [(Int, e)] -> Bool
forall e. Nullable e => e -> Bool
isNull [(Int, e)]
ascs Bool
-> m (AnyChunks rep e)
-> m (AnyChunks rep e)
-> m (AnyChunks rep e)
forall a. Bool -> a -> a -> a
? AnyChunks rep e -> m (AnyChunks rep e)
forall (m :: * -> *) a. Monad m => a -> m a
return AnyChunks rep e
es' (m (AnyChunks rep e) -> m (AnyChunks rep e))
-> m (AnyChunks rep e) -> m (AnyChunks rep e)
forall a b. (a -> b) -> a -> b
$ [(Int, e)] -> m (AnyChunks rep e)
forall (m :: * -> *) map key e.
MapM m map key e =>
[(key, e)] -> m map
newMap [(Int, e)]
ascs
    overwrite es' :: AnyChunks rep e
es'@(AnyChunks [rep e]
es) [(Int, e)]
ascs = AnyChunks rep e
es' AnyChunks rep e -> m () -> m (AnyChunks rep e)
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ Int -> [rep e] -> [(Int, e)] -> m ()
forall (f :: * -> *) a i b.
(BorderedM f a i, MapM f a Int b) =>
Int -> [a] -> [(Int, b)] -> f ()
go Int
0 [rep e]
es ((Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0) (Int -> Bool) -> ((Int, e) -> Int) -> (Int, e) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, e) -> Int
forall a b. (a, b) -> a
fst ((Int, e) -> Bool) -> [(Int, e)] -> [(Int, e)]
forall l e. Linear l e => (e -> Bool) -> l -> l
`except` [(Int, e)]
ascs)
      where
        go :: Int -> [a] -> [(Int, b)] -> f ()
go Int
o (a
x : [a]
xs) [(Int, b)]
ie = Bool -> f () -> f ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless ([(Int, b)] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [(Int, b)]
ie) (f () -> f ()) -> f () -> f ()
forall a b. (a -> b) -> a -> b
$ do
          Int
n <- a -> f Int
forall (m :: * -> *) b i. BorderedM m b i => b -> m Int
getSizeOf a
x
          let ([(Int, b)]
as, [(Int, b)]
bs) = ((Int, b) -> Bool) -> [(Int, b)] -> ([(Int, b)], [(Int, b)])
forall l e. Linear l e => (e -> Bool) -> l -> (l, l)
partition (\ (Int
i, b
_) -> Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
o) [(Int, b)]
ie
          a -> [(Int, b)] -> f a
forall (m :: * -> *) map key e.
MapM m map key e =>
map -> [(key, e)] -> m map
overwrite a
x [(Int, b)]
as f a -> f () -> f ()
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Int -> [a] -> [(Int, b)] -> f ()
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
o) [a]
xs [(Int, b)]
bs
        go Int
_ [a]
_ [(Int, b)]
_ = () -> f ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
    
    kfoldrM :: (Int -> e -> acc -> m acc) -> acc -> AnyChunks rep e -> m acc
kfoldrM = (Int -> e -> acc -> m acc) -> acc -> AnyChunks rep e -> m acc
forall (m :: * -> *) l e r.
LinearM m l e =>
(Int -> e -> r -> m r) -> r -> l -> m r
ofoldrM
    kfoldlM :: (Int -> acc -> e -> m acc) -> acc -> AnyChunks rep e -> m acc
kfoldlM = (Int -> acc -> e -> m acc) -> acc -> AnyChunks rep e -> m acc
forall (m :: * -> *) l e r.
LinearM m l e =>
(Int -> r -> e -> m r) -> r -> l -> m r
ofoldlM

instance (SplitM1 m rep e, IndexedM1 m rep Int e) => IndexedM m (AnyChunks rep e) Int e
  where
    fromAssocs :: (Int, Int) -> [(Int, e)] -> m (AnyChunks rep e)
fromAssocs (Int, Int)
bnds [(Int, e)]
ascs = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e) -> m [rep e] -> m (AnyChunks rep e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [m (rep e)] -> m [rep e]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence ((Int, Int) -> [(Int, e)] -> [m (rep e)]
forall (m :: * -> *) v b.
IndexedM m v Int b =>
(Int, Int) -> [(Int, b)] -> [m v]
go (Int, Int)
bnds [(Int, e)]
ascs)
      where
        go :: (Int, Int) -> [(Int, b)] -> [m v]
go (Int
l, Int
u) [(Int, b)]
ies = (Int, Int) -> Bool
forall i. Index i => (i, i) -> Bool
isEmpty (Int
l, Int
u) Bool -> [m v] -> [m v] -> [m v]
forall a. Bool -> a -> a -> a
? [] ([m v] -> [m v]) -> [m v] -> [m v]
forall a b. (a -> b) -> a -> b
$ (Int, Int) -> [(Int, b)] -> m v
forall (m :: * -> *) v i e.
IndexedM m v i e =>
(i, i) -> [(i, e)] -> m v
fromAssocs (Int
l, Int
n) [(Int, b)]
as m v -> [m v] -> [m v]
forall a. a -> [a] -> [a]
: (Int, Int) -> [(Int, b)] -> [m v]
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, Int
u) [(Int, b)]
bs
          where
            ([(Int, b)]
as, [(Int, b)]
bs) = ((Int, b) -> Bool) -> [(Int, b)] -> ([(Int, b)], [(Int, b)])
forall l e. Linear l e => (e -> Bool) -> l -> (l, l)
partition ((Int, Int) -> Int -> Bool
forall i. Index i => (i, i) -> i -> Bool
inRange (Int
l, Int
n) (Int -> Bool) -> ((Int, b) -> Int) -> (Int, b) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, b) -> Int
forall a b. (a, b) -> a
fst) [(Int, b)]
ies
            n :: Int
n = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
u (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lim)
    
    fromAssocs' :: (Int, Int) -> e -> [(Int, e)] -> m (AnyChunks rep e)
fromAssocs' (Int, Int)
bnds e
defvalue [(Int, e)]
ascs = [rep e] -> AnyChunks rep e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([rep e] -> AnyChunks rep e) -> m [rep e] -> m (AnyChunks rep e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [m (rep e)] -> m [rep e]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence ((Int, Int) -> [(Int, e)] -> [m (rep e)]
go (Int, Int)
bnds [(Int, e)]
ascs)
      where
        go :: (Int, Int) -> [(Int, e)] -> [m (rep e)]
go (Int
l, Int
u) [(Int, e)]
ies = (Int, Int) -> e -> [(Int, e)] -> m (rep e)
forall (m :: * -> *) v i e.
IndexedM m v i e =>
(i, i) -> e -> [(i, e)] -> m v
fromAssocs' (Int
l, Int
n) e
defvalue [(Int, e)]
as m (rep e) -> [m (rep e)] -> [m (rep e)]
forall a. a -> [a] -> [a]
: (Int, Int) -> [(Int, e)] -> [m (rep e)]
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, Int
u) [(Int, e)]
bs
          where
            ([(Int, e)]
as, [(Int, e)]
bs) = ((Int, e) -> Bool) -> [(Int, e)] -> ([(Int, e)], [(Int, e)])
forall l e. Linear l e => (e -> Bool) -> l -> (l, l)
partition ((Int, Int) -> Int -> Bool
forall i. Index i => (i, i) -> i -> Bool
inRange (Int
l, Int
n) (Int -> Bool) -> ((Int, e) -> Int) -> (Int, e) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, e) -> Int
forall a b. (a, b) -> a
fst) [(Int, e)]
ies
            n :: Int
n = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
u (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lim)
    
    {-# INLINE writeM' #-}
    writeM' :: AnyChunks rep e -> Int -> e -> m ()
writeM' AnyChunks rep e
es Int
i e
e = (Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0) Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
`unless` AnyChunks rep e -> Int -> e -> m ()
forall (m :: * -> *) l e. LinearM m l e => l -> Int -> e -> m ()
writeM AnyChunks rep e
es Int
i e
e
    
    fromIndexed' :: v' -> m (AnyChunks rep e)
fromIndexed' = [e] -> m (AnyChunks rep e)
forall (m :: * -> *) l e. LinearM m l e => [e] -> m l
newLinear  ([e] -> m (AnyChunks rep e))
-> (v' -> [e]) -> v' -> m (AnyChunks rep e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.  v' -> [e]
forall l e. Linear l e => l -> [e]
listL
    fromIndexedM :: v' -> m (AnyChunks rep e)
fromIndexedM = [e] -> m (AnyChunks rep e)
forall (m :: * -> *) l e. LinearM m l e => [e] -> m l
newLinear ([e] -> m (AnyChunks rep e))
-> (v' -> m [e]) -> v' -> m (AnyChunks rep e)
forall (m :: * -> *) b c a.
Monad m =>
(b -> m c) -> (a -> m b) -> a -> m c
<=< v' -> m [e]
forall (m :: * -> *) l e. LinearM m l e => l -> m [e]
getLeft

instance (BorderedM1 m rep Int e, SortM1 m rep e, SplitM1 m rep e, LinearM1 m rep e) => SortM m (AnyChunks rep e) e
  where
    sortMBy :: Compare e -> AnyChunks rep e -> m ()
sortMBy = Compare e -> AnyChunks rep e -> m ()
forall (m :: * -> *) v e i.
(LinearM m v e, BorderedM m v i) =>
Compare e -> v -> m ()
timSortBy
    
    sortedMBy :: (e -> e -> Bool) -> AnyChunks rep e -> m Bool
sortedMBy e -> e -> Bool
f = [rep e] -> m Bool
go ([rep e] -> m Bool)
-> (AnyChunks rep e -> [rep e]) -> AnyChunks rep e -> m Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks rep e -> [rep e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        go :: [rep e] -> m Bool
go (rep e
x1 : rep e
x2 : [rep e]
xs) =
          let restM :: m Bool
restM = (e -> e -> Bool) -> m e -> m e -> m Bool
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 e -> e -> Bool
f (rep e -> m e
forall (m :: * -> *) l e. LinearM m l e => l -> m e
getLast rep e
x1) (rep e -> m e
forall (m :: * -> *) l e. LinearM m l e => l -> m e
getHead rep e
x2) m Bool -> m Bool -> m Bool -> m Bool
forall (m :: * -> *) a. Monad m => m Bool -> m a -> m a -> m a
?^ [rep e] -> m Bool
go (rep e
x2 rep e -> [rep e] -> [rep e]
forall a. a -> [a] -> [a]
: [rep e]
xs) (m Bool -> m Bool) -> m Bool -> m Bool
forall a b. (a -> b) -> a -> b
$ Bool -> m Bool
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
          in  (e -> e -> Bool) -> rep e -> m Bool
forall (m :: * -> *) s e.
SortM m s e =>
(e -> e -> Bool) -> s -> m Bool
sortedMBy e -> e -> Bool
f rep e
x1 m Bool -> m Bool -> m Bool -> m Bool
forall (m :: * -> *) a. Monad m => m Bool -> m a -> m a -> m a
?^ m Bool
restM (m Bool -> m Bool) -> m Bool -> m Bool
forall a b. (a -> b) -> a -> b
$ Bool -> m Bool
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
        go      [rep e
x1]      = (e -> e -> Bool) -> rep e -> m Bool
forall (m :: * -> *) s e.
SortM m s e =>
(e -> e -> Bool) -> s -> m Bool
sortedMBy e -> e -> Bool
f rep e
x1
        go       []       = Bool -> m Bool
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True

--------------------------------------------------------------------------------

-- | Creates new local immutable structure and thaw it as fast, as possible.
instance {-# OVERLAPPABLE #-} (Linear1 imm e, Thaw1 m imm mut e) => Thaw m (AnyChunks imm e) (mut e)
  where
    -- @concat [e]@ may return e
    thaw :: AnyChunks imm e -> m (mut e)
thaw (AnyChunks [imm e
e]) = imm e -> m (mut e)
forall (m :: * -> *) v v'. Thaw m v v' => v -> m v'
thaw imm e
e
    -- any correct concat will create an intermediate structure in this case
    thaw (AnyChunks [imm e]
ess) = imm e -> m (mut e)
forall (m :: * -> *) v v'. Thaw m v v' => v -> m v'
unsafeThaw ([imm e] -> imm e
forall l e (f :: * -> *). (Linear l e, Foldable f) => f l -> l
concat [imm e]
ess)
    
    unsafeThaw :: AnyChunks imm e -> m (mut e)
unsafeThaw = imm e -> m (mut e)
forall (m :: * -> *) v v'. Thaw m v v' => v -> m v'
unsafeThaw (imm e -> m (mut e))
-> (AnyChunks imm e -> imm e) -> AnyChunks imm e -> m (mut e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [imm e] -> imm e
forall l e (f :: * -> *). (Linear l e, Foldable f) => f l -> l
concat ([imm e] -> imm e)
-> (AnyChunks imm e -> [imm e]) -> AnyChunks imm e -> imm e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AnyChunks imm e -> [imm e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks

-- | Creates one-chunk mutable stream, may be memory inefficient.
instance {-# OVERLAPPABLE #-} (Thaw1 m imm mut e) => Thaw m (imm e) (AnyChunks mut e)
  where
    unsafeThaw :: imm e -> m (AnyChunks mut e)
unsafeThaw = (mut e -> AnyChunks mut e) -> m (mut e) -> m (AnyChunks mut e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([mut e] -> AnyChunks mut e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([mut e] -> AnyChunks mut e)
-> (mut e -> [mut e]) -> mut e -> AnyChunks mut e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. mut e -> [mut e]
forall l e. Linear l e => e -> l
single) (m (mut e) -> m (AnyChunks mut e))
-> (imm e -> m (mut e)) -> imm e -> m (AnyChunks mut e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. imm e -> m (mut e)
forall (m :: * -> *) v v'. Thaw m v v' => v -> m v'
unsafeThaw
    thaw :: imm e -> m (AnyChunks mut e)
thaw       = (mut e -> AnyChunks mut e) -> m (mut e) -> m (AnyChunks mut e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([mut e] -> AnyChunks mut e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([mut e] -> AnyChunks mut e)
-> (mut e -> [mut e]) -> mut e -> AnyChunks mut e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. mut e -> [mut e]
forall l e. Linear l e => e -> l
single) (m (mut e) -> m (AnyChunks mut e))
-> (imm e -> m (mut e)) -> imm e -> m (AnyChunks mut e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. imm e -> m (mut e)
forall (m :: * -> *) v v'. Thaw m v v' => v -> m v'
thaw

instance {-# OVERLAPS #-} (Thaw1 m imm mut e) => Thaw m (AnyChunks imm e) (AnyChunks mut e)
  where
    unsafeThaw :: AnyChunks imm e -> m (AnyChunks mut e)
unsafeThaw (AnyChunks [imm e]
imm) = [mut e] -> AnyChunks mut e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([mut e] -> AnyChunks mut e) -> m [mut e] -> m (AnyChunks mut e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (imm e -> m (mut e)) -> [imm e] -> m [mut e]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM imm e -> m (mut e)
forall (m :: * -> *) v v'. Thaw m v v' => v -> m v'
unsafeThaw [imm e]
imm
    thaw :: AnyChunks imm e -> m (AnyChunks mut e)
thaw       (AnyChunks [imm e]
imm) = [mut e] -> AnyChunks mut e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([mut e] -> AnyChunks mut e) -> m [mut e] -> m (AnyChunks mut e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (imm e -> m (mut e)) -> [imm e] -> m [mut e]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM imm e -> m (mut e)
forall (m :: * -> *) v v'. Thaw m v v' => v -> m v'
thaw [imm e]
imm

-- | Creates one-chunk immutable stream, may be memory inefficient.
instance {-# OVERLAPPABLE #-} (Freeze1 m mut imm e) => Freeze m (mut e) (AnyChunks imm e)
  where
    unsafeFreeze :: mut e -> m (AnyChunks imm e)
unsafeFreeze = (imm e -> AnyChunks imm e) -> m (imm e) -> m (AnyChunks imm e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([imm e] -> AnyChunks imm e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([imm e] -> AnyChunks imm e)
-> (imm e -> [imm e]) -> imm e -> AnyChunks imm e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. imm e -> [imm e]
forall l e. Linear l e => e -> l
single) (m (imm e) -> m (AnyChunks imm e))
-> (mut e -> m (imm e)) -> mut e -> m (AnyChunks imm e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. mut e -> m (imm e)
forall (m :: * -> *) v' v. Freeze m v' v => v' -> m v
unsafeFreeze
    freeze :: mut e -> m (AnyChunks imm e)
freeze       = (imm e -> AnyChunks imm e) -> m (imm e) -> m (AnyChunks imm e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([imm e] -> AnyChunks imm e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([imm e] -> AnyChunks imm e)
-> (imm e -> [imm e]) -> imm e -> AnyChunks imm e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. imm e -> [imm e]
forall l e. Linear l e => e -> l
single) (m (imm e) -> m (AnyChunks imm e))
-> (mut e -> m (imm e)) -> mut e -> m (AnyChunks imm e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. mut e -> m (imm e)
forall (m :: * -> *) v' v. Freeze m v' v => v' -> m v
freeze

-- | Creates new immutable structure using 'merged'.
instance {-# OVERLAPPABLE #-} (LinearM1 m mut e, Freeze1 m mut imm e) => Freeze m (AnyChunks mut e) (imm e)
  where
    unsafeFreeze :: AnyChunks mut e -> m (imm e)
unsafeFreeze (AnyChunks [mut e]
es) = mut e -> m (imm e)
forall (m :: * -> *) v' v. Freeze m v' v => v' -> m v
unsafeFreeze (mut e -> m (imm e)) -> m (mut e) -> m (imm e)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< [mut e] -> m (mut e)
forall (m :: * -> *) l e (f :: * -> *).
(LinearM m l e, Foldable f) =>
f l -> m l
merged [mut e]
es
    freeze :: AnyChunks mut e -> m (imm e)
freeze       (AnyChunks [mut e]
es) = mut e -> m (imm e)
forall (m :: * -> *) v' v. Freeze m v' v => v' -> m v
freeze       (mut e -> m (imm e)) -> m (mut e) -> m (imm e)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< [mut e] -> m (mut e)
forall (m :: * -> *) l e (f :: * -> *).
(LinearM m l e, Foldable f) =>
f l -> m l
merged [mut e]
es

instance {-# OVERLAPS #-} (Freeze1 m mut imm e) => Freeze m (AnyChunks mut e) (AnyChunks imm e)
  where
    unsafeFreeze :: AnyChunks mut e -> m (AnyChunks imm e)
unsafeFreeze (AnyChunks [mut e]
mut) = [imm e] -> AnyChunks imm e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([imm e] -> AnyChunks imm e) -> m [imm e] -> m (AnyChunks imm e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (mut e -> m (imm e)) -> [mut e] -> m [imm e]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM mut e -> m (imm e)
forall (m :: * -> *) v' v. Freeze m v' v => v' -> m v
unsafeFreeze [mut e]
mut
    freeze :: AnyChunks mut e -> m (AnyChunks imm e)
freeze       (AnyChunks [mut e]
mut) = [imm e] -> AnyChunks imm e
forall (rep :: * -> *) e. [rep e] -> AnyChunks rep e
AnyChunks ([imm e] -> AnyChunks imm e) -> m [imm e] -> m (AnyChunks imm e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (mut e -> m (imm e)) -> [mut e] -> m [imm e]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM mut e -> m (imm e)
forall (m :: * -> *) v' v. Freeze m v' v => v' -> m v
freeze [mut e]
mut

--------------------------------------------------------------------------------

ascsBounds :: (Ord a) => [(a, b)] -> (a, a)
ascsBounds :: [(a, b)] -> (a, a)
ascsBounds =  \ ((a
x, b
_) : [(a, b)]
xs) -> ((a, b) -> (a, a) -> (a, a)) -> (a, a) -> [(a, b)] -> (a, a)
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\ (a
e, b
_) (a
mn, a
mx) -> (a -> a -> a
forall a. Ord a => a -> a -> a
min a
mn a
e, a -> a -> a
forall a. Ord a => a -> a -> a
max a
mx a
e)) (a
x, a
x) [(a, b)]
xs

overEx :: String -> a
overEx :: String -> a
overEx =  IndexException -> a
forall a e. Exception e => e -> a
throw (IndexException -> a) -> (String -> IndexException) -> String -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> IndexException
IndexOverflow (String -> IndexException) -> ShowS -> String -> IndexException
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
"in SDP.Templates.AnyChunks."

underEx :: String -> a
underEx :: String -> a
underEx =  IndexException -> a
forall a e. Exception e => e -> a
throw (IndexException -> a) -> (String -> IndexException) -> String -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> IndexException
IndexUnderflow (String -> IndexException) -> ShowS -> String -> IndexException
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
"in SDP.Templates.AnyChunks."

pfailEx :: String -> a
pfailEx :: String -> a
pfailEx =  PatternMatchFail -> a
forall a e. Exception e => e -> a
throw (PatternMatchFail -> a)
-> (String -> PatternMatchFail) -> String -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> PatternMatchFail
PatternMatchFail (String -> PatternMatchFail) -> ShowS -> String -> PatternMatchFail
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
"in SDP.Templates.AnyChunks."

lim :: Int
lim :: Int
lim =  Int
1024