{-# 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

id :: SRangeList -> SRangeList
id :: SRangeList -> SRangeList
id SRangeList
ss = SRangeList
ss

(.) :: (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
-}
fromRanges :: forall a. Enum a => [(a, a)] -> RangeSet a
fromRanges :: [(a, a)] -> RangeSet a
fromRanges [] = RangeSet a
forall a. RangeSet a
Tip
fromRanges ((a
x, a
y):[(a, a)]
rs) = [(a, a)] -> E -> (SRangeList -> SRangeList) -> E -> RangeSet a
go [(a, a)]
rs E
ey (E -> E -> SRangeList -> SRangeList
SRangeCons E
ex E
ey) E
1
  where
    !ex :: E
ex = a -> E
forall a. Enum a => a -> E
fromEnum a
x
    !ey :: E
ey = a -> E
forall a. Enum a => a -> E
fromEnum a
y
    go :: [(a, a)] -> E -> (SRangeList -> SRangeList) -> Int -> RangeSet a
    go :: [(a, a)] -> E -> (SRangeList -> SRangeList) -> E -> RangeSet a
go [] !E
_ SRangeList -> SRangeList
k !E
n = SRangeList -> E -> RangeSet a
forall a. SRangeList -> E -> RangeSet a
fromDistinctAscRangesSz (SRangeList -> SRangeList
k SRangeList
SNil) E
n
    go ((a
x, a
y):[(a, a)]
rs) E
z SRangeList -> SRangeList
k E
n
      -- ordering and disjointness of the ranges broken
      | E
ex E -> E -> Bool
forall a. Ord a => a -> a -> Bool
<= E
z Bool -> Bool -> Bool
|| E
ey E -> E -> Bool
forall a. Ord a => a -> a -> Bool
<= E
z = E -> E -> RangeSet a -> RangeSet a
forall a. E -> E -> RangeSet a -> RangeSet a
insertRangeE E
ex E
ey (((a, a) -> RangeSet a -> RangeSet a)
-> RangeSet a -> [(a, a)] -> RangeSet a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((a -> a -> RangeSet a -> RangeSet a)
-> (a, a) -> RangeSet a -> RangeSet a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> RangeSet a -> RangeSet a
forall a. Enum a => a -> a -> RangeSet a -> RangeSet a
insertRange) (SRangeList -> E -> RangeSet a
forall a. SRangeList -> E -> RangeSet a
fromDistinctAscRangesSz (SRangeList -> SRangeList
k SRangeList
SNil) E
n) [(a, a)]
rs)
      | Bool
otherwise          = [(a, a)] -> E -> (SRangeList -> SRangeList) -> E -> RangeSet a
go [(a, a)]
rs E
ey (SRangeList -> SRangeList
k (SRangeList -> SRangeList)
-> (SRangeList -> SRangeList) -> SRangeList -> SRangeList
. E -> E -> SRangeList -> SRangeList
SRangeCons E
ex E
ey) (E
n E -> E -> E
forall a. Num a => a -> a -> a
+ E
1)
      where
        !ex :: E
ex = a -> E
forall a. Enum a => a -> E
fromEnum a
x
        !ey :: E
ey = a -> E
forall a. Enum a => a -> E
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
-}
fromDistinctAscRanges :: forall a. Enum a => [(a, a)] -> RangeSet a
fromDistinctAscRanges :: [(a, a)] -> RangeSet a
fromDistinctAscRanges [(a, a)]
rs = [(a, a)] -> (SRangeList -> SRangeList) -> E -> RangeSet a
go [(a, a)]
rs SRangeList -> SRangeList
id E
0
  where
    go :: [(a, a)] -> (SRangeList -> SRangeList) -> Int -> RangeSet a
    go :: [(a, a)] -> (SRangeList -> SRangeList) -> E -> RangeSet a
go [] SRangeList -> SRangeList
k !E
n = SRangeList -> E -> RangeSet a
forall a. SRangeList -> E -> RangeSet a
fromDistinctAscRangesSz (SRangeList -> SRangeList
k SRangeList
SNil) E
n
    go ((a
x, a
y):[(a, a)]
rs) SRangeList -> SRangeList
k E
n = [(a, a)] -> (SRangeList -> SRangeList) -> E -> RangeSet a
go [(a, a)]
rs (SRangeList -> SRangeList
k (SRangeList -> SRangeList)
-> (SRangeList -> SRangeList) -> SRangeList -> SRangeList
. E -> E -> SRangeList -> SRangeList
SRangeCons (a -> E
forall a. Enum a => a -> E
fromEnum a
x) (a -> E
forall a. Enum a => a -> E
fromEnum a
y)) (E
n E -> E -> E
forall a. Num a => a -> a -> a
+ E
1)

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

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

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

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