-- |
-- Module      : Data.Vector.Fusion.Bundle.Size
-- Copyright   : (c) Roman Leshchinskiy 2008-2010
-- License     : BSD-style
--
-- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
-- Stability   : experimental
-- Portability : portable
--
-- Size hints for streams.
--

module Data.Vector.Fusion.Bundle.Size (
  Size(..), clampedSubtract, smaller, smallerThan, larger, toMax, upperBound, lowerBound
) where

import Data.Vector.Fusion.Util ( delay_inline )

-- | Size hint
data Size = Exact Int          -- ^ Exact size
          | Max   Int          -- ^ Upper bound on the size
          | Unknown            -- ^ Unknown size
        deriving( Size -> Size -> Bool
(Size -> Size -> Bool) -> (Size -> Size -> Bool) -> Eq Size
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, Int -> Size -> ShowS
[Size] -> ShowS
Size -> String
(Int -> Size -> ShowS)
-> (Size -> String) -> ([Size] -> ShowS) -> Show Size
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 )

instance Num Size where
  Exact m :: Int
m + :: Size -> Size -> Size
+ Exact n :: Int
n = (Int -> Size) -> Int -> Int -> Size
checkedAdd Int -> Size
Exact Int
m Int
n
  Exact m :: Int
m + Max   n :: Int
n = (Int -> Size) -> Int -> Int -> Size
checkedAdd Int -> Size
Max Int
m Int
n

  Max   m :: Int
m + Exact n :: Int
n = (Int -> Size) -> Int -> Int -> Size
checkedAdd Int -> Size
Max Int
m Int
n
  Max   m :: Int
m + Max   n :: Int
n = (Int -> Size) -> Int -> Int -> Size
checkedAdd Int -> Size
Max Int
m Int
n

  _       + _       = Size
Unknown


  Exact m :: Int
m - :: Size -> Size -> Size
- Exact n :: Int
n = (Int -> Size) -> Int -> Int -> Size
checkedSubtract Int -> Size
Exact Int
m Int
n
  Exact m :: Int
m - Max   _ = Int -> Size
Max   Int
m

  Max   m :: Int
m - Exact n :: Int
n = (Int -> Size) -> Int -> Int -> Size
checkedSubtract Int -> Size
Max Int
m Int
n
  Max   m :: Int
m - Max   _ = Int -> Size
Max   Int
m
  Max   m :: Int
m - Unknown = Int -> Size
Max   Int
m

  _       - _       = Size
Unknown


  fromInteger :: Integer -> Size
fromInteger n :: Integer
n     = Int -> Size
Exact (Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n)

  * :: Size -> Size -> Size
(*)    = String -> Size -> Size -> Size
forall a. HasCallStack => String -> a
error "vector: internal error * for Bundle.size isn't defined"
  abs :: Size -> Size
abs    = String -> Size -> Size
forall a. HasCallStack => String -> a
error "vector: internal error abs for Bundle.size isn't defined"
  signum :: Size -> Size
signum = String -> Size -> Size
forall a. HasCallStack => String -> a
error "vector: internal error signum for Bundle.size isn't defined"

