1-- |
2-- Module      : Data.Vector.Fusion.Bundle.Size
3-- Copyright   : (c) Roman Leshchinskiy 2008-2010
4-- License     : BSD-style
5--
6-- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
7-- Stability   : experimental
8-- Portability : portable
9--
10-- Size hints for streams.
11--
12
13module Data.Vector.Fusion.Bundle.Size (
14  Size(..), clampedSubtract, smaller, smallerThan, larger, toMax, upperBound, lowerBound
15) where
16
17import Data.Vector.Fusion.Util ( delay_inline )
18
19-- | Size hint
20data Size = Exact Int          -- ^ Exact size
21          | Max   Int          -- ^ Upper bound on the size
22          | Unknown            -- ^ Unknown size
23        deriving( Eq, Show )
24
25instance Num Size where
26  Exact m + Exact n = checkedAdd Exact m n
27  Exact m + Max   n = checkedAdd Max m n
28
29  Max   m + Exact n = checkedAdd Max m n
30  Max   m + Max   n = checkedAdd Max m n
31
32  _       + _       = Unknown
33
34
35  Exact m - Exact n = checkedSubtract Exact m n
36  Exact m - Max   _ = Max   m
37
38  Max   m - Exact n = checkedSubtract Max m n
39  Max   m - Max   _ = Max   m
40  Max   m - Unknown = Max   m
41
42  _       - _       = Unknown
43
44
45  fromInteger n     = Exact (fromInteger n)
46
47  (*)    = error "vector: internal error * for Bundle.size isn't defined"
48  abs    = error "vector: internal error abs for Bundle.size isn't defined"
49  signum = error "vector: internal error signum for Bundle.size isn't defined"
50
51{-# INLINE checkedAdd #-}
52checkedAdd :: (Int -> Size) -> Int -> Int -> Size
53checkedAdd con m n
54    -- Note: we assume m and n are >= 0.
55  | r < m || r < n =
56      error $ "Data.Vector.Fusion.Bundle.Size.checkedAdd: overflow: " ++ show r
57  | otherwise = con r
58  where
59    r = m + n
60
61{-# INLINE checkedSubtract #-}
62checkedSubtract :: (Int -> Size) -> Int -> Int -> Size
63checkedSubtract con m n
64  | r < 0 =
65      error $ "Data.Vector.Fusion.Bundle.Size.checkedSubtract: underflow: " ++ show r
66  | otherwise = con r
67  where
68    r = m - n
69
70-- | Subtract two sizes with clamping to 0, for drop-like things
71{-# INLINE clampedSubtract #-}
72clampedSubtract :: Size -> Size -> Size
73clampedSubtract (Exact m) (Exact n) = Exact (max 0 (m - n))
74clampedSubtract (Max   m) (Exact n)
75  | m <= n = Exact 0
76  | otherwise = Max (m - n)
77clampedSubtract (Exact m) (Max   _) = Max m
78clampedSubtract (Max   m) (Max   _) = Max m
79clampedSubtract _         _ = Unknown
80
81-- | Minimum of two size hints
82smaller :: Size -> Size -> Size
83{-# INLINE smaller #-}
84smaller (Exact m) (Exact n) = Exact (delay_inline min m n)
85smaller (Exact m) (Max   n) = Max   (delay_inline min m n)
86smaller (Exact m) Unknown   = Max   m
87smaller (Max   m) (Exact n) = Max   (delay_inline min m n)
88smaller (Max   m) (Max   n) = Max   (delay_inline min m n)
89smaller (Max   m) Unknown   = Max   m
90smaller Unknown   (Exact n) = Max   n
91smaller Unknown   (Max   n) = Max   n
92smaller Unknown   Unknown   = Unknown
93
94-- | Select a safe smaller than known size.
95smallerThan :: Int -> Size -> Size
96{-# INLINE smallerThan #-}
97smallerThan m (Exact n) = Exact (delay_inline min m n)
98smallerThan m (Max   n) = Max   (delay_inline min m n)
99smallerThan _ Unknown   = Unknown
100
101
102-- | Maximum of two size hints
103larger :: Size -> Size -> Size
104{-# INLINE larger #-}
105larger (Exact m) (Exact n)             = Exact (delay_inline max m n)
106larger (Exact m) (Max   n) | m >= n    = Exact m
107                           | otherwise = Max   n
108larger (Max   m) (Exact n) | n >= m    = Exact n
109                           | otherwise = Max   m
110larger (Max   m) (Max   n)             = Max   (delay_inline max m n)
111larger _         _                     = Unknown
112
113-- | Convert a size hint to an upper bound
114toMax :: Size -> Size
115toMax (Exact n) = Max n
116toMax (Max   n) = Max n
117toMax Unknown   = Unknown
118
119-- | Compute the minimum size from a size hint
120lowerBound :: Size -> Int
121lowerBound (Exact n) = n
122lowerBound _         = 0
123
124-- | Compute the maximum size from a size hint if possible
125upperBound :: Size -> Maybe Int
126upperBound (Exact n) = Just n
127upperBound (Max   n) = Just n
128upperBound Unknown   = Nothing
129
130