-- |
-- 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 { DoubleLinkedItem a -> a
itemVal  :: a,
                     DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev :: IORef (Maybe (DoubleLinkedItem 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 { DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead :: IORef (Maybe (DoubleLinkedItem a)),
                     DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail :: IORef (Maybe (DoubleLinkedItem a)), 
                     DoubleLinkedList a -> IORef Int
listSize :: IORef Int }

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

-- | Create a new list.
newList :: IO (DoubleLinkedList a)
newList :: IO (DoubleLinkedList a)
newList =
  do IORef (Maybe (DoubleLinkedItem a))
head <- Maybe (DoubleLinkedItem a)
-> IO (IORef (Maybe (DoubleLinkedItem a)))
forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing 
     IORef (Maybe (DoubleLinkedItem a))
tail <- Maybe (DoubleLinkedItem a)
-> IO (IORef (Maybe (DoubleLinkedItem a)))
forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
     IORef Int
size <- Int -> IO (IORef Int)
forall a. a -> IO (IORef a)
newIORef Int
0
     DoubleLinkedList a -> IO (DoubleLinkedList a)
forall (m :: * -> *) a. Monad m => a -> m a
return DoubleLinkedList :: forall a.
IORef (Maybe (DoubleLinkedItem a))
-> IORef (Maybe (DoubleLinkedItem a))
-> IORef Int
-> DoubleLinkedList a
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 :: DoubleLinkedList a -> a -> IO ()
listInsertFirst DoubleLinkedList a
x a
v =
  do Int
size <- IORef Int -> IO Int
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef Int
forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x)
     let size' :: Int
size' = Int
size Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
     Int
size' Int -> IO () -> IO ()
`seq` IORef Int -> Int -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef Int
forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x) Int
size'
     Maybe (DoubleLinkedItem a)
head <- IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
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 <- Maybe (DoubleLinkedItem a)
-> IO (IORef (Maybe (DoubleLinkedItem a)))
forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
            IORef (Maybe (DoubleLinkedItem a))
next <- Maybe (DoubleLinkedItem a)
-> IO (IORef (Maybe (DoubleLinkedItem a)))
forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
            let item :: Maybe (DoubleLinkedItem a)
item = DoubleLinkedItem a -> Maybe (DoubleLinkedItem a)
forall a. a -> Maybe a
Just DoubleLinkedItem :: forall a.
a
-> IORef (Maybe (DoubleLinkedItem a))
-> IORef (Maybe (DoubleLinkedItem a))
-> DoubleLinkedItem a
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 }
            IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
item
            IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
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 <- Maybe (DoubleLinkedItem a)
-> IO (IORef (Maybe (DoubleLinkedItem a)))
forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
            IORef (Maybe (DoubleLinkedItem a))
next <- Maybe (DoubleLinkedItem a)
-> IO (IORef (Maybe (DoubleLinkedItem a)))
forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
head
            let item :: Maybe (DoubleLinkedItem a)
item = DoubleLinkedItem a -> Maybe (DoubleLinkedItem a)
forall a. a -> Maybe a
Just DoubleLinkedItem :: forall a.
a
-> IORef (Maybe (DoubleLinkedItem a))
-> IORef (Maybe (DoubleLinkedItem a))
-> DoubleLinkedItem a
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 }
            IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
h) Maybe (DoubleLinkedItem a)
item
            IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
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 :: DoubleLinkedList a -> a -> IO ()
listAddLast DoubleLinkedList a
x a
v =
  do Int
size <- IORef Int -> IO Int
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef Int
forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x)
     let size' :: Int
size' = Int
size Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
     Int
size' Int -> IO () -> IO ()
`seq` IORef Int -> Int -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef Int
forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x) Int
size'
     Maybe (DoubleLinkedItem a)
tail <- IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
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 <- Maybe (DoubleLinkedItem a)
-> IO (IORef (Maybe (DoubleLinkedItem a)))
forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
            IORef (Maybe (DoubleLinkedItem a))
next <- Maybe (DoubleLinkedItem a)
-> IO (IORef (Maybe (DoubleLinkedItem a)))
forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
            let item :: Maybe (DoubleLinkedItem a)
item = DoubleLinkedItem a -> Maybe (DoubleLinkedItem a)
forall a. a -> Maybe a
Just DoubleLinkedItem :: forall a.
a
-> IORef (Maybe (DoubleLinkedItem a))
-> IORef (Maybe (DoubleLinkedItem a))
-> DoubleLinkedItem a
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 }
            IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
item
            IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
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 <- Maybe (DoubleLinkedItem a)
-> IO (IORef (Maybe (DoubleLinkedItem a)))
forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
tail
            IORef (Maybe (DoubleLinkedItem a))
next <- Maybe (DoubleLinkedItem a)
-> IO (IORef (Maybe (DoubleLinkedItem a)))
forall a. a -> IO (IORef a)
newIORef Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
            let item :: Maybe (DoubleLinkedItem a)
