{-# LANGUAGE CPP #-}

module Data.Ranged.RangedSet (
   -- ** Ranged Set Type
   RSet,
   rSetRanges,
   -- ** Ranged Set construction functions and their preconditions
   makeRangedSet,
   unsafeRangedSet,
   validRangeList,
   normaliseRangeList,
   rSingleton,
   rSetUnfold,
   -- ** Predicates
   rSetIsEmpty,
   rSetIsFull,
   (-?-),  rSetHas,
   (-<=-), rSetIsSubset,
   (-<-),  rSetIsSubsetStrict,
   -- ** Set Operations
   (-\/-), rSetUnion,
   (-/\-), rSetIntersection,
   (-!-),  rSetDifference,
   rSetNegation,
   -- ** Useful Sets
   rSetEmpty,
   rSetFull,
) where

import Data.Ranged.Boundaries
import Data.Ranged.Ranges
#if !MIN_VERSION_base(4,11,0)
import Data.Semigroup
#endif

import qualified Data.List as List

infixl 7 -/\-
infixl 6 -\/-, -!-
infixl 5 -<=-, -<-, -?-

-- | An RSet (for Ranged Set) is a list of ranges.  The ranges must be sorted
-- and not overlap.
newtype DiscreteOrdered v => RSet v = RSet {forall v. DiscreteOrdered v => RSet v -> [Range v]
rSetRanges :: [Range v]}
   deriving (RSet v -> RSet v -> Bool
(RSet v -> RSet v -> Bool)
-> (RSet v -> RSet v -> Bool) -> Eq (RSet v)
forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
== :: RSet v -> RSet v -> Bool
$c/= :: forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
/= :: RSet v -> RSet v -> Bool
Eq, Int -> RSet v -> ShowS
[RSet v] -> ShowS
RSet v -> String
(Int -> RSet v -> ShowS)
-> (RSet v -> String) -> ([RSet v] -> ShowS) -> Show (RSet v)
forall v. (DiscreteOrdered v, Show v) => Int -> RSet v -> ShowS
forall v. (DiscreteOrdered v, Show v) => [RSet v] -> ShowS
forall v. (DiscreteOrdered v, Show v) => RSet v -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall v. (DiscreteOrdered v, Show v) => Int -> RSet v -> ShowS
showsPrec :: Int -> RSet v -> ShowS
$cshow :: forall v. (DiscreteOrdered v, Show v) => RSet v -> String
show :: RSet v -> String
$cshowList :: forall v. (DiscreteOrdered v, Show v) => [RSet v] -> ShowS
showList :: [RSet v] -> ShowS
Show, Eq (RSet v)
Eq (RSet v)
-> (RSet v -> RSet v -> Ordering)
-> (RSet v -> RSet v -> Bool)
-> (RSet v -> RSet v -> Bool)
-> (RSet v -> RSet v -> Bool)
-> (RSet v -> RSet v -> Bool)
-> (RSet v -> RSet v -> RSet v)
-> (RSet v -> RSet v -> RSet v)
-> Ord (RSet v)
RSet v -> RSet v -> Bool
RSet v -> RSet v -> Ordering
RSet v -> RSet v -> RSet v
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 v. DiscreteOrdered v => Eq (RSet v)
forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
forall v. DiscreteOrdered v => RSet v -> RSet v -> Ordering
forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
$ccompare :: forall v. DiscreteOrdered v => RSet v -> RSet v -> Ordering
compare :: RSet v -> RSet v -> Ordering
$c< :: forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
< :: RSet v -> RSet v -> Bool
$c<= :: forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
<= :: RSet v -> RSet v -> Bool
$c> :: forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
> :: RSet v -> RSet v -> Bool
$c>= :: forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
>= :: RSet v -> RSet v -> Bool
$cmax :: forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
max :: RSet v -> RSet v -> RSet v
$cmin :: forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
min :: RSet v -> RSet v -> RSet v
Ord)

instance DiscreteOrdered a => Semigroup (RSet a) where
    <> :: RSet a -> RSet a -> RSet a
(<>) = RSet a -> RSet a -> RSet a
forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetUnion

instance DiscreteOrdered a => Monoid (RSet a) where
    mempty :: RSet a
mempty  = RSet a
forall a. DiscreteOrdered a => RSet a
rSetEmpty
    mappend :: RSet a -> RSet a -> RSet a
mappend = RSet a -> RSet a -> RSet a
forall a. Semigroup a => a -> a -> a
(<>)

-- | Determine if the ranges in the list are both in order and non-overlapping.
-- If so then they are suitable input for the unsafeRangedSet function.
validRangeList :: DiscreteOrdered v => [Range v] -> Bool
validRangeList :: forall v. DiscreteOrdered v => [Range v] -> Bool
validRangeList [Range v]
rs = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and ([Bool] -> Bool) -> [Bool] -> Bool
forall a b. (a -> b) -> a -> b
$
  (Range v -> Bool) -> [Range v] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (\ (Range Boundary v
lower Boundary v
upper) -> Boundary v
lower Boundary v -> Boundary v -> Bool
forall a. Ord a => a -> a -> Bool
<= Boundary v
upper) [Range v]
rs Bool -> [Bool] -> [Bool]
forall a. a -> [a] -> [a]
:
  (Range v -> Range v -> Bool) -> [Range v] -> [Range v] -> [Bool]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\ (Range Boundary v
_ Boundary v
upper1) (Range Boundary v
lower2 Boundary v
_) -> Boundary v
upper1 Boundary v -> Boundary v -> Bool
forall a. Ord a => a -> a -> Bool
<= Boundary v
lower2) [Range v]
rs (Int -> [Range v] -> [Range v]
forall a. Int -> [a] -> [a]
drop Int
1 [Range v]
rs)


