{-# 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 :: a -> RangeSet a
singleton a
x = Size -> Size -> Size -> RangeSet a
forall a. Size -> Size -> Size -> RangeSet a
single Size
1 (a -> Size
forall a. Enum a => a -> Size
fromEnum a
x) (a -> Size
forall a. Enum a => a -> Size
fromEnum a
x)

{-|
Is this set empty?

@since 0.0.1.0
-}
null :: RangeSet a -> Bool
null :: 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 :: RangeSet a -> Bool
full RangeSet a
Tip = Bool
False
full (Fork Size
_ Size
_ Size
l Size
u RangeSet a
_ RangeSet a
_) = Size
l Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== a -> Size
forall a. Enum a => a -> Size
fromEnum @a a
forall a. Bounded a => a
minBound Bool -> Bool -> Bool
&& a -> Size
forall a. Enum a => a -> Size
fromEnum @a a
forall a. Bounded a => a
maxBound Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
u

{-|
Does this set contain a single element?

@since 0.0.1.0
-}
isSingle :: RangeSet a -> Bool
isSingle :: RangeSet a -> Bool
isSingle (Fork Size
_ Size
1 Size
_ Size
_ RangeSet a
_ RangeSet a
_) = Bool
True
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 :: RangeSet a -> Maybe a
extractSingle (Fork Size
_ Size
1 Size
x Size
_ RangeSet a
_ RangeSet a
_) = a -> Maybe a
forall a. a -> Maybe a
Just (Size -> a
forall a. Enum a => Size -> a
toEnum Size
x)
extractSingle RangeSet a
_                  = Maybe a
forall a. Maybe a
Nothing

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

@since 0.0.1.0
-}
sizeRanges :: Enum a => RangeSet a -> Int
sizeRanges :: RangeSet a -> Size
sizeRanges = (a -> a -> Size -> Size -> Size) -> Size -> RangeSet a -> Size
forall a b.
Enum a =>
(a -> a -> b -> b -> b) -> b -> RangeSet a -> b
fold (\a
_ a
_ Size
szl Size
szr -> Size
szl Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
szr Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
1) Size
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 :: a -> RangeSet a -> Bool
notMember a
x = Bool -> Bool
not (Bool -> Bool) -> (RangeSet a -> Bool) -> RangeSet a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> RangeSet a -> Bool
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 :: RangeSet a -> Maybe a
findMin RangeSet a
Tip = Maybe a
forall a. Maybe a
Nothing
findMin (Fork Size
_ Size
_ Size
l Size
u RangeSet a
lt RangeSet a
_) = let (# !Size
m, !Size
_ #) = Size -> Size -> RangeSet a -> (# Size, Size #)
forall a. Size -> Size -> RangeSet a -> (# Size, Size #)
minRange Size
l Size
u RangeSet a
lt in a -> Maybe a
forall a. a -> Maybe a
Just (Size -> a
forall a. Enum a => Size -> a
toEnum Size
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 :: RangeSet a -> Maybe a
findMax RangeSet a
Tip = Maybe a
forall a. Maybe a
Nothing
findMax (Fork Size
_ Size
_ Size
l Size
u RangeSet a
_ RangeSet a
rt) = let (# !Size
_, !Size
m #) = Size -> Size -> RangeSet a -> (# Size, Size #)
forall a. Size -> Size -> RangeSet a -> (# Size, Size #)
maxRange Size
l Size
u RangeSet a
rt in a -> Maybe a
forall a. a -> Maybe a
Just (Size -> a
forall a. Enum a => Size -> a
toEnum Size
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 :: a -> RangeSet a -> RangeSet a
allLess = Size -> RangeSet a -> RangeSet a
forall a. Size -> RangeSet a -> RangeSet a
allLessE (Size -> RangeSet a -> RangeSet a)
-> (a -> Size) -> a -> RangeSet a -> RangeSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Size
forall a. Enum a => a -> Size
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 :: a -> RangeSet a -> RangeSet a
allMore = Size -> RangeSet a -> RangeSet a
forall a. Size -> RangeSet a -> RangeSet a
allMoreE (Size -> RangeSet a -> RangeSet a)
-> (a -> Size) -> a -> RangeSet a -> RangeSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Size
forall a. Enum a => a -> Size
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 :: RangeSet a -> RangeSet a
complement RangeSet a
Tip = Size -> Size -> Size -> RangeSet a
forall a. Size -> Size -> Size -> RangeSet a
single (Size -> Size -> Size
diffE Size
minBoundE Size
maxBoundE) Size
minBoundE Size
maxBoundE
  where
    !minBoundE :: Size
minBoundE = a -> Size
forall a. Enum a => a -> Size
fromEnum @a a
forall a. Bounded a => a
minBound
    !maxBoundE :: Size
maxBoundE = a -> Size
forall a. Enum a => a -> Size
fromEnum @a a
forall a. Bounded a => a
maxBound
complement RangeSet a
t | RangeSet a -> Bool
forall a. (Enum a, Bounded a) => RangeSet a -> Bool
full RangeSet a
t = RangeSet a
forall a. RangeSet a
Tip
complement t :: RangeSet a
t@(Fork Size
_ Size
sz Size
l Size
u RangeSet a
lt RangeSet a
rt) = case StrictMaybeE
maxl of
  SJust Size
x -> Size -> Size -> Size -> RangeSet a -> RangeSet a
forall a. Size -> Size -> Size -> RangeSet a -> RangeSet a
unsafeInsertR (Size -> Size -> Size
diffE Size
x Size
maxBoundE) Size
x Size
maxBoundE RangeSet a
t'
  StrictMaybeE
SNothing -> RangeSet a
t'
  where
    !minBoundE :: Size
minBoundE = a -> Size
forall a. Enum a => a -> Size
fromEnum @a a
forall a. Bounded a => a
minBound
    !maxBoundE :: Size
maxBoundE = a -> Size
forall a. Enum a => a -> Size
fromEnum @a a
forall a. Bounded a => a
maxBound
    (# !Size
minl, !Size
minu, !RangeSet a
rest #) = Size
-> Size
-> Size
-> RangeSet a
-> RangeSet a
-> (# Size, Size, RangeSet a #)
forall a.
Size
-> Size
-> Size
-> RangeSet a
-> RangeSet a
-> (# Size, Size, RangeSet a #)
minDelete Size
sz Size
l Size
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 #) | Size
minl Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
minBoundE = Size -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push (Size -> Size
forall a. Enum a => a -> a
succ Size
minu) RangeSet a
rest
                      | Bool
otherwise         = Size -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push Size
minBoundE RangeSet a
t

    safeSucc :: Size -> StrictMaybeE
safeSucc !Size
x
      | Size
x Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
maxBoundE = StrictMaybeE
SNothing
      | Bool
otherwise      = Size -> StrictMaybeE
SJust (Size -> Size
forall a. Enum a => a -> a
succ Size
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 :: Size -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push !Size
maxl RangeSet a
Tip = (# RangeSet a
forall a. RangeSet a
Tip, Size -> StrictMaybeE
SJust Size
maxl #)
    push Size
min (Fork Size
_ Size
_ Size
u Size
max RangeSet a
lt RangeSet a
Tip) =
      let (# !RangeSet a
lt', SJust Size
l #) = Size -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push Size
min RangeSet a
lt
      in  (# Size -> Size -> RangeSet a -> RangeSet a -> RangeSet a
forall a. Size -> Size -> RangeSet a -> RangeSet a -> RangeSet a
fork Size
l (Size -> Size
forall a. Enum a => a -> a
pred Size
u) RangeSet a
lt' RangeSet a
forall a. RangeSet a
Tip, Size -> StrictMaybeE
safeSucc Size
max #)
    push Size
min (Fork Size
_ Size
_ Size
u Size
l' RangeSet a
lt rt :: RangeSet a
rt@Fork{}) =
      let (# !RangeSet a
lt', SJust Size
l #) = Size -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push Size
min RangeSet a
lt
          -- this is safe, because we know the right-tree contains elements larger than l'
          !(# !RangeSet a
rt', !StrictMaybeE
max #) = Size -> RangeSet a -> (# RangeSet a, StrictMaybeE #)
push (Size -> Size
forall a. Enum a => a -> a
succ Size
l') RangeSet a
rt
      in  (# Size -> Size -> RangeSet a -> RangeSet a -> RangeSet a
forall a. Size -> Size -> RangeSet a -> RangeSet a -> RangeSet a
fork Size
l (Size -> Size
forall a. Enum a => a -> a
pred Size
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 :: RangeSet a -> RangeSet a -> Bool
isProperSubsetOf RangeSet a
t1 RangeSet a
t2 = RangeSet a -> Size
forall a. RangeSet a -> Size
size RangeSet a
t1 Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
< RangeSet a -> Size
forall a. RangeSet a -> Size
size RangeSet a
t2 Bool -> Bool -> Bool
&& RangeSet a -> RangeSet a -> 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 :: RangeSet a -> RangeSet a -> Bool
isSubsetOf RangeSet a
t1 RangeSet a
t2 = RangeSet a -> Size
forall a. RangeSet a -> Size
size RangeSet a
t1 Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
<= RangeSet a -> Size
forall a. RangeSet a -> Size
size RangeSet a
t2 Bool -> Bool -> Bool
&& RangeSet a -> RangeSet a -> 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 :: RangeSet a -> [a]
elems RangeSet a
t = (a -> a -> ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a])
-> ([a] -> [a]) -> RangeSet a -> [a] -> [a]
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 ([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]
range a
l a
u [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++) ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
rt) [a] -> [a]
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 :: RangeSet a -> [a]
unelems RangeSet a
t = (Size
 -> Size
 -> (Size -> Size -> [a] -> [a])
 -> (Size -> Size -> [a] -> [a])
 -> Size
 -> Size
 -> [a]
 -> [a])
-> (Size -> Size -> [a] -> [a])
-> RangeSet a
-> Size
-> Size
-> [a]
-> [a]
forall b a. (Size -> Size -> b -> b -> b) -> b -> RangeSet a -> b
foldE Size
-> Size
-> (Size -> Size -> [a] -> [a])
-> (Size -> Size -> [a] -> [a])
-> Size
-> Size
-> [a]
-> [a]
fork Size -> Size -> [a] -> [a]
tip RangeSet a
t (a -> Size
forall a. Enum a => a -> Size
fromEnum @a a
forall a. Bounded a => a
minBound) (a -> Size
forall a. Enum a => a -> Size
fromEnum @a a
forall a. Bounded a => a
maxBound) []
  where
    fork :: E -> E -> (E -> E -> [a] -> [a]) -> (E -> E -> [a] -> [a]) -> E -> E -> ([a] -> [a])
    fork :: Size
-> Size
-> (Size -> Size -> [a] -> [a])
-> (Size -> Size -> [a] -> [a])
-> Size
-> Size
-> [a]
-> [a]
fork Size
l' Size
u' Size -> Size -> [a] -> [a]
lt Size -> Size -> [a] -> [a]
rt Size
l Size
u = [a] -> [a]
dxs ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
dys
      where
        dxs :: [a] -> [a]
dxs | Size
l' Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
l   = [a] -> [a]
forall a. a -> a
id
            | Bool
otherwise = Size -> Size -> [a] -> [a]
lt Size
l (Size -> Size
forall a. Enum a => a -> a
pred Size
l')
        dys :: [a] -> [a]
dys | Size
u Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
u'   = [a] -> [a]
forall a. a -> a
id
            | Bool
otherwise = Size -> Size -> [a] -> [a]
rt (Size -> Size
forall a. Enum a => a -> a
succ Size
u') Size
u
    tip :: E -> E -> [a] -> [a]
    tip :: Size -> Size -> [a] -> [a]
tip Size
l Size
u = (a -> a -> [a]
forall a. Enum a => a -> a -> [a]
range (Size -> a
forall a. Enum a => Size -> a
toEnum Size
l) (Size -> a
forall a. Enum a => Size -> a
toEnum Size
u) [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++)