{- |
Module      :  Data.RangeSet.IntMap
Description :  Specialization of Data.RangeSet.Map to Ints
Copyright   :  (c) Dylan Simon, 2015
License     :  MIT

This is simply a specialization of "Data.RangeSet.Map" to 'Int'.

The implementation of 'RIntSet' is based on "Data.IntMap.Strict".
-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE Safe               #-}
module Data.RangeSet.IntMap (
  -- * Range set type
  RIntSet

  -- * 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.IntMap.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 RIntSet = RSet (Map.IntMap Int)
  deriving (RIntSet -> RIntSet -> Bool
(RIntSet -> RIntSet -> Bool)
-> (RIntSet -> RIntSet -> Bool) -> Eq RIntSet
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: RIntSet -> RIntSet -> Bool
== :: RIntSet -> RIntSet -> Bool
$c/= :: RIntSet -> RIntSet -> Bool
/= :: RIntSet -> RIntSet -> Bool
Eq, Eq RIntSet
Eq RIntSet =>
(RIntSet -> RIntSet -> Ordering)
-> (RIntSet -> RIntSet -> Bool)
-> (RIntSet -> RIntSet -> Bool)
-> (RIntSet -> RIntSet -> Bool)
-> (RIntSet -> RIntSet -> Bool)
-> (RIntSet -> RIntSet -> RIntSet)
-> (RIntSet -> RIntSet -> RIntSet)
-> Ord RIntSet
RIntSet -> RIntSet -> Bool
RIntSet -> RIntSet -> Ordering
RIntSet -> RIntSet -> RIntSet
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
$ccompare :: RIntSet -> RIntSet -> Ordering
compare :: RIntSet -> RIntSet -> Ordering
$c< :: RIntSet -> RIntSet -> Bool
< :: RIntSet -> RIntSet -> Bool
$c<= :: RIntSet -> RIntSet -> Bool
<= :: RIntSet -> RIntSet -> Bool
$c> :: RIntSet -> RIntSet -> Bool
> :: RIntSet -> RIntSet -> Bool
$c>= :: RIntSet -> RIntSet -> Bool
>= :: RIntSet -> RIntSet -> Bool
$cmax :: RIntSet -> RIntSet -> RIntSet
max :: RIntSet -> RIntSet -> RIntSet
$cmin :: RIntSet -> RIntSet -> RIntSet
min :: RIntSet -> RIntSet -> RIntSet
Ord, Typeable)

instance Show RIntSet where
  showsPrec :: Int -> RIntSet -> ShowS
showsPrec Int
d RIntSet
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 -> [(Int, Int)] -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (RIntSet -> [(Int, Int)]
toRangeList RIntSet
x)

instance Semigroup RIntSet where
  <> :: RIntSet -> RIntSet -> RIntSet
(<>) = RIntSet -> RIntSet -> RIntSet
union

instance Monoid RIntSet where
  mempty :: RIntSet
mempty  = RIntSet
empty
  mappend :: RIntSet -> RIntSet -> RIntSet
mappend = RIntSet -> RIntSet -> RIntSet
union

instance NFData RIntSet where
  rnf :: RIntSet -> ()
rnf (RSet IntMap Int
xs) = IntMap Int -> ()
forall a. NFData a => a -> ()
rnf IntMap Int
xs

{- Operators -}
infixl 9 \\ --

-- | /O(n+m)/. See 'difference'.
(\\) :: RIntSet -> RIntSet -> RIntSet
RIntSet
m1 \\ :: RIntSet -> RIntSet -> RIntSet
\\ RIntSet
m2 = RIntSet -> RIntSet -> RIntSet
difference RIntSet
m1 RIntSet
m2

{- Query -}

-- | /O(1)/. Is this the empty set?
null :: RIntSet -> Bool
null :: RIntSet -> Bool
null (RSet IntMap Int
m) = IntMap Int -> Bool
forall a. IntMap a -> Bool
Map.null IntMap Int
m

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

-- | /O(n)/. The number of the elements in the set.
size :: RIntSet -> Int
size :: RIntSet -> Int
size (RSet IntMap Int
xm) = Sum Int -> Int
forall a. Sum a -> a
getSum (Sum Int -> Int) -> Sum Int -> Int
forall a b. (a -> b) -> a -> b
$ (Int -> Int -> Sum Int) -> IntMap Int -> Sum Int
forall m a. Monoid m => (Int -> a -> m) -> IntMap a -> m
Map.foldMapWithKey Int -> Int -> Sum Int
forall a. Enum a => a -> a -> Sum Int
rangeSize IntMap Int
xm

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

-- | /O(log n)/. Is the element in the set?
member :: Int -> RIntSet -> Bool
member :: Int -> RIntSet -> Bool
member Int
x = Int -> Int -> RIntSet -> Bool
contains' Int
x Int
x

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

-- | /O(log n)/. Find largest element smaller than the given one.
lookupLT :: Int -> RIntSet -> Maybe Int
lookupLT :: Int -> RIntSet -> Maybe Int
lookupLT Int
x (RSet IntMap Int
xm) = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min (Int -> Int
forall a. Enum a => a -> a
pred Int
x) (Int -> Int) -> ((Int, Int) -> Int) -> (Int, Int) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, Int) -> Int
forall a b. (a, b) -> b
snd ((Int, Int) -> Int) -> Maybe (Int, Int) -> Maybe Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> IntMap Int -> Maybe (Int, Int)
forall a. Int -> IntMap a -> Maybe (Int, a)
Map.lookupLT Int
x IntMap Int
xm

-- | /O(log n)/. Find smallest element greater than the given one.
lookupGT :: Int -> RIntSet -> Maybe Int
lookupGT :: Int -> RIntSet -> Maybe Int
lookupGT Int
x (RSet IntMap Int
xm)
  | Just (Int
_, Int
b) <- Int -> IntMap Int -> Maybe (Int, Int)
forall a. Int -> IntMap a -> Maybe (Int, a)
Map.lookupLE Int
x IntMap Int
xm, Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
b = Int -> Maybe Int
forall a. a -> Maybe a
Just (Int -> Int
forall a. Enum a => a -> a
succ Int
x)
  | Bool
otherwise = (Int, Int) -> Int
forall a b. (a, b) -> a
fst ((Int, Int) -> Int) -> Maybe (Int, Int) -> Maybe Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> IntMap Int -> Maybe (Int, Int)
forall a. Int -> IntMap a -> Maybe (Int, a)
Map.lookupGT Int
x IntMap Int
xm

-- | /O(log n)/. Find largest element smaller or equal to than the given one.
lookupLE :: Int -> RIntSet -> Maybe Int
lookupLE :: Int -> RIntSet -> Maybe Int
lookupLE Int
x (RSet IntMap Int
xm) = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
x (Int -> Int) -> ((Int, Int) -> Int) -> (Int, Int) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, Int) -> Int
forall a b. (a, b) -> b
snd ((Int, Int) -> Int) -> Maybe (Int, Int) -> Maybe Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> IntMap Int -> Maybe (Int, Int)
forall a. Int -> IntMap a -> Maybe (Int, a)
Map.lookupLE Int
x IntMap Int
xm

