module Data.Rsv.RList (
RList
, empty
, isEmpty
, toList
, insert
, Delete
, sInsert
, SDelete
) where
import Control.Arrow (first)
import Control.Lens (makeLensesFor, (&), (%~), (+~), (%%~))
import Control.Monad.Trans.State.Strict (StateT, state)
data RList a = RList {
nextIndex :: Int,
subList :: [(Int, a)]
}
makeLensesFor ((\x -> (x, x ++ "_")) <$> ["nextIndex", "subList"]) ''RList
empty :: RList a
empty = RList { nextIndex = 0, subList = [] }
isEmpty :: RList a -> Bool
isEmpty sl = null (subList sl)
toList :: RList a -> [a]
toList l = snd <$> reverse (subList l)
type Delete a = RList a -> (Maybe a, RList a)
insert :: a -> RList a -> (Delete a, RList a)
insert v sl = let idx = nextIndex sl in
(deleteAt idx, sl & nextIndex_ +~ 1 & subList_ %~ ((idx, v) :))
deleteAt :: Int -> RList a -> (Maybe a, RList a)
deleteAt idx l = l & subList_ %%~ deleteAt_ idx
deleteAt_ :: Int -> [(Int, a)] -> (Maybe a, [(Int, a)])
deleteAt_ _ [] = (Nothing, [])
deleteAt_ idx (h:t) = if fst h == idx
then (Just (snd h), t)
else (h :) <$> deleteAt_ idx t
type SDelete a m = StateT (RList a) m (Maybe a)
sInsert :: Monad m => a -> StateT (RList a) m (SDelete a m)
sInsert v = state $ first state . insert v