content: {-# LANGUAGE DeriveTraversable #-}
  {-# LANGUAGE TypeFamilies #-}
  {-|
     Util: A list with a O(1) size function
   -}
  module Data.Equality.Utils.SizedList where
  
  import qualified Data.List
  import GHC.Exts
  import Data.Foldable
  
  -- | A list with O(1) size access and O(1) conversion to normal list
  data SList a = SList ![a] {-# UNPACK #-} !Int
    deriving Traversable
  
  instance Semigroup (SList a) where
    (<>) (SList a i) (SList b j) = SList (a <> b) (i+j)
    {-# INLINE (<>) #-}
  
  instance Monoid (SList a) where
    mempty = SList mempty 0
    {-# INLINE mempty #-}
  
  instance Functor SList where
    fmap f (SList a i) = SList (fmap f a) i
    {-# INLINE fmap #-}
  
  instance Foldable SList where
    fold       ( SList l _) = fold l
    foldMap f  ( SList l _) = foldMap f l
    foldMap' f ( SList l _) = foldMap' f l
    foldr f b  ( SList l _) = foldr f b l
    foldr' f b ( SList l _) = foldr' f b l
    foldl f b  ( SList l _) = foldl f b l
    foldl' f b ( SList l _) = foldl' f b l
    foldr1 f   ( SList l _) = foldr1 f l
    foldl1 f   ( SList l _) = foldl1 f l
    toList     ( SList l _) = l
    null       ( SList l _) = Data.List.null l
    length     ( SList _ i) = i
    elem x     ( SList l _) = x `elem` l
    maximum    ( SList l _) = maximum l
    minimum    ( SList l _) = minimum l
    sum        ( SList l _) = sum l
    product    ( SList l _) = product l
  
  instance IsList (SList a) where
    type Item (SList a) = a
    fromList l          = SList l (length l)
    fromListN i l       = SList l i
    toList (SList l _)  = l
  
  -- | Prepend an item to the list in O(1)
  (|:) :: a -> SList a -> SList a
  (|:) a (SList l i) = SList (a:l) (i+1)
  {-# INLINE (|:) #-}
  
  -- | Make a normal list from the sized list in O(1)
  toListSL :: SList a -> [a]
  toListSL (SList l _) = l
  {-# INLINE toListSL #-}
  
  -- | Get the size of the list in O(1)
  sizeSL :: SList a -> Int
  sizeSL (SList _ i) = i
  {-# INLINE sizeSL #-}
  