    {-# 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 = DLList s a -> DLList s a
    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
            x <- Maybe (Node s a) -> m (MutVar s (Maybe (Node s a)))
    RefElement (MutVar s (Maybe (Node s a)))
    -> m (MutVar s (Maybe (Node s a)))
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    RefElement c -> m c
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    RefElement (MutVar s (Maybe (Node s a)))
    -> m (MutVar s (Maybe (Node s a)))
    newRef (Maybe (Node s a) -> m (MutVar s (Maybe (Node s a))))
    -> Maybe (Node s a) -> m (MutVar s (Maybe (Node s a)))
    forall a b. (a -> b) -> a -> b
    $! Maybe (Node s a)
    forall a. Maybe a
    Nothing
            y <- newRef $! Nothing
            return $! DLList x 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
            mfront <- MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> m (RefElement c)
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    readRef MutVar s (Maybe (Node s a))
    frontRef
            case mfront of
                Maybe (Node s a)
    Nothing -> Maybe a -> m (Maybe a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Maybe a
    forall a. Maybe a
    Nothing
                Just (Node a
    val MutVar s (Maybe (Node s a))
    _ MutVar s (Maybe (Node s a))
    nextRef) -> do
                    mnext <- MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> m (RefElement c)
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    readRef MutVar s (Maybe (Node s a))
    nextRef
                    case mnext of
                        Maybe (Node s a)
    Nothing -> do
                            MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> RefElement c -> m ()
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    writeRef MutVar s (Maybe (Node s a))
    frontRef (Maybe (Node s a) -> m ()) -> Maybe (Node s a) -> m ()
    forall a b. (a -> b) -> a -> b
    $! Maybe (Node s a)
    forall a. Maybe a
    Nothing
                            MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> RefElement c -> m ()
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    writeRef MutVar s (Maybe (Node s a))
    backRef (Maybe (Node s a) -> m ()) -> Maybe (Node s a) -> m ()
    forall a b. (a -> b) -> a -> b
    $! Maybe (Node s a)
    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
                            MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> RefElement c -> m ()
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    writeRef MutVar s (Maybe (Node s a))
    prevRef (Maybe (Node s a) -> m ()) -> Maybe (Node s a) -> m ()
    forall a b. (a -> b) -> a -> b
    $! Maybe (Node s a)
    forall a. Maybe a
    Nothing
                            MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> RefElement c -> m ()
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    writeRef MutVar s (Maybe (Node s a))
    frontRef (Maybe (Node s a) -> m ()) -> Maybe (Node s a) -> m ()
    forall a b. (a -> b) -> a -> b
    $! Node s a -> Maybe (Node s a)
    forall a. a -> Maybe a
    Just Node s a
    next
                    return $ Just 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
            mback <- MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> m (RefElement c)
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    readRef MutVar s (Maybe (Node s a))
    backRef
            case mback of
                Maybe (Node s a)
    Nothing -> Maybe a -> m (Maybe a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Maybe a
    forall a. Maybe a
    Nothing
                Just (Node a
    val MutVar s (Maybe (Node s a))
    prevRef MutVar s (Maybe (Node s a))
    _) -> do
                    mprev <- MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> m (RefElement c)
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    readRef MutVar s (Maybe (Node s a))
    prevRef
                    case mprev of
                        Maybe (Node s a)
    Nothing -> do
                            MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> RefElement c -> m ()
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    writeRef MutVar s (Maybe (Node s a))
    frontRef (Maybe (Node s a) -> m ()) -> Maybe (Node s a) -> m ()
    forall a b. (a -> b) -> a -> b
    $! Maybe (Node s a)
    forall a. Maybe a
    Nothing
                            MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> RefElement c -> m ()
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    writeRef MutVar s (Maybe (Node s a))
    backRef (Maybe (Node s a) -> m ()) -> Maybe (Node s a) -> m ()
    forall a b. (a -> b) -> a -> b
    $! Maybe (Node s a)
    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
                            MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> RefElement c -> m ()
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    writeRef MutVar s (Maybe (Node s a))
    nextRef (Maybe (Node s a) -> m ()) -> Maybe (Node s a) -> m ()
    forall a b. (a -> b) -> a -> b
    $! Maybe (Node s a)
    forall a. Maybe a
    Nothing
                            MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> RefElement c -> m ()
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> RefElement (MutVar s (Maybe (Node s a))) -> m ()
    writeRef MutVar s (Maybe (Node s a))
    backRef (Node s a -> Maybe (Node s a)
    forall a. a -> Maybe a
    Just Node s a
    prev)
                    return $ Just 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
            mfront <- MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> m (RefElement c)
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    readRef MutVar s (Maybe (Node s a))
    frontRef
            case mfront of
                Maybe (Node s a)
    Nothing -> do
                    prevRef <- Maybe (Node s a) -> m (MutVar s (Maybe (Node s a)))
    RefElement (MutVar s (Maybe (Node s a)))
    -> m (MutVar s (Maybe (Node s a)))
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    RefElement c -> m c
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    RefElement (MutVar s (Maybe (Node s a)))
    -> m (MutVar s (Maybe (Node s a)))
    newRef (Maybe (Node s a) -> m (MutVar s (Maybe (Node s a))))
    -> Maybe (Node s a) -> m (MutVar s (Maybe (Node s a)))
    forall a b. (a -> b) -> a -> b
    $! Maybe (Node s a)
    forall a. Maybe a
    Nothing
                    nextRef <- newRef $! Nothing
                    let node = Node s a -> Maybe (Node s a)
    forall a. a -> Maybe a
    Just (Node s a -> Maybe (Node s a)) -> Node s a -> Maybe (Node s a)
    forall a b. (a -> b) -> a -> b
    $ a
    -> MutVar s (Maybe (Node s a))
    -> MutVar s (Maybe (Node s a))
    -> Node s a
    forall s a.
    a
    -> MutVar s (Maybe (Node s a))
    -> MutVar s (Maybe (Node s a))
    -> Node s a
    Node a
    CollElement (DLList s a)
    val MutVar s (Maybe (Node s a))
    prevRef MutVar s (Maybe (Node s a))
    nextRef
                    writeRef frontRef node
                    writeRef backRef node
                Just front :: Node s a
    front@(Node a
    _ MutVar s (Maybe (Node s a))
    prevRef MutVar s (Maybe (Node s a))
    _) -> do
                    prevRefNew <- Maybe (Node s a) -> m (MutVar s (Maybe (Node s a)))
    RefElement (MutVar s (Maybe (Node s a)))
    -> m (MutVar s (Maybe (Node s a)))
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    RefElement c -> m c
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    RefElement (MutVar s (Maybe (Node s a)))
    -> m (MutVar s (Maybe (Node s a)))
    newRef (Maybe (Node s a) -> m (MutVar s (Maybe (Node s a))))
    -> Maybe (Node s a) -> m (MutVar s (Maybe (Node s a)))
    forall a b. (a -> b) -> a -> b
    $! Maybe (Node s a)
    forall a. Maybe a
    Nothing
                    nextRef <- newRef $ Just front
                    let node = Node s a -> Maybe (Node s a)
    forall a. a -> Maybe a
    Just (Node s a -> Maybe (Node s a)) -> Node s a -> Maybe (Node s a)
    forall a b. (a -> b) -> a -> b
    $ a
    -> MutVar s (Maybe (Node s a))
    -> MutVar s (Maybe (Node s a))
    -> Node s a
    forall s a.
    a
    -> MutVar s (Maybe (Node s a))
    -> MutVar s (Maybe (Node s a))
    -> Node s a
    Node a
    CollElement (DLList s a)
    val MutVar s (Maybe (Node s a))
    prevRefNew MutVar s (Maybe (Node s a))
    nextRef
                    writeRef prevRef node
                    writeRef frontRef 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
            mback <- MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    c -> m (RefElement c)
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    MutVar s (Maybe (Node s a))
    -> m (RefElement (MutVar s (Maybe (Node s a))))
    readRef MutVar s (Maybe (Node s a))
    backRef
            case mback of
                Maybe (Node s a)
    Nothing -> do
                    prevRef <- Maybe (Node s a) -> m (MutVar s (Maybe (Node s a)))
    RefElement (MutVar s (Maybe (Node s a)))
    -> m (MutVar s (Maybe (Node s a)))
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    RefElement c -> m c
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    RefElement (MutVar s (Maybe (Node s a)))
    -> m (MutVar s (Maybe (Node s a)))
    newRef (Maybe (Node s a) -> m (MutVar s (Maybe (Node s a))))
    -> Maybe (Node s a) -> m (MutVar s (Maybe (Node s a)))
    forall a b. (a -> b) -> a -> b
    $! Maybe (Node s a)
    forall a. Maybe a
    Nothing
                    nextRef <- newRef $! Nothing
                    let node = Node s a -> Maybe (Node s a)
    forall a. a -> Maybe a
    Just (Node s a -> Maybe (Node s a)) -> Node s a -> Maybe (Node s a)
    forall a b. (a -> b) -> a -> b
    $! a
    -> MutVar s (Maybe (Node s a))
    -> MutVar s (Maybe (Node s a))
    -> Node s a
    forall s a.
    a
    -> MutVar s (Maybe (Node s a))
    -> MutVar s (Maybe (Node s a))
    -> Node s a
    Node a
    CollElement (DLList s a)
    val MutVar s (Maybe (Node s a))
    prevRef MutVar s (Maybe (Node s a))
    nextRef
                    writeRef frontRef $! node
                    writeRef backRef $! node
                Just back :: Node s a
    back@(Node a
    _ MutVar s (Maybe (Node s a))
    _ MutVar s (Maybe (Node s a))
    nextRef) -> do
                    nextRefNew <- Maybe (Node s a) -> m (MutVar s (Maybe (Node s a)))
    RefElement (MutVar s (Maybe (Node s a)))
    -> m (MutVar s (Maybe (Node s a)))
    forall c (m :: * -> *).
    (MutableRef c, PrimMonad m, PrimState m ~ MCState c) =>
    RefElement c -> m c
    forall (m :: * -> *).
    (PrimMonad m,
     PrimState m ~ MCState (MutVar s (Maybe (Node s a)))) =>
    RefElement (MutVar s (Maybe (Node s a)))
    -> m (MutVar s (Maybe (Node s a)))
    newRef (Maybe (Node s a) -> m (MutVar s (Maybe (Node s a))))
    -> Maybe (Node s a) -> m (MutVar s (Maybe (Node s a)))
    forall a b. (a -> b) -> a -> b
    $! Maybe (Node s a)
    forall a. Maybe a
    Nothing
                    prevRef <- newRef $! Just back
                    let node = Node s a -> Maybe (Node s a)
    forall a. a -> Maybe a
    Just (Node s a -> Maybe (Node s a)) -> Node s a -> Maybe (Node s a)
    forall a b. (a -> b) -> a -> b
    $! a
    -> MutVar s (Maybe (Node s a))
    -> MutVar s (Maybe (Node s a))
    -> Node s a
    forall s a.
    a
    -> MutVar s (Maybe (Node s a))
    -> MutVar s (Maybe (Node s a))
    -> Node s a
    Node a
    CollElement (DLList s a)
    val MutVar s (Maybe (Node s a))
    prevRef MutVar s (Maybe (Node s a))
    nextRefNew
                    writeRef nextRef $! node
                    writeRef backRef $! node
        {-# INLINE pushBack #-}