-- | Rearrange and merge the ranges in the list so that they are in order and
-- non-overlapping.
normaliseRangeList :: DiscreteOrdered v => [Range v] -> [Range v]
normaliseRangeList :: forall v. DiscreteOrdered v => [Range v] -> [Range v]
normaliseRangeList = [Range v] -> [Range v]
forall v. DiscreteOrdered v => [Range v] -> [Range v]
normalise ([Range v] -> [Range v])
-> ([Range v] -> [Range v]) -> [Range v] -> [Range v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Range v] -> [Range v]
forall a. Ord a => [a] -> [a]
List.sort ([Range v] -> [Range v])
-> ([Range v] -> [Range v]) -> [Range v] -> [Range v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Range v -> Bool) -> [Range v] -> [Range v]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (Range v -> Bool) -> Range v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Range v -> Bool
forall v. DiscreteOrdered v => Range v -> Bool
rangeIsEmpty)


-- Private routine: normalise a range list that is known to be already sorted.
-- This precondition is not checked.
normalise :: DiscreteOrdered v => [Range v] -> [Range v]
normalise :: forall v. DiscreteOrdered v => [Range v] -> [Range v]
normalise (Range v
r1:Range v
r2:[Range v]
rs) =
         if Range v -> Range v -> Bool
forall {v}. DiscreteOrdered v => Range v -> Range v -> Bool
overlap Range v
r1 Range v
r2
               then [Range v] -> [Range v]
forall v. DiscreteOrdered v => [Range v] -> [Range v]
normalise ([Range v] -> [Range v]) -> [Range v] -> [Range v]
forall a b. (a -> b) -> a -> b
$
                       Boundary v -> Boundary v -> Range v
forall v. Boundary v -> Boundary v -> Range v
Range (Range v -> Boundary v
forall v. Range v -> Boundary v
rangeLower Range v
r1)
                             (Boundary v -> Boundary v -> Boundary v
forall a. Ord a => a -> a -> a
max (Range v -> Boundary v
forall v. Range v -> Boundary v
rangeUpper Range v
r1) (Range v -> Boundary v
forall v. Range v -> Boundary v
rangeUpper Range v
r2))
                       Range v -> [Range v] -> [Range v]
