{-# 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 :: Size -> E -> E -> RangeSet a -> RangeSet a
unsafeInsertL :: Size -> Size -> Size -> RangeSet a -> RangeSet a
unsafeInsertL !Size
newSz !Size
l !Size
u = RangeSet a -> RangeSet a
forall a. RangeSet a -> RangeSet a
go
  where
    go :: RangeSet a -> RangeSet a
    go :: RangeSet a -> RangeSet a
go RangeSet a
Tip = Size -> Size -> Size -> RangeSet a
forall a. Size -> Size -> Size -> RangeSet a
single Size
newSz Size
l Size
u
    go (Fork Size
_ Size
sz Size
l' Size
u' RangeSet a
lt RangeSet a
rt) = Size -> Size -> Size -> RangeSet a -> RangeSet a -> RangeSet a
forall a.
Size -> Size -> Size -> RangeSet a -> RangeSet a -> RangeSet a
balanceL (Size
sz Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
newSz) Size
l' Size
u' (RangeSet a -> RangeSet a
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 :: Size -> E -> E -> RangeSet a -> RangeSet a
unsafeInsertR :: Size -> Size -> Size -> RangeSet a -> RangeSet a
unsafeInsertR !Size
newSz !Size
l !Size
u = RangeSet a -> RangeSet a
forall a. RangeSet a -> RangeSet a
go
  where
    go :: RangeSet a -> RangeSet a
    go :: RangeSet a -> RangeSet a
go RangeSet a
Tip = Size -> Size -> Size -> RangeSet a
forall a. Size -> Size -> Size -> RangeSet a
single Size
newSz Size
l Size
u
    go (Fork Size
_ Size
sz Size
l' Size
u' RangeSet a
lt RangeSet a
rt) = Size -> Size -> Size -> RangeSet a -> RangeSet a -> RangeSet a
forall a.
Size -> Size -> Size -> RangeSet a -> RangeSet a -> RangeSet a
balanceR (Size
sz Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
newSz) Size
l' Size
u' RangeSet a
lt (RangeSet a -> RangeSet a
forall a. RangeSet a -> RangeSet a
go RangeSet a
rt)

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

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