{-# LANGUAGE DeriveDataTypeable, DeriveGeneric #-}
{- |
Module      :  ./Common/Lib/SizedList.hs
Description :  lists with their size similar to Data.Edison.Seq.SizedSeq
Copyright   :  C. Maeder DFKI Bremen 2008
License     :  GPLv2 or higher, see LICENSE.txt

Maintainer  :  Christian.Maeder@dfki.de
Stability   :  experimental
Portability :  portable

a list plus its length for a more efficient history implementation.
Parts of the implementation is stolen from Data.Edison.Seq.SizedSeq
-}

module Common.Lib.SizedList
  ( SizedList
  , fromList
  , toList
  , empty
  , singleton
  , cons
  , append
  , head
  , tail
  , null
  , size
  , reverse
  , take
  , drop
  , map
  ) where

import Prelude hiding (null, head, tail, reverse, take, drop, map)

import Data.Data
import qualified Data.List as List

import GHC.Generics (Generic)

data SizedList a = N !Int [a] deriving (Int -> SizedList a -> ShowS
[SizedList a] -> ShowS
SizedList a -> String
(Int -> SizedList a -> ShowS)
-> (SizedList a -> String)
-> ([SizedList a] -> ShowS)
-> Show (SizedList a)
forall a. Show a => Int -> SizedList a -> ShowS
forall a. Show a => [SizedList a] -> ShowS
forall a. Show a => SizedList a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [SizedList a] -> ShowS
$cshowList :: forall a. Show a => [SizedList a] -> ShowS
show :: SizedList a -> String
$cshow :: forall a. Show a => SizedList a -> String
showsPrec :: Int -> SizedList a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> SizedList a -> ShowS
Show, SizedList a -> SizedList a -> Bool
(SizedList a -> SizedList a -> Bool)
-> (SizedList a -> SizedList a -> Bool) -> Eq (SizedList a)
forall a. Eq a => SizedList a -> SizedList a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: SizedList a -> SizedList a -> Bool
$c/= :: forall a. Eq a => SizedList a -> SizedList a -> Bool
== :: SizedList a -> SizedList a -> Bool
$c== :: forall a. Eq a => SizedList a -> SizedList a -> Bool
Eq, Eq (SizedList a)
Eq (SizedList a) =>
(SizedList a -> SizedList a -> Ordering)
-> (SizedList a -> SizedList a -> Bool)
-> (SizedList a -> SizedList a -> Bool)
-> (SizedList a -> SizedList a -> Bool)
-> (SizedList a -> SizedList a -> Bool)
-> (SizedList a -> SizedList a -> SizedList a)
-> (SizedList a -> SizedList a -> SizedList a)
-> Ord (SizedList a)
SizedList a -> SizedList a -> Bool
SizedList a -> SizedList a -> Ordering
SizedList a -> SizedList a -> SizedList a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (SizedList a)
forall a. Ord a => SizedList a -> SizedList a -> Bool
forall a. Ord a => SizedList a -> SizedList a -> Ordering
forall a. Ord a => SizedList a -> SizedList a -> SizedList a
min :: SizedList a -> SizedList a -> SizedList a
$cmin :: forall a. Ord a => SizedList a -> SizedList a -> SizedList a
max :: SizedList a -> SizedList a -> SizedList a
$cmax :: forall a. Ord a => SizedList a -> SizedList a -> SizedList a
>= :: SizedList a -> SizedList a -> Bool
$c>= :: forall a. Ord a => SizedList a -> SizedList a -> Bool
> :: SizedList a -> SizedList a -> Bool
$c> :: forall a. Ord a => SizedList a -> SizedList a -> Bool
<= :: SizedList a -> SizedList a -> Bool
$c<= :: forall a. Ord a => SizedList a -> SizedList a -> Bool
< :: SizedList a -> SizedList a -> Bool
$c< :: forall a. Ord a => SizedList a -> SizedList a -> Bool
compare :: SizedList a -> SizedList a -> Ordering
$ccompare :: forall a. Ord a => SizedList a -> SizedList a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (SizedList a)
Ord, Typeable, Typeable (SizedList a)
Constr
DataType
Typeable (SizedList a) =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> SizedList a -> c (SizedList a))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (SizedList a))
-> (SizedList a -> Constr)
-> (SizedList a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (SizedList a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (SizedList a)))
-> ((forall b. Data b => b -> b) -> SizedList a -> SizedList a)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> SizedList a -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> SizedList a -> r)
-> (forall u. (forall d. Data d => d -> u) -> SizedList a -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> SizedList a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a))
-> Data (SizedList a)
SizedList a -> Constr
SizedList a -> DataType
(forall d. Data d => c (t d)) -> Maybe (c (SizedList a))
(forall b. Data b => b -> b) -> SizedList a -> SizedList a
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SizedList a -> c (SizedList a)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SizedList a)
forall a. Data a => Typeable (SizedList a)
forall a. Data a => SizedList a -> Constr
forall a. Data a => SizedList a -> DataType
forall a.
Data a =>
(forall b. Data b => b -> b) -> SizedList a -> SizedList a
forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> SizedList a -> u
forall a u.
Data a =>
(forall d. Data d => d -> u) -> SizedList a -> [u]
forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SizedList a -> r
forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SizedList a -> r
forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)
forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)
forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SizedList a)
forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SizedList a -> c (SizedList a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (SizedList a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SizedList a))
forall a.
Typeable a =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> SizedList a -> u
forall u. (forall d. Data d => d -> u) -> SizedList a -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SizedList a -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SizedList a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SizedList a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SizedList a -> c (SizedList a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (SizedList a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SizedList a))
$cN :: Constr
$tSizedList :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)
gmapMp :: (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)
gmapM :: (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)
gmapQi :: Int -> (forall d. Data d => d -> u) -> SizedList a -> u
$cgmapQi :: forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> SizedList a -> u
gmapQ :: (forall d. Data d => d -> u) -> SizedList a -> [u]
$cgmapQ :: forall a u.
Data a =>
(forall d. Data d => d -> u) -> SizedList a -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SizedList a -> r
$cgmapQr :: forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SizedList a -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SizedList a -> r
$cgmapQl :: forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SizedList a -> r
gmapT :: (forall b. Data b => b -> b) -> SizedList a -> SizedList a
$cgmapT :: forall a.
Data a =>
(forall b. Data b => b -> b) -> SizedList a -> SizedList a
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SizedList a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SizedList a))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (SizedList a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (SizedList a))
dataTypeOf :: SizedList a -> DataType
$cdataTypeOf :: forall a. Data a => SizedList a -> DataType
toConstr :: SizedList a -> Constr
$ctoConstr :: forall a. Data a => SizedList a -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SizedList a)
$cgunfold :: forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SizedList a)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SizedList a -> c (SizedList a)
$cgfoldl :: forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SizedList a -> c (SizedList a)
$cp1Data :: forall a. Data a => Typeable (SizedList a)
Data, (forall x. SizedList a -> Rep (SizedList a) x)
-> (forall x. Rep (SizedList a) x -> SizedList a)
-> Generic (SizedList a)
forall x. Rep (SizedList a) x -> SizedList a
forall x. SizedList a -> Rep (SizedList a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (SizedList a) x -> SizedList a
forall a x. SizedList a -> Rep (SizedList a) x
$cto :: forall a x. Rep (SizedList a) x -> SizedList a
$cfrom :: forall a x. SizedList a -> Rep (SizedList a) x
Generic)