item = DoubleLinkedItem a -> Maybe (DoubleLinkedItem a)
forall a. a -> Maybe a
Just DoubleLinkedItem :: forall a.
a
-> IORef (Maybe (DoubleLinkedItem a))
-> IORef (Maybe (DoubleLinkedItem a))
-> DoubleLinkedItem a
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 }
            IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
t) Maybe (DoubleLinkedItem a)
item
            IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
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 :: DoubleLinkedList a -> IO ()
listRemoveFirst DoubleLinkedList a
x =
  do Maybe (DoubleLinkedItem a)
head <- IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) 
     case Maybe (DoubleLinkedItem a)
head of
       Maybe (DoubleLinkedItem a)
Nothing ->
         [Char] -> IO ()
forall a. HasCallStack => [Char] -> a
error [Char]
"Empty list: listRemoveFirst"
       Just DoubleLinkedItem a
h ->
         do Int
size  <- IORef Int -> IO Int
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef Int
forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x)
            let size' :: Int
size' = Int
size Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
            Int
size' Int -> IO () -> IO ()
`seq` IORef Int -> Int -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef Int
forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x) Int
size'
            Maybe (DoubleLinkedItem a)
head' <- IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
h)
            case Maybe (DoubleLinkedItem a)
head' of
              Maybe (DoubleLinkedItem a)
Nothing ->
                do IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
                   IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
              Just DoubleLinkedItem a
h' ->
                do IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
h') Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
                   IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
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 :: DoubleLinkedList a -> IO ()
listRemoveLast DoubleLinkedList a
x =
  do Maybe (DoubleLinkedItem a)
tail <- IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) 
     case Maybe (DoubleLinkedItem a)
tail of
       Maybe (DoubleLinkedItem a)
Nothing ->
         [Char] -> IO ()
forall a. HasCallStack => [Char] -> a
error [Char]
"Empty list: listRemoveLast"
       Just DoubleLinkedItem a
t ->
         do Int
size  <- IORef Int -> IO Int
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef Int
forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x)
            let size' :: Int
size' =  Int
size Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
            Int
size' Int -> IO () -> IO ()
`seq` IORef Int -> Int -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef Int
forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x) Int
size'
            Maybe (DoubleLinkedItem a)
tail' <- IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
t)
            case Maybe (DoubleLinkedItem a)
tail' of
              Maybe (DoubleLinkedItem a)
Nothing ->
                do IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
                   IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
              Just DoubleLinkedItem a
t' ->
                do IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
t') Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
                   IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
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 :: DoubleLinkedList a -> IO a
listFirst DoubleLinkedList a
x =
  do Maybe (DoubleLinkedItem a)
head <- IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x)
     case Maybe (DoubleLinkedItem a)
head of
       Maybe (DoubleLinkedItem a)
Nothing ->
         [Char] -> IO a
forall a. HasCallStack => [Char] -> a
error [Char]
"Empty list: listFirst"
       Just DoubleLinkedItem a
h ->
         a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> IO a) -> a -> IO a
forall a b. (a -> b) -> a -> b
$ DoubleLinkedItem a -> a
forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
h

-- | Return the last element.
listLast :: DoubleLinkedList a -> IO a
listLast :: DoubleLinkedList a -> IO a
listLast DoubleLinkedList a
x =
  do Maybe (DoubleLinkedItem a)
tail <- IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x)
     case Maybe (DoubleLinkedItem a)
tail of
       Maybe (DoubleLinkedItem a)
Nothing ->
         [Char] -> IO a
forall a. HasCallStack => [Char] -> a
error [Char]
"Empty list: listLast"
       Just DoubleLinkedItem a
t ->
         a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> IO a) -> a -> IO a
forall a b. (a -> b) -> a -> b
$ DoubleLinkedItem a -> a
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 :: DoubleLinkedList a -> a -> IO Bool
listRemove DoubleLinkedList a
x a
v = (Maybe a -> Bool) -> IO (Maybe a) -> IO Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Maybe a -> Bool
forall a. Maybe a -> Bool
isJust (IO (Maybe a) -> IO Bool) -> IO (Maybe a) -> IO Bool
forall a b. (a -> b) -> a -> b
$ DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
forall a. DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
listRemoveBy DoubleLinkedList a
x (a -> a -> Bool
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 :: DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
listRemoveBy DoubleLinkedList a
x a -> Bool
p = IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) IO (Maybe (DoubleLinkedItem a))
-> (Maybe (DoubleLinkedItem a) -> IO (Maybe a)) -> IO (Maybe a)
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   -> Maybe a -> IO (Maybe a)
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing
            Just DoubleLinkedItem a
item ->
              do let f :: Bool
f = a -> Bool
p (DoubleLinkedItem a -> a
forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
item)
                 if Bool -> Bool
not Bool
f
                   then IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
item) IO (Maybe (DoubleLinkedItem a))
-> (Maybe (DoubleLinkedItem a) -> IO (Maybe a)) -> IO (Maybe a)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Maybe (DoubleLinkedItem a) -> IO (Maybe a)
loop
                   else do Int
