{- |
Module      :  Data.RangeSet.Internal
Description :  Support functions for dealing with distinct ordered range lists
Copyright   :  (c) Dylan Simon 2015
License     :  MIT

Maintainer  :  oleg.grenrus@iki.fi
Stability   :  experimental
Portability :  non-portable (tested with GHC only)

Most functions in this module deal with normalized (closed, fst <= snd,
non-overlapping, non-adjacent, ordered) ranges, but do not check this
assumption.  Most users should use a higher-level interface.
-}
{-# LANGUAGE Safe #-}
module Data.RangeSet.Internal
  ( rangeSize
  , rangeIsSubsetList
  , isSubsetRangeList
  , insertRangeList
  , deleteRangeList
  , unionRangeList
  , differenceRangeList
  , intersectRangeList
  , complementRangeList
  , fromAscElemList
  , fromElemList
  , normalizeRangeList
  , validRangeList
  ) where

import Data.List   (sort)
import Data.Monoid (Sum (..))

-- | Determine the number of items in an 'Enum' range as a 'Sum'
rangeSize :: Enum a => a -> a -> Sum Int
rangeSize :: forall a. Enum a => a -> a -> Sum Int
rangeSize a
a a
b = Int -> Sum Int
forall a. a -> Sum a
Sum (Int -> Sum Int) -> Int -> Sum Int
forall a b. (a -> b) -> a -> b
$ Int -> Int
forall a. Enum a => a -> a
succ (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ a -> Int
forall a. Enum a => a -> Int
fromEnum a
b Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall a. Enum a => a -> Int
fromEnum a
a

-- | Determine if @[x,y]@ is a subset of the list, returning the list right of
-- @y@ if so.
rangeIsSubsetList :: Ord a => a -> a -> [(a, a)] -> Maybe [(a, a)]
rangeIsSubsetList :: forall a. Ord a => a -> a -> [(a, a)] -> Maybe [(a, a)]
rangeIsSubsetList a
x a
y ((a
u,a
v):[(a, a)]
s)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
u = Maybe [(a, a)]
forall a. Maybe a
Nothing
  | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
v = [(a, a)] -> Maybe [(a, a)]
forall a. a -> Maybe a
Just ((a
y,a
v)(a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
:[(a, a)]
s)
  | Bool
otherwise = a -> a -> [(a, a)] -> Maybe [(a, a)]
forall a. Ord a => a -> a -> [(a, a)] -> Maybe [(a, a)]
rangeIsSubsetList a
x a
y [(a, a)]
s
rangeIsSubsetList a
_ a
_ [] = Maybe [(a, a)]
forall a. Maybe a
Nothing

-- | Determine if the first list is a subset of the second.
isSubsetRangeList :: Ord a => [(a, a)] -> [(a, a)] -> Bool
isSubsetRangeList :: forall a. Ord a => [(a, a)] -> [(a, a)] -> Bool
isSubsetRangeList ((a
x,a
y):[(a, a)]
as) [(a, a)]
bs = Bool -> ([(a, a)] -> Bool) -> Maybe [(a, a)] -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False ([(a, a)] -> [(a, a)] -> Bool
forall a. Ord a => [(a, a)] -> [(a, a)] -> Bool
isSubsetRangeList [(a, a)]
as) (Maybe [(a, a)] -> Bool) -> Maybe [(a, a)] -> Bool
forall a b. (a -> b) -> a -> b
$ a -> a -> [(a, a)] -> Maybe [(a, a)]
forall a. Ord a => a -> a -> [(a, a)] -> Maybe [(a, a)]
rangeIsSubsetList a
x a
y [(a, a)]
bs
isSubsetRangeList [] [(a, a)]
_ = Bool
True

-- | Add @[x,y]@.
--
-- There are three possibilities we consider, when inserting into non-empty set:
--
-- * discretely after: continue
-- * discretely before: prepend
-- * overlapping: union and prepend
insertRangeList :: (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
insertRangeList :: forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
insertRangeList a
x a
y set :: [(a, a)]
set@(uv :: (a, a)
uv@(a
u,a
v) : [(a, a)]
xs)
  | a
v a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x Bool -> Bool -> Bool
&& a -> a
forall a. Enum a => a -> a
succ a
v a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
x = (a, a)
uv (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: a -> a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
insertRangeList a
x a
y [(a, a)]
xs
  | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
u Bool -> Bool -> Bool
&& a -> a
forall a. Enum a => a -> a
succ a
y a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
u = (a
x,a
y) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)]
set
  | Bool
otherwise            = a -> a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
prependRangeList (a -> a -> a
forall a. Ord a => a -> a -> a
min a
x a
u) (a -> a -> a
forall a. Ord a => a -> a -> a
max a
y a
v) [(a, a)]
xs
insertRangeList a
x a
y [] = [(a
x,a
y)]

-- | Add @[x,y]@ to the beginning (assuming @x <= u@).
prependRangeList :: (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
prependRangeList :: forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
prependRangeList a
x a
y set :: [(a, a)]
set@((a
u,a
v) : [(a, a)]
xs)
  | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
u Bool -> Bool -> Bool
&& a -> a
forall a. Enum a => a -> a
succ a
y a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
u = (a
x,a
y) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)]
set
  | Bool
otherwise            = a -> a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
prependRangeList a
x (a -> a -> a
forall a. Ord a => a -> a -> a
max a
y a
v) [(a, a)]
xs
prependRangeList a
x a
y [] = [(a
x,a
y)]

-- | Union two range lists.
unionRangeList :: (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
unionRangeList :: forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
unionRangeList aset :: [(a, a)]
aset@(xy :: (a, a)
xy@(a
x,a
y):[(a, a)]
as) bset :: [(a, a)]
bset@(uv :: (a, a)
uv@(a
u,a
v):[(a, a)]
bs)
  | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
u Bool -> Bool -> Bool
&& a -> a
forall a. Enum a => a -> a
succ a
y a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
u = (a, a)
xy (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
unionRangeList [(a, a)]
as [(a, a)]
bset
  | a
v a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x Bool -> Bool -> Bool
&& a -> a
forall a. Enum a => a -> a
succ a
v a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
x = (a, a)
uv (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
unionRangeList [(a, a)]
aset [(a, a)]
bs
  | Bool
otherwise = a -> a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
prependRangeList (a -> a -> a
forall a. Ord a => a -> a -> a
min a
x a
u) (a -> a -> a
forall a. Ord a => a -> a -> a
max a
y a
v) ([(a, a)] -> [(a, a)]) -> [(a, a)] -> [(a, a)]
forall a b. (a -> b) -> a -> b
$ [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
unionRangeList [(a, a)]
as [(a, a)]
bs
unionRangeList [(a, a)]
s [] = [(a, a)]
s
unionRangeList [] [(a, a)]
s = [(a, a)]
s

-- | Remove a range from a range list.
--
-- There are 6 possibilities we consider, when deleting from non-empty set:
--
-- * more
-- * less
-- * strictly inside (splits)
-- * overlapping less-edge
-- * overlapping more-edge
-- * stricly larger
deleteRangeList :: (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
deleteRangeList :: forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
deleteRangeList a
x a
y set :: [(a, a)]
set@(s :: (a, a)
s@(a
u,a
v) : [(a, a)]
xs)
  | a
v a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x = (a, a)
s (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: a -> a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
deleteRangeList a
x a
y [(a, a)]
xs
  | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
u = [(a, a)]
set
  | a
u a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x = (a
u, a -> a
forall a. Enum a => a -> a
pred a
x) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)]
t
  | Bool
otherwise = [(a, a)]
t where
  t :: [(a, a)]
t = a -> a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
trimRangeList' a
y a
v [(a, a)]
xs
deleteRangeList a
_ a
_ [] = []

-- | Remove @(,y]@ while (re-)adding @(y,v]@ if valid
trimRangeList' :: (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
trimRangeList' :: forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
trimRangeList' a
y a
v [(a, a)]
xs
  | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
v = (a -> a
forall a. Enum a => a -> a
succ a
y, a
v) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)]
xs
  | Bool
otherwise = a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => a -> [(a, a)] -> [(a, a)]
trimRangeList a
y [(a, a)]
xs

-- | Remove @(,y]@
trimRangeList :: (Ord a, Enum a) => a -> [(a, a)] -> [(a, a)]
trimRangeList :: forall a. (Ord a, Enum a) => a -> [(a, a)] -> [(a, a)]
trimRangeList a
y set :: [(a, a)]
set@((a
u,a
v) : [(a, a)]
xs)
  | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
u = [(a, a)]
set
  | Bool
otherwise = a -> a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
trimRangeList' a
y a
v [(a, a)]
xs
trimRangeList a
_ [] = []

-- | Compute the set difference, removing each range in the second list from
-- the first.
differenceRangeList :: (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
differenceRangeList :: forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
differenceRangeList aset :: [(a, a)]
aset@(xy :: (a, a)
xy@(a
x,a
y):[(a, a)]
as) bset :: [(a, a)]
bset@((a
u,a
v):[(a, a)]
bs)
  | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
u = (a, a)
xy (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
differenceRangeList [(a, a)]
as [(a, a)]
bset
  | a
v a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x = [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
differenceRangeList [(a, a)]
aset [(a, a)]
bs
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
u = (a
x, a -> a
forall a. Enum a => a -> a
pred a
u) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)]
t
  | Bool
otherwise = [(a, a)]
t where
  t :: [(a, a)]
t = [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
differenceRangeList (a -> a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
trimRangeList' a
v a
y [(a, a)]
as) [(a, a)]
bs
differenceRangeList [(a, a)]
s [] = [(a, a)]
s
differenceRangeList [] [(a, a)]
_ = []

-- | Compute the intersection.
intersectRangeList :: Ord a => [(a, a)] -> [(a, a)] -> [(a, a)]
intersectRangeList :: forall a. Ord a => [(a, a)] -> [(a, a)] -> [(a, a)]
intersectRangeList aset :: [(a, a)]
aset@((a
x,a
y):[(a, a)]
as) bset :: [(a, a)]
bset@((a
u,a
v):[(a, a)]
bs)
  | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
u = [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. Ord a => [(a, a)] -> [(a, a)] -> [(a, a)]
intersectRangeList [(a, a)]
as [(a, a)]
bset
  | a
v a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x = [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. Ord a => [(a, a)] -> [(a, a)] -> [(a, a)]
intersectRangeList [(a, a)]
aset [(a, a)]
bs
  | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
v = (a -> a -> a
forall a. Ord a => a -> a -> a
max a
x a
u, a
y) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. Ord a => [(a, a)] -> [(a, a)] -> [(a, a)]
intersectRangeList [(a, a)]
as [(a, a)]
bset
  | Bool
otherwise = (a -> a -> a
forall a. Ord a => a -> a -> a
max a
x a
u, a
v) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. Ord a => [(a, a)] -> [(a, a)] -> [(a, a)]
intersectRangeList [(a, a)]
aset [(a, a)]
bs
intersectRangeList [(a, a)]
_ [] = []
intersectRangeList [] [(a, a)]
_ = []

-- | Compute the complement intersected with @[x,)@ assuming @x<u@.
complementRangeList' :: (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> [(a, a)]
complementRangeList' :: forall a. (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> [(a, a)]
complementRangeList' a
x ((a
u,a
v):[(a, a)]
s) = (a
x,a -> a
forall a. Enum a => a -> a
pred a
u) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> [(a, a)]
complementRangeList'' a
v [(a, a)]
s
complementRangeList' a
x [] = [(a
x,a
forall a. Bounded a => a
maxBound)]

-- | Compute the complement intersected with @(x,)@.
complementRangeList'' :: (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> [(a, a)]
complementRangeList'' :: forall a. (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> [(a, a)]
complementRangeList'' a
x [(a, a)]
s
  | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. Bounded a => a
maxBound = []
  | Bool
otherwise = a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> [(a, a)]
complementRangeList' (a -> a
forall a. Enum a => a -> a
succ a
x) [(a, a)]
s

-- | Compute the complement.
complementRangeList :: (Ord a, Enum a, Bounded a) => [(a, a)] -> [(a, a)]
complementRangeList :: forall a. (Ord a, Enum a, Bounded a) => [(a, a)] -> [(a, a)]
complementRangeList s :: [(a, a)]
s@((a
x,a
y):[(a, a)]
s')
  | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. Bounded a => a
minBound = a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> [(a, a)]
complementRangeList'' a
y [(a, a)]
s'
  | Bool
otherwise = a -> [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> [(a, a)]
complementRangeList' a
forall a. Bounded a => a
minBound [(a, a)]
s
complementRangeList [] = [(a
forall a. Bounded a => a
minBound, a
forall a. Bounded a => a
maxBound)]

-- | Take elements off the beginning of the list while they are equal or
-- adjacent to the given item, and return the last removed item and remaining
-- list.
takeWhileAdj :: (Eq a, Enum a) => a -> [a] -> (a, [a])
takeWhileAdj :: forall a. (Eq a, Enum a) => a -> [a] -> (a, [a])
takeWhileAdj a
x yl :: [a]
yl@(a
y:[a]
l)
  | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y Bool -> Bool -> Bool
|| a -> a
forall a. Enum a => a -> a
succ a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y = a -> [a] -> (a, [a])
forall a. (Eq a, Enum a) => a -> [a] -> (a, [a])
takeWhileAdj a
y [a]
l
  | Bool
otherwise = (a
x, [a]
yl)
takeWhileAdj a
x [] = (a
x, [])

-- | Take ranges off the beginning of a unnormalized but sorted and valid range
-- list while they are overlapping or adjacent to the given value, and return
-- the last removed item and remaining list.
takeWhileRangeAdj :: (Ord a, Enum a) => a -> [(a,a)] -> (a, [(a,a)])
takeWhileRangeAdj :: forall a. (Ord a, Enum a) => a -> [(a, a)] -> (a, [(a, a)])
takeWhileRangeAdj a
x yzl :: [(a, a)]
yzl@((a
y,a
z):[(a, a)]
l)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
y Bool -> Bool -> Bool
|| a -> a
forall a. Enum a => a -> a
succ a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y = a -> [(a, a)] -> (a, [(a, a)])
forall a. (Ord a, Enum a) => a -> [(a, a)] -> (a, [(a, a)])
takeWhileRangeAdj (a -> a -> a
forall a. Ord a => a -> a -> a
max a
x a
z) [(a, a)]
l
  | Bool
otherwise = (a
x, [(a, a)]
yzl)
takeWhileRangeAdj a
x [] = (a
x, [])

-- | Normalize a sorted list of elements to a range list.
fromAscElemList :: (Eq a, Enum a) => [a] -> [(a, a)]
fromAscElemList :: forall a. (Eq a, Enum a) => [a] -> [(a, a)]
fromAscElemList (a
x:[a]
l) = (a
x, a
y) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [a] -> [(a, a)]
forall a. (Eq a, Enum a) => [a] -> [(a, a)]
fromAscElemList [a]
l' where
  (a
y, [a]
l') = a -> [a] -> (a, [a])
forall a. (Eq a, Enum a) => a -> [a] -> (a, [a])
takeWhileAdj a
x [a]
l
fromAscElemList [] = []

-- | Normalize an arbitrary list of elements to a range list.
fromElemList :: (Ord a, Enum a) => [a] -> [(a, a)]
fromElemList :: forall a. (Ord a, Enum a) => [a] -> [(a, a)]
fromElemList = [a] -> [(a, a)]
forall a. (Eq a, Enum a) => [a] -> [(a, a)]
fromAscElemList ([a] -> [(a, a)]) -> ([a] -> [a]) -> [a] -> [(a, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. Ord a => [a] -> [a]
sort

-- | Normalize a sorted list of valid ranges.
mergeRangeList :: (Ord a, Enum a) => [(a, a)] -> [(a, a)]
mergeRangeList :: forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)]
mergeRangeList ((a
x,a
y):[(a, a)]
l) = (a
x,a
y') (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)]
mergeRangeList [(a, a)]
l' where
  (a
y', [(a, a)]
l') = a -> [(a, a)] -> (a, [(a, a)])
forall a. (Ord a, Enum a) => a -> [(a, a)] -> (a, [(a, a)])
takeWhileRangeAdj a
y [(a, a)]
l
mergeRangeList [] = []

-- | Normalize an arbitrary list of ranges.
normalizeRangeList :: (Ord a, Enum a) => [(a, a)] -> [(a, a)]
normalizeRangeList :: forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)]
normalizeRangeList = [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)]
mergeRangeList ([(a, a)] -> [(a, a)])
-> ([(a, a)] -> [(a, a)]) -> [(a, a)] -> [(a, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(a, a)] -> [(a, a)]
forall a. Ord a => [a] -> [a]
sort ([(a, a)] -> [(a, a)])
-> ([(a, a)] -> [(a, a)]) -> [(a, a)] -> [(a, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, a) -> Bool) -> [(a, a)] -> [(a, a)]
forall a. (a -> Bool) -> [a] -> [a]
filter (a, a) -> Bool
forall {a}. Ord a => (a, a) -> Bool
valid where
  valid :: (a, a) -> Bool
valid (a
x,a
y) = a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y

-- | Check if a list is normalized and strictly above @b@.
validRangeList' :: (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> Bool
validRangeList' :: forall a. (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> Bool
validRangeList' a
b ((a
x,a
y):[(a, a)]
s) = a
b a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
forall a. Bounded a => a
maxBound Bool -> Bool -> Bool
&& a -> a
forall a. Enum a => a -> a
succ a
b a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x Bool -> Bool -> Bool
&& a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y Bool -> Bool -> Bool
&& a -> [(a, a)] -> Bool
forall a. (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> Bool
validRangeList' a
y [(a, a)]
s
validRangeList' a
_ [] = Bool
True

-- | Check if a list is normalized.
validRangeList :: (Ord a, Enum a, Bounded a) => [(a, a)] -> Bool
validRangeList :: forall a. (Ord a, Enum a, Bounded a) => [(a, a)] -> Bool
validRangeList ((a
x,a
y):[(a, a)]
s) = a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y Bool -> Bool -> Bool
&& a -> [(a, a)] -> Bool
forall a. (Ord a, Enum a, Bounded a) => a -> [(a, a)] -> Bool
validRangeList' a
y [(a, a)]
s
validRangeList [] = Bool
True