{-# LANGUAGE PatternGuards, BangPatterns, TypeFamilies #-}
{-# LANGUAGE CPP #-}
#if __GLASGOW_HASKELL__ >= 702
{-# LANGUAGE Trustworthy #-}
#endif

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

-- |

-- Module      :  Data.Stream.Future.Skew

-- Copyright   :  (C) 2008-2015 Edward Kmett,

--                (C) 2004 Dave Menendez

-- License     :  BSD-style (see the file LICENSE)

--

-- Maintainer  :  Edward Kmett <ekmett@gmail.com>

-- Stability   :  provisional

-- Portability :  portable

--

-- Anticausal streams implemented as non-empty skew binary random access lists

--

-- The Applicative zips streams, but since these are potentially infinite

-- this is stricter than would be desired. You almost always want

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



module Data.Stream.Future.Skew
    ( Future(..)
    , (<|)      -- O(1)

    , length    -- O(log n)

    , tail      -- O(1)

    , last      -- O(log n)

    , uncons    -- O(1)

    , index     -- O(log n)

    , drop      -- O(log n)

    , dropWhile -- O(n)

    , indexed
    , from
    , break
    , span
    , split     -- O(log n)

    , splitW    -- O(log n)

    , replicate -- O(log n)

    , insert    -- O(n)

    , insertBy
    , update
    , adjust    -- O(log n)

    , toFuture
    , singleton
    ) where

import Control.Applicative hiding (empty)
import Control.Comonad
import Data.Functor.Alt
import Data.Functor.Extend
#if MIN_VERSION_base(4,8,0)
import Prelude hiding (tail, drop, dropWhile, last, span, repeat, replicate, break)
import Data.Foldable (toList)
#else
import Data.Foldable
import Data.Traversable (Traversable, traverse)
import Prelude hiding (null, tail, drop, dropWhile, length, foldr, last, span, repeat, replicate, break)
#endif
#if !(MIN_VERSION_base(4,11,0))
import Data.Semigroup hiding (Last)
#endif
import Data.Semigroup.Foldable
import Data.Semigroup.Traversable
#if MIN_VERSION_base(4,7,0)
import qualified GHC.Exts as Exts
#endif

infixr 5 :<, <|

data Complete a
    = Tip a
    | Bin {-# UNPACK #-} !Int a !(Complete a) !(Complete a)
    deriving Int -> Complete a -> ShowS
forall a. Show a => Int -> Complete a -> ShowS
forall a. Show a => [Complete a] -> ShowS
forall a. Show a => Complete a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Complete a] -> ShowS
$cshowList :: forall a. Show a => [Complete a] -> ShowS
show :: Complete a -> String
$cshow :: forall a. Show a => Complete a -> String
showsPrec :: Int -> Complete a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Complete a -> ShowS
Show

instance Functor Complete where
  fmap :: forall a b. (a -> b) -> Complete a -> Complete b
fmap a -> b
f (Tip a
a) = forall a. a -> Complete a
Tip (a -> b
f a
a)
  fmap a -> b
f (Bin Int
w a
a Complete a
l Complete a
r) = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
w (a -> b
f a
a) (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Complete a
l) (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Complete a
r)

instance Extend Complete where
  extended :: forall a b. (Complete a -> b) -> Complete a -> Complete b
extended = forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend

instance Comonad Complete where
  extend :: forall a b. (Complete a -> b) -> Complete a -> Complete b
extend Complete a -> b
f w :: Complete a
w@Tip {} = forall a. a -> Complete a
Tip (Complete a -> b
f Complete a
w)
  extend Complete a -> b
f w :: Complete a
w@(Bin Int
n a
_ Complete a
l Complete a
r) = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n (Complete a -> b
f Complete a
w) (forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend Complete a -> b
f Complete a
l) (forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend Complete a -> b
f Complete a
r)
  extract :: forall a. Complete a -> a
extract (Tip a
a) = a
a
  extract (Bin Int
_ a
a Complete a
_ Complete a
_) = a
a

instance Foldable Complete where
  foldMap :: forall m a. Monoid m => (a -> m) -> Complete a -> m
foldMap a -> m
f (Tip a
a) = a -> m
f a
a
  foldMap a -> m
f (Bin Int
_ a
a Complete a
l Complete a
r) = a -> m
f a
a forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Complete a
l forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Complete a
r
  foldr :: forall a b. (a -> b -> b) -> b -> Complete a -> b
foldr a -> b -> b
f b
z (Tip a
a) = a -> b -> b
f a
a b
z
  foldr a -> b -> b
f b
z (Bin Int
_ a
a Complete a
l Complete a
r) = a -> b -> b
f a
a (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
z Complete a
r) Complete a
l)
#if MIN_VERSION_base(4,8,0)
  length :: forall a. Complete a -> Int
length Tip{} = Int
1
  length (Bin Int
n a
_ Complete a
_ Complete a
_) = Int
n
  null :: forall a. Complete a -> Bool
null Complete a
_ = Bool
False
#endif

instance Foldable1 Complete where
  foldMap1 :: forall m a. Semigroup m => (a -> m) -> Complete a -> m
foldMap1 a -> m
f (Tip a
a) = a -> m
f a
a
  foldMap1 a -> m
f (Bin Int
_ a
a Complete a
l Complete a
r) = a -> m
f a
a forall a. Semigroup a => a -> a -> a
<> forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Complete a
l forall a. Semigroup a => a -> a -> a
<> forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Complete a
r

instance Traversable Complete where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Complete a -> f (Complete b)
traverse a -> f b
f (Tip a
a) = forall a. a -> Complete a
Tip forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a
  traverse a -> f b
f (Bin Int
n a
a Complete a
l Complete a
r) = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Complete a
l forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Complete a
r

instance Traversable1 Complete where
  traverse1 :: forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> Complete a -> f (Complete b)
traverse1 a -> f b
f (Tip a
a) = forall a. a -> Complete a
Tip forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a
  traverse1 a -> f b
f (Bin Int
n a
a Complete a
l Complete a
r) = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
f Complete a
l forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
f Complete a
r

bin :: a -> Complete a -> Complete a -> Complete a
bin :: forall a. a -> Complete a -> Complete a -> Complete a
bin a
a Complete a
l Complete a
r = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin (Int
1 forall a. Num a => a -> a -> a
+ forall a. Complete a -> Int
weight Complete a
l forall a. Num a => a -> a -> a
+ forall a. Complete a -> Int
weight Complete a
r) a
a Complete a
l Complete a
r
{-# INLINE bin #-}

weight :: Complete a -> Int
weight :: forall a. Complete a -> Int
weight Tip{} = Int
1
weight (Bin Int
w a
_ Complete a
_ Complete a
_) = Int
w
{-# INLINE weight #-}

-- A future is a non-empty skew binary random access list of nodes.

-- The last node, however, is allowed to contain fewer values.

data Future a
  = Last !(Complete a)
  | !(Complete a) :< Future a
--  deriving Show



instance Show a => Show (Future a) where
  showsPrec :: Int -> Future a -> ShowS
showsPrec Int
d Future a
as = Bool -> ShowS -> ShowS
showParen (Int
d forall a. Ord a => a -> a -> Bool
>= Int
10) forall a b. (a -> b) -> a -> b
$
    String -> ShowS
showString String
"fromList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (forall (t :: * -> *) a. Foldable t => t a -> [a]
toList Future a
as)

instance Functor Future where
  fmap :: forall a b. (a -> b) -> Future a -> Future b
fmap a -> b
f (Complete a
t :< Future a
ts) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Complete a
t forall a. Complete a -> Future a -> Future a
:< forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Future a
ts
  fmap a -> b
f (Last Complete a
t) = forall a. Complete a -> Future a
Last (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Complete a
t)

instance Extend Future where
  extended :: forall a b. (Future a -> b) -> Future a -> Future b
extended = forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend

instance Comonad Future where
  extend :: forall a b. (Future a -> b) -> Future a -> Future b
extend Future a -> b
g (Last Complete a
t)  = forall a. Complete a -> Future a
Last (forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g Complete a
t forall a. Complete a -> Future a
Last)
  extend Future a -> b
g (Complete a
t :< Future a
ts) = forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g Complete a
t (forall a. Complete a -> Future a -> Future a
:< Future a
ts) forall a. Complete a -> Future a -> Future a
:< forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend Future a -> b
g Future a
ts
  extract :: forall a. Future a -> a
extract (Complete a
a :< Future a
_) = forall (w :: * -> *) a. Comonad w => w a -> a
extract Complete a
a
  extract (Last Complete a
a) = forall (w :: * -> *) a. Comonad w => w a -> a
extract Complete a
a

extendTree :: (Future a -> b) -> Complete a -> (Complete a -> Future a) -> Complete b
extendTree :: forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g w :: Complete a
w@Tip{}         Complete a -> Future a
f = forall a. a -> Complete a
Tip (Future a -> b
g (Complete a -> Future a
f Complete a
w))
extendTree Future a -> b
g w :: Complete a
w@(Bin Int
n a
_ Complete a
l Complete a
r) Complete a -> Future a
f = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n (Future a -> b
g (Complete a -> Future a
f Complete a
w)) (forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g Complete a
l (forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
f Complete a
r))  (forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g Complete a
r Complete a -> Future a
f)

instance Apply Future where
  Last (Tip a -> b
f)         <.> :: forall a b. Future (a -> b) -> Future a -> Future b
<.> Future a
as                   = forall a. a -> Future a
singleton (a -> b
f (forall (w :: * -> *) a. Comonad w => w a -> a
extract Future a
as))
  Future (a -> b)
fs                   <.> Last (Tip a
a)         = forall a. a -> Future a
singleton (forall (w :: * -> *) a. Comonad w => w a -> a
extract Future (a -> b)
fs a
a)
  Last (Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf) <.> Last (Bin Int
_ a
a Complete a
la Complete a
ra) = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete (a -> b)
rf  forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete a
ra )
  Last (Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf) <.> Bin Int
_ a
a Complete a
la Complete a
ra :< Future a
as  = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete (a -> b)
rf  forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< Complete a
ra forall a. Complete a -> Future a -> Future a
:< Future a
as)
  Last (Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf) <.> Tip a
a :< Future a
as          = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete (a -> b)
rf  forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Future a
as            )
  Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf :< Future (a -> b)