{-# INLINE checkedAdd #-}
checkedAdd :: (Int -> Size) -> Int -> Int -> Size
checkedAdd :: (Int -> Size) -> Int -> Int -> Size
checkedAdd con :: Int -> Size
con m :: Int
m n :: Int
n
    -- Note: we assume m and n are >= 0.
  | Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
m Bool -> Bool -> Bool
|| Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n =
      String -> Size
forall a. HasCallStack => String -> a
error (String -> Size) -> String -> Size
forall a b. (a -> b) -> a -> b
$ "Data.Vector.Fusion.Bundle.Size.checkedAdd: overflow: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
r
  | Bool
otherwise = Int -> Size
con Int
r
  where
    r :: Int
r = Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n

{-# INLINE checkedSubtract #-}
checkedSubtract :: (Int -> Size) -> Int -> Int -> Size
checkedSubtract :: (Int -> Size) -> Int -> Int -> Size
checkedSubtract con :: Int -> Size
con m :: Int
m n :: Int
n
  | Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< 0 =
      String -> Size
forall a. HasCallStack => String -> a
error (String -> Size) -> String -> Size
forall a b. (a -> b) -> a -> b
$ "Data.Vector.Fusion.Bundle.Size.checkedSubtract: underflow: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
r
  | Bool
otherwise = Int -> Size
con Int
r
  where
    r :: Int
r = Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n

-- | Subtract two sizes with clamping to 0, for drop-like things
{-# INLINE clampedSubtract #-}
clampedSubtract :: Size -> Size -> Size
clampedSubtract :: Size -> Size -> Size
clampedSubtract (Exact m :: Int
m) (Exact n :: Int
n) = Int -> Size
Exact (Int -> Int -> Int
forall a. Ord a => a -> a -> a
max 0 (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n))
clampedSubtract (Max   m :: Int
m) (Exact n :: Int
n)
  | Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
n = Int -> Size
Exact 0
  | Bool
otherwise = Int -> Size
Max (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n)
clampedSubtract (Exact m :: Int
m) (Max   _) = Int -> Size
Max Int
m
clampedSubtract (Max   m :: Int
m) (Max   _) = Int -> Size
Max Int
m
clampedSubtract _         _ = Size
Unknown

-- | Minimum of two size hints
smaller :: Size -> Size -> Size
{-# INLINE smaller #-}
smaller :: Size -> Size -> Size
smaller (Exact m :: Int
m) (Exact n :: Int
n) = Int -> Size
Exact ((Int -> Int -> Int) -> Int -> Int -> Int
forall a b. (a -> b) -> a -> b
delay_inline Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
m Int
n)
smaller (Exact m :: Int
m) (Max   n :: Int
n) = Int -> Size
Max   ((Int -> Int -> Int) -> Int -> Int -> Int
forall a b. (a -> b) -> a -> b
delay_inline Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
m Int
n)
smaller (Exact m :: Int
m) Unknown   = Int -> Size
Max   Int
m
smaller (Max   m :: Int
m) (Exact n :: Int
n) = Int -> Size
Max   ((Int -> Int -> Int) -> Int -> Int -> Int
forall a b. (a -> b) -> a -> b
delay_inline Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
m Int
n)
smaller (Max   m :: Int
m) (Max   n :: Int
n) = Int -> Size
Max   ((Int -> Int -> Int) -> Int -> Int -> Int
forall a b. (a -> b) -> a -> b
delay_inline Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
m Int
n)
smaller (Max   m :: Int
m) Unknown   = Int -> Size
Max   Int
m
smaller Unknown   (Exact n :: Int
n) = Int -> Size
Max   Int
n
smaller Unknown   (Max   n :: Int
n) = Int -> Size
Max   Int
n
smaller Unknown   Unknown   = Size
Unknown

-- | Select a safe smaller than known size.
smallerThan :: Int -> Size -> Size
{-# INLINE smallerThan #-}
smallerThan :: Int -> Size -> Size
smallerThan m :: Int
m (Exact n :: Int
n) = Int -> Size
Exact ((Int -> Int -> Int) -> Int -> Int -> Int
forall a b. (a -> b) -> a -> b
delay_inline Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
m Int
n)
smallerThan m :: Int
m (Max   n :: Int
n) = Int -> Size
Max   ((Int -> Int -> Int) -> Int -> Int -> Int
forall a b. (a -> b) -> a -> b
delay_inline Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
m Int
n)
smallerThan _ Unknown   = Size
Unknown


-- | Maximum of two size hints
larger :: Size -> Size -> Size
{-# INLINE larger #-}
larger :: Size -> Size -> Size
larger (Exact m :: Int
m) (Exact n :: Int
n)             = Int -> Size
Exact ((Int -> Int -> Int) -> Int -> Int -> Int
forall a b. (a -> b) -> a -> b
delay_inline Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
m Int
n)
larger (Exact m :: Int
m) (Max   n :: Int
n) | Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = Int -> Size
Exact Int
m
                           | Bool
otherwise = Int -> Size
Max   Int
n
larger (Max   m :: Int
m) (Exact n :: Int
n) | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
m    = Int -> Size
Exact Int
n
                           | Bool
otherwise = Int -> Size
Max   Int
m
larger (Max   m :: Int
m) (Max   n :: Int
n)             = Int -> Size
Max   ((Int -> Int -> Int) -> Int -> Int -> Int
forall a b. (a -> b) -> a -> b
delay_inline Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
m Int
n)
larger _         _                     = Size
Unknown

-- | Convert a size hint to an upper bound
toMax :: Size -> Size
toMax :: Size -> Size
toMax (Exact n :: Int
n) = Int -> Size
Max Int
n
toMax (Max   n :: Int
n) = Int -> Size
Max Int
n
toMax Unknown   = Size
Unknown

-- | Compute the minimum size from a size hint
lowerBound :: Size -> Int
lowerBound :: Size -> Int
lowerBound (Exact n :: Int
n) = Int
n
lowerBound _         = 0

-- | Compute the maximum size from a size hint if possible
upperBound :: Size -> Maybe Int
upperBound :: Size -> Maybe Int
upperBound (Exact n :: Int
n) = Int -> Maybe Int
forall a. a -> Maybe a
Just Int
n
upperBound (Max   n :: Int
n) = Int -> Maybe Int
forall a. a -> Maybe a
Just Int
n
upperBound Unknown   = Maybe Int
forall a. Maybe a
Nothing