{-# 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.Enum
import Data.RangeSet.Internal.Lumpers

{-# INLINEABLE allLessE #-}
allLessE :: E -> RangeSet a -> RangeSet a
allLessE :: E -> RangeSet a -> RangeSet a
allLessE !E
_ RangeSet a
Tip = RangeSet a
forall a. RangeSet a
Tip
allLessE E
x (Fork E
_ E
_ E
l E
u RangeSet a
lt RangeSet a
rt) = case E -> E -> Ordering
forall a. Ord a => a -> a -> Ordering
compare E
x E
l of
  Ordering
EQ          -> RangeSet a
lt
  Ordering
LT          -> E -> RangeSet a -> RangeSet a
forall a. E -> RangeSet a -> RangeSet a
allLessE E
x RangeSet a
lt
  Ordering
GT | E
x E -> E -> Bool
forall a. Ord a => a -> a -> Bool
<= E
u -> E -> E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> E -> RangeSet a -> RangeSet a
unsafeInsertR (E -> E -> E
diffE E
l (E -> E
forall a. Enum a => a -> a
pred E
x)) E
l (E -> E
forall a. Enum a => a -> a
pred E
x) (E -> RangeSet a -> RangeSet a
forall a. E -> RangeSet a -> RangeSet a
allLessE E
x RangeSet a
lt)
  Ordering
GT          -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
link E
l E
u RangeSet a
lt (E -> RangeSet a -> RangeSet a
forall a. E -> RangeSet a -> RangeSet a
allLessE E
x RangeSet a
rt)

{-# INLINEABLE allMoreE #-}
allMoreE :: E -> RangeSet a -> RangeSet a
allMoreE :: E -> RangeSet a -> RangeSet a
allMoreE !E
_ RangeSet a
Tip = RangeSet a
forall a. RangeSet a
Tip
allMoreE E
x (Fork E
_ E
_ E
l E
u RangeSet a
lt RangeSet a
rt) = case E -> E -> Ordering
forall a. Ord a => a -> a -> Ordering
compare E
u E
x of
  Ordering
EQ          -> RangeSet a
rt
  Ordering
LT          -> E -> RangeSet a -> RangeSet a
forall a. E -> RangeSet a -> RangeSet a
allMoreE E
x RangeSet a
rt
  Ordering
GT | E
l E -> E -> Bool
forall a. Ord a => a -> a -> Bool
<= E
x -> E -> E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> E -> RangeSet a -> RangeSet a
unsafeInsertL (E -> E -> E
diffE (E -> E
forall a. Enum a => a -> a
succ E
x) E
u) (E -> E
forall a. Enum a => a -> a
succ E
x) E
u (E -> RangeSet a -> RangeSet a
forall a. E -> RangeSet a -> RangeSet a
allMoreE E
x RangeSet a
rt)
  Ordering
GT          -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
link E
l E
u (E -> RangeSet a -> RangeSet a
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 :: E -> E -> RangeSet a -> (# RangeSet a, RangeSet a #)
split !E
_ !E
_ RangeSet a
Tip = (# RangeSet a
forall a. RangeSet a
Tip, RangeSet a
forall a. RangeSet a
Tip #)
split E
l E
u (Fork E
_ E
_ E
l' E
u' RangeSet a
lt RangeSet a
rt)
  | E
u E -> E -> Bool
forall a. Ord a => a -> a -> Bool
< E
l' = let (# !RangeSet a
llt, !RangeSet a
lgt #) = E -> E -> RangeSet a -> (# RangeSet a, RangeSet a #)
forall a. E -> E -> RangeSet a -> (# RangeSet a, RangeSet a #)
split E
l E
u RangeSet a
lt in (# RangeSet a
llt, E -> E -> RangeSet a -> RangeSet a -> RangeSet a
forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
link E
l' E
u' RangeSet a
lgt RangeSet a
rt #)
  | E
u' E -> E -> Bool
forall a. Ord a => a -> a -> Bool
< E
l = let (# !RangeSet a
rlt, !RangeSet a
rgt #) = E -> E -> RangeSet a -> (# RangeSet a, RangeSet a #)
forall a. E -> E -> RangeSet a -> (# RangeSet a, RangeSet a #)
split E
l E
u RangeSet a
rt in (# E -> E -> RangeSet a -> RangeSet a -> RangeSet a
forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
link E
l' E
u' RangeSet a
lt RangeSet a
rlt, RangeSet a
rgt #)
  -- The ranges overlap in some way
  | Bool
otherwise = let !lt' :: RangeSet a
lt' = case E -> E -> Ordering
forall a. Ord a => a -> a -> Ordering
compare E
l' E
l of
                      Ordering
EQ -> RangeSet a
lt
                      Ordering
LT -> E -> E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> E -> RangeSet a -> RangeSet a
unsafeInsertR (E -> E -> E
diffE E
l' (E -> E
forall a. Enum a => a -> a
pred E
l)) E
l' (E -> E
forall a. Enum a => a -> a
pred E
l) RangeSet a
lt
                      Ordering
GT -> E -> RangeSet a -> RangeSet a
forall a. E -> RangeSet a -> RangeSet a
allLessE E
l RangeSet a
lt
                    !rt' :: RangeSet a
rt' = case E -> E -> Ordering
forall a. Ord a => a -> a -> Ordering
compare E
u E
u' of
                      Ordering
EQ -> RangeSet a
rt
                      Ordering
LT -> E -> E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> E -> RangeSet a -> RangeSet a
unsafeInsertL (E -> E -> E
diffE (E -> E
forall a. Enum a => a -> a
succ E
u) E
u') (E -> E
forall a. Enum a => a -> a
succ E
u) E
u' RangeSet a
rt
                      Ordering
GT -> E -> RangeSet a -> RangeSet a
forall a. E -> RangeSet a -> RangeSet a
allMoreE E
u RangeSet a
rt
                in (# RangeSet a
lt', RangeSet a
rt' #)

{-# INLINE splitOverlap #-}
splitOverlap :: E -> E -> RangeSet a -> (# RangeSet a, RangeSet a, RangeSet a #)
splitOverlap :: E -> E -> RangeSet a -> (# RangeSet a, RangeSet a, RangeSet a #)
splitOverlap !E
l !E
u !RangeSet a
t = let (# RangeSet a
lt', RangeSet a
rt' #) = E -> E -> RangeSet a -> (# RangeSet a, RangeSet a #)
forall a. E -> E -> RangeSet a -> (# RangeSet a, RangeSet a #)
split E
l E
u RangeSet a
t in (# RangeSet a
lt', E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> RangeSet a -> RangeSet a
overlapping E
l E
u RangeSet a
t, RangeSet a
rt' #)

{-# INLINABLE overlapping #-}
overlapping :: E -> E -> RangeSet a -> RangeSet a
overlapping :: E -> E -> RangeSet a -> RangeSet a
overlapping !E
_ !E
_ RangeSet a
Tip = RangeSet a
forall a. RangeSet a
Tip
overlapping E
x E
y (Fork E
_ E
sz E
l E
u RangeSet a
lt RangeSet a
rt) =
  case E -> E -> Ordering
forall a. Ord a => a -> a -> Ordering
compare E
l E
x of
    -- range is outside to the left
    Ordering
GT -> let !lt' :: RangeSet a
lt' = {-allMoreEqX-} E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> RangeSet a -> RangeSet a
overlapping E
x E
y RangeSet a
lt
          in case Ordering
cmpY of
               -- range is totally outside
               Ordering
GT -> E -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
forall a. E -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
disjointLink E
nodeSz E
l E
u RangeSet a
lt' RangeSet a
rt'
               Ordering
EQ -> E -> E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> E -> RangeSet a -> RangeSet a
unsafeInsertR E
nodeSz E
l E
u RangeSet a
lt'
               Ordering
LT | E
y E -> E -> Bool
forall a. Ord a => a -> a -> Bool
>= E
l -> E -> E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> E -> RangeSet a -> RangeSet a
unsafeInsertR (E -> E -> E
diffE E
l E
y) E
l E
y RangeSet a
lt'
               Ordering
LT          -> RangeSet a
lt' {-overlapping x y lt-}
    -- range is inside on the left
    Ordering
EQ -> case Ordering
cmpY of
      -- range is outside on the right
      Ordering
GT -> E -> E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> E -> RangeSet a -> RangeSet a
unsafeInsertL E
nodeSz E
l E
u RangeSet a
rt'
      Ordering
LT -> RangeSet a
forall a. RangeSet a
t'
      Ordering
EQ -> E -> E -> E -> RangeSet a
forall a. E -> E -> E -> RangeSet a
single E
nodeSz E
l E
u
    Ordering
LT -> case Ordering
cmpY of
      -- range is outside on the right
      Ordering
GT | E
x E -> E -> Bool
forall a. Ord a => a -> a -> Bool
<= E
u -> E -> E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> E -> RangeSet a -> RangeSet a
unsafeInsertL (E -> E -> E
diffE E
x E
u) E
x E
u RangeSet a
rt'
      Ordering
GT          -> RangeSet a
rt' {-overlapping x y rt-}
      Ordering
_           -> RangeSet a
forall a. RangeSet a
t'
  where
    !cmpY :: Ordering
cmpY = E -> E -> Ordering
forall a. Ord a => a -> a -> Ordering
compare E
y E
u
    !nodeSz :: E
nodeSz = E
sz E -> E -> E
forall a. Num a => a -> a -> a
- RangeSet a -> E
forall a. RangeSet a -> E
size RangeSet a
lt E -> E -> E
forall a. Num a => a -> a -> a
- RangeSet a -> E
forall a. RangeSet a -> E
size RangeSet a
rt
    -- leave lazy!
    rt' :: RangeSet a
rt' = {-allLessEqY-} E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> RangeSet a -> RangeSet a
overlapping E
x E
y RangeSet a
rt
    t' :: RangeSet a
    t' :: RangeSet a
t' = E -> E -> E -> RangeSet a
forall a. E -> E -> E -> RangeSet a
single (E -> E -> E
diffE E
x E
y) E
x E
y

    {-allLessEqY Tip = Tip
    allLessEqY (Fork _ sz l u lt rt) = case compare y l of
      EQ         -> unsafeInsertR 1 y y lt
      LT         -> allLessEqY lt
      GT | y < u -> unsafeInsertR (diffE l y) l y (allLessEqY lt)
      GT         -> disjointLink (sz - size lt - size rt) l u lt (allLessEqY rt)

    allMoreEqX Tip = Tip
    allMoreEqX (Fork _ sz l u lt rt) = case compare u x of
      EQ         -> unsafeInsertL 1 x x rt
      LT         -> allMoreEqX rt
      GT | l < x -> unsafeInsertL (diffE x u) x u (allMoreEqX rt)
      GT         -> disjointLink (sz - size lt - size rt) l u (allMoreEqX lt) rt-}