{-# LANGUAGE BangPatterns, ScopedTypeVariables, Safe #-}
module Data.RangeSet.Builders (fromRanges, fromDistinctAscRanges, insertRange, fromList, fromDistinctAscList) where

import Prelude hiding (id, (.))
import Data.RangeSet.Internal
import Data.RangeSet.Primitives
import Data.List (foldl')

{-# INLINE id #-}
id :: SRangeList -> SRangeList
id :: SRangeList -> SRangeList
id SRangeList
ss = SRangeList
ss

{-# INLINE (.) #-}
(.) :: (SRangeList -> SRangeList) -> (SRangeList -> SRangeList) -> SRangeList -> SRangeList
(SRangeList -> SRangeList
f . :: (SRangeList -> SRangeList)
-> (SRangeList -> SRangeList) -> SRangeList -> SRangeList
. SRangeList -> SRangeList
g) SRangeList
ss = SRangeList -> SRangeList
f (SRangeList -> SRangeList
g SRangeList
ss)

{-|
Constructs a `RangeSet` given a list of ranges.

@since 0.0.1.0
-}
{-# INLINABLE fromRanges #-}
fromRanges :: forall a. Enum a => [(a, a)] -> RangeSet a
fromRanges :: forall a. Enum a => [(a, a)] -> RangeSet a
fromRanges [] = forall a. RangeSet a
Tip
fromRanges ((a
x, a
y):[(a, a)]
rs) = [(a, a)] -> Int -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [(a, a)]
rs Int
ey (Int -> Int -> SRangeList -> SRangeList
SRangeCons Int
ex Int
ey) Int
1
  where
    !ex :: Int
ex = forall a. Enum a => a -> Int
fromEnum a
x
    !ey :: Int
ey = forall a. Enum a => a -> Int
fromEnum a
y
    go :: [(a, a)] -> E -> (SRangeList -> SRangeList) -> Int -> RangeSet a
    go :: [(a, a)] -> Int -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [] !Int
_ SRangeList -> SRangeList
k !Int
n = forall a. SRangeList -> Int -> RangeSet a
fromDistinctAscRangesSz (SRangeList -> SRangeList
k SRangeList
SNil) Int
n
    go ((a
x, a
y):[(a, a)]
rs) Int
z SRangeList -> SRangeList
k Int
n
      -- ordering and disjointness of the ranges broken
      | Int
ex forall a. Ord a => a -> a -> Bool
<= Int
z Bool -> Bool -> Bool
|| Int
ey forall a. Ord a => a -> a -> Bool
<= Int
z = forall a. Int -> Int -> RangeSet a -> RangeSet a
insertRangeE Int
ex Int
ey (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a. Enum a => a -> a -> RangeSet a -> RangeSet a
insertRange)) (forall a. SRangeList -> Int -> RangeSet a
fromDistinctAscRangesSz (SRangeList -> SRangeList
k SRangeList
SNil) Int
n) [(a, a)]
rs)
      | Bool
otherwise          = [(a, a)] -> Int -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [(a, a)]
rs Int
ey (SRangeList -> SRangeList
k (SRangeList -> SRangeList)
-> (SRangeList -> SRangeList) -> SRangeList -> SRangeList
. Int -> Int -> SRangeList -> SRangeList
SRangeCons Int
ex Int
ey) (Int
n forall a. Num a => a -> a -> a
+ Int
1)
      where
        !ex :: Int
ex = forall a. Enum a => a -> Int
fromEnum a
x
        !ey :: Int
ey = forall a. Enum a => a -> Int
fromEnum a
y

{-|
Constructs a `RangeSet` given a list of ranges that are in ascending order and do not overlap (this is unchecked).

@since 0.0.1.0
-}
{-# INLINABLE fromDistinctAscRanges #-}
fromDistinctAscRanges :: forall a. Enum a => [(a, a)] -> RangeSet a
fromDistinctAscRanges :: forall a. Enum a => [(a, a)] -> RangeSet a
fromDistinctAscRanges [(a, a)]
rs = [(a, a)] -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [(a, a)]
rs SRangeList -> SRangeList
id Int
0
  where
    go :: [(a, a)] -> (SRangeList -> SRangeList) -> Int -> RangeSet a
    go :: [(a, a)] -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [] SRangeList -> SRangeList
k !Int
n = forall a. SRangeList -> Int -> RangeSet a
fromDistinctAscRangesSz (SRangeList -> SRangeList
k SRangeList
SNil) Int
n
    go ((a
x, a
y):[(a, a)]
rs) SRangeList -> SRangeList
k Int
n = [(a, a)] -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [(a, a)]
rs (SRangeList -> SRangeList
k (SRangeList -> SRangeList)
-> (SRangeList -> SRangeList) -> SRangeList -> SRangeList
. Int -> Int -> SRangeList -> SRangeList
SRangeCons (forall a. Enum a => a -> Int
fromEnum a
x) (forall a. Enum a => a -> Int
fromEnum a
y)) (Int
n forall a. Num a => a -> a -> a
+ Int
1)

{-|
Inserts a range into a `RangeSet`.

@since 0.0.1.0
-}
{-# INLINE insertRange #-}
insertRange :: Enum a => a -> a -> RangeSet a -> RangeSet a
insertRange :: forall a. Enum a => a -> a -> RangeSet a -> RangeSet a
insertRange a
l a
u RangeSet a
t =
  let !le :: Int
le = forall a. Enum a => a -> Int
fromEnum a
l
      !ue :: Int
ue = forall a. Enum a => a -> Int
fromEnum a
u
  in forall a. Int -> Int -> RangeSet a -> RangeSet a
insertRangeE Int
le Int
ue RangeSet a
t

{-|
Builds a `RangeSet` from a given list of elements.

@since 0.0.1.0
-}
{-# INLINABLE fromList #-}
fromList :: forall a. Enum a => [a] -> RangeSet a
fromList :: forall a. Enum a => [a] -> RangeSet a
fromList [] = forall a. RangeSet a
Tip
fromList (a
x:[a]
xs) = [a]
-> Int -> Int -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [a]
xs (forall a. Enum a => a -> Int
fromEnum a
x) (forall a. Enum a => a -> Int
fromEnum a
x) SRangeList -> SRangeList
id Int
1
  where
    go :: [a] -> E -> E -> (SRangeList -> SRangeList) -> Int -> RangeSet a
    go :: [a]
-> Int -> Int -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [] !Int
l !Int
u SRangeList -> SRangeList
k !Int
n = forall a. SRangeList -> Int -> RangeSet a
fromDistinctAscRangesSz (SRangeList -> SRangeList
k (Int -> Int -> SRangeList -> SRangeList
SRangeCons Int
l Int
u SRangeList
SNil)) Int
n
    go (!a
x:[a]
xs) Int
l Int
u SRangeList -> SRangeList
k Int
n
      -- ordering or uniqueness is broken
      | Int
ex forall a. Ord a => a -> a -> Bool
<= Int
u      = forall a. Int -> RangeSet a -> RangeSet a
insertE Int
ex (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a. Enum a => a -> RangeSet a -> RangeSet a
insert) (forall a. SRangeList -> Int -> RangeSet a
fromDistinctAscRangesSz (SRangeList -> SRangeList
k (Int -> Int -> SRangeList -> SRangeList
SRangeCons Int
l Int
u SRangeList
SNil)) Int
n) [a]
xs)
      -- the current range is expanded
      | Int
ex forall a. Eq a => a -> a -> Bool
== forall a. Enum a => a -> a
succ Int
u = [a]
-> Int -> Int -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [a]
xs Int
l Int
ex SRangeList -> SRangeList
k Int
n
      -- a new range begins
      | Bool
otherwise    = [a]
-> Int -> Int -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [a]
xs Int
ex Int
ex (SRangeList -> SRangeList
k (SRangeList -> SRangeList)
-> (SRangeList -> SRangeList) -> SRangeList -> SRangeList
. Int -> Int -> SRangeList -> SRangeList
SRangeCons Int
l Int
u) (Int
n forall a. Num a => a -> a -> a
+ Int
1)
      where !ex :: Int
ex = forall a. Enum a => a -> Int
fromEnum a
x


-- not sure if this one is any use, it avoids one comparison per element...
{-|
Builds a `RangeSet` from a given list of elements that are in ascending order with no duplicates (this is unchecked).

@since 0.0.1.0
-}
{-# INLINABLE fromDistinctAscList #-}
fromDistinctAscList :: forall a. Enum a => [a] -> RangeSet a
fromDistinctAscList :: forall a. Enum a => [a] -> RangeSet a
fromDistinctAscList [] = forall a. RangeSet a
Tip
fromDistinctAscList (a
x:[a]
xs) = [a]
-> Int -> Int -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [a]
xs (forall a. Enum a => a -> Int
fromEnum a
x) (forall a. Enum a => a -> Int
fromEnum a
x) SRangeList -> SRangeList
id Int
1
  where
    go :: [a] -> E -> E -> (SRangeList -> SRangeList) -> Int -> RangeSet a
    go :: [a]
-> Int -> Int -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [] !Int
l !Int
u SRangeList -> SRangeList
k !Int
n = forall a. SRangeList -> Int -> RangeSet a
fromDistinctAscRangesSz (SRangeList -> SRangeList
k (Int -> Int -> SRangeList -> SRangeList
SRangeCons Int
l Int
u SRangeList
SNil)) Int
n
    go (!a
x:[a]
xs) Int
l Int
u SRangeList -> SRangeList
k Int
n
      -- the current range is expanded
      | Int
ex forall a. Eq a => a -> a -> Bool
== forall a. Enum a => a -> a
succ Int
u = [a]
-> Int -> Int -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [a]
xs Int
l Int
ex SRangeList -> SRangeList
k Int
n
      -- a new range begins
      | Bool
otherwise    = [a]
-> Int -> Int -> (SRangeList -> SRangeList) -> Int -> RangeSet a
go [a]
xs Int
ex Int
ex (SRangeList -> SRangeList
k (SRangeList -> SRangeList)
-> (SRangeList -> SRangeList) -> SRangeList -> SRangeList
. Int -> Int -> SRangeList -> SRangeList
SRangeCons Int
l Int
u) (Int
n forall a. Num a => a -> a -> a
+ Int
1)
      where !ex :: Int
ex = forall a. Enum a => a -> Int
fromEnum a
x