{- |
Module      :  Data.RangeSet.Map
Description :  A slightly less trivial implementation of range sets
Copyright   :  (c) Dylan Simon, 2015
License     :  MIT

A slightly less trivial implementation of range sets.

This is nearly identical to "Data.RangeSet.List" except for some important
performance differences:

* Most query functions in this module are /O(log n)/ rather than /O(n)/, so may
  be much faster.
* Most composition functions have the same time complexity but a higher
  constant, so may be somewhat slower.

If you're mainly calling 'member', you should consider using this module, but
if you're calling 'union', 'deleteRange', and other range manipulation
functions as often as querying, you might stick with the list implementation.

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

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

The implementation of 'RSet' is based on "Data.Map.Strict".

-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE Safe               #-}
module Data.RangeSet.Map (
  -- * 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
  , fromRList
  , toRList
  , fromNormalizedRangeList

  ) where

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

import           Control.DeepSeq (NFData (..))
import qualified Data.Foldable   as Fold
import           Data.Functor    ((<$>))
import qualified Data.Map.Strict as Map
import           Data.Monoid     (Monoid (..), getSum)
import           Data.Semigroup  (Semigroup (..))
import           Data.Typeable   (Typeable)

import           Data.RangeSet.Internal
import qualified Data.RangeSet.List     as RList

-- | Internally set is represented as sorted list of distinct inclusive ranges.
newtype RSet a = RSet (Map.Map 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 NFData a => NFData (RSet a) where
  rnf :: RSet a -> ()
rnf (RSet Map a a
xs) = Map a a -> ()
forall a. NFData a => a -> ()
rnf Map 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 (RSet Map a a
m) = Map a a -> Bool
forall k a. Map k a -> Bool
Map.null Map a a
m

-- | /O(1)/. Is this the empty 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 Map a a
xm) = 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) -> Map a a -> Sum Int
forall m k a. Monoid m => (k -> a -> m) -> Map k a -> m
Map.foldMapWithKey a -> a -> Sum Int
forall a. Enum a => a -> a -> Sum Int
rangeSize Map a a
xm

