{-# 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)

-- Testing Utilities
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)