-- |
-- Module     : Simulation.Aivika.DoubleLinkedList
-- Copyright  : Copyright (c) 2009-2017, David Sorokin <david.sorokin@gmail.com>
-- License    : BSD3
-- Maintainer : David Sorokin <david.sorokin@gmail.com>
-- Stability  : experimental
-- Tested with: GHC 8.0.1
--
-- An imperative double-linked list.
--
module Simulation.Aivika.DoubleLinkedList 
       (DoubleLinkedList, 
        listNull, 
        listCount,
        newList, 
        listInsertFirst,
        listAddLast,
        listRemoveFirst,
        listRemoveLast,
        listRemove,
        listRemoveBy,
        listContains,
        listContainsBy,
        listFirst,
        listLast,
        clearList,
        freezeList) where 

import Data.IORef
import Data.Maybe

import Control.Monad

-- | A cell of the double-linked list.
data DoubleLinkedItem a = 
  DoubleLinkedItem { forall a. DoubleLinkedItem a -> a
itemVal  :: a,
                     forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev :: IORef (Maybe (DoubleLinkedItem a)),
                     forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext :: IORef (Maybe (DoubleLinkedItem a)) }
  
-- | The 'DoubleLinkedList' type represents an imperative double-linked list.
data DoubleLinkedList a =  
  DoubleLinkedList { forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead :: IORef (Maybe (DoubleLinkedItem a)),
                     forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail :: IORef (Maybe (DoubleLinkedItem a)), 
                     forall a. DoubleLinkedList a -> IORef Int
listSize :: IORef Int }

-- | Test whether the list is empty.
listNull :: DoubleLinkedList a -> IO Bool
listNull :: forall a. DoubleLinkedList a -> IO Bool
listNull DoubleLinkedList a
x =
  do Maybe (DoubleLinkedItem a)
head <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) 
     case Maybe (DoubleLinkedItem a)
head of
       Maybe (DoubleLinkedItem a)
Nothing -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True
       Just DoubleLinkedItem a
_  -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
    
-- | Return the number of elements in the list.
listCount :: DoubleLinkedList a -> IO Int
listCount :: forall a. DoubleLinkedList a -> IO Int
listCount DoubleLinkedList a
x = forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x)

-- | Create a new list.
newList :: IO (DoubleLinkedList a)
newList :: forall a. IO (DoubleLinkedList a)
newList =
  do IORef (Maybe (DoubleLinkedItem a))
head <- forall a. a -> IO (IORef a)
newIORef forall a. Maybe a
Nothing 
     IORef (Maybe (DoubleLinkedItem a))
tail <- forall a. a -> IO (IORef a)
newIORef forall a. Maybe a
Nothing
     IORef Int
size <- forall a. a -> IO (IORef a)
newIORef Int
0
     forall (m :: * -> *) a. Monad m => a -> m a
return DoubleLinkedList { listHead :: IORef (Maybe (DoubleLinkedItem a))
listHead = IORef (Maybe (DoubleLinkedItem a))
head,
                               listTail :: IORef (Maybe (DoubleLinkedItem a))
listTail = IORef (Maybe (DoubleLinkedItem a))
tail,
                               listSize :: IORef Int
listSize = IORef Int
size }

-- | Insert a new element in the beginning.
listInsertFirst :: DoubleLinkedList a -> a -> IO ()
listInsertFirst :: forall a. DoubleLinkedList a -> a -> IO ()
listInsertFirst DoubleLinkedList a
x a
v =
  do Int
size <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x)
     let size' :: Int
size' = Int
size forall a. Num a => a -> a -> a
+ Int
1
     Int
size' seq :: forall a b. a -> b -> b
`seq` forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x) Int
size'
     Maybe (DoubleLinkedItem a)
head <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x)
     case Maybe (DoubleLinkedItem a)
head of
       Maybe (DoubleLinkedItem a)
Nothing ->
         do IORef (Maybe (DoubleLinkedItem a))
prev <- forall a. a -> IO (IORef a)
newIORef forall a. Maybe a
Nothing
            IORef (Maybe (DoubleLinkedItem a))
next <- forall a. a -> IO (IORef a)
newIORef forall a. Maybe a
Nothing
            let item :: Maybe (DoubleLinkedItem a)
