-- | List type that supports O(1) amortized 'cons', 'snoc', 'uncons' and 'isEmpty'.
module General.Bilist(
    Bilist, cons, snoc, uncons, toList, isEmpty
    ) where

import Data.Semigroup
import Prelude


data Bilist a = Bilist [a] [a]

toList :: Bilist a -> [a]
toList :: forall a. Bilist a -> [a]
toList (Bilist [a]
as [a]
bs) = [a]
as forall a. [a] -> [a] -> [a]
++ forall a. [a] -> [a]
reverse [a]
bs

isEmpty :: Bilist a -> Bool
isEmpty :: forall a. Bilist a -> Bool
isEmpty (Bilist [a]
as [a]
bs) = forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
as Bool -> Bool -> Bool
&& forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
bs

instance Eq a => Eq (Bilist a) where
    Bilist a
a == :: Bilist a -> Bilist a -> Bool
== Bilist a
b = forall a. Bilist a -> [a]
toList Bilist a
a forall a. Eq a => a -> a -> Bool
== forall a. Bilist a -> [a]
toList Bilist a
b

instance Semigroup (Bilist a) where
    Bilist a
a <> :: Bilist a -> Bilist a -> Bilist a
<> Bilist a
b = forall a. [a] -> [a] -> Bilist a
Bilist (forall a. Bilist a -> [a]
toList Bilist a
a forall a. [a] -> [a] -> [a]
++ forall a. Bilist a -> [a]
toList Bilist a
b) []

instance Monoid (Bilist a) where
    mempty :: Bilist a
mempty = forall a. [a] -> [a] -> Bilist a
Bilist [] []
    mappend :: Bilist a -> Bilist a -> Bilist a
mappend = forall a. Semigroup a => a -> a -> a
(<>)

cons :: a -> Bilist a -> Bilist a
cons :: forall a. a -> Bilist a -> Bilist a
cons a
x (Bilist [a]
as [a]
bs) = forall a. [a] -> [a] -> Bilist a
Bilist (a
xforall a. a -> [a] -> [a]
:[a]
as) [a]
bs

snoc :: Bilist a -> a -> Bilist a
snoc :: forall a. Bilist a -> a -> Bilist a
snoc (Bilist [a]
as [a]
bs) a
x = forall a. [a] -> [a] -> Bilist a
Bilist [a]
as (a
xforall a. a -> [a] -> [a]
:[a]
bs)

uncons :: Bilist a -> Maybe (a, Bilist a)
uncons :: forall a. Bilist a -> Maybe (a, Bilist a)
uncons (Bilist [] []) = forall a. Maybe a
Nothing
uncons (Bilist (a
a:[a]
as) [a]
bs) = forall a. a -> Maybe a
Just (a
a, forall a. [a] -> [a] -> Bilist a
Bilist [a]
as [a]
bs)
uncons (Bilist [] [a]
bs) = forall a. Bilist a -> Maybe (a, Bilist a)
uncons forall a b. (a -> b) -> a -> b
$ forall a. [a] -> [a] -> Bilist a
Bilist (forall a. [a] -> [a]
reverse [a]
bs) []