contains' :: Ord a => a -> a -> RSet a -> Bool
contains' :: forall a. Ord a => a -> a -> RSet a -> Bool
contains' a
x a
y (RSet Map a a
xm) = ((a, a) -> Bool) -> Maybe (a, a) -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
Fold.any ((a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<=) (a -> Bool) -> ((a, a) -> a) -> (a, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, a) -> a
forall a b. (a, b) -> b
snd) (Maybe (a, a) -> Bool) -> Maybe (a, a) -> Bool
forall a b. (a -> b) -> a -> b
$ a -> Map a a -> Maybe (a, a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupLE a
x Map a a
xm

-- | /O(log 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 = a -> a -> RSet a -> Bool
forall a. Ord a => a -> a -> RSet a -> Bool
contains' a
x a
x

-- | /O(log 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(log 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 Map a a
xm) = a -> a -> a
forall a. Ord a => a -> a -> a
min (a -> a
forall a. Enum a => a -> a
pred a
x) (a -> a) -> ((a, a) -> a) -> (a, a) -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, a) -> a
forall a b. (a, b) -> b
snd ((a, a) -> a) -> Maybe (a, a) -> Maybe a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Map a a -> Maybe (a, a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupLT a
x Map a a
xm

-- | /O(log 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 Map a a
xm)
  | Just (a
_, a
b) <- a -> Map a a -> Maybe (a, a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupLE a
x Map a a
xm, 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) -> a
forall a b. (a, b) -> a
fst ((a, a) -> a) -> Maybe (a, a) -> Maybe a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Map a a -> Maybe (a, a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupGT a
x Map a a
xm

-- | /O(log 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 Map a a
xm) = a -> a -> a
forall a. Ord a => a -> a -> a
min a
x (a -> a) -> ((a, a) -> a) -> (a, a) -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, a) -> a
forall a b. (a, b) -> b
snd ((a, a) -> a) -> Maybe (a, a) -> Maybe a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Map a a -> Maybe (a, a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupLE a
x Map a a
xm

-- | /O(log 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 Map a a
xm)
  | Just (a
_, a
b) <- a -> Map a a -> Maybe (a, a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupLE a
x Map a a
xm, 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) -> a
forall a b. (a, b) -> a
fst ((a, a) -> a) -> Maybe (a, a) -> Maybe a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Map a a -> Maybe (a, a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupGT a
x Map a a
xm

-- | /O(log 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
s
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y = a -> a -> RSet a -> Bool
forall a. Ord a => a -> a -> RSet a -> Bool
contains' a
x a
y RSet a
s
  | 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
x RSet a
y = [(a, a)] -> [(a, a)] -> Bool
forall a. Ord a => [(a, a)] -> [(a, a)] -> Bool
isSubsetRangeList (RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList RSet a
x) (RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList RSet a
y)

{- Construction -}

-- | /O(1)/. The empty set.
empty :: RSet a
empty :: forall a. RSet a
empty = Map a a -> RSet a
forall a. Map a a -> RSet a
RSet Map a a
forall k a. Map k a
Map.empty

-- | /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 = Map a a -> RSet a
forall a. Map a a -> RSet a
RSet (Map a a -> RSet a) -> Map a a -> RSet a
forall a b. (a -> b) -> a -> b
$ a -> a -> Map a a
forall k a. k -> a -> Map k a
Map.singleton 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 -}

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 RSet a
s = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
unRangeList ([(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)] -> [(a, a)]) -> [(a, a)] -> [(a, a)]
forall a b. (a -> b) -> a -> b
$ RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList RSet a
s

-- | /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 = a -> a -> RSet a -> RSet a
forall a. (Ord a, Enum a) => a -> a -> RSet a -> RSet a
insertRange' a
x a
x

-- | /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) RSet a
set
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y      = RSet a
set
  | Bool
otherwise  = a -> a -> RSet a -> RSet a
forall a. (Ord a, Enum a) => a -> a -> RSet a -> RSet a
insertRange' a
x a
y RSet 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 = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
unRangeList ([(a, a)] -> RSet a) -> (RSet a -> [(a, a)]) -> RSet a -> RSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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)] -> [(a, a)])
-> (RSet a -> [(a, a)]) -> RSet a -> [(a, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList

-- | /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 = a -> a -> RSet a -> RSet a
forall a. (Ord a, Enum a) => a -> a -> RSet a -> RSet a
deleteRange' a
x a
x

-- | /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) RSet a
set
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y      = RSet a
set
  | Bool
otherwise  = a -> a -> RSet a -> RSet a
forall a. (Ord a, Enum a) => a -> a -> RSet a -> RSet a
deleteRange' a
x a
y RSet a
set

{- 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
x RSet a
y = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
unRangeList ([(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 (RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList RSet a
x) (RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList RSet a
y)

-- | /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
x RSet a
y = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
unRangeList ([(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 (RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList RSet a
x) (RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList RSet a
y)

-- | /O(n*m)/. The intersection of two sets.
intersection :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a
intersection :: forall a. (Ord a, Enum a) => RSet a -> RSet a -> RSet a
intersection RSet a
x RSet a
y = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
unRangeList ([(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 (RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList RSet a
x) (RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList RSet a
y)

{- 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 = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
unRangeList ([(a, a)] -> RSet a) -> (RSet a -> [(a, a)]) -> RSet a -> RSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(a, a)] -> [(a, a)]
forall a. (Ord a, Enum a, Bounded a) => [(a, a)] -> [(a, a)]
complementRangeList ([(a, a)] -> [(a, a)])
-> (RSet a -> [(a, a)]) -> RSet a -> [(a, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList

{- Filter -}

-- | /O(log 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(log 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 Map a a
xm)
  | Just a
y <- Maybe a
xv = (Map a a -> RSet a
forall a. Map a a -> RSet a
RSet Map a a
ml, Bool
True, Map a a -> RSet a
forall a. Map a a -> RSet a
RSet (Map a a -> RSet a) -> Map a a -> RSet a
forall a b. (a -> b) -> a -> b
$ Bool -> a -> a -> Map a a -> Map a a
forall {k} {a}. Ord k => Bool -> k -> a -> Map k a -> Map k a
insertIf (a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y) (a -> a
forall a. Enum a => a -> a
succ a
x) a
y Map a a
mr)
  | Just ((a
u,a
v), Map a a
ml') <- Map a a -> Maybe ((a, a), Map a a)
forall k a. Map k a -> Maybe ((k, a), Map k a)
Map.maxViewWithKey Map a a
ml =
    if a
v a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x
      then (Map a a -> RSet a
forall a. Map a a -> RSet a
RSet Map a a
ml, Bool
False, Map a a -> RSet a
forall a. Map a a -> RSet a
RSet Map a a
mr)
      else (Map a a -> RSet a
forall a. Map a a -> RSet a
RSet (Map a a -> RSet a) -> Map a a -> RSet a
forall a b. (a -> b) -> a -> b
$ Bool -> a -> a -> Map a a -> Map a a
forall {k} {a}. Ord k => Bool -> k -> a -> Map k a -> Map k a
insertIf (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) Map a a
ml', Bool
True, Map a a -> RSet a
forall a. Map a a -> RSet a
RSet (Map a a -> RSet a) -> Map a a -> RSet a
forall a b. (a -> b) -> a -> b
$ Bool -> a -> a -> Map a a -> Map a a
forall {k} {a}. Ord k => Bool -> k -> a -> Map k a -> Map k a
insertIf (a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
v) (a -> a
forall a. Enum a => a -> a
succ a
x) a
v Map a a
mr)
  | Bool
otherwise = (Map a a -> RSet a
forall a. Map a a -> RSet a
RSet Map a a
ml {- empty -}, Bool
False, Map a a -> RSet a
forall a. Map a a -> RSet a
RSet {- mr -} Map a a
xm)
  where
  (Map a a
ml, Maybe a
xv, Map a a
mr) = a -> Map a a -> (Map a a, Maybe a, Map a a)
forall k a. Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
Map.splitLookup a
x Map a a
xm
  insertIf :: Bool -> k -> a -> Map k a -> Map k a
insertIf Bool
False k
_ a
_ = Map k a -> Map k a
forall a. a -> a
id
  insertIf Bool
True k
a a
b = k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
a a
b

{- Min/Max -}

-- | /O(log n)/. The minimal element of a set.
findMin :: RSet a -> a
findMin :: forall a. RSet a -> a
findMin (RSet Map a a
m) = (a, a) -> a
forall a b. (a, b) -> a
fst ((a, a) -> a) -> (a, a) -> a
forall a b. (a -> b) -> a -> b
$ Map a a -> (a, a)
forall k a. Map k a -> (k, a)
Map.findMin Map a a
m

-- | /O(log n)/. The maximal element of a set.
findMax :: RSet a -> a
findMax :: forall a. RSet a -> a
findMax (RSet Map a a
m) = (a, a) -> a
forall a b. (a, b) -> b
snd ((a, a) -> a) -> (a, a) -> a
forall a b. (a -> b) -> a -> b
$ Map a a -> (a, a)
forall k a. Map k a -> (k, a)
Map.findMax Map a a
m

{- Conversion -}

unRangeList :: [(a, a)] -> RSet a
unRangeList :: forall a. [(a, a)] -> RSet a
unRangeList = Map a a -> RSet a
forall a. Map a a -> RSet a
RSet (Map a a -> RSet a) -> ([(a, a)] -> Map a a) -> [(a, a)] -> RSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(a, a)] -> Map a a
forall k a. [(k, a)] -> Map k a
Map.fromDistinctAscList

-- | /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 (in arbitrary order). /r/ is the size of longest range.
toList :: Enum a => RSet a -> [a]
toList :: forall a. Enum a => RSet a -> [a]
toList (RSet Map a a
xm) = (a -> a -> [a]) -> Map a a -> [a]
forall m k a. Monoid m => (k -> a -> m) -> Map k a -> m
Map.foldMapWithKey a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromTo Map a a
xm

-- | /O(n*log n)/. Create a set from a list of elements.
-- Note that unlike "Data.Set" and other binary trees, this always requires a full sort and traversal to create distinct, disjoint ranges before constructing the tree.
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
unRangeList ([(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.
-- Note that unlike "Data.Set" and other binary trees, this always requires a full traversal to create distinct, disjoint ranges before constructing the tree.
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
unRangeList ([(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 Map a a
xm) = (a -> a -> [a] -> [a]) -> [a] -> Map a a -> [a]
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey (\a
a -> [a] -> [a] -> [a]
forall 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]
forall a. Enum a => a -> a -> [a]
enumFromTo a
a) [] Map a a
xm

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

-- | /O(n*log n)/. Create a set from a list of range pairs.
-- Note that unlike "Data.Set" and other binary trees, this always requires a full sort and traversal to create distinct, disjoint ranges before constructing the tree.
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
unRangeList ([(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)/. Convert a list-based 'RList.RSet' to a map-based 'RSet'.
fromRList :: RList.RSet a -> RSet a
fromRList :: forall a. RSet a -> RSet a
fromRList = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
fromNormalizedRangeList ([(a, a)] -> RSet a) -> (RSet a -> [(a, a)]) -> RSet a -> RSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
RList.toRangeList

-- | /O(n)/. Convert a map-based 'RSet' to a list-based 'RList.RSet'.
toRList :: RSet a -> RList.RSet a
toRList :: forall a. RSet a -> RSet a
toRList = [(a, a)] -> RSet a
forall a. [(a, a)] -> RSet a
RList.fromNormalizedRangeList ([(a, a)] -> RSet a) -> (RSet a -> [(a, a)]) -> RSet a -> RSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RSet a -> [(a, a)]
forall a. RSet a -> [(a, a)]
toRangeList

-- | /O(n)/. 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 = Map a a -> RSet a
forall a. Map a a -> RSet a
RSet (Map a a -> RSet a) -> ([(a, a)] -> Map a a) -> [(a, a)] -> RSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(a, a)] -> Map a a
forall k a. [(k, a)] -> Map k a
Map.fromDistinctAscList

-- | /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 Map a a
xm) = Map a a -> Bool
forall k a. Ord k => Map k a -> Bool
Map.valid Map a a
xm Bool -> Bool -> Bool
&& [(a, a)] -> Bool
forall a. (Ord a, Enum a, Bounded a) => [(a, a)] -> Bool
validRangeList (Map a a -> [(a, a)]
forall k a. Map k a -> [(k, a)]
Map.toAscList Map a a
xm)