{-# LANGUAGE MagicHash, UnboxedTuples, TypeApplications, BangPatterns, ScopedTypeVariables, Safe #-}
{-|
Module      : Data.RangeSet
Description : Efficient set for (semi-)contiguous data.
License     : BSD-3-Clause
Maintainer  : Jamie Willis
Stability   : stable

This module contains the implementation of an efficient set for contiguous data. It has a much
smaller memory footprint than a @Set@, and can result in asymptotically faster operations.

@since 0.0.1.0
-}
module Data.RangeSet (
    RangeSet,
    module Data.RangeSet.Primitives,
    singleton, null, full, isSingle, extractSingle, size, sizeRanges,
    notMember, findMin, findMax,
    module Data.RangeSet.SetCrossSet, complement,
    isSubsetOf, isProperSubsetOf,
    allLess, allMore,
    elems, unelems,
    module Data.RangeSet.Builders,
  ) where

import Prelude hiding (null)
import Data.RangeSet.Internal
import Data.RangeSet.Builders
import Data.RangeSet.Primitives
import Data.RangeSet.SetCrossSet

{-|
A `RangeSet` containing a single value.

@since 0.0.1.0
-}
singleton :: Enum a => a -> RangeSet a
singleton :: forall a. Enum a => a -> RangeSet a
singleton a
x = forall a. E -> E -> RangeSet a
single (forall a. Enum a => a -> E
fromEnum a
x) (forall a. Enum a => a -> E
fromEnum a
x)

{-|
Is this set empty?

@since 0.0.1.0
-}
null :: RangeSet a -> Bool
null :: forall a. RangeSet a -> Bool
null RangeSet a
Tip = Bool
True
null RangeSet a
_ = Bool
False

{-|
Is this set full?

@since 0.0.1.0
-}
full :: forall a. (Enum a, Bounded a) => RangeSet a -> Bool
full :: forall a. (Enum a, Bounded a) => RangeSet a -> Bool
full RangeSet a
Tip = Bool
False
full (Fork H
_ E
l E
u RangeSet a
_ RangeSet a
_) = E
l forall a. Eq a => a -> a -> Bool
== forall a. Enum a => a -> E
fromEnum @a forall a. Bounded a => a
minBound Bool -> Bool -> Bool
&& forall a. Enum a => a -> E
fromEnum @a forall a. Bounded a => a
maxBound forall a. Eq a => a -> a -> Bool
== E
u

{-|
Does this set contain a single element?

@since 0.0.1.0
-}
isSingle :: RangeSet a -> Bool
isSingle :: forall a. RangeSet a -> Bool
isSingle (Fork H
1 E
l E
u RangeSet a
_ RangeSet a
_) = E
l forall a. Eq a => a -> a -> Bool
== E
u
isSingle RangeSet a
_ = Bool
False

{-|
Possibly extract the element contained in the set if it is a singleton set.

@since 0.0.1.0
-}
extractSingle :: Enum a => RangeSet a -> Maybe a
extractSingle :: forall a. Enum a => RangeSet a -> Maybe a
extractSingle (Fork H
1 E
x E
y RangeSet a
_ RangeSet a
_) | E
x forall a. Eq a => a -> a -> Bool
== E
y = forall a. a -> Maybe a
Just (forall a. Enum a => E -> a
toEnum E
x)
extractSingle RangeSet a
_ = forall a. Maybe a
Nothing

{-|
Return the number of /contiguous ranges/ that populate the set.

@since 0.0.1.0
-}
sizeRanges :: RangeSet a -> Int
sizeRanges :: forall a. RangeSet a -> E
sizeRanges = forall b a. (E -> E -> b -> b -> b) -> b -> RangeSet a -> b
foldE (\E
_ E
_ E
szl E
szr -> E
szl forall a. Num a => a -> a -> a
+ E
szr forall a. Num a => a -> a -> a
+ E
1) E
0

{-|
Test whether or not a given value is not found within the set.

@since 0.0.1.0
-}
{-# INLINEABLE notMember #-}
notMember :: Enum a => a -> RangeSet a -> Bool
notMember :: forall a. Enum a => a -> RangeSet a -> Bool
notMember a
x = Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Enum a => a -> RangeSet a -> Bool
member a
x

{-|
Find the minimum value within the set, if one exists.

@since 0.0.1.0
-}
{-# INLINE findMin #-}
findMin :: Enum a => RangeSet a -> Maybe a
findMin :: forall a. Enum a => RangeSet a -> Maybe a
findMin RangeSet a
Tip = forall a. Maybe a
Nothing
findMin (Fork H
_ E
l E
u RangeSet a
lt RangeSet a
_) = let (# !E
m, !E
_ #) = forall a. E -> E -> RangeSet a -> (# E, E #)
minRange E
l E
u RangeSet a
lt in forall a. a -> Maybe a
Just (forall a. Enum a => E -> a
toEnum E
m)

{-|
Find the maximum value within the set, if one exists.

@since 0.0.1.0
-}
{-# INLINE findMax #-}
findMax :: Enum a => RangeSet a -> Maybe a
findMax :: forall a. Enum a => RangeSet a -> Maybe a
findMax RangeSet a
Tip = forall a. Maybe a
Nothing
findMax (Fork H
_ E
l E
u RangeSet a
_ RangeSet a
rt) = let (# !E
_, !E
m #) = forall a. E -> E -> RangeSet a -> (# E, E #)
maxRange E
l E
u RangeSet a
rt in forall a. a -> Maybe a
Just (forall a. Enum a => E -> a
toEnum E
m)

{-|
Filters a set by removing all values greater than or equal to the given value.

@since 0.0.1.0
-}
{-# INLINEABLE allLess #-}
allLess :: Enum a => a -> RangeSet a -> RangeSet a
allLess :: forall a. Enum a => a -> RangeSet a -> RangeSet a
allLess = forall a. E -> RangeSet a -> RangeSet a
allLessE forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Enum a => a -> E
fromEnum

{-|
Filters a set by removing all values less than or equal to the given value.

@since 0.0.1.0
-}
{-# INLINEABLE allMore #-}
allMore :: Enum a => a -> RangeSet a -> RangeSet a
allMore :: forall a. Enum a => a -> RangeSet a -> RangeSet a
allMore = forall a. E -> RangeSet a -> RangeSet a
allMoreE forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Enum a => a -> E
fromEnum

{-|
Inverts a set: every value which was an element is no longer an element, and every value that
was not an element now is. This is only possible on `Bounded` types.

@since 0.0.1.0
-}
{-# INLINEABLE complement #-}
complement :: forall a. (Bounded a, Enum a) => RangeSet a -> RangeSet a
complement :: forall a. (Bounded a, Enum a) => RangeSet a -> RangeSet a
complement RangeSet a
Tip = forall a. E -> E -> RangeSet a
single E
minBoundE E
maxBoundE
  where
    !minBoundE :: E
minBoundE = forall a. Enum a => a -> E
fromEnum @a forall a. Bounded a => a
minBound
    !maxBoundE :: E
maxBoundE = forall a. Enum a => a -> E
fromEnum @a forall a. Bounded a => a
maxBound
complement RangeSet a
t | forall a. (Enum a, Bounded a) => RangeSet a -> Bool
full RangeSet a
t = forall a. RangeSet a
Tip
complement t :: RangeSet a
t@(Fork H
_ E
l E
u RangeSet a
lt RangeSet a
rt) = case StrictMaybeE
maxl of
  SJust E
x -> forall a. E -> E -> RangeSet a -> RangeSet a
unsafeInsertR E
x E
maxBoundE RangeSet a
t'
  StrictMaybeE
SNothing -> RangeSet a
t'
  where
    !minBoundE :: E
minBoundE = forall a. Enum a => a -> E
fromEnum @a forall a. Bounded a => a
minBound
    !maxBoundE :: E
maxBoundE = forall a. Enum a => a -> E
fromEnum @a forall a. Bounded a => a
maxBound
    (# !E
minl, !E
minu, !RangeSet a
rest #) = forall a.
E -> E -> RangeSet a -> RangeSet a -> (# E, E, RangeSet a #)
minDelete E
l E
u RangeSet a
lt RangeSet a
rt

    -- The complement of a tree is at most 1 larger or smaller than the original
    -- if both min and max are minBound and maxBound, it will shrink
    -- if neither min or max are minBound or maxBound, it will grow
    -- otherwise, the tree will not change size
    -- The insert or shrink will happen at an extremity, and rebalance need only occur along the spine
                       -- this is safe, because we've checked for the maxSet case already
    !(# !RangeSet a
t', !StrictMaybeE
maxl #) | E
minl forall a. Eq a => a -> a -> Bool
== E
minBoundE = E -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push (forall a. Enum a => a -> a
succ E
minu) RangeSet a
rest
                      | Bool
otherwise         = E -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push E
minBoundE RangeSet a
t

    safeSucc :: E -> StrictMaybeE
safeSucc !E
x
      | E
x forall a. Eq a => a -> a -> Bool
== E
maxBoundE = StrictMaybeE
SNothing
      | Bool
otherwise      = E -> StrictMaybeE
SJust (forall a. Enum a => a -> a
succ E
x)

    -- the argument l should not be altered, it /must/ be the correct lower bound
    -- the return /must/ be the next correct lower bound
    push :: E -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
    push :: E -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push !E
maxl RangeSet a
Tip = (# forall a. RangeSet a
Tip, E -> StrictMaybeE
SJust E
maxl #)
    push E
min (Fork H
_ E
u E
max RangeSet a
lt RangeSet a
Tip) =
      let (# !RangeSet a
lt', SJust E
l #) = E -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push E
min RangeSet a
lt
      in  (# forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
fork E
l (forall a. Enum a => a -> a
pred E
u) RangeSet a
lt' forall a. RangeSet a
Tip, E -> StrictMaybeE
safeSucc E
max #)
    push E
min (Fork H
_ E
u E
l' RangeSet a
lt rt :: RangeSet a
rt@Fork{}) =
      let (# !RangeSet a
lt', SJust E
l #) = E -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push E
min RangeSet a
lt
          -- this is safe, because we know the right-tree contains elements larger than l'
          !(# !RangeSet a
rt', !StrictMaybeE
max #) = E -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push (forall a. Enum a => a -> a
succ E
l') RangeSet a
rt
      in  (# forall a. E -> E -> RangeSet a -> RangeSet a -> RangeSet a
fork E
l (forall a. Enum a => a -> a
pred E
u) RangeSet a
lt' RangeSet a
rt', StrictMaybeE
max #)

{-|
Tests if all the element of the first set appear in the second, but also that the first and second
sets are not equal.

@since 0.0.1.0
-}
{-# INLINE isProperSubsetOf #-}
isProperSubsetOf :: RangeSet a -> RangeSet a -> Bool
isProperSubsetOf :: forall a. RangeSet a -> RangeSet a -> Bool
isProperSubsetOf RangeSet a
t1 RangeSet a
t2 = forall a. RangeSet a -> E
size RangeSet a
t1 forall a. Ord a => a -> a -> Bool
< forall a. RangeSet a -> E
size RangeSet a
t2 Bool -> Bool -> Bool
&& forall a. RangeSet a -> RangeSet a -> Bool
uncheckedSubsetOf RangeSet a
t1 RangeSet a
t2

{-|
Tests if all the elements of the first set appear in the second.

@since 0.0.1.0
-}
{-# INLINEABLE isSubsetOf #-}
isSubsetOf :: RangeSet a -> RangeSet a -> Bool
isSubsetOf :: forall a. RangeSet a -> RangeSet a -> Bool
isSubsetOf RangeSet a
t1 RangeSet a
t2 = forall a. RangeSet a -> E
size RangeSet a
t1 forall a. Ord a => a -> a -> Bool
<= forall a. RangeSet a -> E
size RangeSet a
t2 Bool -> Bool -> Bool
&& forall a. RangeSet a -> RangeSet a -> Bool
uncheckedSubsetOf RangeSet a
t1 RangeSet a
t2

{-|
Returns all the elements found within the set.

@since 0.0.1.0
-}
{-# INLINE elems #-}
elems :: Enum a => RangeSet a -> [a]
elems :: forall a. Enum a => RangeSet a -> [a]
elems RangeSet a
t = forall a b.
Enum a =>
(a -> a -> b -> b -> b) -> b -> RangeSet a -> b
fold (\a
l a
u [a] -> [a]
lt [a] -> [a]
rt -> [a] -> [a]
lt forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall a. Enum a => a -> a -> [a]
range a
l a
u forall a. [a] -> [a] -> [a]
++) forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
rt) forall a. a -> a
id RangeSet a
t []

{-|
Returns all the values that are not found within the set.

@since 0.0.1.0
-}
{-# INLINEABLE unelems #-}
unelems :: forall a. (Bounded a, Enum a) => RangeSet a -> [a]
unelems :: forall a. (Bounded a, Enum a) => RangeSet a -> [a]
unelems RangeSet a
t = forall b a. (E -> E -> b -> b -> b) -> b -> RangeSet a -> b
foldE E
-> E
-> (E -> E -> [a] -> [a])
-> (E -> E -> [a] -> [a])
-> E
-> E
-> [a]
-> [a]
fork E -> E -> [a] -> [a]
tip RangeSet a
t (forall a. Enum a => a -> E
fromEnum @a forall a. Bounded a => a
minBound) (forall a. Enum a => a -> E
fromEnum @a forall a. Bounded a => a
maxBound) []
  where
    fork :: E -> E -> (E -> E -> [a] -> [a]) -> (E -> E -> [a] -> [a]) -> E -> E -> ([a] -> [a])
    fork :: E
-> E
-> (E -> E -> [a] -> [a])
-> (E -> E -> [a] -> [a])
-> E
-> E
-> [a]
-> [a]
fork E
l' E
u' E -> E -> [a] -> [a]
lt E -> E -> [a] -> [a]
rt E
l E
u = [a] -> [a]
dxs forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
dys
      where
        dxs :: [a] -> [a]
dxs | E
l' forall a. Eq a => a -> a -> Bool
== E
l   = forall a. a -> a
id
            | Bool
otherwise = E -> E -> [a] -> [a]
lt E
l (forall a. Enum a => a -> a
pred E
l')
        dys :: [a] -> [a]
dys | E
u forall a. Eq a => a -> a -> Bool
== E
u'   = forall a. a -> a
id
            | Bool
otherwise = E -> E -> [a] -> [a]
rt (forall a. Enum a => a -> a
succ E
u') E
u
    tip :: E -> E -> [a] -> [a]
    tip :: E -> E -> [a] -> [a]
tip E
l E
u = (forall a. Enum a => a -> a -> [a]
range (forall a. Enum a => E -> a
toEnum E
l) (forall a. Enum a => E -> a
toEnum E
u) forall a. [a] -> [a] -> [a]
++)