{-# LANGUAGE DerivingStrategies, RoleAnnotations, CPP, Trustworthy #-}
#if __GLASGOW_HASKELL__ > 900
{-# LANGUAGE UnliftedDatatypes #-}
#endif
module Data.RangeSet.Internal.Types (module Data.RangeSet.Internal.Types) where

import Prelude

#if __GLASGOW_HASKELL__ > 900
import GHC.Exts (UnliftedType)
#endif

type Size = Int
type E = Int
{-|
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 #-} !Int {-# UNPACK #-} !Size {-# UNPACK #-} !E {-# UNPACK #-} !E !(RangeSet a) !(RangeSet a)
                | Tip
                deriving stock Int -> RangeSet a -> ShowS
[RangeSet a] -> ShowS
RangeSet a -> String
(Int -> RangeSet a -> ShowS)
-> (RangeSet a -> String)
-> ([RangeSet a] -> ShowS)
-> Show (RangeSet a)
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 :: RangeSet a -> Int
size RangeSet a
Tip = Int
0
size (Fork Int
_ Int
sz Int
_ Int
_ RangeSet a
_ RangeSet a
_) = Int
sz

{-# INLINE height #-}
height :: RangeSet a -> Int
height :: RangeSet a -> Int
height RangeSet a
Tip = Int
0
height (Fork Int
h Int
_ Int
_ Int
_ RangeSet a
_ RangeSet a
_) = Int
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 :: (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 Int
_ Int
_ Int
l Int
u RangeSet a
lt RangeSet a
rt) = Int -> Int -> b -> b -> b
fork Int
l Int
u ((Int -> Int -> b -> b -> b) -> b -> RangeSet a -> b
forall b a. (Int -> Int -> b -> b -> b) -> b -> RangeSet a -> b
foldE Int -> Int -> b -> b -> b
fork b
tip RangeSet a
lt) ((Int -> Int -> b -> b -> b) -> b -> RangeSet a -> b
forall b a. (Int -> Int -> b -> b -> b) -> b -> RangeSet a -> b
foldE Int -> Int -> b -> b -> b
fork b
tip RangeSet a
rt)

#if __GLASGOW_HASKELL__ > 900
type StrictMaybeE :: UnliftedType
#endif
data StrictMaybeE = SJust {-# UNPACK #-} !E | SNothing

#if __GLASGOW_HASKELL__ > 900
type SRangeList :: UnliftedType
#endif
data SRangeList = SRangeCons {-# UNPACK #-} !E {-# UNPACK #-} !E !SRangeList | SNil

-- Instances
instance Eq (RangeSet a) where
  {-# INLINABLE (==) #-}
  RangeSet a
t1 == :: RangeSet a -> RangeSet a -> Bool
== RangeSet a
t2 = RangeSet a -> Int
forall a. RangeSet a -> Int
size RangeSet a
t1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== RangeSet a -> Int
forall a. RangeSet a -> Int
size RangeSet a
t2 Bool -> Bool -> Bool
&& RangeSet a -> [(Int, Int)]
forall a. RangeSet a -> [(Int, Int)]
ranges RangeSet a
t1 [(Int, Int)] -> [(Int, Int)] -> Bool
forall a. Eq a => a -> a -> Bool
== RangeSet a -> [(Int, Int)]
forall a. RangeSet a -> [(Int, Int)]
ranges RangeSet a
t2
    where
      {-# INLINE ranges #-}
      ranges :: RangeSet a -> [(E, E)]
      ranges :: RangeSet a -> [(Int, Int)]
ranges RangeSet a
t = (Int
 -> Int
 -> ([(Int, Int)] -> [(Int, Int)])
 -> ([(Int, Int)] -> [(Int, Int)])
 -> [(Int, Int)]
 -> [(Int, Int)])
-> ([(Int, Int)] -> [(Int, Int)])
-> RangeSet a
-> [(Int, Int)]
-> [(Int, Int)]
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 ([(Int, Int)] -> [(Int, Int)])
-> ([(Int, Int)] -> [(Int, Int)]) -> [(Int, Int)] -> [(Int, Int)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int
l, Int
u) (Int, Int) -> [(Int, Int)] -> [(Int, Int)]
forall a. a -> [a] -> [a]
:) ([(Int, Int)] -> [(Int, Int)])
-> ([(Int, Int)] -> [(Int, Int)]) -> [(Int, Int)] -> [(Int, Int)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, Int)] -> [(Int, Int)]
rt) [(Int, Int)] -> [(Int, Int)]
forall a. a -> a
id RangeSet a
t []