-- | /O(log n)/. Find smallest element greater or equal to than the given one.
lookupGE :: Int -> RIntSet -> Maybe Int
lookupGE :: Int -> RIntSet -> Maybe Int
lookupGE Int
x (RSet IntMap Int
xm)
  | Just (Int
_, Int
b) <- Int -> IntMap Int -> Maybe (Int, Int)
forall a. Int -> IntMap a -> Maybe (Int, a)
Map.lookupLE Int
x IntMap Int
xm, Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
b = Int -> Maybe Int
forall a. a -> Maybe a
Just Int
x
  | Bool
otherwise = (Int, Int) -> Int
forall a b. (a, b) -> a
fst ((Int, Int) -> Int) -> Maybe (Int, Int) -> Maybe Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> IntMap Int -> Maybe (Int, Int)
forall a. Int -> IntMap a -> Maybe (Int, a)
Map.lookupGT Int
x IntMap Int
xm

-- | /O(log n)/. Is the entire range contained within the set?
containsRange :: (Int, Int) -> RIntSet -> Bool
containsRange :: (Int, Int) -> RIntSet -> Bool
containsRange (Int
x,Int
y) RIntSet
s
  | Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
y = Int -> Int -> RIntSet -> Bool
contains' Int
x Int
y RIntSet
s
  | Bool
otherwise = Bool
True

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

{- Construction -}

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

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

singletonRange' :: Int -> Int -> RIntSet
singletonRange' :: Int -> Int -> RIntSet
singletonRange' Int
x Int
y = IntMap Int -> RIntSet
RSet (IntMap Int -> RIntSet) -> IntMap Int -> RIntSet
forall a b. (a -> b) -> a -> b
$ Int -> Int -> IntMap Int
forall a. Int -> a -> IntMap a
Map.singleton Int
x Int
y

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

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

{- Construction -}