forall a. a -> [a] -> [a]
: [Range v]
rs
               else Range v
r1 Range v -> [Range v] -> [Range v]
forall a. a -> [a] -> [a]
: ([Range v] -> [Range v]
forall v. DiscreteOrdered v => [Range v] -> [Range v]
normalise ([Range v] -> [Range v]) -> [Range v] -> [Range v]
forall a b. (a -> b) -> a -> b
$ Range v
r2 Range v -> [Range v] -> [Range v]
forall a. a -> [a] -> [a]
: [Range v]
rs)
   where
      overlap :: Range v -> Range v -> Bool
overlap (Range Boundary v
_ Boundary v
upper1) (Range Boundary v
lower2 Boundary v
_) = Boundary v
upper1 Boundary v -> Boundary v -> Bool
forall a. Ord a => a -> a -> Bool
>= Boundary v
lower2

normalise [Range v]
rs = [Range v]
rs


-- | Create a new Ranged Set from a list of ranges.  The list may contain
-- ranges that overlap or are not in ascending order.
makeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v
makeRangedSet :: forall v. DiscreteOrdered v => [Range v] -> RSet v
makeRangedSet = [Range v] -> RSet v
forall v. DiscreteOrdered v => [Range v] -> RSet v
RSet ([Range v] -> RSet v)
-> ([Range v] -> [Range v]) -> [Range v] -> RSet v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Range v] -> [Range v]
forall v. DiscreteOrdered v => [Range v] -> [Range v]
normaliseRangeList


-- | Create a new Ranged Set from a list of ranges. @validRangeList ranges@
-- must return @True@.  This precondition is not checked.
unsafeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v
unsafeRangedSet :: forall v. DiscreteOrdered v => [Range v] -> RSet v
unsafeRangedSet = [Range v] -> RSet v
forall v. DiscreteOrdered v => [Range v] -> RSet v
RSet

-- | Create a Ranged Set from a single element.
rSingleton :: DiscreteOrdered v => v -> RSet v
rSingleton :: forall v. DiscreteOrdered v => v -> RSet v
rSingleton v
v = [Range v] -> RSet v
forall v. DiscreteOrdered v => [Range v] -> RSet v
unsafeRangedSet [v -> Range v
forall v. v -> Range v
singletonRange v
v]

-- | True if the set has no members.
rSetIsEmpty :: DiscreteOrdered v => RSet v -> Bool
rSetIsEmpty :: forall v. DiscreteOrdered v => RSet v -> Bool
rSetIsEmpty = [Range v] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([Range v] -> Bool) -> (RSet v -> [Range v]) -> RSet v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RSet v -> [Range v]
forall v. DiscreteOrdered v => RSet v -> [Range v]
rSetRanges


-- | True if the negation of the set has no members.
rSetIsFull :: DiscreteOrdered v => RSet v -> Bool
rSetIsFull :: forall v. DiscreteOrdered v => RSet v -> Bool
rSetIsFull = RSet v -> Bool
forall v. DiscreteOrdered v => RSet v -> Bool
rSetIsEmpty (RSet v -> Bool) -> (RSet v -> RSet v) -> RSet v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RSet v -> RSet v
forall a. DiscreteOrdered a => RSet a -> RSet a
rSetNegation


-- | True if the value is within the ranged set.  Infix precedence is left 5.
rSetHas, (-?-) :: DiscreteOrdered v => RSet v -> v -> Bool
rSetHas :: forall v. DiscreteOrdered v => RSet v -> v -> Bool
rSetHas (RSet [Range v]
ls) v
value = [Range v] -> Bool
rSetHas1 [Range v]
ls
   where
      rSetHas1 :: [Range v] -> Bool
rSetHas1 [] = Bool
False
      rSetHas1 (Range v
r:[Range v]
rs)
         | v
value v -> Boundary v -> Bool
forall v. Ord v => v -> Boundary v -> Bool
/>/ Range v -> Boundary v
forall v. Range v -> Boundary v
rangeLower Range v
r = Range v -> v -> Bool
forall v. Ord v => Range v -> v -> Bool
rangeHas Range v
r v
value Bool -> Bool -> Bool
|| [Range v] -> Bool
rSetHas1 [Range v]
rs
         | Bool
