{-# LANGUAGE UnboxedTuples, BangPatterns, Safe #-}
module Data.RangeSet.SetCrossSet (union, intersection, difference, disjoint) where

import Prelude
import Data.RangeSet.Internal

{-|
Unions two sets together such that if and only if an element appears in either one of the sets, it
will appear in the result set.

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

{-|
Intersects two sets such that an element appears in the result if and only if it is present in both
of the provided sets.

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

{-|
Do two sets have no elements in common?

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

{-|
Removes all elements from the first set that are found in the second set.

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