fromList :: [a] -> SizedList a
fromList :: [a] -> SizedList a
fromList xs :: [a]
xs = Int -> [a] -> SizedList a
forall a. Int -> [a] -> SizedList a
N ([a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) [a]
xs

toList :: SizedList a -> [a]
toList :: SizedList a -> [a]
toList (N _ xs :: [a]
xs) = [a]
xs

empty :: SizedList a
empty :: SizedList a
empty = Int -> [a] -> SizedList a
forall a. Int -> [a] -> SizedList a
N 0 []

singleton :: a -> SizedList a
singleton :: a -> SizedList a
singleton x :: a
x = Int -> [a] -> SizedList a
forall a. Int -> [a] -> SizedList a
N 1 [a
x]

cons :: a -> SizedList a -> SizedList a
cons :: a -> SizedList a -> SizedList a
cons x :: a
x (N n :: Int
n xs :: [a]
xs) = Int -> [a] -> SizedList a
forall a. Int -> [a] -> SizedList a
N (Int -> Int
forall a. Enum a => a -> a
succ Int
n) ([a] -> SizedList a) -> [a] -> SizedList a
forall a b. (a -> b) -> a -> b
$ a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs

append :: SizedList a -> SizedList a -> SizedList a
append :: SizedList a -> SizedList a -> SizedList a
append (N m :: Int
m xs :: [a]
xs) (N n :: Int
n ys :: [a]
ys) = Int -> [a] -> SizedList a
forall a. Int -> [a] -> SizedList a
N (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n) ([a] -> SizedList a) -> [a] -> SizedList a
forall a b. (a -> b) -> a -> b
$ [a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
ys

head :: SizedList a -> a
head :: SizedList a -> a
head (N n :: Int
n xs :: [a]
xs) = case [a]
xs of
  x :: a
x : _ | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> 0 -> a
x
  _ -> String -> a
forall a. HasCallStack => String -> a
error "SizedList.head: empty list"

tail :: SizedList a -> SizedList a
tail :: SizedList a -> SizedList a
tail (N n :: Int
n xs :: [a]
xs) = case [a]
xs of
  _ : r :: [a]
r | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> 0 -> Int -> [a] -> SizedList a
forall a. Int -> [a] -> SizedList a
N (Int -> Int
forall a. Enum a => a -> a
pred Int
n) [a]
r
  _ -> String -> SizedList a
forall a. HasCallStack => String -> a
error "SizedList.tail: empty list"

null :: SizedList a -> Bool
null :: SizedList a -> Bool
null (N n :: Int
n _) = Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0

size :: SizedList a -> Int
size :: SizedList a -> Int
size (N n :: Int
n _) = Int
n

reverse :: SizedList a -> SizedList a
reverse :: SizedList a -> SizedList a
reverse (N n :: Int
n xs :: [a]
xs) = Int -> [a] -> SizedList a
forall a. Int -> [a] -> SizedList a
N Int
n ([a] -> [a]
forall a. [a] -> [a]
List.reverse [a]
xs)

take :: Int -> SizedList a -> SizedList a
take :: Int -> SizedList a -> SizedList a
take i :: Int
i original :: SizedList a
original@(N n :: Int
n xs :: [a]
xs)
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = SizedList a
forall a. SizedList a
empty
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = SizedList a
original
  | Bool
otherwise = Int -> [a] -> SizedList a
forall a. Int -> [a] -> SizedList a
N Int
i ([a] -> SizedList a) -> [a] -> SizedList a
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
List.take Int
i [a]
xs

drop :: Int -> SizedList a -> SizedList a
drop :: Int -> SizedList a -> SizedList a
drop i :: Int
i original :: SizedList a
original@(N n :: Int
n xs :: [a]
xs)
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = SizedList a
original
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = SizedList a
forall a. SizedList a
empty
  | Bool
otherwise = Int -> [a] -> SizedList a
forall a. Int -> [a] -> SizedList a
N (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i) ([a] -> SizedList a) -> [a] -> SizedList a
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
List.drop Int
i [a]
xs

map :: (a -> b) -> SizedList a -> SizedList b
map :: (a -> b) -> SizedList a -> SizedList b
map f :: a -> b
f (N n :: Int
n xs :: [a]
xs) = Int -> [b] -> SizedList b
forall a. Int -> [a] -> SizedList a
N Int
n ((a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
List.map a -> b
f [a]
xs)