{- |
Module      :  Data.RangeSet.List
Description :  A trivial implementation of range sets
Copyright   :  (c) Oleg Grenrus 2014
License     :  MIT

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

A trivial implementation of range sets.

This module is intended to be imported qualified, to avoid name
clashes with Prelude functions, e.g.

>  import Data.RangeSet.List (RSet)
>  import qualified Data.RangeSet.List as RSet

The implementation of 'RSet' is based on /list/.

Compared to 'Data.Set', this module imposes also 'Enum' restriction for many
functions.  We must be able to identify consecutive elements to be able to
/glue/ and /split/ ranges properly.

The implementation assumes that

> x < succ x
> pred x < x

and there aren't elements in between (not true for 'Float' and 'Double').  Also
'succ' and 'pred' are never called for largest or smallest value respectively.
-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE Safe               #-}
module Data.RangeSet.List (
  -- * Range set type
  RSet

  -- * Operators
  , (\\)

  -- * Query
  , null
  , isFull
  , size
  , member
  , notMember
  , lookupLT
  , lookupGT
  , lookupLE
  , lookupGE
  , containsRange
  , isSubsetOf
  , valid

  -- * Construction
  , empty
  , full
  , singleton
  , singletonRange
  , insert
  , insertRange
  , delete
  , deleteRange

  -- * Combine
  , union
  , difference
  , intersection

  -- * Filter
  , split
  , splitMember

  -- * Min/Max
  , findMin
  , findMax

  -- * Complement
  , complement

  -- * Conversion
  , elems
  , toList
  , fromList
  , fromAscList
  , toAscList
  , toRangeList
  , fromRangeList
  , fromNormalizedRangeList
  , toSet

  ) where

import           Prelude hiding (filter, foldl, foldr, map, null)
import qualified Prelude

import           Control.DeepSeq (NFData (..))
import           Data.Foldable   (foldMap)
import           Data.Hashable   (Hashable (..))
import           Data.Maybe      (isJust)
import           Data.Monoid     (Monoid (..), getSum)
import           Data.Semigroup  (Semigroup (..))
import qualified Data.Set        as Set
import           Data.Typeable   (Typeable)

import Data.RangeSet.Internal

-- | Internally set is represented as sorted list of distinct inclusive ranges.
newtype RSet a = RSet [(a, a)]
  deriving (RSet a -> RSet a -> Bool
(RSet a -> RSet a -> Bool)
-> (RSet a -> RSet a -> Bool) -> Eq (RSet a)
forall a. Eq a => RSet a -> RSet a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => RSet a -> RSet a -> Bool
== :: RSet a -> RSet a -> Bool
$c/= :: forall a. Eq a => RSet a -> RSet a -> Bool
/= :: RSet a -> RSet a -> Bool
Eq, Eq (RSet a)
Eq (RSet a) =>
(RSet a -> RSet a -> Ordering)
-> (RSet a -> RSet a -> Bool)
-> (RSet a -> RSet a -> Bool)
-> (RSet a -> RSet a -> Bool)
-> (RSet a -> RSet a -> Bool)
-> (RSet a -> RSet a -> RSet a)
-> (RSet a -> RSet a -> RSet a)
-> Ord (RSet a)
RSet a -> RSet a -> Bool
RSet a -> RSet a -> Ordering
RSet a -> RSet a -> RSet a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (RSet a)
forall a. Ord a => RSet a -> RSet a -> Bool
forall a. Ord a => RSet a -> RSet a -> Ordering
forall a. Ord a => RSet a -> RSet a -> RSet a
$ccompare :: forall a. Ord a => RSet a -> RSet a -> Ordering
compare :: RSet a -> RSet a -> Ordering
$c< :: forall a. Ord a => RSet a -> RSet a -> Bool
< :: RSet a -> RSet a -> Bool
$c<= :: forall a. Ord a => RSet a -> RSet a -> Bool
<= :: RSet a -> RSet a -> Bool
$c> :: forall a. Ord a => RSet a -> RSet a -> Bool
> :: RSet a -> RSet a -> Bool
$c>= :: forall a. Ord a => RSet a -> RSet a -> Bool
>= :: RSet a -> RSet a -> Bool
$cmax :: forall a. Ord a => RSet a -> RSet a -> RSet a
max :: RSet a -> RSet a -> RSet a
$cmin :: forall a. Ord a => RSet a -> RSet a -> RSet a
min :: RSet a -> RSet a -> RSet a
Ord, Typeable)

instance Show a => Show (RSet a) where
  showsPrec :: Int -> RSet a -> ShowS
showsPrec Int
d RSet a
x = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10)
    (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"fromRangeList "
    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [(a, a)] -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList RSet a
x)

