{-# LANGUAGE UnboxedTuples, BangPatterns, Safe #-}
module Data.RangeSet.SetCrossSet (union, intersection, difference, disjoint) where
import Prelude
import Data.RangeSet.Internal
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'
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
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'
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
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