{-# LANGUAGE UnboxedTuples, BangPatterns, Safe #-}
module Data.RangeSet.SetCrossSet (union, intersection, difference, disjoint) where
import Prelude
import Data.RangeSet.Internal
{-# INLINABLE union #-}
union :: Enum a => RangeSet a -> RangeSet a -> RangeSet a
union :: RangeSet a -> RangeSet a -> RangeSet a
union RangeSet a
t RangeSet a
Tip = RangeSet a
t
union RangeSet a
Tip RangeSet a
t = RangeSet a
t
union t :: RangeSet a
t@(Fork Int
_ Int
_ Int
l Int
u RangeSet a
lt RangeSet a
rt) RangeSet a
t' = case Int -> Int -> RangeSet a -> (# RangeSet a, RangeSet a #)
forall a. Int -> Int -> RangeSet a -> (# RangeSet a, RangeSet a #)
split Int
l Int
u RangeSet a
t' of
(# RangeSet a
lt', RangeSet a
rt' #)
| RangeSet a -> RangeSet a -> Bool
forall a. RangeSet a -> RangeSet a -> Bool
stayedSame RangeSet a
lt RangeSet a
ltlt', RangeSet a -> RangeSet a -> Bool
forall a. RangeSet a -> RangeSet a -> Bool
stayedSame RangeSet a
rt RangeSet a
rtrt' -> RangeSet a
t
| Bool
otherwise -> Int -> Int -> RangeSet a -> RangeSet a -> RangeSet a
forall a. Int -> Int -> RangeSet a -> RangeSet a -> RangeSet a
link Int
l Int
u RangeSet a
ltlt' RangeSet a
rtrt'
where !ltlt' :: RangeSet a
ltlt' = RangeSet a
lt RangeSet a -> RangeSet a -> RangeSet a
forall a. Enum a => RangeSet a -> RangeSet a -> RangeSet a
`union` RangeSet a
lt'
!rtrt' :: RangeSet a
rtrt' = RangeSet a
rt RangeSet a -> RangeSet a -> RangeSet a
forall a. Enum a => RangeSet a -> RangeSet a -> RangeSet a
`union` RangeSet a
rt'
{-# INLINABLE intersection #-}
intersection :: Enum a => RangeSet a -> RangeSet a -> RangeSet a
intersection :: RangeSet a -> RangeSet a -> RangeSet a
intersection RangeSet a
Tip RangeSet a
_ = RangeSet a
forall a. RangeSet a
Tip
intersection RangeSet a
_ RangeSet a
Tip = RangeSet a
forall a. RangeSet a
Tip
intersection t1 :: RangeSet a
t1@(Fork Int
_ Int
_ Int
l1 Int
u1 RangeSet a
lt1 RangeSet a
rt1) RangeSet a
t2 =
case RangeSet a
overlap of
RangeSet a
Tip -> RangeSet a -> RangeSet a -> RangeSet a
forall a. RangeSet a -> RangeSet a -> RangeSet a
disjointMerge RangeSet a
lt1lt2 RangeSet a
rt1rt2
Fork Int
1 Int
sz Int
x Int
y RangeSet a
_ RangeSet a
_
| Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
l1, Int
y Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
u1
, RangeSet a -> RangeSet a -> Bool
forall a. RangeSet a -> RangeSet a -> Bool
stayedSame RangeSet a
lt1 RangeSet a
lt1lt2, RangeSet a -> RangeSet a -> Bool
forall a. RangeSet a -> RangeSet a -> Bool
stayedSame RangeSet a
rt1 RangeSet a
rt1rt2 -> RangeSet a
t1
| Bool
otherwise -> Int -> Int -> Int -> RangeSet a -> RangeSet a -> RangeSet a
forall a.
Int -> Int -> Int -> RangeSet a -> RangeSet a -> RangeSet a
disjointLink Int
sz Int
x Int
y RangeSet a
lt1lt2 RangeSet a
rt1rt2
Fork Int
_ Int
sz Int
x Int
y RangeSet a
lt' RangeSet a
rt' -> Int -> Int -> Int -> RangeSet a -> RangeSet a -> RangeSet a
forall a.
Int -> Int -> Int -> RangeSet a -> RangeSet a -> RangeSet a
disjointLink (Int
sz Int -> Int -> Int
forall a. Num a => a -> a -> a
- RangeSet a -> Int
forall a. RangeSet a -> Int
size RangeSet a
lt' Int -> Int -> Int
forall a. Num a => a -> a -> a
- RangeSet a -> Int
forall a. RangeSet a -> Int
size RangeSet a
rt') Int
x Int
y (RangeSet a -> RangeSet a -> RangeSet a
forall a. RangeSet a -> RangeSet a -> RangeSet a
disjointMerge RangeSet a
lt1lt2 RangeSet a
lt') (RangeSet a -> RangeSet a -> RangeSet a
forall a. RangeSet a -> RangeSet a -> RangeSet a
disjointMerge RangeSet a
rt' RangeSet a
rt1rt2)
where
(# !RangeSet a
lt2, !RangeSet a
overlap, !RangeSet a
rt2 #) = Int
-> Int -> RangeSet a -> (# RangeSet a, RangeSet a, RangeSet a #)
forall a.
Int
-> Int -> RangeSet a -> (# RangeSet a, RangeSet a, RangeSet a #)
splitOverlap Int
l1 Int
u1 RangeSet a
t2
!lt1lt2 :: RangeSet a
lt1lt2 = RangeSet a -> RangeSet a -> RangeSet a
forall a. Enum a => RangeSet a -> RangeSet a -> RangeSet a
intersection RangeSet a
lt1 RangeSet a
lt2
!rt1rt2 :: RangeSet a
rt1rt2 = RangeSet a -> RangeSet a -> RangeSet a
forall a. Enum a => RangeSet a -> RangeSet a -> RangeSet a
intersection RangeSet a
rt1 RangeSet a
rt2
{-# INLINE disjoint #-}
disjoint :: Enum a => RangeSet a -> RangeSet a -> Bool
disjoint :: RangeSet a -> RangeSet a -> Bool
disjoint RangeSet a
Tip RangeSet a
_ = Bool
True
disjoint RangeSet a
_ RangeSet a
Tip = Bool
True
disjoint (Fork Int
_ Int
_ Int
l Int
u RangeSet a
lt RangeSet a
rt) RangeSet a
t = case Int
-> Int -> RangeSet a -> (# RangeSet a, RangeSet a, RangeSet a #)
forall a.
Int
-> Int -> RangeSet a -> (# RangeSet a, RangeSet a, RangeSet a #)
splitOverlap Int
l Int
u RangeSet a
t of
(# RangeSet a
lt', RangeSet a
Tip, RangeSet a
rt' #) -> RangeSet a -> RangeSet a -> Bool
forall a. Enum a => RangeSet a -> RangeSet a -> Bool
disjoint RangeSet a
lt RangeSet a
lt' Bool -> Bool -> Bool
&& RangeSet a -> RangeSet a -> Bool
forall a. Enum a => RangeSet a -> RangeSet a -> Bool
disjoint RangeSet a
rt RangeSet a
rt'
(# RangeSet a, RangeSet a, RangeSet a #)
_ -> Bool
False
{-# INLINEABLE difference #-}
difference :: Enum a => RangeSet a -> RangeSet a -> RangeSet a
difference :: RangeSet a -> RangeSet a -> RangeSet a
difference RangeSet a
Tip RangeSet a
_ = RangeSet a
forall a. RangeSet a
Tip
difference RangeSet a
t RangeSet a
Tip = RangeSet a
t
difference RangeSet a
t (Fork Int
_ Int
_ Int
l Int
u RangeSet a
lt RangeSet a
rt) = case Int -> Int -> RangeSet a -> (# RangeSet a, RangeSet a #)
forall a. Int -> Int -> RangeSet a -> (# RangeSet a, RangeSet a #)
split Int
l Int
u RangeSet a
t of
(# RangeSet a
lt', RangeSet a
rt' #)
| RangeSet a -> Int
forall a. RangeSet a -> Int
size RangeSet a
lt'lt Int -> Int -> Int
forall a. Num a => a -> a -> a
+ RangeSet a -> Int
forall a. RangeSet a -> Int
size RangeSet a
rt'rt Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== RangeSet a -> Int
forall a. RangeSet a -> Int
size RangeSet a
t -> RangeSet a
t
| Bool
otherwise -> RangeSet a -> RangeSet a -> RangeSet a
forall a. RangeSet a -> RangeSet a -> RangeSet a
disjointMerge RangeSet a
lt'lt RangeSet a
rt'rt
where
!lt'lt :: RangeSet a
lt'lt = RangeSet a -> RangeSet a -> RangeSet a
forall a. Enum a => RangeSet a -> RangeSet a -> RangeSet a
difference RangeSet a
lt' RangeSet a
lt
!rt'rt :: RangeSet a
rt'rt = RangeSet a -> RangeSet a -> RangeSet a
forall a. Enum a => RangeSet a -> RangeSet a -> RangeSet a
difference RangeSet a
rt' RangeSet a
rt