-- |
-- Module      : Foundation.List.DList
-- License     : BSD-style
-- Maintainer  : Nicolas Di Prima <nicolas@primetype.co.uk>
-- Stability   : statble
-- Portability : portable
--
-- Data structure for optimised operations (append, cons, snoc) on list
--
module Foundation.List.DList
    ( DList
    ) where

import Foundation.Internal.Base
import Foundation.Collection
import Foundation.Class.Bifunctor

newtype DList a = DList { unDList :: [a] -> [a] }
  deriving (Typeable)

instance Eq a => Eq (DList a) where
    (==) dl1 dl2 = (==) (toList dl1) (toList dl2)

instance Ord a => Ord (DList a) where
    compare dl1 dl2 = compare (toList dl1) (toList dl2)

instance Show a => Show (DList a) where
    show = show . toList

instance IsList (DList a) where
    type Item (DList a) = a
    fromList = DList . (<>)
    toList = flip unDList []

instance Monoid (DList a) where
    mempty = DList id
    mappend dl1 dl2 = DList $ unDList dl1 . unDList dl2

instance Functor DList where
    fmap f = foldr (cons . f) mempty

instance Applicative DList where
    pure = singleton
    (<*>) m1 m2 = m1 >>= \x1 -> m2 >>= \x2 -> return (x1 x2)

instance Monad DList where
    (>>=) m k = foldr (mappend . k) mempty m
    return = singleton

type instance Element (DList a) = a

instance Foldable (DList a) where
    foldr f b = foldr f b . toList
    foldl f b = foldl f b . toList
    foldl' f b = foldl' f b . toList

instance Collection (DList a) where
    null = null . toList
    length = length . toList
    elem a = elem a . toList
    maximum = maximum . nonEmpty_ . toList
    minimum = minimum . nonEmpty_ . toList
    all f = all f . toList
    any f = any f . toList

instance Sequential (DList a) where
    take n = fromList . take n . toList
    revTake n = fromList . revTake n . toList
    drop n = fromList . drop n . toList
    revDrop n = fromList . revDrop n . toList
    splitAt n = bimap fromList fromList . splitAt n . toList
    splitOn f = fmap fromList . splitOn f . toList
    break f = bimap fromList fromList . break f . toList
    breakElem e = bimap fromList fromList . breakElem e . toList
    intersperse e = fromList . intersperse e . toList
    intercalate e = intercalate e . toList
    span f = bimap fromList fromList . span f . toList
    filter f = fromList . filter f . toList
    partition f = bimap fromList fromList . partition f . toList
    reverse = fromList . reverse . toList
    uncons dl = second fromList <$> uncons (toList dl)
    unsnoc dl = first fromList <$> unsnoc (toList dl)
    cons e dl = DList $ (:) e . unDList dl
    snoc dl e = DList $ unDList dl . (:) e
    find f = find f . toList
    sortBy comp = fromList . sortBy comp . toList
    singleton = DList . (:)
    replicate n e = fromList $ replicate n e