insertRange' :: Int -> Int -> RIntSet -> RIntSet
insertRange' :: Int -> Int -> RIntSet -> RIntSet
insertRange' Int
x Int
y RIntSet
s = [(Int, Int)] -> RIntSet
unRangeList ([(Int, Int)] -> RIntSet) -> [(Int, Int)] -> RIntSet
forall a b. (a -> b) -> a -> b
$ Int -> Int -> [(Int, Int)] -> [(Int, Int)]
forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
insertRangeList Int
x Int
y ([(Int, Int)] -> [(Int, Int)]) -> [(Int, Int)] -> [(Int, Int)]
forall a b. (a -> b) -> a -> b
$ RIntSet -> [(Int, Int)]
toRangeList RIntSet
s

-- | /O(n)/. Insert an element in a set.
insert :: Int -> RIntSet -> RIntSet
insert :: Int -> RIntSet -> RIntSet
insert Int
x = Int -> Int -> RIntSet -> RIntSet
insertRange' Int
x Int
x

-- | /O(n)/. Insert a continuos range in a set.
insertRange :: (Int, Int) -> RIntSet -> RIntSet
insertRange :: (Int, Int) -> RIntSet -> RIntSet
insertRange (Int
x, Int
y) RIntSet
set
  | Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
y      = RIntSet
set
  | Bool
otherwise  = Int -> Int -> RIntSet -> RIntSet
insertRange' Int
x Int
y RIntSet
set

deleteRange' :: Int -> Int -> RIntSet -> RIntSet
deleteRange' :: Int -> Int -> RIntSet -> RIntSet
deleteRange' Int
x Int
y RIntSet
s = [(Int, Int)] -> RIntSet
unRangeList ([(Int, Int)] -> RIntSet) -> [(Int, Int)] -> RIntSet
forall a b. (a -> b) -> a -> b
$ Int -> Int -> [(Int, Int)] -> [(Int, Int)]
forall a. (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)]
deleteRangeList Int
x Int
y ([(Int, Int)] -> [(Int, Int)]) -> [(Int, Int)] -> [(Int, Int)]
forall a b. (a -> b) -> a -> b
$ RIntSet -> [(Int, Int)]
toRangeList RIntSet
s

-- | /O(n). Delete an element from a set.
delete :: Int -> RIntSet -> RIntSet
delete :: Int -> RIntSet -> RIntSet
delete Int
x = Int -> Int -> RIntSet -> RIntSet
deleteRange' Int
x Int
x

-- | /O(n). Delete a continuos range from a set.
deleteRange :: (Int, Int) -> RIntSet -> RIntSet
deleteRange :: (Int, Int) -> RIntSet -> RIntSet
deleteRange (Int
x, Int
y) RIntSet
set
  | Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
y      = RIntSet
set
  | Bool
otherwise  = Int -> Int -> RIntSet -> RIntSet
deleteRange' Int
x Int
y RIntSet
set

{- Combination -}

-- | /O(n*m)/. The union of two sets.
union :: RIntSet -> RIntSet -> RIntSet
union :: RIntSet -> RIntSet -> RIntSet
union RIntSet
x RIntSet
y = [(Int, Int)] -> RIntSet
unRangeList ([(Int, Int)] -> RIntSet) -> [(Int, Int)] -> RIntSet
forall a b. (a -> b) -> a -> b
$ [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
unionRangeList (RIntSet -> [(Int, Int)]
toRangeList RIntSet
x) (RIntSet -> [(Int, Int)]
toRangeList RIntSet
y)

-- | /O(n*m)/. Difference of two sets.
difference :: RIntSet -> RIntSet -> RIntSet
difference :: RIntSet -> RIntSet -> RIntSet
difference RIntSet
x RIntSet
y = [(Int, Int)] -> RIntSet
unRangeList ([(Int, Int)] -> RIntSet) -> [(Int, Int)] -> RIntSet
forall a b. (a -> b) -> a -> b
$ [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)]
differenceRangeList (RIntSet -> [(Int, Int)]
toRangeList RIntSet
x) (RIntSet -> [(Int, Int)]
toRangeList RIntSet
y)