instance (Ord a, Enum a) => Semigroup (RSet a) where
    <> :: RSet a -> RSet a -> RSet a
(<>) = RSet a -> RSet a -> RSet a
forall a. (Ord a, Enum a) => RSet a -> RSet a -> RSet a
union

instance (Ord a, Enum a) => Monoid (RSet a) where
    mempty :: RSet a
mempty  = RSet a
forall a. RSet a
empty
    mappend :: RSet a -> RSet a -> RSet a
mappend = RSet a -> RSet a -> RSet a
forall a. (Ord a, Enum a) => RSet a -> RSet a -> RSet a
union

instance Hashable a => Hashable (RSet a) where
    hashWithSalt :: Int -> RSet a -> Int
hashWithSalt Int
salt (RSet [(a, a)]
xs) = Int -> [(a, a)] -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt [(a, a)]
xs

instance NFData a => NFData (RSet a) where
    rnf :: RSet a -> ()
rnf (RSet [(a, a)]
xs) = [(a, a)] -> ()
forall a. NFData a => a -> ()
rnf [(a, a)]
xs

{- Operators -}
infixl 9 \\ --

-- | /O(n+m)/. See 'difference'.
(\\) :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a
RSet a
m1 \\ :: forall a. (Ord a, Enum a) => RSet a -> RSet a -> RSet a
\\ RSet a
m2 = RSet a -> RSet a -> RSet a
forall a. (Ord a, Enum a) => RSet a -> RSet a -> RSet a
difference RSet a
m1 RSet a
m2

{- Query -}

-- | /O(1)/. Is this the empty set?
null :: RSet a -> Bool
null :: forall a. RSet a -> Bool
null = [(a, a)] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Prelude.null ([(a, a)] -> Bool) -> (RSet a -> [(a, a)]) -> RSet a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList

-- | /O(1)/. Is this the full set?
isFull :: (Eq a, Bounded a) => RSet a -> Bool
isFull :: forall a. (Eq a, Bounded a) => RSet a -> Bool
isFull = RSet a -> RSet a -> Bool
forall a. Eq a => a -> a -> Bool
(==) RSet a
forall a. Bounded a => RSet a
full

