{-# LANGUAGE TypeFamilies #-}
-- | Doubly-linked list
module Data.Mutable.DLList
    ( DLList
    , asDLList
    , module Data.Mutable.Class
    ) where

import Data.Mutable.Class

data Node s a = Node
    a
    (MutVar s (Maybe (Node s a))) -- previous
    (MutVar s (Maybe (Node s a))) -- next

-- | A doubly-linked list.
--
-- Since 0.3.0
data DLList s a = DLList (MutVar s (Maybe (Node s a))) (MutVar s (Maybe (Node s a)))

-- |
-- Since 0.2.0
asDLList :: DLList s a -> DLList s a
asDLList :: forall s a. DLList s a -> DLList s a
asDLList = forall a. a -> a
id
{-# INLINE asDLList #-}

instance MutableContainer (DLList s a) where
    type MCState (DLList s a) = s
instance MutableCollection (DLList s a) where
    type CollElement (DLList s a) = a
    newColl :: forall (m :: * -> *).
(PrimMonad m, PrimState m ~ MCState (DLList s a)) =>
m (DLList s a)
newColl = do
        MutVar s (Maybe (Node s a))
x <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
RefElement c -> m c
newRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
        MutVar s (Maybe (Node s a))
y <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
RefElement c -> m c
newRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
        forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$! forall s a.
MutVar s (Maybe (Node s a))
-> MutVar s (Maybe (Node s a)) -> DLList s a
DLList MutVar s (Maybe (Node s a))
x MutVar s (Maybe (Node s a))
y
    {-# INLINE newColl #-}
instance MutablePopFront (DLList s a) where
    popFront :: forall (m :: * -> *).
(PrimMonad m, PrimState m ~ MCState (DLList s a)) =>
DLList s a -> m (Maybe (CollElement (DLList s a)))
popFront (DLList MutVar s (Maybe (Node s a))
frontRef MutVar s (Maybe (Node s a))
backRef) = do
        Maybe (Node s a)
mfront <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> m (RefElement c)
readRef MutVar s (Maybe (Node s a))
frontRef
        case Maybe (Node s a)
mfront of
            Maybe (Node s a)
Nothing -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
            Just (Node a
val MutVar s (Maybe (Node s a))
_ MutVar s (Maybe (Node s a))
nextRef) -> do
                Maybe (Node s a)
mnext <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> m (RefElement c)
readRef MutVar s (Maybe (Node s a))
nextRef
                case Maybe (Node s a)
mnext of
                    Maybe (Node s a)
Nothing -> do
                        forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
frontRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                        forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
backRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                    Just next :: Node s a
next@(Node a
_ MutVar s (Maybe (Node s a))
prevRef MutVar s (Maybe (Node s a))
_) -> do
                        forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
prevRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                        forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
frontRef forall a b. (a -> b) -> a -> b
$! forall a. a -> Maybe a
Just Node s a
next
                forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just a
val
    {-# INLINE popFront #-}
instance MutablePopBack (DLList s a) where
    popBack :: forall (m :: * -> *).
(PrimMonad m, PrimState m ~ MCState (DLList s a)) =>
DLList s a -> m (Maybe (CollElement (DLList s a)))
popBack (DLList MutVar s (Maybe (Node s a))
frontRef MutVar s (Maybe (Node s a))
backRef) = do
        Maybe (Node s a)
mback <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> m (RefElement c)
readRef MutVar s (Maybe (Node s a))
backRef
        case Maybe (Node s a)
mback of
            Maybe (Node s a)
Nothing -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
            Just (Node a
val MutVar s (Maybe (Node s a))
prevRef MutVar s (Maybe (Node s a))
_) -> do
                Maybe (Node s a)
mprev <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> m (RefElement c)
readRef MutVar s (Maybe (Node s a))
prevRef
                case Maybe (Node s a)
mprev of
                    Maybe (Node s a)
Nothing -> do
                        forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
frontRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                        forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
backRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                    Just prev :: Node s a
prev@(Node a
_ MutVar s (Maybe (Node s a))
_ MutVar s (Maybe (Node s a))
nextRef) -> do
                        forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
nextRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                        forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
backRef (forall a. a -> Maybe a
Just Node s a
prev)
                forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just a
val
    {-# INLINE popBack #-}
instance MutablePushFront (DLList s a) where
    pushFront :: forall (m :: * -> *).
(PrimMonad m, PrimState m ~ MCState (DLList s a)) =>
DLList s a -> CollElement (DLList s a) -> m ()
pushFront (DLList MutVar s (Maybe (Node s a))
frontRef MutVar s (Maybe (Node s a))
backRef) CollElement (DLList s a)
val = do
        Maybe (Node s a)
mfront <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> m (RefElement c)
readRef MutVar s (Maybe (Node s a))
frontRef
        case Maybe (Node s a)
mfront of
            Maybe (Node s a)
Nothing -> do
                MutVar s (Maybe (Node s a))
prevRef <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
RefElement c -> m c
newRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                MutVar s (Maybe (Node s a))
nextRef <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
RefElement c -> m c
newRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                let node :: Maybe (Node s a)
node = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall s a.
a
-> MutVar s (Maybe (Node s a))
-> MutVar s (Maybe (Node s a))
-> Node s a
Node CollElement (DLList s a)
val MutVar s (Maybe (Node s a))
prevRef MutVar s (Maybe (Node s a))
nextRef
                forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
frontRef Maybe (Node s a)
node
                forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
backRef Maybe (Node s a)
node
            Just front :: Node s a
front@(Node a
_ MutVar s (Maybe (Node s a))
prevRef MutVar s (Maybe (Node s a))
_) -> do
                MutVar s (Maybe (Node s a))
prevRefNew <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
RefElement c -> m c
newRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                MutVar s (Maybe (Node s a))
nextRef <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
RefElement c -> m c
newRef forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just Node s a
front
                let node :: Maybe (Node s a)
node = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall s a.
a
-> MutVar s (Maybe (Node s a))
-> MutVar s (Maybe (Node s a))
-> Node s a
Node CollElement (DLList s a)
val MutVar s (Maybe (Node s a))
prevRefNew MutVar s (Maybe (Node s a))
nextRef
                forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
prevRef Maybe (Node s a)
node
                forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
frontRef Maybe (Node s a)
node
    {-# INLINE pushFront #-}
instance MutablePushBack (DLList s a) where
    pushBack :: forall (m :: * -> *).
(PrimMonad m, PrimState m ~ MCState (DLList s a)) =>
DLList s a -> CollElement (DLList s a) -> m ()
pushBack (DLList MutVar s (Maybe (Node s a))
frontRef MutVar s (Maybe (Node s a))
backRef) CollElement (DLList s a)
val = do
        Maybe (Node s a)
mback <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> m (RefElement c)
readRef MutVar s (Maybe (Node s a))
backRef
        case Maybe (Node s a)
mback of
            Maybe (Node s a)
Nothing -> do
                MutVar s (Maybe (Node s a))
prevRef <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
RefElement c -> m c
newRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                MutVar s (Maybe (Node s a))
nextRef <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
RefElement c -> m c
newRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                let node :: Maybe (Node s a)
node = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall s a.
a
-> MutVar s (Maybe (Node s a))
-> MutVar s (Maybe (Node s a))
-> Node s a
Node CollElement (DLList s a)
val MutVar s (Maybe (Node s a))
prevRef MutVar s (Maybe (Node s a))
nextRef
                forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
frontRef forall a b. (a -> b) -> a -> b
$! Maybe (Node s a)
node
                forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
backRef forall a b. (a -> b) -> a -> b
$! Maybe (Node s a)
node
            Just back :: Node s a
back@(Node a
_ MutVar s (Maybe (Node s a))
_ MutVar s (Maybe (Node s a))
nextRef) -> do
                MutVar s (Maybe (Node s a))
nextRefNew <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
RefElement c -> m c
newRef forall a b. (a -> b) -> a -> b
$! forall a. Maybe a
Nothing
                MutVar s (Maybe (Node s a))
prevRef <- forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
RefElement c -> m c
newRef forall a b. (a -> b) -> a -> b
$! forall a. a -> Maybe a
Just Node s a
back
                let node :: Maybe (Node s a)
node = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! forall s a.
a
-> MutVar s (Maybe (Node s a))
-> MutVar s (Maybe (Node s a))
-> Node s a
Node CollElement (DLList s a)
val MutVar s (Maybe (Node s a))
prevRef MutVar s (Maybe (Node s a))
nextRefNew
                forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
nextRef forall a b. (a -> b) -> a -> b
$! Maybe (Node s a)
node
                forall c (m :: * -> *).
(MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
c -> RefElement c -> m ()
writeRef MutVar s (Maybe (Node s a))
backRef forall a b. (a -> b) -> a -> b
$! Maybe (Node s a)
node
    {-# INLINE pushBack #-}