size <- IORef Int -> IO Int
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef Int
forall a. DoubleLinkedList a -> IORef Int
listSize DoubleLinkedList a
x)
                           Maybe (DoubleLinkedItem a)
prev <- IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
item)
                           Maybe (DoubleLinkedItem a)
next <- IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
item)
                           let size' :: Int
size' = Int
size Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
                           Int
size' Int -> IO () -> IO ()
`seq` IORef Int -> Int -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef Int
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 IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
                                  IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
                             (Maybe (DoubleLinkedItem a)
Nothing, head' :: Maybe (DoubleLinkedItem a)
head'@(Just DoubleLinkedItem a
item')) ->
                               do IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
item') Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
                                  IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
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 IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
item') Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
                                  IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
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 IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
prev') (DoubleLinkedItem a -> Maybe (DoubleLinkedItem a)
forall a. a -> Maybe a
Just DoubleLinkedItem a
next')
                                  IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
next') (DoubleLinkedItem a -> Maybe (DoubleLinkedItem a)
forall a. a -> Maybe a
Just DoubleLinkedItem a
prev')
                           Maybe a -> IO (Maybe a)
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$ DoubleLinkedItem a -> a
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 :: DoubleLinkedList a -> a -> IO Bool
listContains DoubleLinkedList a
x a
v = (Maybe a -> Bool) -> IO (Maybe a) -> IO Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Maybe a -> Bool
forall a. Maybe a -> Bool
isJust (IO (Maybe a) -> IO Bool) -> IO (Maybe a) -> IO Bool
forall a b. (a -> b) -> a -> b
$ DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
forall a. DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
listContainsBy DoubleLinkedList a
x (a -> a -> Bool
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 :: DoubleLinkedList a -> (a -> Bool) -> IO (Maybe a)
listContainsBy DoubleLinkedList a
x a -> Bool
p = IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
x) IO (Maybe (DoubleLinkedItem a))
-> (Maybe (DoubleLinkedItem a) -> IO (Maybe a)) -> IO (Maybe a)
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   -> Maybe a -> IO (Maybe a)
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing
            Just DoubleLinkedItem a
item ->
              do let f :: Bool
f = a -> Bool
p (DoubleLinkedItem a -> a
forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
item)
                 if Bool -> Bool
not Bool
f
                   then IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemNext DoubleLinkedItem a
item) IO (Maybe (DoubleLinkedItem a))
-> (Maybe (DoubleLinkedItem a) -> IO (Maybe a)) -> IO (Maybe a)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Maybe (DoubleLinkedItem a) -> IO (Maybe a)
loop
                   else Maybe a -> IO (Maybe a)
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe a -> IO (Maybe a)) -> Maybe a -> IO (Maybe a)
forall a b. (a -> b) -> a -> b
$ a -> Maybe a
forall a. a -> Maybe a
Just (DoubleLinkedItem a -> a
forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
item)

-- | Clear the contents of the list.
clearList :: DoubleLinkedList a -> IO ()
clearList :: DoubleLinkedList a -> IO ()
clearList DoubleLinkedList a
q =
  do IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listHead DoubleLinkedList a
q) Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
     IORef (Maybe (DoubleLinkedItem a))
-> Maybe (DoubleLinkedItem a) -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
q) Maybe (DoubleLinkedItem a)
forall a. Maybe a
Nothing
     IORef Int -> Int -> IO ()
forall a. IORef a -> a -> IO ()
writeIORef (DoubleLinkedList a -> IORef Int
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 :: DoubleLinkedList a -> IO [a]
freezeList DoubleLinkedList a
x = IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedList a -> IORef (Maybe (DoubleLinkedItem a))
listTail DoubleLinkedList a
x) IO (Maybe (DoubleLinkedItem a))
-> (Maybe (DoubleLinkedItem a) -> IO [a]) -> IO [a]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= [a] -> Maybe (DoubleLinkedItem a) -> IO [a]
forall a. [a] -> Maybe (DoubleLinkedItem a) -> IO [a]
loop []
  where loop :: [a] -> Maybe (DoubleLinkedItem a) -> IO [a]
loop [a]
acc Maybe (DoubleLinkedItem a)
Nothing     = [a] -> IO [a]
forall (m :: * -> *) a. Monad m => a -> m a
return [a]
acc
        loop [a]
acc (Just DoubleLinkedItem a
item) = IORef (Maybe (DoubleLinkedItem a))
-> IO (Maybe (DoubleLinkedItem a))
forall a. IORef a -> IO a
readIORef (DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
forall a. DoubleLinkedItem a -> IORef (Maybe (DoubleLinkedItem a))
itemPrev DoubleLinkedItem a
item) IO (Maybe (DoubleLinkedItem a))
-> (Maybe (DoubleLinkedItem a) -> IO [a]) -> IO [a]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= [a] -> Maybe (DoubleLinkedItem a) -> IO [a]
loop (DoubleLinkedItem a -> a
forall a. DoubleLinkedItem a -> a
itemVal DoubleLinkedItem a
item a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
acc)