fs  <.> Last (Bin Int
_ a
a Complete a
la Complete a
ra) = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< Complete (a -> b)
rf forall a. Complete a -> Future a -> Future a
:< Future (a -> b)
fs forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete a
ra )
  Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf :< Future (a -> b)
fs  <.> Tip a
a :< Future a
as          = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< Complete (a -> b)
rf forall a. Complete a -> Future a -> Future a
:< Future (a -> b)
fs forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Future a
as            )
  Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf :< Future (a -> b)
fs  <.> Bin Int
_ a
a Complete a
la Complete a
ra :< Future a
as  = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< Complete (a -> b)
rf forall a. Complete a -> Future a -> Future a
:< Future (a -> b)
fs forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< Complete a
ra forall a. Complete a -> Future a -> Future a
:< Future a
as)
  Tip a -> b
f :< Future (a -> b)
fs          <.> Tip a
a :< Future a
as          = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Future (a -> b)
fs             forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Future a
as            )
  Tip a -> b
f :< Future (a -> b)
fs          <.> Bin Int
_ a
a Complete a
la Complete a
ra :< Future a
as  = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Future (a -> b)
fs             forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< Complete a
ra forall a. Complete a -> Future a -> Future a
:< Future a
as)
  Tip a -> b
f :< Future (a -> b)
fs          <.> Last (Bin Int
_ a
a Complete a
la Complete a
ra) = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Future (a -> b)
fs             forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete a
ra )