item = forall a. a -> Maybe a
Just DoubleLinkedItem { itemVal :: a
itemVal = a
v, 
                                               itemPrev :: IORef (Maybe (DoubleLinkedItem a))
itemPrev = IORef (Maybe (DoubleLinkedItem a))
prev, 
                                               itemNext :: IORef (Maybe (DoubleLinkedItem a))
itemNext = IORef (Maybe (DoubleLinkedItem a))
next }
            forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
item
            forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
item
       Just DoubleLinkedItem a
h ->
         do IORef (Maybe (DoubleLinkedItem a))
prev <- forall a. a -> IO (IORef a)
newIORef forall a. Maybe a
Nothing
            IORef (Maybe (DoubleLinkedItem a))
next <- forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
head
            let item :: Maybe (DoubleLinkedItem a)
item = forall a. a -> Maybe a
Just DoubleLinkedItem { itemVal :: a
itemVal = a
v,
                                               itemPrev :: IORef (Maybe (DoubleLinkedItem a))
itemPrev = IORef (Maybe (DoubleLinkedItem a))
prev,
                                               itemNext :: IORef (Maybe (DoubleLinkedItem a))
itemNext = IORef (Maybe (DoubleLinkedItem a))
next }
            forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
h) Maybe (DoubleLinkedItem a)
item
            forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
item

-- | Add a new element to the end.
listAddLast :: DoubleLinkedList a -> a -> IO ()
listAddLast :: forall a. DoubleLinkedList a -> a -> IO ()
listAddLast DoubleLinkedList a
x a
v =
  do Int
size <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x)
     let size' :: Int
size' = Int
size forall a. Num a => a -> a -> a
+ Int
1
     Int
size' seq :: forall a b. a -> b -> b
`seq` forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x) Int
size'
     Maybe (DoubleLinkedItem a)
tail <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x)
     case Maybe (DoubleLinkedItem a)
tail of
       Maybe (DoubleLinkedItem a)
Nothing ->
         do IORef (Maybe (DoubleLinkedItem a))
prev <- forall a. a -> IO (IORef a)
newIORef forall a. Maybe a
Nothing
            IORef (Maybe (DoubleLinkedItem a))
next <- forall a. a -> IO (IORef a)
newIORef forall a. Maybe a
Nothing
            let item :: Maybe (DoubleLinkedItem a)
item = forall a. a -> Maybe a
Just DoubleLinkedItem { itemVal :: a
itemVal = a
v, 
                                               itemPrev :: IORef (Maybe (DoubleLinkedItem a))
itemPrev = IORef (Maybe (DoubleLinkedItem a))
prev, 
                                               itemNext :: IORef (Maybe (DoubleLinkedItem a))
itemNext = IORef (Maybe (DoubleLinkedItem a))
next }
            forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
item
            forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
item
       Just DoubleLinkedItem a
t ->
         do IORef (Maybe (DoubleLinkedItem a))
prev <- forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
tail
            IORef (Maybe (DoubleLinkedItem a))
next <- forall a. a -> IO (IORef a)
newIORef forall a. Maybe a
Nothing
            let item :: Maybe (DoubleLinkedItem a)
item = forall a. a -> Maybe a
Just DoubleLinkedItem { itemVal :: a
itemVal = a
v,
                                               itemPrev :: IORef (Maybe (DoubleLinkedItem a))
itemPrev = IORef (Maybe (DoubleLinkedItem a))
prev,
                                               itemNext :: IORef (Maybe (DoubleLinkedItem a))
itemNext = IORef (Maybe (DoubleLinkedItem a))
next }
            forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
t) Maybe (DoubleLinkedItem a)
item
            forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
item

-- | Remove the first element.
listRemoveFirst :: DoubleLinkedList a -> IO ()
listRemoveFirst :: forall a. DoubleLinkedList a -> IO ()
listRemoveFirst DoubleLinkedList a
x =
  do Maybe (DoubleLinkedItem a)
head <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) 
     case Maybe (DoubleLinkedItem a)
head of
       Maybe (DoubleLinkedItem a)
Nothing ->
         forall a. HasCallStack => [Char] -> a
error [Char]
"Empty list: listRemoveFirst"
       Just DoubleLinkedItem a