-- | /O(n)/. The number of the elements in the set.
size :: Enum a => RSet a -> Int
size :: forall a. Enum a => RSet a -> Int
size (RSet [(a, a)]
xs) = Sum Int -> Int
forall a. Sum a -> a
getSum (Sum Int -> Int) -> Sum Int -> Int
forall a b. (a -> b) -> a -> b
$ ((a, a) -> Sum Int) -> [(a, a)] -> Sum Int
forall m a. Monoid m => (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ((a -> a -> Sum Int) -> (a, a) -> Sum Int
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> Sum Int
forall a. Enum a => a -> a -> Sum Int
rangeSize) [(a, a)]
xs

-- | /O(n)/. Is the element in the set?
member :: Ord a => a -> RSet a -> Bool
member :: forall a. Ord a => a -> RSet a -> Bool
member a
x (RSet [(a, a)]
xs) = [(a, a)] -> Bool
f [(a, a)]
xs where
  f :: [(a, a)] -> Bool
f ((a
a,a
b):[(a, a)]
s)
    | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
a = Bool
False
    | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
b = Bool
True
    | Bool
otherwise = [(a, a)] -> Bool
f [(a, a)]
s
  f [] = Bool
False

-- | /O(n)/. Is the element not in the set?
notMember :: Ord a => a -> RSet a -> Bool
notMember :: forall a. Ord a => a -> RSet a -> Bool
notMember a
a RSet a
r = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ a -> RSet a -> Bool
forall a. Ord a => a -> RSet a -> Bool
member a
a RSet a
r

-- | /O(n)/. Find largest element smaller than the given one.
lookupLT :: (Ord a, Enum a) => a -> RSet a -> Maybe a
lookupLT :: forall a. (Ord a, Enum a) => a -> RSet a -> Maybe a
lookupLT a
x (RSet [(a, a)]
xs) = Maybe a -> [(a, a)] -> Maybe a
f Maybe a
forall a. Maybe a
Nothing [(a, a)]
xs where
  f :: Maybe a -> [(a, a)] -> Maybe a
f Maybe a
l ((a
a,a
b):[(a, a)]
s)
    | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
a = Maybe a
l
    | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
b Bool -> Bool -> Bool
|| a -> a
forall a. Enum a => a -> a
pred a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b = a -> Maybe a
forall a. a -> Maybe a
Just (a -> a
forall a. Enum a => a -> a
pred a
x)
    | Bool
otherwise = Maybe a -> [(a, a)] -> Maybe a
f (a -> Maybe a
forall a. a -> Maybe a
Just a
b) [(a, a)]
s
  f Maybe a
l [] = Maybe a
l

-- | /O(n)/. Find smallest element greater than the given one.
lookupGT :: (Ord a, Enum a) => a -> RSet a -> Maybe a
lookupGT :: forall a. (Ord a, Enum a) => a -> RSet a -> Maybe a
lookupGT a
x (RSet [(a, a)]
xs) = [(a, a)] -> Maybe a
f [(a, a)]
xs where
  f :: [(a, a)] -> Maybe a
f ((a
a,a
b):[(a, a)]
s)
    | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
a = a -> Maybe a
forall a. a -> Maybe a
Just a
a
    | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
b = a -> Maybe a
forall a. a -> Maybe a
Just (a -> a
forall a. Enum a => a -> a
succ a
x)
    | Bool
otherwise = [(a, a)] -> Maybe a
f [(a, a)]
s
  f [] = Maybe a
forall a. Maybe a
Nothing

-- | /O(n)/. Find largest element smaller or equal to than the given one.
lookupLE :: Ord a => a -> RSet a -> Maybe a
lookupLE :: forall a. Ord a => a -> RSet a -> Maybe a
lookupLE a
x (RSet [(a, a)]
xs) = Maybe a -> [(a, a)] -> Maybe a
f Maybe a
forall a. Maybe a
Nothing [(a, a)]
xs where
  f :: Maybe a -> [(a, a)] -> Maybe a
f Maybe a
l ((a
a,a
b):[(a, a)]
s)
    | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
a = Maybe a
l
    | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
b = a -> Maybe a
forall a. a -> Maybe a
Just a
x
    | Bool
otherwise = Maybe a -> [(a, a)] -> Maybe a
f (a -> Maybe a
forall a. a -> Maybe a
Just a
b) [(a, a)]
s
  f Maybe a
l [] = Maybe a
l

-- | /O(n)/. Find smallest element greater or equal to than the given one.
lookupGE :: Ord a => a -> RSet a -> Maybe a
lookupGE :: forall a. Ord a => a -> RSet a -> Maybe a
lookupGE a
x (RSet [(a, a)]
xs) = [(a, a)] -> Maybe a
f [(a, a)]
xs where
  f :: [(a, a)] -> Maybe a
f ((a
a,a
b):[(a, a)]
s)
    | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
a = a -> Maybe a
forall a. a -> Maybe a
Just a
a
    | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
b = a -> Maybe a
forall a. a -> Maybe a
Just a
x
    | Bool
otherwise = [(a, a)] -> Maybe a
f [(a, a)]
s
  f [] = Maybe a
forall a. Maybe a
Nothing

-- | /O(n)/. Is the entire range contained within the set?
containsRange :: Ord a => (a, a) -> RSet a -> Bool
containsRange :: forall a. Ord a => (a, a) -> RSet a -> Bool
containsRange (a
x,a
y) (RSet [(a, a)]
xs)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y = Maybe [(a, a)] -> Bool
forall a. Maybe a -> Bool
isJust (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)]
xs
  | Bool
otherwise = Bool
True

-- | /O(n+m)/. Is this a subset?
-- @(s1 `isSubsetOf` s2)@ tells whether @s1@ is a subset of @s2@.
isSubsetOf :: Ord a => RSet a -> RSet a -> Bool
isSubsetOf :: forall a. Ord a => RSet a -> RSet a -> Bool
isSubsetOf (RSet [(a, a)]
xs) (RSet [(a, a)]
ys) = [(a, a)] -> [(a, a)] -> Bool
forall a. Ord a => [(a, a)] -> [(a, a)] -> Bool
isSubsetRangeList [(a, a)]
xs [(a, a)]
ys

-- MISSING: isProperSubsetOf isRangeProperSubsetOf? overlapsRange?

{- Construction -}

-- | /O(1)/. The empty set.
empty :: RSet a
empty :: forall a. RSet a
empty = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet []

-- | /O(1)/. The full set.
full :: Bounded a => RSet a
full :: forall a. Bounded a => RSet a
full = a -> a -> RSet a
forall a. a -> a -> RSet a
singletonRange' a
forall a. Bounded a => a
minBound a
forall a. Bounded a => a
maxBound

singletonRange' :: a -> a -> RSet a
singletonRange' :: forall a. a -> a -> RSet a
singletonRange' a
x a
y = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet [(a
x, a
y)]

-- | /O(1)/. Create a singleton set.
singleton :: a -> RSet a
singleton :: forall a. a -> RSet a
singleton a
x = a -> a -> RSet a
forall a. a -> a -> RSet a
singletonRange' a
x a
x

-- | /O(1)/. Create a continuos range set.
singletonRange :: Ord a => (a, a) -> RSet a
singletonRange :: forall a. Ord a => (a, a) -> RSet a
singletonRange (a
x, a
y) | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y     = RSet a
forall a. RSet a
empty
                      | Bool
otherwise = a -> a -> RSet a
forall a. a -> a -> RSet a
singletonRange' a
x a
y

{- Construction -}

-- | /O(n)/. Insert an element in a set.
insert :: (Ord a, Enum a) => a -> RSet a -> RSet a
insert :: forall a. (Ord a, Enum a) => a -> RSet a -> RSet a
insert a
x (RSet [(a, a)]
xs) = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ([(a, a)] -> RSet a) -> [(a, a)] -> RSet 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)]
insertRangeList a
x a
x [(a, a)]
xs

-- | /O(n)/. Insert a continuos range in a set.
insertRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a
insertRange :: forall a. (Ord a, Enum a) => (a, a) -> RSet a -> RSet a
insertRange (a
x, a
y) set :: RSet a
set@(RSet [(a, a)]
xs)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y      = RSet a
set
  | Bool
otherwise  = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ([(a, a)] -> RSet a) -> [(a, a)] -> RSet 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)]
insertRangeList a
x a
y [(a, a)]
xs

-- | /O(n). Delete an element from a set.
delete :: (Ord a, Enum a) => a -> RSet a -> RSet a
delete :: forall a. (Ord a, Enum a) => a -> RSet a -> RSet a
delete a
x (RSet [(a, a)]
xs) = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ([(a, a)] -> RSet a) -> [(a, a)] -> RSet 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)]
deleteRangeList a
x a
x [(a, a)]
xs

-- | /O(n). Delete a continuos range from a set.
deleteRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a
deleteRange :: forall a. (Ord a, Enum a) => (a, a) -> RSet a -> RSet a
deleteRange (a
x, a
y) set :: RSet a
set@(RSet [(a, a)]
xs)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y      = RSet a
set
  | Bool
otherwise  = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ([(a, a)] -> RSet a) -> [(a, a)] -> RSet 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)]
deleteRangeList a
x a
y [(a, a)]
xs

{- Combination -}

-- | /O(n+m)/. The union of two sets.
union :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a
union :: forall a. (Ord a, Enum a) => RSet a -> RSet a -> RSet a
union (RSet [(a, a)]
xs) (RSet [(a, a)]
ys) = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ([(a, a)] -> RSet a) -> [(a, a)] -> RSet 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)]
xs [(a, a)]
ys

-- | /O(n+m)/. Difference of two sets.
difference :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a
difference :: forall a. (Ord a, Enum a) => RSet a -> RSet a -> RSet a
difference (RSet [(a, a)]
xs) (RSet [(a, a)]
ys) = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ([(a, a)] -> RSet a) -> [(a, a)] -> RSet 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)]
differenceRangeList [(a, a)]
xs [(a, a)]
ys

