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