{-# LANGUAGE BangPatterns, UnboxedTuples, Safe #-}
module Data.RangeSet.Internal.Inserters (module Data.RangeSet.Internal.Inserters) where

import Prelude

import Data.RangeSet.Internal.Types
import Data.RangeSet.Internal.SmartConstructors
import Data.RangeSet.Internal.Extractors

{-|
Inserts an range at the left-most position in the tree.
It *must* not overlap with any other range within the tree.
It *must* be /known/ not to exist within the tree.
-}
{-# INLINEABLE unsafeInsertL #-}
unsafeInsertL :: E -> E -> RangeSet a -> RangeSet a
unsafeInsertL :: forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertL !E
l !E
u = forall a. RangeSet a -> RangeSet a
go
  where
    go :: RangeSet a -> RangeSet a
    go :: forall a. RangeSet a -> RangeSet a
go RangeSet a
Tip = forall a. E -> E -> RangeSet a
single E
l E
u
    go (Fork H
_ E
l' E
u' RangeSet a
lt RangeSet a
rt) = forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
balanceL E
l' E
u' (forall a. RangeSet a -> RangeSet a
go RangeSet a
lt) RangeSet a
rt

{-|
Inserts an range at the right-most position in the tree.
It *must* not overlap with any other range within the tree.
It *must* be /known/ not to exist within the tree.
-}
{-# INLINEABLE unsafeInsertR #-}
unsafeInsertR :: E -> E -> RangeSet a -> RangeSet a
unsafeInsertR :: forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertR !E
l !E
u = forall a. RangeSet a -> RangeSet a
go
  where
    go :: RangeSet a -> RangeSet a
    go :: forall a. RangeSet a -> RangeSet a
go RangeSet a
Tip = forall a. E -> E -> RangeSet a
single E
l E
u
    go (Fork H
_ E
l' E
u' RangeSet a
lt RangeSet a
rt) = forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
balanceR E
l' E
u' RangeSet a
lt (forall a. RangeSet a -> RangeSet a
go RangeSet a
rt)

{-# INLINEABLE insertLAdj #-}
insertLAdj :: E -> E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
insertLAdj :: forall a.
E -> E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
insertLAdj !E
l !E
u !H
th !E
tl !E
tu !RangeSet a
tlt !RangeSet a
trt = case forall a. E -> E -> RangeSet a -> (# E, E #)
minRange E
tl E
tu RangeSet a
tlt of
  (# !E
l', E
_ #) | E
l' forall a. Eq a => a -> a -> Bool
== forall a. Enum a => a -> a
succ E
u -> forall a.
E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
fuseL E
l H
th E
tl E
tu RangeSet a
tlt RangeSet a
trt
               | Bool
otherwise    -> forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
balanceL E
tl E
tu (forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertL E
l E
u RangeSet a
tlt) RangeSet a
trt
  where
    {-# INLINEABLE fuseL #-}
    fuseL :: E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
    fuseL :: forall a.
E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
fuseL !E
l' !H
h !E
l !E
u RangeSet a
lt RangeSet a
rt = case RangeSet a
lt of
      RangeSet a
Tip -> forall a. H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
Fork H
h E
l' E
u forall a. RangeSet a
Tip RangeSet a
rt
      Fork H
lh E
ll E
lu RangeSet a
llt RangeSet a
lrt  -> forall a. H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
Fork H
h E
l E
u (forall a.
E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
fuseL E
l' H
lh E
ll E
lu RangeSet a
llt RangeSet a
lrt) RangeSet a
rt

{-# INLINEABLE insertRAdj #-}
insertRAdj :: E -> E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
insertRAdj :: forall a.
E -> E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
insertRAdj !E
l !E
u !H
th !E
tl !E
tu !RangeSet a
tlt !RangeSet a
trt = case forall a. E -> E -> RangeSet a -> (# E, E #)
maxRange E
tl E
tu RangeSet a
trt of
  (# E
_, !E
u' #) | E
u' forall a. Eq a => a -> a -> Bool
== forall a. Enum a => a -> a
pred E
l -> forall a.
E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
fuseR E
u H
th E
tl E
tu RangeSet a
tlt RangeSet a
trt
               | Bool
otherwise    -> forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
balanceR E
tl E
tu RangeSet a
tlt (forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertR E
l E
u RangeSet a
trt)
  where
    {-# INLINEABLE fuseR #-}
    fuseR :: E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
    fuseR :: forall a.
E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
fuseR !E
u' !H
h !E
l !E
u RangeSet a
lt RangeSet a
rt = case RangeSet a
rt of
      RangeSet a
Tip -> forall a. H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
Fork H
h E
l E
u' RangeSet a
lt forall a. RangeSet a
Tip
      Fork H
rh E
rl E
ru RangeSet a
rlt RangeSet a
rrt  -> forall a. H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
Fork H
h E
l E
u RangeSet a
lt (forall a.
E -> H -> E -> E -> RangeSet a -> RangeSet a -> RangeSet a
fuseR E
u' H
rh E
rl E
ru RangeSet a
rlt RangeSet a
rrt)