{-# 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
{-|
A @Set@ type designed for types that are `Enum` as well as `Ord`. This allows the `RangeSet` to
compress the data when it is contiguous, reducing memory-footprint and enabling otherwise impractical
operations like `complement` for `Bounded` types.

@since 0.0.1.0
-}
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

{-|
Return the number of /elements/ in the set.

@since 0.0.1.0
-}
{-# 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) -- ^ Function that combines the lower and upper values (inclusive) for a range with the folded left- and right-subtrees.
      -> b                       -- ^ Value to be substituted at the leaves.
      -> 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

-- Instances
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 []