{-# LANGUAGE BangPatterns, UnboxedTuples, Safe #-}
module Data.RangeSet.Internal.Splitters (module Data.RangeSet.Internal.Splitters) where
import Prelude
import Data.RangeSet.Internal.Types
import Data.RangeSet.Internal.SmartConstructors
import Data.RangeSet.Internal.Inserters
import Data.RangeSet.Internal.Lumpers
{-# INLINEABLE allLessE #-}
allLessE :: E -> RangeSet a -> RangeSet a
allLessE :: forall a. E -> RangeSet a -> RangeSet a
allLessE !E
_ RangeSet a
Tip = forall a. RangeSet a
Tip
allLessE E
x (Fork H
_ E
l E
u RangeSet a
lt RangeSet a
rt) = case forall a. Ord a => a -> a -> Ordering
compare E
x E
l of
Ordering
EQ -> RangeSet a
lt
Ordering
LT -> forall a. E -> RangeSet a -> RangeSet a
allLessE E
x RangeSet a
lt
Ordering
GT | E
x forall a. Ord a => a -> a -> Bool
<= E
u -> forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertR E
l (forall a. Enum a => a -> a
pred E
x) (forall a. E -> RangeSet a -> RangeSet a
allLessE E
x RangeSet a
lt)
Ordering
GT -> forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
link E
l E
u RangeSet a
lt (forall a. E -> RangeSet a -> RangeSet a
allLessE E
x RangeSet a
rt)
{-# INLINEABLE allMoreE #-}
allMoreE :: E -> RangeSet a -> RangeSet a
allMoreE :: forall a. E -> RangeSet a -> RangeSet a
allMoreE !E
_ RangeSet a
Tip = forall a. RangeSet a
Tip
allMoreE E
x (Fork H
_ E
l E
u RangeSet a
lt RangeSet a
rt) = case forall a. Ord a => a -> a -> Ordering
compare E
u E
x of
Ordering
EQ -> RangeSet a
rt
Ordering
LT -> forall a. E -> RangeSet a -> RangeSet a
allMoreE E
x RangeSet a
rt
Ordering
GT | E
l forall a. Ord a => a -> a -> Bool
<= E
x -> forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertL (forall a. Enum a => a -> a
succ E
x) E
u (forall a. E -> RangeSet a -> RangeSet a
allMoreE E
x RangeSet a
rt)
Ordering
GT -> forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
link E
l E
u (forall a. E -> RangeSet a -> RangeSet a
allMoreE E
x RangeSet a
lt) RangeSet a
rt
{-# INLINEABLE split #-}
split :: E -> E -> RangeSet a -> (# RangeSet a, RangeSet a #)
split :: forall a. E -> E -> RangeSet a -> (# RangeSet a, RangeSet a #)
split !E
_ !E
_ RangeSet a
Tip = (# forall a. RangeSet a
Tip, forall a. RangeSet a
Tip #)
split E
l E
u (Fork H
_ E
l' E
u' RangeSet a
lt RangeSet a
rt) = forall a.
E
-> E
-> E
-> E
-> RangeSet a
-> RangeSet a
-> (# RangeSet a, RangeSet a #)
splitFork E
l E
u E
l' E
u' RangeSet a
lt RangeSet a
rt
{-# INLINEABLE splitFork #-}
splitFork :: E -> E -> E -> E -> RangeSet a -> RangeSet a -> (# RangeSet a, RangeSet a #)
splitFork :: forall a.
E
-> E
-> E
-> E
-> RangeSet a
-> RangeSet a
-> (# RangeSet a, RangeSet a #)
splitFork E
l E
u E
l' E
u' RangeSet a
lt RangeSet a
rt
| E
u forall a. Ord a => a -> a -> Bool
< E
l' = let (# !RangeSet a
llt, !RangeSet a
lgt #) = forall a. E -> E -> RangeSet a -> (# RangeSet a, RangeSet a #)
split E
l E
u RangeSet a
lt in (# RangeSet a
llt, forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
link E
l' E
u' RangeSet a
lgt RangeSet a
rt #)
| E
u' forall a. Ord a => a -> a -> Bool
< E
l = let (# !RangeSet a
rlt, !RangeSet a
rgt #) = forall a. E -> E -> RangeSet a -> (# RangeSet a, RangeSet a #)
split E
l E
u RangeSet a
rt in (# forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
link E
l' E
u' RangeSet a
lt RangeSet a
rlt, RangeSet a
rgt #)
| Bool
otherwise = let !lt' :: RangeSet a
lt' = case forall a. Ord a => a -> a -> Ordering
compare E
l' E
l of
Ordering
EQ -> RangeSet a
lt
Ordering
LT -> forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertR E
l' (forall a. Enum a => a -> a
pred E
l) RangeSet a
lt
Ordering
GT -> forall a. E -> RangeSet a -> RangeSet a
allLessE E
l RangeSet a
lt
!rt' :: RangeSet a
rt' = case forall a. Ord a => a -> a -> Ordering
compare E
u E
u' of
Ordering
EQ -> RangeSet a
rt
Ordering
LT -> forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertL (forall a. Enum a => a -> a
succ E
u) E
u' RangeSet a
rt
Ordering
GT -> forall a. E -> RangeSet a -> RangeSet a
allMoreE E
u RangeSet a
rt
in (# RangeSet a
lt', RangeSet a
rt' #)
{-# INLINE splitOverlapFork #-}
splitOverlapFork :: E -> E -> E -> E -> RangeSet a -> RangeSet a -> (# RangeSet a, RangeSet a, RangeSet a #)
splitOverlapFork :: forall a.
E
-> E
-> E
-> E
-> RangeSet a
-> RangeSet a
-> (# RangeSet a, RangeSet a, RangeSet a #)
splitOverlapFork !E
l !E
u !E
l' !E
u' !RangeSet a
lt !RangeSet a
rt =
let (# RangeSet a
lt', RangeSet a
rt' #) = forall a.
E
-> E
-> E
-> E
-> RangeSet a
-> RangeSet a
-> (# RangeSet a, RangeSet a #)
splitFork E
l E
u E
l' E
u' RangeSet a
lt RangeSet a
rt in (# RangeSet a
lt', forall a.
E -> E -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
overlappingFork E
l E
u E
l' E
u' RangeSet a
lt RangeSet a
rt, RangeSet a
rt' #)
{-# INLINABLE overlapping #-}
overlapping :: E -> E -> RangeSet a -> RangeSet a
overlapping :: forall a. E -> E -> RangeSet a -> RangeSet a
overlapping !E
_ !E
_ RangeSet a
Tip = forall a. RangeSet a
Tip
overlapping E
x E
y (Fork H
_ E
l E
u RangeSet a
lt RangeSet a
rt) = forall a.
E -> E -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
overlappingFork E
x E
y E
l E
u RangeSet a
lt RangeSet a
rt
{-# INLINABLE overlappingFork #-}
overlappingFork :: E -> E -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
overlappingFork :: forall a.
E -> E -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
overlappingFork E
x E
y E
l E
u RangeSet a
lt RangeSet a
rt =
case forall a. Ord a => a -> a -> Ordering
compare E
l E
x of
Ordering
GT -> let !lt' :: RangeSet a
lt' = forall a. E -> E -> RangeSet a -> RangeSet a
overlapping E
x E
y RangeSet a
lt
in case Ordering
cmpY of
Ordering
GT -> forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
disjointLink E
l E
u RangeSet a
lt' RangeSet a
rt'
Ordering
EQ -> forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertR E
l E
u RangeSet a
lt'
Ordering
LT | E
y forall a. Ord a => a -> a -> Bool
>= E
l -> forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertR E
l E
y RangeSet a
lt'
Ordering
LT -> RangeSet a
lt'
Ordering
EQ -> case Ordering
cmpY of
Ordering
GT -> forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertL E
l E
u RangeSet a
rt'
Ordering
LT -> forall a. RangeSet a
t'
Ordering
EQ -> forall a. E -> E -> RangeSet a
single E
l E
u
Ordering
LT -> case Ordering
cmpY of
Ordering
GT | E
x forall a. Ord a => a -> a -> Bool
<= E
u -> forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertL E
x E
u RangeSet a
rt'
Ordering
GT -> RangeSet a
rt'
Ordering
_ -> forall a. RangeSet a
t'
where
!cmpY :: Ordering
cmpY = forall a. Ord a => a -> a -> Ordering
compare E
y E
u
rt' :: RangeSet a
rt' = forall a. E -> E -> RangeSet a -> RangeSet a
overlapping E
x E
y RangeSet a
rt
t' :: RangeSet a
t' :: forall a. RangeSet a
t' = forall a. E -> E -> RangeSet a
single E
x E
y