{-# LANGUAGE Safe #-}
module Data.RangeSet.Internal.TestingUtils (module Data.RangeSet.Internal.TestingUtils) where
import Prelude
import Control.Applicative (liftA2)
import Data.RangeSet.Internal.Types
import Data.RangeSet.Internal.Enum (diffE)
valid :: RangeSet a -> Bool
valid :: RangeSet a -> Bool
valid RangeSet a
t = RangeSet a -> Bool
forall a. RangeSet a -> Bool
balanced RangeSet a
t Bool -> Bool -> Bool
&& RangeSet a -> Bool
forall a. RangeSet a -> Bool
wellSized RangeSet a
t Bool -> Bool -> Bool
&& Bool -> RangeSet a -> Bool
forall a. Bool -> RangeSet a -> Bool
orderedNonOverlappingAndCompressed Bool
True RangeSet a
t
balanced :: RangeSet a -> Bool
balanced :: RangeSet a -> Bool
balanced RangeSet a
Tip = Bool
True
balanced (Fork Int
h Int
_ Int
_ Int
_ RangeSet a
lt RangeSet a
rt) =
Int
h Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int -> Int -> Int
forall a. Ord a => a -> a -> a
max (RangeSet a -> Int
forall a. RangeSet a -> Int
height RangeSet a
lt) (RangeSet a -> Int
forall a. RangeSet a -> Int
height RangeSet a
rt) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Bool -> Bool -> Bool
&&
RangeSet a -> Int
forall a. RangeSet a -> Int
height RangeSet a
rt Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
h Bool -> Bool -> Bool
&&
Int -> Int
forall a. Num a => a -> a
abs (RangeSet a -> Int
forall a. RangeSet a -> Int
height RangeSet a
lt Int -> Int -> Int
forall a. Num a => a -> a -> a
- RangeSet a -> Int
forall a. RangeSet a -> Int
height RangeSet a
rt) Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1 Bool -> Bool -> Bool
&&
RangeSet a -> Bool
forall a. RangeSet a -> Bool
balanced RangeSet a
lt Bool -> Bool -> Bool
&&
RangeSet a -> Bool
forall a. RangeSet a -> Bool
balanced RangeSet a
rt
wellSized :: RangeSet a -> Bool
wellSized :: RangeSet a -> Bool
wellSized RangeSet a
Tip = Bool
True
wellSized (Fork Int
_ Int
sz Int
l Int
u RangeSet a
lt RangeSet a
rt) = Int
sz Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== RangeSet a -> Int
forall a. RangeSet a -> Int
size RangeSet a
lt Int -> Int -> Int
forall a. Num a => a -> a -> a
+ RangeSet a -> Int
forall a. RangeSet a -> Int
size RangeSet a
rt Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int -> Int
diffE Int
l Int
u Bool -> Bool -> Bool
&& RangeSet a -> Bool
forall a. RangeSet a -> Bool
wellSized RangeSet a
lt Bool -> Bool -> Bool
&& RangeSet a -> Bool
forall a. RangeSet a -> Bool
wellSized RangeSet a
rt
orderedNonOverlappingAndCompressed :: Bool -> RangeSet a -> Bool
orderedNonOverlappingAndCompressed :: Bool -> RangeSet a -> Bool
orderedNonOverlappingAndCompressed Bool
checkCompressed = (Int -> Bool) -> (Int -> Bool) -> RangeSet a -> Bool
forall a. (Int -> Bool) -> (Int -> Bool) -> RangeSet a -> Bool
bounded (Bool -> Int -> Bool
forall a b. a -> b -> a
const Bool
True) (Bool -> Int -> Bool
forall a b. a -> b -> a
const Bool
True)
where
bounded :: (E -> Bool) -> (E -> Bool) -> RangeSet a -> Bool
bounded :: (Int -> Bool) -> (Int -> Bool) -> RangeSet a -> Bool
bounded Int -> Bool
_ Int -> Bool
_ RangeSet a
Tip = Bool
True
bounded Int -> Bool
lo Int -> Bool
hi (Fork Int
_ Int
_ Int
l Int
u RangeSet a
lt RangeSet a
rt) =
Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
u Bool -> Bool -> Bool
&&
Int -> Bool
lo Int
l Bool -> Bool -> Bool
&&
Int -> Bool
hi Int
u Bool -> Bool -> Bool
&&
(Int -> Bool) -> (Int -> Bool) -> RangeSet a -> Bool
forall a. (Int -> Bool) -> (Int -> Bool) -> RangeSet a -> Bool
bounded Int -> Bool
lo (Int -> Int -> Bool
boundAbove Int
l) RangeSet a
lt Bool -> Bool -> Bool
&&
(Int -> Bool) -> (Int -> Bool) -> RangeSet a -> Bool
forall a. (Int -> Bool) -> (Int -> Bool) -> RangeSet a -> Bool
bounded (Int -> Int -> Bool
boundBelow Int
u) Int -> Bool
hi RangeSet a
rt
boundAbove :: E -> E -> Bool
boundAbove :: Int -> Int -> Bool
boundAbove Int
l | Bool
checkCompressed = (Bool -> Bool -> Bool)
-> (Int -> Bool) -> (Int -> Bool) -> Int -> Bool
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Bool -> Bool -> Bool
(&&) (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
l) (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int -> Int
forall a. Enum a => a -> a
pred Int
l)
| Bool
otherwise = (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
l)
boundBelow :: E -> E -> Bool
boundBelow :: Int -> Int -> Bool
boundBelow Int
u | Bool
checkCompressed = (Bool -> Bool -> Bool)
-> (Int -> Bool) -> (Int -> Bool) -> Int -> Bool
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Bool -> Bool -> Bool
(&&) (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
u) (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int -> Int
forall a. Enum a => a -> a
succ Int
u)
| Bool
otherwise = (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
u)