instance ComonadApply Future where
  <@> :: forall a b. Future (a -> b) -> Future a -> Future b
(<@>) = forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
(<.>)

instance Applicative Future where
  pure :: forall a. a -> Future a
pure a
a0 = forall a. a -> Complete a -> Future a
go a
a0 (forall a. a -> Complete a
Tip a
a0) where
    go :: a -> Complete a -> Future a
    go :: forall a. a -> Complete a -> Future a
go a
a Complete a
as | Complete a
ass <- forall a. a -> Complete a -> Complete a -> Complete a
bin a
a Complete a
as Complete a
as = Complete a
as forall a. Complete a -> Future a -> Future a
:< forall a. a -> Complete a -> Future a
go a
a Complete a
ass
  <*> :: forall a b. Future (a -> b) -> Future a -> Future b
(<*>) = forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
(<.>)

instance Alt Future where
  Future a
as <!> :: forall a. Future a -> Future a -> Future a
<!> Future a
bs = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Future a -> Future a
(<|) Future a
bs Future a
as

instance Foldable Future where
  foldMap :: forall m a. Monoid m => (a -> m) -> Future a -> m
foldMap a -> m
f (Complete a
t :< Future a
ts) = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Complete a
t forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Future a
ts
  foldMap a -> m
f (Last Complete a
t) = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Complete a
t
  foldr :: forall a b. (a -> b -> b) -> b -> Future a -> b
foldr a -> b -> b
f b
z (Complete a
t :< Future a
ts) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
z Future a
ts) Complete a
t
  foldr a -> b -> b
f b
z (Last Complete a
t) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
z Complete a
t
#if MIN_VERSION_base(4,8,0)
  length :: forall a. Future a -> Int
length (Last Complete a
t) = forall a. Complete a -> Int
weight Complete a
t
  length (Complete a
t :< Future a
ts) = forall a. Complete a -> Int
weight Complete a
t forall a. Num a => a -> a -> a
+ forall (t :: * -> *) a. Foldable t => t a -> Int
length Future a
ts
  null :: forall a. Future a -> Bool
null Future a
_ = Bool
False
#endif

instance Foldable1 Future where
  foldMap1 :: forall m a. Semigroup m => (a -> m) -> Future a -> m
foldMap1 a -> m
f (Complete a
t :< Future a
ts) = forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Complete a
t forall a. Semigroup a => a -> a -> a
<> forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Future a
ts
  foldMap1 a -> m
f (Last Complete a
t) = forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Complete a
t

instance Traversable Future where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Future a -> f (Future b)
traverse a -> f b
f (Complete a
t :< Future a
ts) = forall a. Complete a -> Future a -> Future a
(:<) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Complete a
t forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Future a
ts
  traverse a -> f b
f (Last Complete a
t) = forall a. Complete a -> Future a
Last forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Complete a
t

instance Traversable1 Future where
  traverse1 :: forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> Future a -> f (Future b)
traverse1 a -> f b
f (Complete a
t :< Future a
ts) = forall a. Complete a -> Future a -> Future a
(:<) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
f Complete a
t forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
f Future a
ts
  traverse1 a -> f b
