module Test.Credit.Deque.Bankers where

import Prettyprinter (Pretty)
import Control.Monad.Credit
import Test.Credit
import Test.Credit.Deque.Base
import Test.Credit.Deque.Streams

-- | Delay a computation, but do not consume any credits
indirect :: MonadInherit m => SLazyCon m (Stream m a) -> m (Stream m a)
indirect :: forall (m :: * -> *) a.
MonadInherit m =>
SLazyCon m (Stream m a) -> m (Stream m a)
indirect SLazyCon m (Stream m a)
t = SLazyCon m (Stream m a) -> m (Thunk m (SLazyCon m) (Stream m a))
forall (m :: * -> *) (t :: * -> *) a.
MonadLazy m =>
t a -> m (Thunk m t a)
forall (t :: * -> *) a. t a -> m (Thunk m t a)
delay SLazyCon m (Stream m a)
t m (Thunk m (SLazyCon m) (Stream m a))
-> (Thunk m (SLazyCon m) (Stream m a) -> m (Stream m a))
-> m (Stream m a)
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Stream m a -> m (Stream m a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Stream m a -> m (Stream m a))
-> (Thunk m (SLazyCon m) (Stream m a) -> Stream m a)
-> Thunk m (SLazyCon m) (Stream m a)
-> m (Stream m a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Thunk m (SLazyCon m) (Stream m a) -> Stream m a
forall (m :: * -> *) a. SThunk m (Stream m a) -> Stream m a
SIndirect

data BDeque a m = BDeque
  { forall a (m :: * -> *). BDeque a m -> Stream m a
front :: Stream m a
  , forall a (m :: * -> *). BDeque a m -> Int
lenf :: !Int
  , forall a (m :: * -> *). BDeque a m -> Stream m a
ghostf :: Stream m a
  , forall a (m :: * -> *). BDeque a m -> Stream m a
rear :: Stream m a
  , forall a (m :: * -> *). BDeque a m -> Int
lenr :: !Int
  , forall a (m :: * -> *). BDeque a m -> Stream m a
ghostr :: Stream m a
  }

isEmpty :: BDeque a m -> Bool
isEmpty :: forall a (m :: * -> *). BDeque a m -> Bool
isEmpty (BDeque Stream m a
_ Int
0 Stream m a
_ Stream m a
_ Int
0 Stream m a
_) = Bool
True
isEmpty (BDeque Stream m a
_ Int
_ Stream m a
_ Stream m a
_ Int
_ Stream m a
_) = Bool
False

size :: BDeque a m -> Int
size :: forall a (m :: * -> *). BDeque a m -> Int
size (BDeque Stream m a
_ Int
lenf Stream m a
_ Stream m a
_ Int
lenr Stream m a
_) = Int
lenf Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lenr

-- Rough proof sketch:
-- After rebalancing, the front and rear streams have at most lenf + lenr debits.
-- Need (c - 1) * n/2 cons operations before rebalance, which means we have to
-- pay off 2 / (c - 1) debits on each stream per cons operation.
-- Need (c - 1) / c * n/2 uncons operations before rebalance, which means we have to
-- pay off at least 2*c / (c - 1) debits on each stream per uncons operation
-- (but also at least (c + 1) debits to be able to force on element).
-- Not sure if the analysis above works for c < 3

bdeque :: MonadInherit m => BDeque a m -> m (BDeque a m)
bdeque :: forall (m :: * -> *) a.
MonadInherit m =>
BDeque a m -> m (BDeque a m)
bdeque (BDeque Stream m a
f Int
lenf Stream m a
gf Stream m a
r Int
lenr Stream m a
gr)
  | Int
lenf Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
c Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
lenr Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 = do
    let i :: Int
i = (Int
lenf Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lenr) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
    let j :: Int
j = Int
lenf Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lenr Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i
    Stream m a
f' <- SLazyCon m (Stream m a) -> m (Stream m a)
forall (m :: * -> *) a.
MonadInherit m =>
SLazyCon m (Stream m a) -> m (Stream m a)
indirect (Int -> Stream m a -> SLazyCon m (Stream m a)
forall (m :: * -> *) a1.
Int -> Stream m a1 -> SLazyCon m (Stream m a1)
STake Int
i Stream m a
f)
    Stream m a
f'' <- SLazyCon m (Stream m a) -> m (Stream m a)
forall (m :: * -> *) a.
MonadInherit m =>
SLazyCon m (Stream m a) -> m (Stream m a)
indirect (Int -> Stream m a -> Stream m a -> SLazyCon m (Stream m a)
forall (m :: * -> *) a1.
Int -> Stream m a1 -> Stream m a1 -> SLazyCon m (Stream m a1)
SRevDrop Int
i Stream m a
f Stream m a
forall (m :: * -> *) a. Stream m a
SNil)
    Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit (Int -> Credit
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c) Stream m a
f'' m () -> m () -> m ()
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Int -> Stream m a -> m ()
forall (m :: * -> *) a. MonadInherit m => Int -> Stream m a -> m ()
eval (Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c) Stream m a
f''
    Stream m a
r' <- SLazyCon m (Stream m a) -> m (Stream m a)
forall (m :: * -> *) a.
MonadInherit m =>
SLazyCon m (Stream m a) -> m (Stream m a)
indirect (Stream m a -> Stream m a -> SLazyCon m (Stream m a)
forall (m :: * -> *) a1.
Stream m a1 -> Stream m a1 -> SLazyCon m (Stream m a1)
SAppend Stream m a
r Stream m a
f'')
    Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit Credit
1 Stream m a
r'
    BDeque a m -> m (BDeque a m)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (BDeque a m -> m (BDeque a m)) -> BDeque a m -> m (BDeque a m)
forall a b. (a -> b) -> a -> b
$ Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
forall a (m :: * -> *).
Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
BDeque Stream m a
f' Int
i Stream m a
f' Stream m a
r' Int
j Stream m a
r'
  | Int
lenr Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
c Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
lenf Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 = do
    let j :: Int
j = (Int
lenf Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lenr) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
    let i :: Int
i = Int
lenf Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lenr Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
j
    Stream m a
r' <- SLazyCon m (Stream m a) -> m (Stream m a)
forall (m :: * -> *) a.
MonadInherit m =>
SLazyCon m (Stream m a) -> m (Stream m a)
indirect (Int -> Stream m a -> SLazyCon m (Stream m a)
forall (m :: * -> *) a1.
Int -> Stream m a1 -> SLazyCon m (Stream m a1)
STake Int
j Stream m a
r)
    Stream m a
r'' <- SLazyCon m (Stream m a) -> m (Stream m a)
forall (m :: * -> *) a.
MonadInherit m =>
SLazyCon m (Stream m a) -> m (Stream m a)
indirect (Int -> Stream m a -> Stream m a -> SLazyCon m (Stream m a)
forall (m :: * -> *) a1.
Int -> Stream m a1 -> Stream m a1 -> SLazyCon m (Stream m a1)
SRevDrop Int
j Stream m a
r Stream m a
forall (m :: * -> *) a. Stream m a
SNil)
    Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit (Int -> Credit
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c) Stream m a
r'' m () -> m () -> m ()
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Int -> Stream m a -> m ()
forall (m :: * -> *) a. MonadInherit m => Int -> Stream m a -> m ()
eval (Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c) Stream m a
r''
    Stream m a
f' <- SLazyCon m (Stream m a) -> m (Stream m a)
forall (m :: * -> *) a.
MonadInherit m =>
SLazyCon m (Stream m a) -> m (Stream m a)
indirect (Stream m a -> Stream m a -> SLazyCon m (Stream m a)
forall (m :: * -> *) a1.
Stream m a1 -> Stream m a1 -> SLazyCon m (Stream m a1)
SAppend Stream m a
f Stream m a
r'')
    Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit Credit
1 Stream m a
f'
    BDeque a m -> m (BDeque a m)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (BDeque a m -> m (BDeque a m)) -> BDeque a m -> m (BDeque a m)
forall a b. (a -> b) -> a -> b
$ Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
forall a (m :: * -> *).
Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
BDeque Stream m a
f' Int
i Stream m a
f' Stream m a
r' Int
j Stream m a
r'
  | Bool
otherwise =
    BDeque a m -> m (BDeque a m)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (BDeque a m -> m (BDeque a m)) -> BDeque a m -> m (BDeque a m)
forall a b. (a -> b) -> a -> b
$ Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
forall a (m :: * -> *).
Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
BDeque Stream m a
f Int
lenf Stream m a
gf Stream m a
r Int
lenr Stream m a
gr

instance Deque BDeque where
  empty :: forall (m :: * -> *) a. MonadInherit m => m (BDeque a m)
empty = BDeque a m -> m (BDeque a m)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (BDeque a m -> m (BDeque a m)) -> BDeque a m -> m (BDeque a m)
forall a b. (a -> b) -> a -> b
$ Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
forall a (m :: * -> *).
Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
BDeque Stream m a
forall (m :: * -> *) a. Stream m a
SNil Int
0 Stream m a
forall (m :: * -> *) a. Stream m a
SNil Stream m a
forall (m :: * -> *) a. Stream m a
SNil Int
0 Stream m a
forall (m :: * -> *) a. Stream m a
SNil
  cons :: forall (m :: * -> *) a.
MonadInherit m =>
a -> BDeque a m -> m (BDeque a m)
cons a
x (BDeque Stream m a
f Int
fl Stream m a
gf Stream m a
r Int
rl Stream m a
gr) = Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit Credit
1 Stream m a
gf m () -> m () -> m ()
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit Credit
1 Stream m a
gr m () -> m (BDeque a m) -> m (BDeque a m)
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>>
    BDeque a m -> m (BDeque a m)
forall (m :: * -> *) a.
MonadInherit m =>
BDeque a m -> m (BDeque a m)
bdeque (Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
forall a (m :: * -> *).
Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
BDeque (a -> Stream m a -> Stream m a
forall (m :: * -> *) a. a -> Stream m a -> Stream m a
SCons a
x Stream m a
f) (Int
fl Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Stream m a
gf Stream m a
r Int
rl Stream m a
gr)
  snoc :: forall (m :: * -> *) a.
MonadInherit m =>
BDeque a m -> a -> m (BDeque a m)
snoc (BDeque Stream m a
f Int
fl Stream m a
gf Stream m a
r Int
rl Stream m a
gr) a
x = Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit Credit
1 Stream m a
gf m () -> m () -> m ()
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit Credit
1 Stream m a
gr m () -> m (BDeque a m) -> m (BDeque a m)
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>>
    BDeque a m -> m (BDeque a m)
forall (m :: * -> *) a.
MonadInherit m =>
BDeque a m -> m (BDeque a m)
bdeque (Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
forall a (m :: * -> *).
Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
BDeque Stream m a
f Int
fl Stream m a
gf (a -> Stream m a -> Stream m a
forall (m :: * -> *) a. a -> Stream m a -> Stream m a
SCons a
x Stream m a
r) (Int
rl Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Stream m a
gr)
  uncons :: forall (m :: * -> *) a.
MonadInherit m =>
BDeque a m -> m (Maybe (a, BDeque a m))
uncons (BDeque Stream m a
f Int
fl Stream m a
gf Stream m a
r Int
rl Stream m a
gr) = Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit (Int -> Credit
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c Credit -> Credit -> Credit
forall a. Num a => a -> a -> a
+ Credit
1) Stream m a
gf m () -> m () -> m ()
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit (Int -> Credit
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c Credit -> Credit -> Credit
forall a. Num a => a -> a -> a
+ Credit
1) Stream m a
gr m () -> m (Maybe (a, BDeque a m)) -> m (Maybe (a, BDeque a m))
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Stream m a
-> (a -> Stream m a -> m (Maybe (a, BDeque a m)))
-> m (Maybe (a, BDeque a m))
-> m (Maybe (a, BDeque a m))
forall (m :: * -> *) a b.
MonadInherit m =>
Stream m a -> (a -> Stream m a -> m b) -> m b -> m b
smatch Stream m a
f
    (\a
x Stream m a
f -> BDeque a m -> m (BDeque a m)
forall (m :: * -> *) a.
MonadInherit m =>
BDeque a m -> m (BDeque a m)
bdeque (Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
forall a (m :: * -> *).
Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
BDeque Stream m a
f (Int
fl Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Stream m a
gf Stream m a
r Int
rl Stream m a
gr) m (BDeque a m)
-> (BDeque a m -> m (Maybe (a, BDeque a m)))
-> m (Maybe (a, BDeque a m))
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \BDeque a m
q -> Maybe (a, BDeque a m) -> m (Maybe (a, BDeque a m))
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe (a, BDeque a m) -> m (Maybe (a, BDeque a m)))
-> Maybe (a, BDeque a m) -> m (Maybe (a, BDeque a m))
forall a b. (a -> b) -> a -> b
$ (a, BDeque a m) -> Maybe (a, BDeque a m)
forall a. a -> Maybe a
Just (a
x, BDeque a m
q))
    (Stream m a
-> (a -> Stream m a -> m (Maybe (a, BDeque a m)))
-> m (Maybe (a, BDeque a m))
-> m (Maybe (a, BDeque a m))
forall (m :: * -> *) a b.
MonadInherit m =>
Stream m a -> (a -> Stream m a -> m b) -> m b -> m b
smatch Stream m a
r
      (\a
x Stream m a
_ -> m (BDeque a m)
forall (m :: * -> *) a. MonadInherit m => m (BDeque a m)
forall (q :: * -> (* -> *) -> *) (m :: * -> *) a.
(Deque q, MonadInherit m) =>
m (q a m)
empty m (BDeque a m)
-> (BDeque a m -> m (Maybe (a, BDeque a m)))
-> m (Maybe (a, BDeque a m))
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \BDeque a m
q -> Maybe (a, BDeque a m) -> m (Maybe (a, BDeque a m))
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe (a, BDeque a m) -> m (Maybe (a, BDeque a m)))
-> Maybe (a, BDeque a m) -> m (Maybe (a, BDeque a m))
forall a b. (a -> b) -> a -> b
$ (a, BDeque a m) -> Maybe (a, BDeque a m)
forall a. a -> Maybe a
Just (a
x, BDeque a m
q))
      (Maybe (a, BDeque a m) -> m (Maybe (a, BDeque a m))
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe (a, BDeque a m)
forall a. Maybe a
Nothing))
  unsnoc :: forall (m :: * -> *) a.
MonadInherit m =>
BDeque a m -> m (Maybe (BDeque a m, a))
unsnoc (BDeque Stream m a
f Int
fl Stream m a
gf Stream m a
r Int
rl Stream m a
gr) = Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit (Int -> Credit
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c Credit -> Credit -> Credit
forall a. Num a => a -> a -> a
+ Credit
1) Stream m a
gr m () -> m () -> m ()
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Credit -> Stream m a -> m ()
forall (m :: * -> *) a.
MonadInherit m =>
Credit -> Stream m a -> m ()
credit (Int -> Credit
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c Credit -> Credit -> Credit
forall a. Num a => a -> a -> a
+ Credit
1) Stream m a
gf m () -> m (Maybe (BDeque a m, a)) -> m (Maybe (BDeque a m, a))
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Stream m a
-> (a -> Stream m a -> m (Maybe (BDeque a m, a)))
-> m (Maybe (BDeque a m, a))
-> m (Maybe (BDeque a m, a))
forall (m :: * -> *) a b.
MonadInherit m =>
Stream m a -> (a -> Stream m a -> m b) -> m b -> m b
smatch Stream m a
r
    (\a
x Stream m a
r -> BDeque a m -> m (BDeque a m)
forall (m :: * -> *) a.
MonadInherit m =>
BDeque a m -> m (BDeque a m)
bdeque (Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
forall a (m :: * -> *).
Stream m a
-> Int
-> Stream m a
-> Stream m a
-> Int
-> Stream m a
-> BDeque a m
BDeque Stream m a
f Int
fl Stream m a
gf Stream m a
r (Int
rl Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Stream m a
gr) m (BDeque a m)
-> (BDeque a m -> m (Maybe (BDeque a m, a)))
-> m (Maybe (BDeque a m, a))
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \BDeque a m
q -> Maybe (BDeque a m, a) -> m (Maybe (BDeque a m, a))
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe (BDeque a m, a) -> m (Maybe (BDeque a m, a)))
-> Maybe (BDeque a m, a) -> m (Maybe (BDeque a m, a))
forall a b. (a -> b) -> a -> b
$ (BDeque a m, a) -> Maybe (BDeque a m, a)
forall a. a -> Maybe a
Just (BDeque a m
q, a
x))
    (Stream m a
-> (a -> Stream m a -> m (Maybe (BDeque a m, a)))
-> m (Maybe (BDeque a m, a))
-> m (Maybe (BDeque a m, a))
forall (m :: * -> *) a b.
MonadInherit m =>
Stream m a -> (a -> Stream m a -> m b) -> m b -> m b
smatch Stream m a
f
      (\a
x Stream m a
_ -> m (BDeque a m)
forall (m :: * -> *) a. MonadInherit m => m (BDeque a m)
forall (q :: * -> (* -> *) -> *) (m :: * -> *) a.
(Deque q, MonadInherit m) =>
m (q a m)
empty m (BDeque a m)
-> (BDeque a m -> m (Maybe (BDeque a m, a)))
-> m (Maybe (BDeque a m, a))
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \BDeque a m
q -> Maybe (BDeque a m, a) -> m (Maybe (BDeque a m, a))
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe (BDeque a m, a) -> m (Maybe (BDeque a m, a)))
-> Maybe (BDeque a m, a) -> m (Maybe (BDeque a m, a))
forall a b. (a -> b) -> a -> b
$ (BDeque a m, a) -> Maybe (BDeque a m, a)
forall a. a -> Maybe a
Just (BDeque a m
q, a
x))
      (Maybe (BDeque a m, a) -> m (Maybe (BDeque a m, a))
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe (BDeque a m, a)
forall a. Maybe a
Nothing))
  concat :: forall (m :: * -> *) a.
MonadInherit m =>
BDeque a m -> BDeque a m -> m (BDeque a m)
concat = BDeque a m -> BDeque a m -> m (BDeque a m)
forall a. HasCallStack => a
undefined

instance BoundedDeque BDeque where
  qcost :: forall a. Size -> DequeOp a -> Credit
qcost Size
_ (Cons a
_) = Int -> Credit
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c Credit -> Credit -> Credit
forall a. Num a => a -> a -> a
+ Credit
3
  qcost Size
_ (Snoc a
_) = Int -> Credit
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c Credit -> Credit -> Credit
forall a. Num a => a -> a -> a
+ Credit
3
  qcost Size
_ DequeOp a
Uncons = Credit
3 Credit -> Credit -> Credit
forall a. Num a => a -> a -> a
* Int -> Credit
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c Credit -> Credit -> Credit
forall a. Num a => a -> a -> a
+ Credit
4
  qcost Size
_ DequeOp a
Unsnoc = Credit
3 Credit -> Credit -> Credit
forall a. Num a => a -> a -> a
* Int -> Credit
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c Credit -> Credit -> Credit
forall a. Num a => a -> a -> a
+ Credit
4
  qcost Size
_ DequeOp a
Concat = Credit
0

instance (MonadMemory m, MemoryCell m a) => MemoryCell m (BDeque a m) where
  prettyCell :: BDeque a m -> m Memory
prettyCell (BDeque Stream m a
f Int
fl Stream m a
_ Stream m a
r Int
rl Stream m a
_) = do
    Memory
f' <- Stream m a -> m Memory
forall (m :: * -> *) a. MemoryCell m a => a -> m Memory
prettyCell Stream m a
f
    Memory
fl' <- Int -> m Memory
forall (m :: * -> *) a. MemoryCell m a => a -> m Memory
prettyCell Int
fl
    Memory
r' <- Stream m a -> m Memory
forall (m :: * -> *) a. MemoryCell m a => a -> m Memory
prettyCell Stream m a
r
    Memory
rl' <- Int -> m Memory
forall (m :: * -> *) a. MemoryCell m a => a -> m Memory
prettyCell Int
rl
    Memory -> m Memory
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Memory -> m Memory) -> Memory -> m Memory
forall a b. (a -> b) -> a -> b
$ String -> [Memory] -> Memory
mkMCell String
"BDeque" [Memory
f', Memory
fl', Memory
r', Memory
rl']

instance Pretty a => MemoryStructure (BDeque (PrettyCell a)) where
  prettyStructure :: forall (m :: * -> *).
MonadMemory m =>
BDeque (PrettyCell a) m -> m Memory
prettyStructure = BDeque (PrettyCell a) m -> m Memory
forall (m :: * -> *) a. MemoryCell m a => a -> m Memory
prettyCell