{-# LANGUAGE DerivingStrategies, RoleAnnotations, Trustworthy, BangPatterns #-}
{-# LANGUAGE UnliftedDatatypes #-}
module Data.RangeSet.Internal.Types (module Data.RangeSet.Internal.Types) where
import Prelude
import GHC.Exts (UnliftedType)
import GHC.Word (Word8)
import Data.RangeSet.Internal.Unsafe
type E = Int
type H = Word8
data RangeSet a = Fork {-# UNPACK #-} !H {-# UNPACK #-} !E {-# UNPACK #-} !E !(RangeSet a) !(RangeSet a)
| Tip
deriving stock Int -> RangeSet a -> ShowS
forall a. Int -> RangeSet a -> ShowS
forall a. [RangeSet a] -> ShowS
forall a. RangeSet a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [RangeSet a] -> ShowS
$cshowList :: forall a. [RangeSet a] -> ShowS
show :: RangeSet a -> String
$cshow :: forall a. RangeSet a -> String
showsPrec :: Int -> RangeSet a -> ShowS
$cshowsPrec :: forall a. Int -> RangeSet a -> ShowS
Show
type role RangeSet nominal
{-# INLINE size #-}
size :: RangeSet a -> Int
size :: forall a. RangeSet a -> Int
size = forall b a. (Int -> Int -> b -> b -> b) -> b -> RangeSet a -> b
foldE (\Int
l Int
u Int
szl Int
szr -> Int
szl forall a. Num a => a -> a -> a
+ Int
szr forall a. Num a => a -> a -> a
+ (Int
u forall a. Num a => a -> a -> a
- Int
l forall a. Num a => a -> a -> a
+ Int
1)) Int
0
{-# INLINE height #-}
height :: RangeSet a -> H
height :: forall a. RangeSet a -> H
height RangeSet a
Tip = H
0
height (Fork H
h Int
_ Int
_ RangeSet a
_ RangeSet a
_) = H
h
{-# INLINEABLE foldE #-}
foldE :: (E -> E -> b -> b -> b)
-> b
-> RangeSet a
-> b
foldE :: forall b a. (Int -> Int -> b -> b -> b) -> b -> RangeSet a -> b
foldE Int -> Int -> b -> b -> b
_ b
tip RangeSet a
Tip = b
tip
foldE Int -> Int -> b -> b -> b
fork b
tip (Fork H
_ Int
l Int
u RangeSet a
lt RangeSet a
rt) = Int -> Int -> b -> b -> b
fork Int
l Int
u (forall b a. (Int -> Int -> b -> b -> b) -> b -> RangeSet a -> b
foldE Int -> Int -> b -> b -> b
fork b
tip RangeSet a
lt) (forall b a. (Int -> Int -> b -> b -> b) -> b -> RangeSet a -> b
foldE Int -> Int -> b -> b -> b
fork b
tip RangeSet a
rt)
type StrictMaybeE :: UnliftedType
data StrictMaybeE = SJust {-# UNPACK #-} !E | SNothing
type SRangeList :: UnliftedType
data SRangeList = SRangeCons {-# UNPACK #-} !E {-# UNPACK #-} !E !SRangeList | SNil
absDiff :: H -> H -> H
absDiff :: H -> H -> H
absDiff !H
h1 !H
h2
| H
h1 forall a. Ord a => a -> a -> Bool
> H
h2 = H
h1 forall a. Num a => a -> a -> a
- H
h2
| Bool
otherwise = H
h2 forall a. Num a => a -> a -> a
- H
h1
instance Eq (RangeSet a) where
{-# INLINABLE (==) #-}
RangeSet a
t1 == :: RangeSet a -> RangeSet a -> Bool
== RangeSet a
t2 = forall a. a -> a -> Bool
ptrEq RangeSet a
t1 RangeSet a
t2 Bool -> Bool -> Bool
|| (H -> H -> H
absDiff (forall a. RangeSet a -> H
height RangeSet a
t1) (forall a. RangeSet a -> H
height RangeSet a
t2) forall a. Ord a => a -> a -> Bool
<= H
1 Bool -> Bool -> Bool
&& forall a. RangeSet a -> [(Int, Int)]
ranges RangeSet a
t1 forall a. Eq a => a -> a -> Bool
== forall a. RangeSet a -> [(Int, Int)]
ranges RangeSet a
t2)
where
{-# INLINE ranges #-}
ranges :: RangeSet a -> [(E, E)]
ranges :: forall a. RangeSet a -> [(Int, Int)]
ranges RangeSet a
t = forall b a. (Int -> Int -> b -> b -> b) -> b -> RangeSet a -> b
foldE (\Int
l Int
u [(Int, Int)] -> [(Int, Int)]
lt [(Int, Int)] -> [(Int, Int)]
rt -> [(Int, Int)] -> [(Int, Int)]
lt forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int
l, Int
u) forall a. a -> [a] -> [a]
:) forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, Int)] -> [(Int, Int)]
rt) forall a. a -> a
id RangeSet a
t []