f (Last Complete a
t) = forall a. Complete a -> Future a
Last forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
f Complete a
t

-- | /O(log n)/

replicate :: Int -> a -> Future a
replicate :: forall a. Int -> a -> Future a
replicate Int
n a
a
  | Int
n forall a. Ord a => a -> a -> Bool
<= Int
0    = forall a. HasCallStack => String -> a
error String
"replicate: non-positive argument"
  | Bool
otherwise = forall b r.
Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r
go Int
1 Int
n a
a (forall a. a -> Complete a
Tip a
a) (\ Int
_ Future a
r -> Future a
r)
  where
  -- invariants:

  -- tb is a complete tree of i nodes all equal to b

  -- 1 <= i = 2^m-1 <= j

  -- k accepts r such that 0 <= r < i

  go :: Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r
  go :: forall b r.
Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r
go !Int
i !Int
j b
b Complete b
tb Int -> Future b -> r
k
    | Int
j forall a. Ord a => a -> a -> Bool
>= Int
i2p1 = forall b r.
Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r
go Int
i2p1 Int
j b
b (forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
i2p1 b
b Complete b
tb Complete b
tb) Int -> Future b -> r
k'
    | Int
j forall a. Ord a => a -> a -> Bool
>= Int
i2   = Int -> Future b -> r
k (Int
j forall a. Num a => a -> a -> a
- Int
i2) (Complete b
tb forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete b
tb)
    | Bool
otherwise = Int -> Future b -> r
k (Int
j forall a. Num a => a -> a -> a
- Int
i) (forall a. Complete a -> Future a
Last Complete b
tb)
    where
      i2 :: Int
i2 = Int
i forall a. Num a => a -> a -> a
* Int
2
      i2p1 :: Int
i2p1 = Int
i2 forall a. Num a => a -> a -> a
+ Int
1
      k' :: Int -> Future b -> r
k' Int
r Future b
xs
        | Int
r forall a. Ord a => a -> a -> Bool
>= Int
i2   = Int -> Future b -> r
k (Int
r forall a. Num a => a -> a -> a
- Int
i2) (Complete b
tb forall a. Complete a -> Future a -> Future a
:< Complete b
tb forall a. Complete a -> Future a -> Future a
:< Future b
xs)
        | Int
r forall a. Ord a => a -> a -> Bool
>= Int
i    = Int -> Future b -> r
k (Int
r forall a. Num a => a -> a -> a
- Int
i) (Complete b
tb forall a. Complete a -> Future a -> Future a
:< Future b
xs)
        | Bool