otherwise              = Bool
False

-?- :: forall v. DiscreteOrdered v => RSet v -> v -> Bool
(-?-) = RSet v -> v -> Bool
forall v. DiscreteOrdered v => RSet v -> v -> Bool
rSetHas

-- | True if the first argument is a subset of the second argument, or is
-- equal.
--
-- Infix precedence is left 5.
rSetIsSubset, (-<=-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool
rSetIsSubset :: forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
rSetIsSubset RSet v
rs1 RSet v
rs2 = RSet v -> Bool
forall v. DiscreteOrdered v => RSet v -> Bool
rSetIsEmpty (RSet v
rs1 RSet v -> RSet v -> RSet v
forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
-!- RSet v
rs2)
-<=- :: forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
(-<=-) = RSet v -> RSet v -> Bool
forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
rSetIsSubset


-- | True if the first argument is a strict subset of the second argument.
--
-- Infix precedence is left 5.
rSetIsSubsetStrict, (-<-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool
rSetIsSubsetStrict :: forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
rSetIsSubsetStrict RSet v
rs1 RSet v
rs2 =
   RSet v -> Bool
forall v. DiscreteOrdered v => RSet v -> Bool
rSetIsEmpty (RSet v
rs1 RSet v -> RSet v -> RSet v
forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
-!- RSet v
rs2)
   Bool -> Bool -> Bool
&& Bool -> Bool
not (RSet v -> Bool
forall v. DiscreteOrdered v => RSet v -> Bool
rSetIsEmpty (RSet v
rs2 RSet v -> RSet v -> RSet v
forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
-!- RSet v
rs1))

-<- :: forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
(-<-) = RSet v -> RSet v -> Bool
forall v. DiscreteOrdered v => RSet v -> RSet v -> Bool
rSetIsSubsetStrict

-- | Set union for ranged sets.  Infix precedence is left 6.
rSetUnion, (-\/-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
-- Implementation note: rSetUnion merges the two lists into a single
-- sorted list and then calls normalise to combine overlapping ranges.
rSetUnion :: forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetUnion (RSet [Range v]
ls1) (RSet [Range v]
ls2) = [Range v] -> RSet v
forall v. DiscreteOrdered v => [Range v] -> RSet v
RSet ([Range v] -> RSet v) -> [Range v] -> RSet v
forall a b. (a -> b) -> a -> b
$ [Range v] -> [Range v]
forall v. DiscreteOrdered v => [Range v] -> [Range v]
normalise ([Range v] -> [Range v]) -> [Range v] -> [Range v]
forall a b. (a -> b) -> a -> b
$ [Range v] -> [Range v] -> [Range v]
forall {a}. Ord a => [a] -> [a] -> [a]
merge [Range v]
ls1 [Range v]
ls2
   where
      merge :: [a] -> [a] -> [a]
merge [a]
ms1 [] = [a]
ms1
      merge [] [a]
ms2 = [a]
ms2
      merge ms1 :: [a]
ms1@(a
h1:[a]
t1) ms2 :: [a]
ms2@(a
h2:[a]
t2) =
         if a
h1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<  a
h2
            then a
h1 a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge [a]
t1 [a]
ms2
            else a
h2 a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge [a]
ms1 [a]
t2

-\/- :: forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
(-\/-) = RSet v -> RSet v -> RSet v
forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetUnion

-- | Set intersection for ranged sets.  Infix precedence is left 7.
rSetIntersection, (-/\-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetIntersection :: forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetIntersection (RSet [Range v]
ls1) (RSet [Range v]
ls2) =
   [Range v] -> RSet v
forall v. DiscreteOrdered v => [Range v] -> RSet v
RSet ([Range v] -> RSet v) -> [Range v] -> RSet v
forall a b. (a -> b) -> a -> b
$ (Range v -> Bool) -> [Range v] -> [Range v]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (Range v -> Bool) -> Range v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Range v -> Bool
forall v. DiscreteOrdered v => Range v -> Bool
rangeIsEmpty) ([Range v] -> [Range v]) -> [Range v] -> [Range v]
forall a b. (a -> b) -> a -> b
$ [Range v] -> [Range v] -> [Range v]
forall {v}.
DiscreteOrdered v =>
[Range v] -> [Range v] -> [Range v]
merge [Range v]
ls1 [Range v]
ls2
   where
      merge :: [Range v] -> [Range v] -> [Range v]
merge ms1 :: [Range v]
ms1@(Range v
h1:[Range v]
t1) ms2 :: [Range v]
ms2@(Range v
h2:[Range v]
t2) =
         Range v -> Range v -> Range v
forall v. DiscreteOrdered v => Range v -> Range v -> Range v
rangeIntersection Range v
h1 Range v
h2
         Range v -> [Range v] -> [Range v]
forall a. a -> [a] -> [a]
: if Range v -> Boundary v
forall v. Range v -> Boundary v
rangeUpper Range v
h1 Boundary v -> Boundary v -> Bool
forall a. Ord a => a -> a -> Bool
< Range v -> Boundary v
forall v. Range v -> Boundary v
rangeUpper Range v
h2
               then [Range v] -> [Range v] -> [Range v]
merge [Range v]
t1 [Range v]
ms2
               else [Range v] -> [Range v] -> [Range v]
merge [Range v]
ms1 [Range v]
t2
      merge [Range v]
_ [Range v]
_ = []

-/\- :: forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
(-/\-) = RSet v -> RSet v -> RSet v
forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetIntersection


-- | Set difference.  Infix precedence is left 6.
rSetDifference, (-!-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetDifference :: forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetDifference RSet v
rs1 RSet v
rs2 = RSet v
rs1 RSet v -> RSet v -> RSet v
forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
-/\- (RSet v -> RSet v
forall a. DiscreteOrdered a => RSet a -> RSet a
rSetNegation RSet v
rs2)
-!- :: forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
(-!-) = RSet v -> RSet v -> RSet v
forall v. DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetDifference


-- | Set negation.
rSetNegation :: DiscreteOrdered a => RSet a -> RSet a
rSetNegation :: forall a. DiscreteOrdered a => RSet a -> RSet a
rSetNegation RSet a
set = [Range a] -> RSet a
forall v. DiscreteOrdered v => [Range v] -> RSet v
RSet ([Range a] -> RSet a) -> [Range a] -> RSet a
forall a b. (a -> b) -> a -> b
$ [Boundary a] -> [Range a]
forall {v}. [Boundary v] -> [Range v]
ranges1 ([Boundary a] -> [Range a]) -> [Boundary a] -> [Range a]
forall a b. (a -> b) -> a -> b
$ [Boundary a]
setBounds1
   where
      ranges1 :: [Boundary v] -> [Range v]
ranges1 (Boundary v
b1:Boundary v
b2:[Boundary v]
bs) = Boundary v -> Boundary v -> Range v
forall v. Boundary v -> Boundary v -> Range v
Range Boundary v
b1 Boundary v
b2 Range v -> [Range v] -> [Range v]
forall a. a -> [a] -> [a]
: [Boundary v] -> [Range v]
ranges1 [Boundary v]
bs
      ranges1 [Boundary v
BoundaryAboveAll] = []
      ranges1 [Boundary v
b] = [Boundary v -> Boundary v -> Range v
forall v. Boundary v -> Boundary v -> Range v
Range Boundary v
b Boundary v
forall a. Boundary a
BoundaryAboveAll]
      ranges1 [Boundary v]
_ = []
      setBounds1 :: [Boundary a]
setBounds1 = case [Boundary a]
setBounds of
         (Boundary a
BoundaryBelowAll : [Boundary a]
bs)  -> [Boundary a]
bs
         [Boundary a]
_                        -> Boundary a
forall a. Boundary a
BoundaryBelowAll Boundary a -> [Boundary a] -> [Boundary a]
forall a. a -> [a] -> [a]
: [Boundary a]
setBounds
      setBounds :: [Boundary a]
setBounds = [Range a] -> [Boundary a]
forall {v}. [Range v] -> [Boundary v]
bounds ([Range a] -> [Boundary a]) -> [Range a] -> [Boundary a]
forall a b. (a -> b) -> a -> b
$ RSet a -> [Range a]
forall v. DiscreteOrdered v => RSet v -> [Range v]
rSetRanges RSet a
set
      bounds :: [Range v] -> [Boundary v]
bounds (Range v
r:[Range v]
rs) = Range v -> Boundary v
forall v. Range v -> Boundary v
rangeLower Range v
r Boundary v -> [Boundary v] -> [Boundary v]
forall a. a -> [a] -> [a]
: Range v -> Boundary v
forall v. Range v -> Boundary v
rangeUpper Range v
r Boundary v -> [Boundary v] -> [Boundary v]
forall a. a -> [a] -> [a]
: [Range v] -> [Boundary v]
bounds [Range v]
rs
      bounds [Range v]
_ = []

-- | The empty set.
rSetEmpty :: DiscreteOrdered a => RSet a
rSetEmpty :: forall a. DiscreteOrdered a => RSet a
rSetEmpty = [Range a] -> RSet a
forall v. DiscreteOrdered v => [Range v] -> RSet v
RSet []

-- | The set that contains everything.
rSetFull :: DiscreteOrdered a => RSet a
rSetFull :: forall a. DiscreteOrdered a => RSet a
rSetFull = [Range a] -> RSet a
forall v. DiscreteOrdered v => [Range v] -> RSet v
RSet [Boundary a -> Boundary a -> Range a
forall v. Boundary v -> Boundary v -> Range v
Range Boundary a
forall a. Boundary a
BoundaryBelowAll Boundary a
forall a. Boundary a
BoundaryAboveAll]

-- | Construct a range set.
rSetUnfold :: DiscreteOrdered a =>
   Boundary a
      -- ^ A first lower boundary.
   -> (Boundary a -> Boundary a)
      -- ^ A function from a lower boundary to an upper boundary, which must
      -- return a result greater than the argument (not checked).
   -> (Boundary a -> Maybe (Boundary a))
      -- ^ A function from a lower boundary to @Maybe@ the successor lower
      -- boundary, which must return a result greater than the argument
      -- (not checked).  If ranges overlap then they will be merged.
   -> RSet a
rSetUnfold :: forall a.
DiscreteOrdered a =>
Boundary a
-> (Boundary a -> Boundary a)
-> (Boundary a -> Maybe (Boundary a))
-> RSet a
rSetUnfold Boundary a
bound Boundary a -> Boundary a
upperFunc Boundary a -> Maybe (Boundary a)
succFunc = [Range a] -> RSet a
forall v. DiscreteOrdered v => [Range v] -> RSet v
RSet ([Range a] -> RSet a) -> [Range a] -> RSet a
forall a b. (a -> b) -> a -> b
$ [Range a] -> [Range a]
forall v. DiscreteOrdered v => [Range v] -> [Range v]
normalise ([Range a] -> [Range a]) -> [Range a] -> [Range a]
forall a b. (a -> b) -> a -> b
$ Boundary a -> [Range a]
ranges1 Boundary a
bound
   where
      ranges1 :: Boundary a -> [Range a]
ranges1 Boundary a
b =
         Boundary a -> Boundary a -> Range a
forall v. Boundary v -> Boundary v -> Range v
Range Boundary a
b (Boundary a -> Boundary a
upperFunc Boundary a
b)
         Range a -> [Range a] -> [Range a]
forall a. a -> [a] -> [a]
: case Boundary a -> Maybe (Boundary a)
succFunc Boundary a
b of
            Just Boundary a
b2 -> Boundary a -> [Range a]
ranges1 Boundary a
b2
            Maybe (Boundary a)
Nothing -> []