-- | /O(n+m)/. The intersection of two sets.
intersection :: (Ord a) => RSet a -> RSet a -> RSet a
intersection :: forall a. Ord a => RSet a -> RSet a -> RSet a
intersection (RSet [(a, a)]
xs) (RSet [(a, a)]
ys) = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ([(a, a)] -> RSet a) -> [(a, a)] -> RSet a
forall a b. (a -> b) -> a -> b
$ [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. Ord a => [(a, a)] -> [(a, a)] -> [(a, a)]
intersectRangeList [(a, a)]
xs [(a, a)]
ys

{- Complement -}

-- | /O(n)/. Complement of the set.
complement :: (Ord a, Enum a, Bounded a) => RSet a -> RSet a
complement :: forall a. (Ord a, Enum a, Bounded a) => RSet a -> RSet a
complement (RSet [(a, a)]
xs) = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ([(a, a)] -> RSet a) -> [(a, a)] -> RSet a
forall a b. (a -> b) -> a -> b
$ [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a, Bounded a) => [(a, a)] -> [(a, a)]
complementRangeList [(a, a)]
xs

{- Filter -}

-- MISSING: filter partition filterRanges? partitionRanges?

-- | /O(n)/. The expression (@'split' x set@) is a pair @(set1,set2)@
-- where @set1@ comprises the elements of @set@ less than @x@ and @set2@
-- comprises the elements of @set@ greater than @x@.
split :: (Ord a, Enum a) => a -> RSet a -> (RSet a, RSet a)
split :: forall a. (Ord a, Enum a) => a -> RSet a -> (RSet a, RSet a)
split a
x RSet a
s = (RSet a
l, RSet a
r) where (RSet a
l, Bool
_, RSet a
r) = a -> RSet a -> (RSet a, Bool, RSet a)
forall a. (Ord a, Enum a) => a -> RSet a -> (RSet a, Bool, RSet a)
splitMember a
x RSet a
s

-- | /O(n)/. Performs a 'split' but also returns whether the pivot
-- element was found in the original set.
splitMember :: (Ord a, Enum a) => a -> RSet a -> (RSet a, Bool, RSet a)
splitMember :: forall a. (Ord a, Enum a) => a -> RSet a -> (RSet a, Bool, RSet a)
splitMember a
x (RSet [(a, a)]
xs) = [(a, a)] -> (RSet a, Bool, RSet a)
f [(a, a)]
xs where
  f :: [(a, a)] -> (RSet a, Bool, RSet a)
f s :: [(a, a)]
s@(r :: (a, a)
r@(a
a,a
b):[(a, a)]
s') = case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
a of
    Ordering
LT -> (RSet a
forall a. RSet a
empty, Bool
False, [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet [(a, a)]
s)
    Ordering
EQ -> (RSet a
forall a. RSet a
empty, Bool
True, [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet [(a, a)]
xs')
    Ordering
GT
      | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
b -> ([(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet [(a
a, a -> a
forall a. Enum a => a -> a
pred a
x)], Bool
True, [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet [(a, a)]
xs')
      | Bool
otherwise -> (a, a) -> (RSet a, Bool, RSet a) -> (RSet a, Bool, RSet a)
forall {a} {b} {a}.
(a, a) -> (RSet a, b, RSet a) -> (RSet a, b, RSet a)
push (a, a)
r ((RSet a, Bool, RSet a) -> (RSet a, Bool, RSet a))
-> (RSet a, Bool, RSet a) -> (RSet a, Bool, RSet a)
forall a b. (a -> b) -> a -> b
$ [(a, a)] -> (RSet a, Bool, RSet a)
f [(a, a)]
s'
    where
    xs' :: [(a, a)]
xs'
      | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
b = (a -> a
forall a. Enum a => a -> a
succ a
x,a
b)(a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
:[(a, a)]
s'
      | Bool
otherwise = [(a, a)]
s'
  f [] = (RSet a
forall a. RSet a
empty, Bool
False, RSet a
forall a. RSet a
empty)
  push :: (a, a) -> (RSet a, b, RSet a) -> (RSet a, b, RSet a)
push (a, a)
r (RSet [(a, a)]
ls, b
b, RSet [(a, a)]
rs) = ([(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ((a, a)
r(a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
:[(a, a)]
ls), b
b, [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet [(a, a)]
rs)

-- MISSING: lookupIndex findIndex elemAt deleteAt map mapMonotonic fold*
-- mapMonotonic may be reasonable as just need to map range endpoints and check adjacency

{- Min/Max -}

-- | /O(1)/. The minimal element of a set.
findMin :: RSet a -> a
findMin :: forall a. RSet a -> a
findMin (RSet ((a
x, a
_) : [(a, a)]
_))  = a
x
findMin RSet a
_                    = String -> a
forall a. HasCallStack => String -> a
error String
"RangeSet.List.findMin: empty set"

-- | /O(n)/. The maximal element of a set.
findMax :: RSet a -> a
findMax :: forall a. RSet a -> a
findMax (RSet [(a, a)]
rs) = [(a, a)] -> a
forall {a} {b}. [(a, b)] -> b
findMax' [(a, a)]
rs
  where findMax' :: [(a, b)] -> b
findMax' [(a
_, b
x)]  = b
x
        findMax' ((a, b)
_:[(a, b)]
xs)    = [(a, b)] -> b
findMax' [(a, b)]
xs
        findMax' [(a, b)]
_         = String -> b
forall a. HasCallStack => String -> a
error String
"RangeSet.List.findMax: empty set"

-- MISSING: deleteMin deleteMax deleteFindMin deleteFindMax minView maxView

{- Conversion -}

-- | /O(n*r)/. An alias of 'toAscList'. The elements of a set in ascending
-- order. /r/ is the size of longest range.
elems :: Enum a => RSet a -> [a]
elems :: forall a. Enum a => RSet a -> [a]
elems = RSet a -> [a]
forall a. Enum a => RSet a -> [a]
toAscList

-- | /O(n*r)/. Convert the set to a list of elements. /r/ is the size of
-- longest range.
toList :: Enum a => RSet a -> [a]
toList :: forall a. Enum a => RSet a -> [a]
toList (RSet [(a, a)]
xs) = ((a, a) -> [a]) -> [(a, a)] -> [a]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap ((a -> a -> [a]) -> (a, a) -> [a]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromTo) [(a, a)]
xs

-- | /O(n*log n)/. Create a set from a list of elements.
fromList :: (Ord a, Enum a) => [a] -> RSet a
fromList :: forall a. (Ord a, Enum a) => [a] -> RSet a
fromList = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ([(a, a)] -> RSet a) -> ([a] -> [(a, a)]) -> [a] -> RSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [(a, a)]
forall a. (Ord a, Enum a) => [a] -> [(a, a)]
fromElemList

-- | /O(n)/. Create a set from a list of ascending elements.
--
-- /The precondition is not checked./  You may use 'valid' to check the result.
fromAscList :: (Ord a, Enum a) => [a] -> RSet a
fromAscList :: forall a. (Ord a, Enum a) => [a] -> RSet a
fromAscList = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ([(a, a)] -> RSet a) -> ([a] -> [(a, a)]) -> [a] -> RSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [(a, a)]
forall a. (Eq a, Enum a) => [a] -> [(a, a)]
fromAscElemList

-- | /O(n*r)/. Convert the set to an ascending list of elements.
toAscList :: Enum a => RSet a -> [a]
toAscList :: forall a. Enum a => RSet a -> [a]
toAscList = RSet a -> [a]
forall a. Enum a => RSet a -> [a]
toList

-- | /O(1)/. Convert the set to a list of range pairs.
toRangeList :: RSet a -> [(a, a)]
toRangeList :: forall a. RSet a -> [(a, a)]
toRangeList (RSet [(a, a)]
xs) = [(a, a)]
xs

-- | /O(n*log n)/. Create a set from a list of range pairs.
fromRangeList :: (Ord a, Enum a) => [(a, a)] -> RSet a
fromRangeList :: forall a. (Ord a, Enum a) => [(a, a)] -> RSet a
fromRangeList = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet ([(a, a)] -> RSet a)
-> ([(a, a)] -> [(a, a)]) -> [(a, a)] -> RSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)]
normalizeRangeList

-- | /O(n*r)/. Convert the set to a 'Set.Set' of elements. /r/ is the size of
-- longest range.
toSet :: Enum a => RSet a -> Set.Set a
toSet :: forall a. Enum a => RSet a -> Set a
toSet = [a] -> Set a
forall a. [a] -> Set a
Set.fromDistinctAscList ([a] -> Set a) -> (RSet a -> [a]) -> RSet a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RSet a -> [a]
forall a. Enum a => RSet a -> [a]
toAscList

-- | /O(1)/. Convert a normalized, non-adjacent, ascending list of ranges to a
-- set.
--
-- /The precondition is not checked./  In general you should only use this
-- function on the result of 'toRangeList' or ensure 'valid' on the result.
fromNormalizedRangeList :: [(a, a)] -> RSet a
fromNormalizedRangeList :: forall a. [(a, a)] -> RSet a
fromNormalizedRangeList = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RSet

-- | /O(n)/. Ensure that a set is valid. All functions should return valid sets
-- except those with unchecked preconditions: 'fromAscList',
-- 'fromNormalizedRangeList'
valid :: (Ord a, Enum a, Bounded a) => RSet a -> Bool
valid :: forall a. (Ord a, Enum a, Bounded a) => RSet a -> Bool
valid (RSet [(a, a)]
xs) = [(a, a)] -> Bool
forall a. (Ord a, Enum a, Bounded a) => [(a, a)] -> Bool
validRangeList [(a, a)]
xs

-- MISSING: fromDistinctAscList fromAscRangeList