-- | /O(n*m)/. The intersection of two sets.
intersection :: RIntSet -> RIntSet -> RIntSet
intersection :: RIntSet -> RIntSet -> RIntSet
intersection RIntSet
x RIntSet
y = [(Int, Int)] -> RIntSet
unRangeList ([(Int, Int)] -> RIntSet) -> [(Int, Int)] -> RIntSet
forall a b. (a -> b) -> a -> b
$ [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
forall a. Ord a => [(a, a)] -> [(a, a)] -> [(a, a)]
intersectRangeList (RIntSet -> [(Int, Int)]
toRangeList RIntSet
x) (RIntSet -> [(Int, Int)]
toRangeList RIntSet
y)

{- Complement -}

-- | /O(n)/. Complement of the set.
complement :: RIntSet -> RIntSet
complement :: RIntSet -> RIntSet
complement = [(Int, Int)] -> RIntSet
unRangeList ([(Int, Int)] -> RIntSet)
-> (RIntSet -> [(Int, Int)]) -> RIntSet -> RIntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, Int)] -> [(Int, Int)]
forall a. (Ord a, Enum a, Bounded a) => [(a, a)] -> [(a, a)]
complementRangeList ([(Int, Int)] -> [(Int, Int)])
-> (RIntSet -> [(Int, Int)]) -> RIntSet -> [(Int, Int)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RIntSet -> [(Int, Int)]
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 :: Int -> RIntSet -> (RIntSet, RIntSet)
split :: Int -> RIntSet -> (RIntSet, RIntSet)
split Int
x RIntSet
s = (RIntSet
l, RIntSet
r) where (RIntSet
l, Bool
_, RIntSet
r) = Int -> RIntSet -> (RIntSet, Bool, RIntSet)
splitMember Int
x RIntSet
s

-- | /O(log n)/. Performs a 'split' but also returns whether the pivot
-- element was found in the original set.
splitMember :: Int -> RIntSet -> (RIntSet, Bool, RIntSet)
splitMember :: Int -> RIntSet -> (RIntSet, Bool, RIntSet)
splitMember Int
x (RSet IntMap Int
xm)
  | Just Int
y <- Maybe Int
xv = (IntMap Int -> RIntSet
RSet IntMap Int
ml, Bool
True, IntMap Int -> RIntSet
RSet (IntMap Int -> RIntSet) -> IntMap Int -> RIntSet
forall a b. (a -> b) -> a -> b
$ Bool -> Int -> Int -> IntMap Int -> IntMap Int
forall {a}. Bool -> Int -> a -> IntMap a -> IntMap a
insertIf (Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
y) (Int -> Int
forall a. Enum a => a -> a
succ Int
x) Int
y IntMap Int
mr)
  | Just ((Int
u,Int
v), IntMap Int
ml') <- IntMap Int -> Maybe ((Int, Int), IntMap Int)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
Map.maxViewWithKey IntMap Int
ml =
    if Int
v Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
x
      then (IntMap Int -> RIntSet
RSet IntMap Int
ml, Bool
False, IntMap Int -> RIntSet
RSet IntMap Int
mr)
      else (IntMap Int -> RIntSet
RSet (IntMap Int -> RIntSet) -> IntMap Int -> RIntSet
forall a b. (a -> b) -> a -> b
$ Bool -> Int -> Int -> IntMap Int -> IntMap Int
forall {a}. Bool -> Int -> a -> IntMap a -> IntMap a
insertIf (Int
u Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
x) Int
u (Int -> Int
forall a. Enum a => a -> a
pred Int
x) IntMap Int
ml', Bool
True, IntMap Int -> RIntSet
RSet (IntMap Int -> RIntSet) -> IntMap Int -> RIntSet
forall a b. (a -> b) -> a -> b
$ Bool -> Int -> Int -> IntMap Int -> IntMap Int
forall {a}. Bool -> Int -> a -> IntMap a -> IntMap a
insertIf (Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
v) (Int -> Int
forall a. Enum a => a -> a
succ Int
x) Int
v IntMap Int
mr)
  | Bool
otherwise = (IntMap Int -> RIntSet
RSet IntMap Int
ml {- empty -}, Bool
False, IntMap Int -> RIntSet
RSet {- mr -} IntMap Int
xm)
  where
  (IntMap Int
ml, Maybe Int
xv, IntMap Int
mr) = Int -> IntMap Int -> (IntMap Int, Maybe Int, IntMap Int)
forall a. Int -> IntMap a -> (IntMap a, Maybe a, IntMap a)
Map.splitLookup Int
x IntMap Int
xm
  insertIf :: Bool -> Int -> a -> IntMap a -> IntMap a
insertIf Bool
False Int
_ a
_ = IntMap a -> IntMap a
forall a. a -> a
id
  insertIf Bool
True Int
a a
b = Int -> a -> IntMap a -> IntMap a
forall a. Int -> a -> IntMap a -> IntMap a
Map.insert Int
a a
b

{- Min/Max -}

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

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

{- Conversion -}

unRangeList :: [(Int, Int)] -> RIntSet
unRangeList :: [(Int, Int)] -> RIntSet
unRangeList = IntMap Int -> RIntSet
RSet (IntMap Int -> RIntSet)
-> ([(Int, Int)] -> IntMap Int) -> [(Int, Int)] -> RIntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, Int)] -> IntMap Int
forall a. [(Int, a)] -> IntMap 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 :: RIntSet -> [Int]
elems :: RIntSet -> [Int]
elems = RIntSet -> [Int]
toAscList

