{-# 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 Functor SList
Foldable SList
Functor SList
-> Foldable SList
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> SList a -> f (SList b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    SList (f a) -> f (SList a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> SList a -> m (SList b))
-> (forall (m :: * -> *) a. Monad m => SList (m a) -> m (SList a))
-> Traversable SList
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => SList (m a) -> m (SList a)
forall (f :: * -> *) a. Applicative f => SList (f a) -> f (SList a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> SList a -> m (SList b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> SList a -> f (SList b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> SList a -> f (SList b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> SList a -> f (SList b)
$csequenceA :: forall (f :: * -> *) a. Applicative f => SList (f a) -> f (SList a)
sequenceA :: forall (f :: * -> *) a. Applicative f => SList (f a) -> f (SList a)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> SList a -> m (SList b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> SList a -> m (SList b)
$csequence :: forall (m :: * -> *) a. Monad m => SList (m a) -> m (SList a)
sequence :: forall (m :: * -> *) a. Monad m => SList (m a) -> m (SList a)
Traversable

instance Semigroup (SList a) where
  <> :: SList a -> SList a -> SList a
(<>) (SList [a]
a Int
i) (SList [a]
b Int
j) = [a] -> Int -> SList a
forall a. [a] -> Int -> SList a
SList ([a]
a [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> [a]
b) (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
j)
  {-# INLINE (<>) #-}

instance Monoid (SList a) where
  mempty :: SList a
mempty = [a] -> Int -> SList a
forall a. [a] -> Int -> SList a
SList [a]
forall a. Monoid a => a
mempty Int
0
  {-# INLINE mempty #-}

instance Functor SList where
  fmap :: forall a b. (a -> b) -> SList a -> SList b
fmap a -> b
f (SList [a]
a Int
i) = [b] -> Int -> SList b
forall a. [a] -> Int -> SList a
SList ((a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f [a]
a) Int
i
  {-# INLINE fmap #-}

instance Foldable SList where
  fold :: forall m. Monoid m => SList m -> m
fold       ( SList [m]
l Int
_) = [m] -> m
forall m. Monoid m => [m] -> m
forall (t :: * -> *) m. (Foldable t, Monoid m) => t m -> m
fold [m]
l
  foldMap :: forall m a. Monoid m => (a -> m) -> SList a -> m
foldMap a -> m
f  ( SList [a]
l Int
_) = (a -> m) -> [a] -> m
forall m a. Monoid m => (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f [a]
l
  foldMap' :: forall m a. Monoid m => (a -> m) -> SList a -> m
foldMap' a -> m
f ( SList [a]
l Int
_) = (a -> m) -> [a] -> m
forall m a. Monoid m => (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap' a -> m
f [a]
l
  foldr :: forall a b. (a -> b -> b) -> b -> SList a -> b
foldr a -> b -> b
f b
b  ( SList [a]
l Int
_) = (a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
b [a]
l
  foldr' :: forall a b. (a -> b -> b) -> b -> SList a -> b
foldr' a -> b -> b
f b
b ( SList [a]
l Int
_) = (a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' a -> b -> b
f b
b [a]
l
  foldl :: forall b a. (b -> a -> b) -> b -> SList a -> b
foldl b -> a -> b
f b
b  ( SList [a]
l Int
_) = (b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl b -> a -> b
f b
b [a]
l
  foldl' :: forall b a. (b -> a -> b) -> b -> SList a -> b
foldl' b -> a -> b
f b
b ( SList [a]
l Int
_) = (b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
f b
b [a]
l
  foldr1 :: forall a. (a -> a -> a) -> SList a -> a
foldr1 a -> a -> a
f   ( SList [a]
l Int
_) = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldr1 a -> a -> a
f [a]
l
  foldl1 :: forall a. (a -> a -> a) -> SList a -> a
foldl1 a -> a -> a
f   ( SList [a]
l Int
_) = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldl1 a -> a -> a
f [a]
l
  toList :: forall a. SList a -> [a]
toList     ( SList [a]
l Int
_) = [a]
l
  null :: forall a. SList a -> Bool
null       ( SList [a]
l Int
_) = [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Data.List.null [a]
l
  length :: forall a. SList a -> Int
length     ( SList [a]
_ Int
i) = Int
i
  elem :: forall a. Eq a => a -> SList a -> Bool
elem a
x     ( SList [a]
l Int
_) = a
x a -> [a] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
l
  maximum :: forall a. Ord a => SList a -> a
maximum    ( SList [a]
l Int
_) = [a] -> a
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum [a]
l
  minimum :: forall a. Ord a => SList a -> a
minimum    ( SList [a]
l Int
_) = [a] -> a
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [a]
l
  sum :: forall a. Num a => SList a -> a
sum        ( SList [a]
l Int
_) = [a] -> a
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [a]
l
  product :: forall a. Num a => SList a -> a
product    ( SList [a]
l Int
_) = [a] -> a
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product [a]
l

instance IsList (SList a) where
  type Item (SList a) = a
  fromList :: [Item (SList a)] -> SList a
fromList [Item (SList a)]
l          = [a] -> Int -> SList a
forall a. [a] -> Int -> SList a
SList [a]
[Item (SList a)]
l ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
[Item (SList a)]
l)
  fromListN :: Int -> [Item (SList a)] -> SList a
fromListN Int
i [Item (SList a)]
l       = [a] -> Int -> SList a
forall a. [a] -> Int -> SList a
SList [a]
[Item (SList a)]
l Int
i
  toList :: SList a -> [Item (SList a)]
toList (SList [a]
l Int
_)  = [a]
[Item (SList a)]
l

-- | Prepend an item to the list in O(1)
(|:) :: a -> SList a -> SList a
|: :: forall a. a -> SList a -> SList a
(|:) a
a (SList [a]
l Int
i) = [a] -> Int -> SList a
forall a. [a] -> Int -> SList a
SList (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
l) (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
{-# INLINE (|:) #-}

-- | Make a normal list from the sized list in O(1)
toListSL :: SList a -> [a]
toListSL :: forall a. SList a -> [a]
toListSL (SList [a]
l Int
_) = [a]
l
{-# INLINE toListSL #-}

-- | Get the size of the list in O(1)
sizeSL :: SList a -> Int
sizeSL :: forall a. SList a -> Int
sizeSL (SList [a]
_ Int
i) = Int
i
{-# INLINE sizeSL #-}