{- |
Copyright:  (c) 2019-2020 Veronika Romashkina
            (c) 2020-2022 Kowainik
SPDX-License-Identifier: MPL-2.0
Maintainer: Kowainik <xrom.xkov@gmail.com>
Stability:   Stable
Portability: Portable

Lists size representation.
-}

module Slist.Size
    ( Size (..)
    , sizes
    ) where


{- | Data type that represents lists size/lengths.

+-----------+----------+------------+
| List      | @length@ | Size       |
+===========+==========+============+
| @[]@      | @0@      | @Size 0@   |
+-----------+----------+------------+
| @[1..10]@ | @10@     | @Size 10@  |
+-----------+----------+------------+
| @[1..]@   | /hangs/  | @Infinity@ |
+-----------+----------+------------+

Note, that size is not suppose to have negative value, so use
the 'Size' constructor carefully.
-}
data Size
    -- | Finite size
    = Size !Int
    -- | Infinite size.
    | Infinity
    deriving stock (Int -> Size -> ShowS
[Size] -> ShowS
Size -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Size] -> ShowS
$cshowList :: [Size] -> ShowS
show :: Size -> String
$cshow :: Size -> String
showsPrec :: Int -> Size -> ShowS
$cshowsPrec :: Int -> Size -> ShowS
Show, ReadPrec [Size]
ReadPrec Size
Int -> ReadS Size
ReadS [Size]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [Size]
$creadListPrec :: ReadPrec [Size]
readPrec :: ReadPrec Size
$creadPrec :: ReadPrec Size
readList :: ReadS [Size]
$creadList :: ReadS [Size]
readsPrec :: Int -> ReadS Size
$creadsPrec :: Int -> ReadS Size
Read, Size -> Size -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Size -> Size -> Bool
$c/= :: Size -> Size -> Bool
== :: Size -> Size -> Bool
$c== :: Size -> Size -> Bool
Eq, Eq Size
Size -> Size -> Bool
Size -> Size -> Ordering
Size -> Size -> Size
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
min :: Size -> Size -> Size
$cmin :: Size -> Size -> Size
max :: Size -> Size -> Size
$cmax :: Size -> Size -> Size
>= :: Size -> Size -> Bool
$c>= :: Size -> Size -> Bool
> :: Size -> Size -> Bool
$c> :: Size -> Size -> Bool
<= :: Size -> Size -> Bool
$c<= :: Size -> Size -> Bool
< :: Size -> Size -> Bool
$c< :: Size -> Size -> Bool
compare :: Size -> Size -> Ordering
$ccompare :: Size -> Size -> Ordering
Ord)

{- | Efficient implementations of numeric operations with 'Size's.

Any operations with 'Infinity' size results into 'Infinity'. When
'Infinity' is a left argument, all operations are also
right-lazy. Operations are checked for integral overflow under the
assumption that all values inside 'Size' are positive.

>>> Size 10 + Size 5
Size 15
>>> Size 5 * Infinity
Infinity
>>> Infinity + error "Unevaluated size"
Infinity
>>> Size (10 ^ 10) * Size (10 ^ 10)
Infinity
-}
instance Num Size where
    (+) :: Size -> Size -> Size
    Size
Infinity + :: Size -> Size -> Size
+ Size
_ = Size
Infinity
    Size
_ + Size
Infinity = Size
Infinity
    (Size Int
x) + (Size Int
y) =
        if Int
x forall a. Num a => a -> a -> a
+ Int
y forall a. Ord a => a -> a -> Bool
< Int
x  -- integer overflow
        then Size
Infinity
        else Int -> Size
Size forall a b. (a -> b) -> a -> b
$ Int
x forall a. Num a => a -> a -> a
+ Int
y
    {-# INLINE (+) #-}

    (-) :: Size -> Size -> Size
    Size
Infinity - :: Size -> Size -> Size
- Size
_        = Size
Infinity
    Size
_ - Size
Infinity        = Size
Infinity
    (Size Int
x) - (Size Int
y) = Int -> Size
Size (Int
x forall a. Num a => a -> a -> a
- Int
y)
    {-# INLINE (-) #-}

    (*) :: Size -> Size -> Size
    Size
Infinity * :: Size -> Size -> Size
* Size
_ = Size
Infinity
    Size
_ * Size
Infinity = Size
Infinity
    (Size Int
x) * (Size Int
y)
        | Int
x forall a. Eq a => a -> a -> Bool
== Int
0 Bool -> Bool -> Bool
|| Int
y forall a. Eq a => a -> a -> Bool
== Int
0 = Size
0
        | Bool
otherwise =
            let result :: Int
result = Int
x forall a. Num a => a -> a -> a
* Int
y in
            if Int
x forall a. Eq a => a -> a -> Bool
== Int
result forall a. Integral a => a -> a -> a
`div` Int
y
            then Int -> Size
Size (Int
x forall a. Num a => a -> a -> a
* Int
y)
            else Size
Infinity  -- multiplication overflow
    {-# INLINE (*) #-}

    abs :: Size -> Size
    abs :: Size -> Size
abs Size
Infinity = Size
Infinity
    abs (Size Int
x) = Int -> Size
Size forall a b. (a -> b) -> a -> b
$ forall a. Num a => a -> a
abs Int
x
    {-# INLINE abs #-}

    signum :: Size -> Size
    signum :: Size -> Size
signum Size
Infinity = Size
Infinity
    signum (Size Int
x) = Int -> Size
Size (forall a. Num a => a -> a
signum Int
x)
    {-# INLINE signum #-}

    fromInteger :: Integer -> Size
    fromInteger :: Integer -> Size
fromInteger = Int -> Size
Size forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Num a => Integer -> a
fromInteger
    {-# INLINE fromInteger #-}

{- | The minimum possible size for the list is empty list: @Size 0@
The maximum possible size is 'Infinity'.
-}
instance Bounded Size where
    minBound :: Size
    minBound :: Size
minBound = Int -> Size
Size Int
0

    maxBound :: Size
    maxBound :: Size
maxBound = Size
Infinity

{- | Returns the list of sizes from zero to the given one (including).

>>> sizes $ Size 3
[Size 0,Size 1,Size 2,Size 3]

@
>> __sizes Infinity__
[Size 0, Size 1, ..., Size 'maxBound', Infinity]
@
-}
sizes :: Size -> [Size]
sizes :: Size -> [Size]
sizes (Size Int
n) = forall a b. (a -> b) -> [a] -> [b]
map Int -> Size
Size [Int
0..Int
n]
sizes Size
Infinity = forall a b. (a -> b) -> [a] -> [b]
map Int -> Size
Size [Int
0..forall a. Bounded a => a
maxBound] forall a. [a] -> [a] -> [a]
++ [Size
Infinity]