h ->
         do Int
size  <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x)
            let size' :: Int
size' = Int
size forall a. Num a => a -> a -> a
- Int
1
            Int
size' seq :: forall a b. a -> b -> b
`seq` forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x) Int
size'
            Maybe (DoubleLinkedItem a)
head' <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
h)
            case Maybe (DoubleLinkedItem a)
head' of
              Maybe (DoubleLinkedItem a)
Nothing ->
                do forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) forall a. Maybe a
Nothing
                   forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) forall a. Maybe a
Nothing
              Just DoubleLinkedItem a
h' ->
                do forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
h') forall a. Maybe a
Nothing
                   forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
head'

-- | Remove the last element.
listRemoveLast :: DoubleLinkedList a -> IO ()
listRemoveLast :: forall a. DoubleLinkedList a -> IO ()
listRemoveLast DoubleLinkedList a
x =
  do Maybe (DoubleLinkedItem a)
tail <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) 
     case Maybe (DoubleLinkedItem a)
tail of
       Maybe (DoubleLinkedItem a)
Nothing ->
         forall a. HasCallStack => [Char] -> a
error [Char]
"Empty list: listRemoveLast"
       Just DoubleLinkedItem a
t ->
         do Int
size  <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x)
            let size' :: Int
size' =  Int
size forall a. Num a => a -> a -> a
- Int
1
            Int
size' seq :: forall a b. a -> b -> b
`seq` forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x) Int
size'
            Maybe (DoubleLinkedItem a)
tail' <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
t)
            case Maybe (DoubleLinkedItem a)
tail' of
              Maybe (DoubleLinkedItem a)
Nothing ->
                do forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) forall a. Maybe a
Nothing
                   forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) forall a. Maybe a
Nothing
              Just DoubleLinkedItem a
t' ->
                do forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
t') forall a. Maybe a
Nothing
                   forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
tail'

-- | Return the first element.
listFirst :: DoubleLinkedList a -> IO a
listFirst :: forall a. DoubleLinkedList a -> IO a
listFirst DoubleLinkedList a
x =
  do Maybe (DoubleLinkedItem a)
head <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x)
     case Maybe (DoubleLinkedItem a)
head of
       Maybe (DoubleLinkedItem a)
Nothing ->
         forall a. HasCallStack => [Char] -> a
error [Char]
"Empty list: listFirst"
       Just DoubleLinkedItem a
h ->
         forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
h

-- | Return the last element.
listLast :: DoubleLinkedList a -> IO a
listLast :: forall a. DoubleLinkedList a -> IO a
listLast DoubleLinkedList a
x =
  do Maybe (DoubleLinkedItem a)
tail <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x)
     case Maybe (DoubleLinkedItem a)
tail of
       Maybe (DoubleLinkedItem a)
Nothing ->
         forall a. HasCallStack => [Char] -> a
error [Char]
"Empty list: listLast"
       Just DoubleLinkedItem a
t ->
         forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
t

-- | Remove the specified element from the list and return a flag
-- indicating whether the element was found and removed.
listRemove :: Eq a => DoubleLinkedList a -> a -> IO Bool
listRemove :: forall a. Eq a => DoubleLinkedList a -> a -> IO Bool
listRemove DoubleLinkedList a
x a
v = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Maybe a -> Bool
isJust forall a b. (a -> b) -> a -> b
$ forall a. DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
listRemoveBy DoubleLinkedList a
x (forall a. Eq a => a -> a -> Bool
== a
v)

-- | Remove an element satisfying the specified predicate and return
-- the element if found.
listRemoveBy :: DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
listRemoveBy :: forall a. DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
listRemoveBy DoubleLinkedList a
x a -> Bool
p = forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Maybe (DoubleLinkedItem a) -> IO (Maybe a)
loop
  where loop :: Maybe (DoubleLinkedItem a) -> IO (Maybe a)
loop Maybe (DoubleLinkedItem a)
item =
          case Maybe (DoubleLinkedItem a)
item of
            Maybe (DoubleLinkedItem a)
Nothing   -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
            Just DoubleLinkedItem a
item ->
              do let f :: Bool
f = a -> Bool
p (forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
item)
                 if Bool -> Bool
not Bool
f
                   then forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
item) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Maybe (DoubleLinkedItem a) -> IO (Maybe a)
loop
                   else do Int
size <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x)
                           Maybe (DoubleLinkedItem a)
prev <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
item)
                           Maybe (DoubleLinkedItem a)
next <- forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
item)
                           let size' :: Int
size' = Int
size forall a. Num a => a -> a -> a
- Int
1
                           Int
size' seq :: forall a b. a -> b -> b
`seq` forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x) Int
size'
                           case (Maybe (DoubleLinkedItem a)
prev, Maybe (DoubleLinkedItem a)
next) of
                             (Maybe (DoubleLinkedItem a)
Nothing, Maybe (DoubleLinkedItem a)
Nothing) ->
                               do forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) forall a. Maybe a
Nothing
                                  forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) forall a. Maybe a
Nothing
                             (Maybe (DoubleLinkedItem a)
Nothing, head' :: Maybe (DoubleLinkedItem a)
head'@(Just DoubleLinkedItem a
item')) ->
                               do forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
item') forall a. Maybe a
Nothing
                                  forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
head'
                             (tail' :: Maybe (DoubleLinkedItem a)
tail'@(Just DoubleLinkedItem a
item'), Maybe (DoubleLinkedItem a)
Nothing) ->
                               do forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
item') forall a. Maybe a
Nothing
                                  forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
tail'
                             (Just DoubleLinkedItem a
prev', Just DoubleLinkedItem a
next') ->
                               do forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
prev') (forall a. a -> Maybe a
Just DoubleLinkedItem a
next')
                                  forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
next') (forall a. a -> Maybe a
Just DoubleLinkedItem a
prev')
                           forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
item)

-- | Detect whether the specified element is contained in the list.
listContains :: Eq a => DoubleLinkedList a -> a -> IO Bool
listContains :: forall a. Eq a => DoubleLinkedList a -> a -> IO Bool
listContains DoubleLinkedList a
x a
v = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Maybe a -> Bool
isJust forall a b. (a -> b) -> a -> b
$ forall a. DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
listContainsBy DoubleLinkedList a
x (forall a. Eq a => a -> a -> Bool
== a
v)

-- | Detect whether an element satisfying the specified predicate is contained in the list.
listContainsBy :: DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
listContainsBy :: forall a. DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
listContainsBy DoubleLinkedList a
x a -> Bool
p = forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Maybe (DoubleLinkedItem a) -> IO (Maybe a)
loop
  where loop :: Maybe (DoubleLinkedItem a) -> IO (Maybe a)
loop Maybe (DoubleLinkedItem a)
item =
          case Maybe (DoubleLinkedItem a)
item of
            Maybe (DoubleLinkedItem a)
Nothing   -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
            Just DoubleLinkedItem a
item ->
              do let f :: Bool
f = a -> Bool
p (forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
item)
                 if Bool -> Bool
not Bool
f
                   then forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
item) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Maybe (DoubleLinkedItem a) -> IO (Maybe a)
loop
                   else forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just (forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
item)

-- | Clear the contents of the list.
clearList :: DoubleLinkedList a -> IO ()
clearList :: forall a. DoubleLinkedList a -> IO ()
clearList DoubleLinkedList a
q =
  do forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
q) forall a. Maybe a
Nothing
     forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
q) forall a. Maybe a
Nothing
     forall a. IORef a -> a -> IO ()
writeIORef (forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
q) Int
0

-- | Freeze the list and return its contents.
freezeList :: DoubleLinkedList a -> IO [a]
freezeList :: forall a. DoubleLinkedList a -> IO [a]
freezeList DoubleLinkedList a
x = forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall {a}. [a] -> Maybe (DoubleLinkedItem a) -> IO [a]
loop []
  where loop :: [a] -> Maybe (DoubleLinkedItem a) -> IO [a]
loop [a]
acc Maybe (DoubleLinkedItem a)
Nothing     = forall (m :: * -> *) a. Monad m => a -> m a
return [a]
acc
        loop [a]
acc (Just DoubleLinkedItem a
item) = forall a. IORef a -> IO a
readIORef (forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
item) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= [a] -> Maybe (DoubleLinkedItem a) -> IO [a]
loop (forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
item forall a. a -> [a] -> [a]
: [a]
acc)