otherwise = Int -> Future b -> r
k Int
r Future b
xs
{-# INLINE replicate #-}

mapWithIndex :: (Int -> a -> b) -> Future a -> Future b
mapWithIndex :: forall a b. (Int -> a -> b) -> Future a -> Future b
mapWithIndex Int -> a -> b
f0 Future a
as0 = forall {a} {a}. (Int -> a -> a) -> Int -> Future a -> Future a
spine Int -> a -> b
f0 Int
0 Future a
as0
  where
    spine :: (Int -> a -> a) -> Int -> Future a -> Future a
spine Int -> a -> a
f Int
m (Last Complete a
as) = forall a. Complete a -> Future a
Last (forall {a} {a}. (Int -> a -> a) -> Int -> Complete a -> Complete a
tree Int -> a -> a
f Int
m Complete a
as)
    spine Int -> a -> a
f Int
m (Complete a
a :< Future a
as) = forall {a} {a}. (Int -> a -> a) -> Int -> Complete a -> Complete a
tree Int -> a -> a
f Int
m Complete a
a forall a. Complete a -> Future a -> Future a
:< (Int -> a -> a) -> Int -> Future a -> Future a
spine Int -> a -> a
f (Int
m forall a. Num a => a -> a -> a
+ forall a. Complete a -> Int
weight Complete a
a) Future a
as
    tree :: (Int -> a -> a) -> Int -> Complete a -> Complete a
tree Int -> a -> a
f Int
m (Tip a
a) = forall a. a -> Complete a
Tip (Int -> a -> a
f Int
m a
a)
    tree Int -> a -> a
f Int
m (Bin Int
n a
a Complete a
l Complete a
r) = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n (Int -> a -> a
f Int
m a
a) ((Int -> a -> a) -> Int -> Complete a -> Complete a
tree Int -> a -> a
f (Int
m forall a. Num a => a -> a -> a
+ Int
1) Complete a
l) ((Int -> a -> a) -> Int -> Complete a -> Complete a
tree Int -> a -> a
f (Int
m forall a. Num a => a -> a -> a
+ Int
1 forall a. Num a => a -> a -> a
+ forall a. Complete a -> Int
weight Complete a
l) Complete a
r)

indexed :: Future a -> Future (Int, a)
indexed :: forall a. Future a -> Future (Int, a)
indexed = forall a b. (Int -> a -> b) -> Future a -> Future b
mapWithIndex (,)
{-# INLINE indexed #-}

from :: Num a => a -> Future a
from :: forall a. Num a => a -> Future a
from a
a = forall a b. (Int -> a -> b) -> Future a -> Future b
mapWithIndex (forall a. Num a => a -> a -> a
(+) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral) (forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a)
{-# INLINE from #-}

-- | /O(1)/

singleton :: a -> Future a
singleton :: forall a. a -> Future a
singleton a
a = forall a. Complete a -> Future a
Last (forall a. a -> Complete a
Tip a
a)
{-# INLINE singleton #-}

#if !(MIN_VERSION_base(4,8,0))
-- | /O(log n)/.

length :: Future a -> Int
length (Last t) = weight t
length (t :< ts) = weight t + length ts
#endif

-- | /O(1)/ cons

(<|) :: a -> Future a -> Future a
a
a <| :: forall a. a -> Future a -> Future a
<| (Complete a
l :< Last Complete a
r)
  | forall a. Complete a -> Int
weight Complete a
l forall a. Eq a => a -> a -> Bool
== forall a. Complete a -> Int
weight Complete a
r = forall a. Complete a -> Future a
Last (forall a. a -> Complete a -> Complete a -> Complete a
bin a
a Complete a
l Complete a
r)
a
a <| (Complete a
l :< Complete a
r :< Future a
as)
  | forall a. Complete a -> Int
weight Complete a
l forall a. Eq a => a -> a -> Bool
== forall a. Complete a -> Int
weight Complete a
r = forall a. a -> Complete a -> Complete a -> Complete a
bin a
a Complete a
l Complete a
r forall a. Complete a -> Future a -> Future a
:< Future a
as
a
a <| Future a
as = forall a. a -> Complete a
Tip a
a forall a. Complete a -> Future a -> Future a
:< Future a
as
{-# INLINE (<|) #-}

-- | /O(1)/.

tail :: Future a -> Maybe (Future a)
tail :: forall a. Future a -> Maybe (Future a)
tail (Tip{} :< Future a
ts) = forall a. a -> Maybe a
Just Future a
ts
tail (Bin Int
_ a
_ Complete a
l Complete a
r :< Future a
ts) = forall a. a -> Maybe a
Just (Complete a
l forall a. Complete a -> Future a -> Future a
:< Complete a
r forall a. Complete a -> Future a -> Future a
:< Future a
ts)
tail (Last Tip{}) = forall a. Maybe a
Nothing
tail (Last (Bin Int
_ a
_ Complete a
l Complete a
r)) = forall a. a -> Maybe a
Just (Complete a
l forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete a
r)
{-# INLINE tail #-}

-- | /O(log n)/.

last :: Future a -> a
last :: forall a. Future a -> a
last (Complete a
_ :< Future a
as) = forall a. Future a -> a
last Future a
as
last (Last Complete a
as) = forall a. Complete a -> a
go Complete a
as
  where go :: Complete a -> a
go (Tip a
a) = a
a
        go (Bin Int
_ a
_ Complete a
_ Complete a
r) = Complete a -> a
go Complete a
r

-- | /O(1)/.

uncons :: Future a -> (a, Maybe (Future a))
uncons :: forall a. Future a -> (a, Maybe (Future a))
uncons (Last (Tip a
a))       = (a
a, forall a. Maybe a
Nothing)
uncons (Last (Bin Int
_ a
a Complete a
l Complete a
r)) = (a
a, forall a. a -> Maybe a
Just (Complete a
l forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete a
r))
uncons (Tip a
a       :< Future a
as)  = (a
a, forall a. a -> Maybe a
Just Future a
as)
uncons (Bin Int
_ a
a Complete a
l Complete a
r :< Future a
as)  = (a
a, forall a. a -> Maybe a
Just (Complete a
l forall a. Complete a -> Future a -> Future a
:< Complete a
r forall a. Complete a -> Future a -> Future a
:< Future a
as))
{-# INLINE uncons #-}

-- | /O(log n)/.

index :: Int -> Future a -> a
index :: forall a. Int -> Future a -> a
index Int
i (Last Complete a
t)
  | Int
i forall a. Ord a => a -> a -> Bool
< forall a. Complete a -> Int
weight Complete a
t = forall a. Int -> Complete a -> a
indexComplete Int
i Complete a
t
  | Bool
otherwise    = forall a. HasCallStack => String -> a
error String
"index: out of range"
index Int
i (Complete a
t :< Future a
ts)
  | Int
i forall a. Ord a => a -> a -> Bool
< Int
w     = forall a. Int -> Complete a -> a
indexComplete Int
i Complete a
t
  | Bool
otherwise = forall a. Int -> Future a -> a
index (Int
i forall a. Num a => a -> a -> a
- Int
w) Future a
ts
  where w :: Int
w = forall a. Complete a -> Int
weight Complete a
t

indexComplete :: Int -> Complete a -> a
indexComplete :: forall a. Int -> Complete a -> a
indexComplete Int
0 (Tip a
a) = a
a
indexComplete Int
i (Bin Int
w a
a Complete a
l Complete a
r)
  | Int
i forall a. Eq a => a -> a -> Bool
== Int
0    = a
a
  | Int
i forall a. Ord a => a -> a -> Bool
<= Int
w'   = forall a. Int -> Complete a -> a
indexComplete (Int
iforall a. Num a => a -> a -> a
-Int
1) Complete a
l
  | Bool
otherwise = forall a. Int -> Complete a -> a
indexComplete (Int
iforall a. Num a => a -> a -> a
-Int
1forall a. Num a => a -> a -> a
-Int
w') Complete a
r
  where w' :: Int
w' = forall a. Integral a => a -> a -> a
div Int
w Int
2
indexComplete Int
_ Complete a
_ = forall a. HasCallStack => String -> a
error String
"index: index out of range"

-- | /O(log n)/.

drop :: Int -> Future a -> Maybe (Future a)
drop :: forall a. Int -> Future a -> Maybe (Future a)
drop Int
0 Future a
ts = forall a. a -> Maybe a
Just Future a
ts
drop Int
i (Complete a
t :< Future a
ts) = case forall a. Ord a => a -> a -> Ordering
compare Int
i Int
w of
  Ordering
LT -> forall a. a -> Maybe a
Just (forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete Int
i Complete a
t (forall a. Complete a -> Future a -> Future a
:< Future a
ts))
  Ordering
EQ -> forall a. a -> Maybe a
Just Future a
ts
  Ordering
GT -> forall a. Int -> Future a -> Maybe (Future a)
drop (Int
i forall a. Num a => a -> a -> a
- Int
w) Future a
ts
  where w :: Int
w = forall a. Complete a -> Int
weight Complete a
t
drop Int
i (Last Complete a
t)
  | Int
i forall a. Ord a => a -> a -> Bool
< Int
w     = forall a. a -> Maybe a
Just (forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete Int
i Complete a
t forall a. Complete a -> Future a
Last)
  | Bool
otherwise = forall a. Maybe a
Nothing
  where w :: Int
w = forall a. Complete a -> Int
weight Complete a
t

dropComplete :: Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete :: forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete Int
0 Complete a
t Complete a -> Future a
f             = Complete a -> Future a
f Complete a
t
dropComplete Int
1 (Bin Int
_ a
_ Complete a
l Complete a
r) Complete a -> Future a
f = Complete a
l forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
f Complete a
r
dropComplete Int
i (Bin Int
w a
_ Complete a
l Complete a
r) Complete a -> Future a
f = case forall a. Ord a => a -> a -> Ordering
compare (Int
i forall a. Num a => a -> a -> a
- Int
1) Int
w' of
  Ordering
LT -> forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete (Int
iforall a. Num a => a -> a -> a
-Int
1) Complete a
l (forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
f Complete a
r)
  Ordering
EQ -> Complete a -> Future a
f Complete a
r
  Ordering
GT -> forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete (Int
iforall a. Num a => a -> a -> a
-Int
1forall a. Num a => a -> a -> a
-Int
w') Complete a
r Complete a -> Future a
f
  where w' :: Int
w' = forall a. Integral a => a -> a -> a
div Int
w Int
2
dropComplete Int
_ Complete a
_ Complete a -> Future a
_ = forall a. HasCallStack => String -> a
error String
"drop: index out of range"

-- /O(n)/.

dropWhile :: (a -> Bool) -> Future a -> Maybe (Future a)
dropWhile :: forall a. (a -> Bool) -> Future a -> Maybe (Future a)
dropWhile a -> Bool
p Future a
as
  | a -> Bool
p (forall (w :: * -> *) a. Comonad w => w a -> a
extract Future a
as) = forall a. Future a -> Maybe (Future a)
tail Future a
as forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall a. (a -> Bool) -> Future a -> Maybe (Future a)
dropWhile a -> Bool
p
  | Bool
otherwise = forall a. a -> Maybe a
Just Future a
as

-- /O(n)/

span :: (a -> Bool) -> Future a -> ([a], Maybe (Future a))
span :: forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
span a -> Bool
p Future a
aas = case forall a. Future a -> (a, Maybe (Future a))
uncons Future a
aas of
  (a
a, Just Future a
as) | a -> Bool
p a
a, ([a]
ts, Maybe (Future a)
fs) <- forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
span a -> Bool
p Future a
as -> (a
aforall a. a -> [a] -> [a]
:[a]
ts, Maybe (Future a)
fs)
  (a
a, Maybe (Future a)
Nothing) | a -> Bool
p a
a                        -> ([a
a], forall a. Maybe a
Nothing)
  (a
_, Maybe (Future a)
_)                                    -> ([], forall a. a -> Maybe a
Just Future a
aas)

-- /O(n)/

break :: (a -> Bool) -> Future a -> ([a], Maybe (Future a))
break :: forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
break a -> Bool
p = forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
span (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)

-- /(O(n), O(log n))/ split at _some_ edge where function goes from False to True.

-- best used with a monotonic function

split :: (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split :: forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split a -> Bool
p l :: Future a
l@(Last Complete a
a)
  | a -> Bool
p (forall (w :: * -> *) a. Comonad w => w a -> a
extract Complete a
a)  = ([], forall a. a -> Maybe a
Just Future a
l)
  | Bool
otherwise      = forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p Complete a
a forall a. Complete a -> Future a
Last
split a -> Bool
p (Complete a
a :< Future a
as)
  | a -> Bool
p (forall (w :: * -> *) a. Comonad w => w a -> a
extract Future a
as) = forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p Complete a
a (forall a. Complete a -> Future a -> Future a
:< Future a
as)
  | ([a]
ts, Maybe (Future a)
fs) <- forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split a -> Bool
p Future a
as = (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
a, Maybe (Future a)
fs)

-- for use when we know the split occurs within a given tree

splitComplete :: (a -> Bool) -> Complete a -> (Complete a -> Future a) -> ([a], Maybe (Future a))
splitComplete :: forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p t :: Complete a
t@(Tip a
a) Complete a -> Future a
f
  | a -> Bool
p a
a       = ([], forall a. a -> Maybe a
Just (Complete a -> Future a
f Complete a
t))
  | Bool
otherwise = ([a
a], forall a. Maybe a
Nothing)
splitComplete a -> Bool
p t :: Complete a
t@(Bin Int
_ a
a Complete a
l Complete a
r) Complete a -> Future a
f
  | a -> Bool
p a
a                                               = ([], forall a. a -> Maybe a
Just (Complete a -> Future a
f Complete a
t))
  | a -> Bool
p (forall (w :: * -> *) a. Comonad w => w a -> a
extract Complete a
r), ([a]
ts, Maybe (Future a)
fs) <- forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p Complete a
l (forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
f Complete a
r) = (a
aforall a. a -> [a] -> [a]
:[a]
ts, Maybe (Future a)
fs)
  |                ([a]
ts, Maybe (Future a)
fs) <- forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p Complete a
r Complete a -> Future a
f        = (a
aforall a. a -> [a] -> [a]
:forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
l, Maybe (Future a)
fs)

-- /(O(n), O(log n))/ split at _some_ edge where function goes from False to True.

-- best used with a monotonic function

--

-- > splitW p xs = (map extract &&& fmap (fmap extract)) . split p . duplicate

splitW :: (Future a -> Bool) -> Future a -> ([a], Maybe (Future a))
splitW :: forall a. (Future a -> Bool) -> Future a -> ([a], Maybe (Future a))
splitW Future a -> Bool
p l :: Future a
l@(Last Complete a
a)
  | Future a -> Bool
p Future a
l       = ([], forall a. a -> Maybe a
Just Future a
l)
  | Bool
otherwise = forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p Complete a
a forall a. Complete a -> Future a
Last
splitW Future a -> Bool
p (Complete a
a :< Future a
as)
  | Future a -> Bool
p Future a
as                    = forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p Complete a
a (forall a. Complete a -> Future a -> Future a
:< Future a
as)
  | ([a]
ts, Maybe (Future a)
fs) <- forall a. (Future a -> Bool) -> Future a -> ([a], Maybe (Future a))
splitW Future a -> Bool
p Future a
as = (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
a, Maybe (Future a)
fs)

-- for use when we know the split occurs within a given tree

splitCompleteW :: (Future a -> Bool) -> Complete a -> (Complete a -> Future a) -> ([a], Maybe (Future a))
splitCompleteW :: forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p t :: Complete a
t@(Tip a
a) Complete a -> Future a
f
  | Future a
w <- Complete a -> Future a
f Complete a
t, Future a -> Bool
p Future a
w = ([], forall a. a -> Maybe a
Just Future a
w)
  | Bool
otherwise = ([a
a], forall a. Maybe a
Nothing)
splitCompleteW Future a -> Bool
p t :: Complete a
t@(Bin Int
_ a
a Complete a
l Complete a
r) Complete a -> Future a
f
  | Future a
w <- Complete a -> Future a
f Complete a
t, Future a -> Bool
p Future a
w                                    = ([], forall a. a -> Maybe a
Just Future a
w)
  | Future a
w <- Complete a -> Future a
f Complete a
r, Future a -> Bool
p Future a
w, ([a]
ts, Maybe (Future a)
fs) <- forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p Complete a
l (forall a. Complete a -> Future a -> Future a
:< Future a
w) = (a
aforall a. a -> [a] -> [a]
:[a]
ts, Maybe (Future a)
fs)
  |                ([a]
ts, Maybe (Future a)
fs) <- forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p Complete a
r Complete a -> Future a
f      = (a
aforall a. a -> [a] -> [a]
:forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
l, Maybe (Future a)
fs)

#if MIN_VERSION_base(4,7,0)
instance Exts.IsList (Future a) where
  type Item (Future a) = a
  toList :: Future a -> [Item (Future a)]
toList = forall (t :: * -> *) a. Foldable t => t a -> [a]
Data.Foldable.toList
  fromList :: [Item (Future a)] -> Future a
fromList [] = forall a. HasCallStack => String -> a
error String
"fromList: empty list"
  fromList (Item (Future a)
x:[Item (Future a)]
xs) = forall {t}. t -> [t] -> Future t
go Item (Future a)
x [Item (Future a)]
xs
    where go :: t -> [t] -> Future t
go t
a [] = forall a. a -> Future a
singleton t
a
          go t
a (t
b:[t]
bs) = t
a forall a. a -> Future a -> Future a
<| t -> [t] -> Future t
go t
b [t]
bs
#else
fromList :: [a] -> Future a
fromList [] = error "fromList: empty list"
fromList (x:xs) = go x xs
  where go a [] = singleton a
        go a (b:bs) = a <| go b bs
#endif

toFuture :: [a] -> Maybe (Future a)
toFuture :: forall a. [a] -> Maybe (Future a)
toFuture [] = forall a. Maybe a
Nothing
#if MIN_VERSION_base(4,7,0)
toFuture [a]
xs = forall a. a -> Maybe a
Just (forall l. IsList l => [Item l] -> l
Exts.fromList [a]
xs)
#else
toFuture xs = Just (fromList xs)
#endif

-- /O(n)/

insert :: Ord a => a -> Future a -> Future a
insert :: forall a. Ord a => a -> Future a -> Future a
insert a
a Future a
as = case forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split (a
aforall a. Ord a => a -> a -> Bool
<=) Future a
as of
    ([a]
_, Maybe (Future a)
Nothing)  -> forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Future a -> Future a
(<|) (forall a. a -> Future a
singleton a
a) Future a
as
    ([a]
ts, Just Future a
as') -> forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Future a -> Future a
(<|) (a
a forall a. a -> Future a -> Future a
<| Future a
as') [a]
ts

-- /O(n)/. Finds the split in O(log n), but then has to recons

insertBy :: (a -> a -> Ordering) -> a -> Future a -> Future a
insertBy :: forall a. (a -> a -> Ordering) -> a -> Future a -> Future a
insertBy a -> a -> Ordering
cmp a
a Future a
as = case forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split (\a
b -> a -> a -> Ordering
cmp a
a a
b forall a. Ord a => a -> a -> Bool
<= Ordering
EQ) Future a
as of
    ([a]
_, Maybe (Future a)
Nothing)  -> forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Future a -> Future a
(<|) (forall a. a -> Future a
singleton a
a) Future a
as
    ([a]
ts, Just Future a
as') -> forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Future a -> Future a
(<|) (a
a forall a. a -> Future a -> Future a
<| Future a
as') [a]
ts

-- /O(log n)/ Change the value of the nth entry in the future

adjust :: Int -> (a -> a) -> Future a -> Future a
adjust :: forall a. Int -> (a -> a) -> Future a -> Future a
adjust !Int
n a -> a
f d :: Future a
d@(Last Complete a
a)
  | Int
n forall a. Ord a => a -> a -> Bool
< forall a. Complete a -> Int
weight Complete a
a = forall a. Complete a -> Future a
Last (forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete Int
n a -> a
f Complete a
a)
  | Bool
otherwise = Future a
d
adjust !Int
n a -> a
f (Complete a
a :< Future a
as)
  | Int
n forall a. Ord a => a -> a -> Bool
< Int
w = forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete Int
n a -> a
f Complete a
a forall a. Complete a -> Future a -> Future a
:< Future a
as
  | Bool
otherwise = Complete a
a forall a. Complete a -> Future a -> Future a
:< forall a. Int -> (a -> a) -> Future a -> Future a
adjust (Int
n forall a. Num a => a -> a -> a
- Int
w) a -> a
f Future a
as
  where w :: Int
w = forall a. Complete a -> Int
weight Complete a
a

adjustComplete :: Int -> (a -> a) -> Complete a -> Complete a
adjustComplete :: forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete Int
0 a -> a
f (Tip a
a) = forall a. a -> Complete a
Tip (a -> a
f a
a)
adjustComplete Int
_ a -> a
_ t :: Complete a
t@Tip{} = Complete a
t
adjustComplete Int
n a -> a
f (Bin Int
m a
a Complete a
l Complete a
r)
  | Int
n forall a. Eq a => a -> a -> Bool
== Int
0 = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
m (a -> a
f a
a) Complete a
l Complete a
r
  | Int
n forall a. Ord a => a -> a -> Bool
< Int
w = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
m a
a (forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete (Int
n forall a. Num a => a -> a -> a
- Int
1) a -> a
f Complete a
l) Complete a
r
  | Bool
otherwise = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
m a
a Complete a
l (forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete (Int
n forall a. Num a => a -> a -> a
- Int
1 forall a. Num a => a -> a -> a
- Int
w) a -> a
f Complete a
r)
  where w :: Int
w = forall a. Complete a -> Int
weight Complete a
l

update :: Int -> a -> Future a -> Future a
update :: forall a. Int -> a -> Future a -> Future a
update Int
n = forall a. Int -> (a -> a) -> Future a -> Future a
adjust Int
n forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const