-- | /O(n*r)/. Convert the set to a list of elements (in arbitrary order). /r/
-- is the size of longest range.
toList :: RIntSet -> [Int]
toList :: RIntSet -> [Int]
toList (RSet IntMap Int
xm) = (Int -> Int -> [Int]) -> IntMap Int -> [Int]
forall m a. Monoid m => (Int -> a -> m) -> IntMap a -> m
Map.foldMapWithKey Int -> Int -> [Int]
forall a. Enum a => a -> a -> [a]
enumFromTo IntMap Int
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 :: [Int] -> RIntSet
fromList :: [Int] -> RIntSet
fromList = [(Int, Int)] -> RIntSet
unRangeList ([(Int, Int)] -> RIntSet)
-> ([Int] -> [(Int, Int)]) -> [Int] -> RIntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> [(Int, Int)]
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 :: [Int] -> RIntSet
fromAscList :: [Int] -> RIntSet
fromAscList = [(Int, Int)] -> RIntSet
unRangeList ([(Int, Int)] -> RIntSet)
-> ([Int] -> [(Int, Int)]) -> [Int] -> RIntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> [(Int, Int)]
forall a. (Eq a, Enum a) => [a] -> [(a, a)]
fromAscElemList

-- | /O(n*r)/. Convert the set to an ascending list of elements.
toAscList :: RIntSet -> [Int]
toAscList :: RIntSet -> [Int]
toAscList (RSet IntMap Int
xm) = (Int -> Int -> [Int] -> [Int]) -> [Int] -> IntMap Int -> [Int]
forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
Map.foldrWithKey (\Int
a -> [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
(++) ([Int] -> [Int] -> [Int])
-> (Int -> [Int]) -> Int -> [Int] -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Int -> [Int]
forall a. Enum a => a -> a -> [a]
enumFromTo Int
a) [] IntMap Int
xm

-- | /O(n)/. Convert the set to a list of range pairs.
toRangeList :: RIntSet -> [(Int, Int)]
toRangeList :: RIntSet -> [(Int, Int)]
toRangeList (RSet IntMap Int
xs) = IntMap Int -> [(Int, Int)]
forall a. IntMap a -> [(Int, a)]
Map.toAscList IntMap Int
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 :: [(Int, Int)] -> RIntSet
fromRangeList :: [(Int, Int)] -> RIntSet
fromRangeList = [(Int, Int)] -> RIntSet
unRangeList ([(Int, Int)] -> RIntSet)
-> ([(Int, Int)] -> [(Int, Int)]) -> [(Int, Int)] -> RIntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, Int)] -> [(Int, Int)]
forall a. (Ord a, Enum a) => [(a, a)] -> [(a, a)]
normalizeRangeList

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

-- | /O(n)/. Convert a map-based 'RIntSet' to a list-based 'RList.RSet'.
toRList :: RIntSet -> RList.RSet Int
toRList :: RIntSet -> RSet Int
toRList = [(Int, Int)] -> RSet Int
forall a. [(a, a)] -> RSet a
RList.fromNormalizedRangeList ([(Int, Int)] -> RSet Int)
-> (RIntSet -> [(Int, Int)]) -> RIntSet -> RSet Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RIntSet -> [(Int, Int)]
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 :: [(Int, Int)] -> RIntSet
fromNormalizedRangeList :: [(Int, Int)] -> RIntSet
fromNormalizedRangeList = IntMap Int -> RIntSet
RSet (IntMap Int -> RIntSet)
-> ([(Int, Int)] -> IntMap Int) -> [(Int, Int)] -> RIntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, Int)] -> IntMap Int
forall a. [(Int, a)] -> IntMap 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 :: RIntSet -> Bool
valid :: RIntSet -> Bool
valid = [(Int, Int)] -> Bool
forall a. (Ord a, Enum a, Bounded a) => [(a, a)] -> Bool
validRangeList ([(Int, Int)] -> Bool)
-> (RIntSet -> [(Int, Int)]) -> RIntSet -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RIntSet -> [(Int, Int)]
toRangeList