{-# 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
-}
union :: RangeSet a -> RangeSet a -> RangeSet a
union :: forall a. RangeSet a -> RangeSet a -> RangeSet a
union = forall a. RangeSet a -> RangeSet a -> RangeSet a
optimalForHeight
  where
    optimalForHeight :: RangeSet a -> RangeSet a -> RangeSet a
    optimalForHeight :: forall a. RangeSet a -> RangeSet a -> RangeSet a
optimalForHeight RangeSet a
t RangeSet a
Tip =  RangeSet a
t
    optimalForHeight RangeSet a
Tip RangeSet a
t = RangeSet a
t
    optimalForHeight lt :: RangeSet a
lt@(Fork H
lh E
ll E
lu RangeSet a
llt RangeSet a
lrt) rt :: RangeSet a
rt@(Fork H
rh E
rl E
ru RangeSet a
rlt RangeSet a
rrt)
      | H
lh forall a. Ord a => a -> a -> Bool
< H
rh = forall a.
RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> RangeSet a
doUnion RangeSet a
rt E
rl E
ru RangeSet a
rlt RangeSet a
rrt E
ll E
lu RangeSet a
llt RangeSet a
lrt
      | Bool
otherwise = forall a.
RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> RangeSet a
doUnion RangeSet a
lt E
ll E
lu RangeSet a
llt RangeSet a
lrt E
rl E
ru RangeSet a
rlt RangeSet a
rrt

    doUnion :: RangeSet a -> E -> E -> RangeSet a -> RangeSet a -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
    doUnion :: forall a.
RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> RangeSet a
doUnion RangeSet a
t E
ll E
lu RangeSet a
llt RangeSet a
lrt E
rl E
ru RangeSet a
rlt RangeSet a
rrt = case forall a.
E
-> E
-> E
-> E
-> RangeSet a
-> RangeSet a
-> (# RangeSet a, RangeSet a #)
splitFork E
ll E
lu E
rl E
ru RangeSet a
rlt RangeSet a
rrt of
      (# RangeSet a
lt', RangeSet a
rt' #)
        | forall a. RangeSet a -> RangeSet a -> Bool
stayedSame RangeSet a
llt RangeSet a
ltlt', forall a. RangeSet a -> RangeSet a -> Bool
stayedSame RangeSet a
lrt RangeSet a
rtrt' -> RangeSet a
t
        | Bool
otherwise                                  -> forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
link E
ll E
lu RangeSet a
ltlt' RangeSet a
rtrt'
        where !ltlt' :: RangeSet a
ltlt' = RangeSet a
llt forall a. RangeSet a -> RangeSet a -> RangeSet a
`optimalForHeight` RangeSet a
lt'
              !rtrt' :: RangeSet a
rtrt' = RangeSet a
lrt forall a. RangeSet a -> RangeSet a -> RangeSet a
`optimalForHeight` 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
-}
intersection :: RangeSet a -> RangeSet a -> RangeSet a
intersection :: forall a. RangeSet a -> RangeSet a -> RangeSet a
intersection = forall a. RangeSet a -> RangeSet a -> RangeSet a
optimalForHeight
  where
    -- until splitOverlapFork is optimised, this picks the best configuration for performance
    -- this is because more work is done on the right tree than the left tree, so making the
    -- right tree the shallowest saves work in long run
    optimalForHeight :: RangeSet a -> RangeSet a -> RangeSet a
    optimalForHeight :: forall a. RangeSet a -> RangeSet a -> RangeSet a
optimalForHeight RangeSet a
Tip RangeSet a
_ = forall a. RangeSet a
Tip
    optimalForHeight RangeSet a
_ RangeSet a
Tip = forall a. RangeSet a
Tip
    optimalForHeight lt :: RangeSet a
lt@(Fork H
lh E
ll E
lu RangeSet a
llt RangeSet a
lrt) rt :: RangeSet a
rt@(Fork H
rh E
rl E
ru RangeSet a
rlt RangeSet a
rrt)
      | H
lh forall a. Ord a => a -> a -> Bool
< H
rh = forall a.
RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> RangeSet a
doIntersect RangeSet a
rt E
rl E
ru RangeSet a
rlt RangeSet a
rrt E
ll E
lu RangeSet a
llt RangeSet a
lrt
      | Bool
otherwise = forall a.
RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> RangeSet a
doIntersect RangeSet a
lt E
ll E
lu RangeSet a
llt RangeSet a
lrt E
rl E
ru RangeSet a
rlt RangeSet a
rrt

    doIntersect :: RangeSet a -> E -> E -> RangeSet a -> RangeSet a -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
    doIntersect :: forall a.
RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> E
-> E
-> RangeSet a
-> RangeSet a
-> RangeSet a
doIntersect !RangeSet a
lt !E
ll !E
lu !RangeSet a
llt !RangeSet a
lrt !E
rl !E
ru !RangeSet a
rlt !RangeSet a
rrt =
      case RangeSet a
overlap of
        RangeSet a
Tip -> forall a. RangeSet a -> RangeSet a -> RangeSet a
disjointMerge RangeSet a
lltrlt RangeSet a
lrtrrt
        Fork H
1 E
x E
y RangeSet a
_ RangeSet a
_
          | E
x forall a. Eq a => a -> a -> Bool
== E
ll, E
y forall a. Eq a => a -> a -> Bool
== E
lu
          , forall a. RangeSet a -> RangeSet a -> Bool
stayedSame RangeSet a
llt RangeSet a
lltrlt, forall a. RangeSet a -> RangeSet a -> Bool
stayedSame RangeSet a
lrt RangeSet a
lrtrrt -> RangeSet a
lt
          | Bool
otherwise -> forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
disjointLink E
x E
y RangeSet a
lltrlt RangeSet a
lrtrrt
        Fork H
_ E
x E
y RangeSet a
lt' RangeSet a
rt' -> forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
disjointLink E
x E
y (forall a. RangeSet a -> RangeSet a -> RangeSet a
disjointMerge RangeSet a
lltrlt RangeSet a
lt') (forall a. RangeSet a -> RangeSet a -> RangeSet a
disjointMerge RangeSet a
rt' RangeSet a
lrtrrt)
      where
        (# !RangeSet a
lt', !RangeSet a
overlap, !RangeSet a
rt' #) = forall a.
E
-> E
-> E
-> E
-> RangeSet a
-> RangeSet a
-> (# RangeSet a, RangeSet a, RangeSet a #)
splitOverlapFork E
ll E
lu E
rl E
ru RangeSet a
rlt RangeSet a
rrt
        !lltrlt :: RangeSet a
lltrlt = forall a. RangeSet a -> RangeSet a -> RangeSet a
optimalForHeight RangeSet a
llt RangeSet a
lt'
        !lrtrrt :: RangeSet a
lrtrrt = forall a. RangeSet a -> RangeSet a -> RangeSet a
optimalForHeight RangeSet a
lrt RangeSet a
rt'

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

@since 0.0.1.0
-}
disjoint :: RangeSet a -> RangeSet a -> Bool
disjoint :: forall a. RangeSet a -> RangeSet a -> Bool
disjoint RangeSet a
Tip RangeSet a
_ = Bool
True
disjoint RangeSet a
_ RangeSet a
Tip = Bool
True
disjoint (Fork H
_ E
ll E
lu RangeSet a
llt RangeSet a
lrt) (Fork H
_ E
rl E
ru RangeSet a
rlt RangeSet a
rrt) = case forall a.
E
-> E
-> E
-> E
-> RangeSet a
-> RangeSet a
-> (# RangeSet a, RangeSet a, RangeSet a #)
splitOverlapFork E
ll E
lu E
rl E
ru RangeSet a
rlt RangeSet a
rrt of
  (# RangeSet a
lt', RangeSet a
Tip, RangeSet a
rt' #) -> forall a. RangeSet a -> RangeSet a -> Bool
disjoint RangeSet a
llt RangeSet a
lt' Bool -> Bool -> Bool
&& forall a. RangeSet a -> RangeSet a -> Bool
disjoint RangeSet a
lrt 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
-}
difference :: RangeSet a -> RangeSet a -> RangeSet a
difference :: forall a. RangeSet a -> RangeSet a -> RangeSet a
difference RangeSet a
Tip RangeSet a
_ = forall a. RangeSet a
Tip
difference RangeSet a
t RangeSet a
Tip = RangeSet a
t
difference (Fork H
_ E
ll E
lu RangeSet a
llt RangeSet a
lrt) (Fork H
_ E
rl E
ru RangeSet a
rlt RangeSet a
rrt) = case forall a.
E
-> E
-> E
-> E
-> RangeSet a
-> RangeSet a
-> (# RangeSet a, RangeSet a #)
splitFork E
rl E
ru E
ll E
lu RangeSet a
llt RangeSet a
lrt of
  (# RangeSet a
lt', RangeSet a
rt' #) -> forall a. RangeSet a -> RangeSet a -> RangeSet a
disjointMerge RangeSet a
lt'lt RangeSet a
rt'rt
    where
      !lt'lt :: RangeSet a
lt'lt = forall a. RangeSet a -> RangeSet a -> RangeSet a
difference RangeSet a
lt' RangeSet a
rlt
      !rt'rt :: RangeSet a
rt'rt = forall a. RangeSet a -> RangeSet a -> RangeSet a
difference RangeSet a
rt' RangeSet a
rrt