Data.Interval

This module provides the two-parameter type class Interval of types that represent closed intervals (meaning the end-points are included) possibly with some extra annotation. This approach is shared by the Data.IntervalMap.Generic.Interval module of the IntervalMap package. A particular use case are time intervals annotated with event data. The simplest example of an interval type i with end points of type e is the type i = (e,e).

The functions exported from this module are mainly concerned with overlap queries, that is, to identify which intervals in a collection overlap a given interval and if so, to what extent. This functionality is encapsuled in the class IntersectionQuery. If the collection of intervals is known to overlap in end-points only, one can simply use a sequence ordered by left end-point as the search structure. For arbitrary collections we provide the ITree structure (centered interval tree) which stores intervals in subtrees and bins that are annotated with their convex hull, so that it can be decided easily whether there is an interval inside which overlaps a given interval.

The behaviour of the functions is undefined for intervals that violate the implicit assumption that the left end-point is less than or equal to the right end-point.

The functionality provided is similar to the Interval data type in the data-interval package but we focus on closed intervals and let the user decide which concrete data type to use.

Most functions are property-checked for correctness. Checks were implemented by Henning Thielemann.

Types and type classes

class Ord e => Interval e i | i -> e where

class of intervals with end points in a totally ordered type

Minimal complete definition

lb, ub | endPoints

Methods

lb

Arguments

:: i

-> e

lower bound

ub

Arguments

:: i

-> e

upper bound

endPoints

Arguments

:: i

-> (e, e)

end points (inclusive)

Instances

Ord e => Interval e (Identity e)

Defined in Data.Interval

Methods

lb :: Identity e -> e

ub :: Identity e -> e

endPoints :: Identity e -> (e, e)

Ord e => Interval e (e, e)

Defined in Data.Interval

Methods

lb :: (e, e) -> e

ub :: (e, e) -> e

endPoints :: (e, e) -> (e, e)

class Foldable f => IntersectionQuery t e f | t -> f where

class of search structures for interval intersection queries, returning a Foldable of intervals.

Minimal complete definition

getIntersects, getProperIntersects, someIntersects, someProperlyIntersects, maybeBounds, storedIntervals

Methods

getIntersects :: (Interval e i, Interval e j) => i -> t j -> f j

all intervalls touching the first one

getProperIntersects :: (Interval e i, Interval e j) => i -> t j -> f j

all intervals properly intersecting the first one

someIntersects :: (Interval e i, Interval e j) => i -> t j -> Bool

does any interval touch the first one?

someProperlyIntersects :: (Interval e i, Interval e j) => i -> t j -> Bool

does any interval properly intersect the first one?

maybeBounds :: Interval e i => t i -> Maybe (e, e)

the convex hull of the contents

storedIntervals :: Interval e i => t i -> f i

dump the entire search structure's content

Instances

Ord e => IntersectionQuery NonNestedSeq e Seq

Defined in Data.Interval

Methods

getIntersects :: (Interval e i, Interval e j) => i -> NonNestedSeq j -> Seq j

getProperIntersects :: (Interval e i, Interval e j) => i -> NonNestedSeq j -> Seq j

someIntersects :: (Interval e i, Interval e j) => i -> NonNestedSeq j -> Bool

someProperlyIntersects :: (Interval e i, Interval e j) => i -> NonNestedSeq j -> Bool

maybeBounds :: Interval e i => NonNestedSeq i -> Maybe (e, e)

storedIntervals :: Interval e i => NonNestedSeq i -> Seq i

Ord e => IntersectionQuery (ITree e) e Seq

Defined in Data.Interval

Methods

getIntersects :: (Interval e i, Interval e j) => i -> ITree e j -> Seq j

getProperIntersects :: (Interval e i, Interval e j) => i -> ITree e j -> Seq j

someIntersects :: (Interval e i, Interval e j) => i -> ITree e j -> Bool

someProperlyIntersects :: (Interval e i, Interval e j) => i -> ITree e j -> Bool

maybeBounds :: Interval e i => ITree e i -> Maybe (e, e)

storedIntervals :: Interval e i => ITree e i -> Seq i

class Interval e i => Adjust e i | i -> e where

class of Intervals whose bounds can be adjusted

Methods

adjustBounds

Arguments

:: (e -> e)

-> (e -> e)

-> i

-> i

adjust lower and upper bound

shift

Arguments

:: (e -> e)

-> i

-> i

change both bounds using the same function

Instances

Ord e => Adjust e (e, e)

Defined in Data.Interval

Methods

adjustBounds :: (e -> e) -> (e -> e) -> (e, e) -> (e, e)

shift :: (e -> e) -> (e, e) -> (e, e)

class TimeDifference t where

Time types supporting differences

Minimal complete definition

diffTime, addTime

Methods

diffTime :: t -> t -> NominalDiffTime

addTime :: NominalDiffTime -> t -> t

Instances

TimeDifference ZonedTime

addTime preserves the TimeZone

Defined in Data.Interval

Methods

diffTime :: ZonedTime -> ZonedTime -> NominalDiffTime

addTime :: NominalDiffTime -> ZonedTime -> ZonedTime

TimeDifference LocalTime

Defined in Data.Interval

Methods

diffTime :: LocalTime -> LocalTime -> NominalDiffTime

addTime :: NominalDiffTime -> LocalTime -> LocalTime

TimeDifference UTCTime

Defined in Data.Interval

Methods

diffTime :: UTCTime -> UTCTime -> NominalDiffTime

addTime :: NominalDiffTime -> UTCTime -> UTCTime

newtype NonNestedSeq a

Sequences support IntersectionQuery efficiently only in the case when the sequence has the property that for any split xs = ys <> zs into non-empty parts the convex hull of each part is the lb and ub of the leftmost and rightmost element, respectively. This property is guaranteed by fromEndPoints but does not hold in the case where the sequence contains nested intervals:

>>> propSplit (\xs -> hullSeqNonNested xs == hullSeq xs) . splitSeq . sortByRight $ Seq.fromList ([(1,3),(2,4),(4,5),(3,6)] :: [(Int,Int)])
False

Thus, when querying against a set of intervals with nesting, you must use an ITree instead.

forevery genNonNestedIntervalSeq $ \xs -> propSplit (\subseq -> hullSeqNonNested subseq == hullSeq subseq) (splitSeq xs)

Constructors

FromSortedSeq

Fields

• getSeq :: Seq a

Instances

Monad NonNestedSeq

Beware that using >>= may destroy non-nestedness.

Defined in Data.Interval

Methods

(>>=) :: NonNestedSeq a -> (a -> NonNestedSeq b) -> NonNestedSeq b

(>>) :: NonNestedSeq a -> NonNestedSeq b -> NonNestedSeq b

return :: a -> NonNestedSeq a

fail :: String -> NonNestedSeq a

Functor NonNestedSeq

Defined in Data.Interval

Methods

fmap :: (a -> b) -> NonNestedSeq a -> NonNestedSeq b

(<$) :: a -> NonNestedSeq b -> NonNestedSeq a

Applicative NonNestedSeq

Defined in Data.Interval

Methods

pure :: a -> NonNestedSeq a

(<*>) :: NonNestedSeq (a -> b) -> NonNestedSeq a -> NonNestedSeq b

liftA2 :: (a -> b -> c) -> NonNestedSeq a -> NonNestedSeq b -> NonNestedSeq c

(*>) :: NonNestedSeq a -> NonNestedSeq b -> NonNestedSeq b

(<*) :: NonNestedSeq a -> NonNestedSeq b -> NonNestedSeq a

Foldable NonNestedSeq

Defined in Data.Interval

Methods

fold :: Monoid m => NonNestedSeq m -> m

foldMap :: Monoid m => (a -> m) -> NonNestedSeq a -> m

foldr :: (a -> b -> b) -> b -> NonNestedSeq a -> b

foldr' :: (a -> b -> b) -> b -> NonNestedSeq a -> b

foldl :: (b -> a -> b) -> b -> NonNestedSeq a -> b

foldl' :: (b -> a -> b) -> b -> NonNestedSeq a -> b

foldr1 :: (a -> a -> a) -> NonNestedSeq a -> a

foldl1 :: (a -> a -> a) -> NonNestedSeq a -> a

toList :: NonNestedSeq a -> [a]

null :: NonNestedSeq a -> Bool

length :: NonNestedSeq a -> Int

elem :: Eq a => a -> NonNestedSeq a -> Bool

maximum :: Ord a => NonNestedSeq a -> a

minimum :: Ord a => NonNestedSeq a -> a

sum :: Num a => NonNestedSeq a -> a

product :: Num a => NonNestedSeq a -> a

Traversable NonNestedSeq

Defined in Data.Interval

Methods

traverse :: Applicative f => (a -> f b) -> NonNestedSeq a -> f (NonNestedSeq b)

sequenceA :: Applicative f => NonNestedSeq (f a) -> f (NonNestedSeq a)

mapM :: Monad m => (a -> m b) -> NonNestedSeq a -> m (NonNestedSeq b)

sequence :: Monad m => NonNestedSeq (m a) -> m (NonNestedSeq a)

Alternative NonNestedSeq

Beware that using * may destroy non-nestedness.

Defined in Data.Interval

Methods

empty :: NonNestedSeq a

(<|>) :: NonNestedSeq a -> NonNestedSeq a -> NonNestedSeq a

some :: NonNestedSeq a -> NonNestedSeq [a]

many :: NonNestedSeq a -> NonNestedSeq [a]

Filtrable NonNestedSeq

Defined in Data.Interval

Methods

mapMaybe :: (a -> Maybe b) -> NonNestedSeq a -> NonNestedSeq b

catMaybes :: NonNestedSeq (Maybe a) -> NonNestedSeq a

filter :: (a -> Bool) -> NonNestedSeq a -> NonNestedSeq a

mapMaybeA :: (Traversable NonNestedSeq, Applicative p) => (a -> p (Maybe b)) -> NonNestedSeq a -> p (NonNestedSeq b)

filterA :: (Traversable NonNestedSeq, Applicative p) => (a -> p Bool) -> NonNestedSeq a -> p (NonNestedSeq a)

mapEither :: (a -> Either b c) -> NonNestedSeq a -> (NonNestedSeq b, NonNestedSeq c)

mapEitherA :: (Traversable NonNestedSeq, Applicative p) => (a -> p (Either b c)) -> NonNestedSeq a -> p (NonNestedSeq b, NonNestedSeq c)

partitionEithers :: NonNestedSeq (Either a b) -> (NonNestedSeq a, NonNestedSeq b)

Ord e => IntersectionQuery NonNestedSeq e Seq

Defined in Data.Interval

Methods

getIntersects :: (Interval e i, Interval e j) => i -> NonNestedSeq j -> Seq j

getProperIntersects :: (Interval e i, Interval e j) => i -> NonNestedSeq j -> Seq j

someIntersects :: (Interval e i, Interval e j) => i -> NonNestedSeq j -> Bool

someProperlyIntersects :: (Interval e i, Interval e j) => i -> NonNestedSeq j -> Bool

maybeBounds :: Interval e i => NonNestedSeq i -> Maybe (e, e)

storedIntervals :: Interval e i => NonNestedSeq i -> Seq i

Eq a => Eq (NonNestedSeq a)

Defined in Data.Interval

Methods

(==) :: NonNestedSeq a -> NonNestedSeq a -> Bool

(/=) :: NonNestedSeq a -> NonNestedSeq a -> Bool

Ord a => Ord (NonNestedSeq a)

Defined in Data.Interval

Methods

compare :: NonNestedSeq a -> NonNestedSeq a -> Ordering

(<) :: NonNestedSeq a -> NonNestedSeq a -> Bool

(<=) :: NonNestedSeq a -> NonNestedSeq a -> Bool

(>) :: NonNestedSeq a -> NonNestedSeq a -> Bool

(>=) :: NonNestedSeq a -> NonNestedSeq a -> Bool

max :: NonNestedSeq a -> NonNestedSeq a -> NonNestedSeq a

min :: NonNestedSeq a -> NonNestedSeq a -> NonNestedSeq a

Show a => Show (NonNestedSeq a)

Defined in Data.Interval

Methods

showsPrec :: Int -> NonNestedSeq a -> ShowS

show :: NonNestedSeq a -> String

showList :: [NonNestedSeq a] -> ShowS

Semigroup (NonNestedSeq a)

Defined in Data.Interval

Methods

(<>) :: NonNestedSeq a -> NonNestedSeq a -> NonNestedSeq a

sconcat :: NonEmpty (NonNestedSeq a) -> NonNestedSeq a

stimes :: Integral b => b -> NonNestedSeq a -> NonNestedSeq a

Monoid (NonNestedSeq a)

Defined in Data.Interval

Methods

mempty :: NonNestedSeq a

mappend :: NonNestedSeq a -> NonNestedSeq a -> NonNestedSeq a

mconcat :: [NonNestedSeq a] -> NonNestedSeq a

Comparing intervals

intersects :: (Interval e i, Interval e j) => i -> j -> Bool

intersection query.

>>> ((1,2)::(Int,Int)) `intersects` ((2,3)::(Int,Int))
True

foreveryPair genInterval $ \i j -> (lb i <= ub i && lb j <= ub j && i `intersects` j)  ==  (max (lb i) (lb j) <= min (ub i) (ub j))

properlyIntersects :: (Interval e i, Interval e j) => i -> j -> Bool

proper intersection.

foreveryPair genInterval $ \i j -> ((i `intersects` j) && not (i `properlyIntersects` j))  ==  (ub i == lb j || ub j == lb i)

contains :: (Interval e i, Interval e j) => i -> j -> Bool

subset containment

forevery     genInterval $ \i -> i `contains` i

foreveryPair genInterval $ \i j -> (i `contains` j && j `contains` i) == (i==j)

foreveryPair genInterval $ \i j -> i `contains` j == (maybeUnion i j == Just i)

properlyContains :: (Interval e i, Interval e j) => i -> j -> Bool

proper subset containment

covered :: (Interval e i, Interval e j, Adjust e j) => i -> Seq j -> Seq j

compute the components of the part of i covered by the intervals.

foreveryPairOf genInterval genIntervalSeq $ \i js -> all (contains i) (covered i js)

foreveryPairOf genInterval genIntervalSeq $ \i js -> covered i (covered i js) == covered i js

coveredBy :: (Interval e i, Interval e j, Foldable f) => i -> f j -> Bool

True if the first interval is completely covered by the given intervals

foreveryPair   genInterval $ \i j -> j `contains` i == i `coveredBy` [j]

foreveryPairOf genInterval genSortedIntervals $ \i js -> i `coveredBy` js ==> any (flip contains i) (components js)

overlap :: (Interval e i, Interval e j) => i -> j -> Ordering

Overlap ordering. Returns LT or GT if the intervals are disjoint, EQ if the intervals overlap. Note that this violates the following property:

overlap x y == EQ && overlap y z == EQ => overlap x z == EQ

i.e., overlap is not transitive.

foreveryPair genInterval $ \i j -> i `intersects` j  ==  (overlap i j == EQ)

properOverlap :: (Interval e i, Interval e j) => i -> j -> Ordering

Overlap ordering. Returns LT or GT if the intervals are disjoint or touch in end point(s) only, EQ if the intervals properly overlap. Note that this violates the following property:

properOverlap x y == EQ && properOverlap y z == EQ => properOverlap x z == EQ

i.e., properOverlap is not transitive.

foreveryPair genInterval $ \i j -> i `properlyIntersects` j  ==  (properOverlap i j == EQ)

Time intervals

overlapTime :: (TimeDifference t, Interval t i, Interval t j) => i -> j -> NominalDiffTime

Find out the overlap of two time intervals.

forevery genInterval     $ \i -> overlapTime i i == intervalDuration i

foreveryPair genInterval $ \i j -> not (i `properlyIntersects` j) ==> overlapTime i j == 0

foreveryPair genInterval $ \i j -> overlapTime i j == (sum $ fmap intervalDuration $ maybeIntersection i j)

fractionCovered :: (TimeDifference t, Interval t i, Interval t j, Fractional a) => j -> Seq i -> a

percentage of coverage of the first interval by the second sequence of intervals

foreveryPairOf genNonEmptyInterval genIntervalSeq         $ \i js -> i `coveredBy` js == (fractionCovered i js >= (1::Rational))

foreveryPairOf genNonEmptyInterval genNonEmptyIntervalSeq $ \i js -> any (properlyIntersects i) js == (fractionCovered i js > (0::Rational))

prevailing :: (Interval t i, Interval t j, TimeDifference t) => i -> Seq (a, j) -> Maybe a

Prevailing annotation in the first time interval

forevery genInterval $ \i c -> prevailing i (Seq.singleton (c,i)) == Just (c::Char)

foreveryPairOf genInterval genLabeledSeq $ \i js -> isJust (prevailing i js) == any (intersects i . snd) js

forevery genInterval $ \i -> foreveryPair genLabeledSeq $ \js ks -> all (flip elem $ catMaybes [prevailing i js, prevailing i ks]) $ prevailing i (js<>ks)

intervalDuration :: (TimeDifference t, Interval t i) => i -> NominalDiffTime

Convenience function, the diffTime between the endPoints.

Operations on intervals

maybeUnion :: (Interval e j, Interval e i, Adjust e i) => j -> i -> Maybe i

the union of two intervals is an interval if they intersect.

foreveryPair genInterval $ \i j -> isJust (maybeUnion i j) ==> fromJust (maybeUnion i j) `contains` i && fromJust (maybeUnion i j) `contains` j

foreveryPair genInterval $ \i j -> i `intersects` j ==> (maybeUnion i j >>= maybeIntersection i) == Just i

maybeIntersection :: (Interval e j, Interval e i, Adjust e i) => j -> i -> Maybe i

the intersection of two intervals is either empty or an interval.

foreveryPair genInterval $ \i j -> i `intersects` j ==> i `contains` fromJust (maybeIntersection i j)

hull :: (Interval e i, Foldable f, Functor f) => f i -> Maybe (e, e)

O(n) convex hull

\xs -> isJust (hull xs) ==> all (\x -> fromJust (hull xs) `contains` x) (xs :: [(Int,Int)])

hullSeq :: Interval e i => Seq i -> Maybe (e, e)

O(n) convex hull of a sorted (sortByRight) sequence of intervals. the upper bound is guaranteed to be in the rightmost interval, but we have no guarantee of the lower bound.

forevery genSortedIntervalSeq $ \xs -> hullSeq xs == if Seq.null xs then Nothing else Just (minimum (fmap lb xs),maximum (fmap ub xs))

forevery genSortedIntervalSeq $ \xs -> hullSeq xs == hull (toList xs)

hullSeqNonNested :: Interval e i => Seq i -> Maybe (e, e)

O(1) bounds of an ordered, non-nested sequence of intervals. Nothing, if empty.

forevery genNonNestedIntervalSeq $ \xs -> hullSeqNonNested xs == hullSeq xs

without :: (Adjust e i, Interval e j) => i -> j -> [i]

Set difference. The resulting list has zero, one or two elements.

>>> without' (1,5) (4,5)
[(1,4)]
>>> without' (1,5) (2,3)
[(1,2),(3,5)]
>>> without' (1,5) (1,5)
[]
>>> without' (1,5) (0,1)
[(1,5)]

foreveryPair genInterval $ \i j -> length (i `without` j) <= 2

forevery     genInterval $ \i -> i `without` i == []

foreveryPair genInterval $ \i j -> all (contains i) (i `without` j)

foreveryPair genInterval $ \i j -> not $ any (properlyIntersects j) (i `without` j)

contiguous :: Interval e i => [i] -> [[i]]

intersects is not an equivalence relation, because it is not transitive. Hence groupBy intersects does not do what one might expect. This function does the expected and groups overlapping intervals into contiguous blocks.

forevery genSortedIntervals $ all (\xs -> and $ List.zipWith intersects xs (tail xs)) . contiguous

forevery genSortedIntervals $ all ((1==).length.components) . contiguous

components :: (Interval e i, Adjust e i) => [i] -> [i]

Connected components of a list sorted by sortByRight, akin to groupBy intersects. The precondition is not checked.

forevery genSortedIntervals $ \xs -> all (\i -> any (flip contains i) (components xs)) xs

forevery genSortedIntervals $ \xs -> let cs = components xs in all (\(i,j) -> i == j || not (i `intersects` j)) [(c1,c2) | c1 <- cs, c2 <- cs]

componentsSeq :: (Interval e i, Adjust e i) => Seq i -> Seq i

same as components. Is there a way to unify both?

forevery genSortedIntervals   $ \xs -> componentsSeq (Seq.fromList xs) == Seq.fromList (components xs)

forevery genSortedIntervalSeq $ \xs -> let cs = componentsSeq xs in all (\(i,j) -> i == j || not (i `intersects` j)) $ do {c1 <- cs; c2 <- cs; return (c1,c2)}

sortByRight :: Interval e i => Seq i -> Seq i

lexicographical sort by ub, then inverse lb. In the resulting list, the intervals intersecting a given interval form a contiguous sublist.

foreveryPairOf genInterval genSortedIntervalSeq $ \i js -> toList (getIntersects i (FromSortedSeq js)) `List.isSubsequenceOf` toList js

forevery genSortedIntervalSeq $ \xs -> propSplit (\subseq -> subseq == sortByRight subseq) (splitSeq xs)

fromEndPoints :: Ord e => [e] -> Seq (e, e)

construct a sorted contiguous sequence of intervals from a sorted sequence of bounds. Fails if the input sequence is not sorted.

forevery genSortedList $ \xs -> (components $ toList $ fromEndPoints xs) == if length xs < 2 then [] else [(head xs, last xs)]

forevery genSortedList $ \xs -> hullSeqNonNested (fromEndPoints xs) == if length xs < 2 then Nothing else Just (head xs,last xs)

Streaming intervals

splitIntersecting :: (Interval e i, Interval e j) => i -> [j] -> ([j], [j])

When you face the problem of matching two series of intervals against each other, a streaming approach might be more efficient than transforming one of the streams into a search structure. This function drops intervals from the list until the (contiguous) block of intersecting intervals is found. This block (except intervals containing the ub of the query) is removed from the stream. When used as a state transformer on a stream [i] of non-properly overlapping intervals, then one obtains the stream of blocks intersecting the stream of queries.

>>> splitIntersecting ((2,5) :: (Int,Int)) ([(0,1),(2,2),(2,3),(3,6),(6,7)] :: [(Int,Int)])
([(2,2),(2,3),(3,6)],[(3,6),(6,7)])

foreveryPairOf genInterval genNonNestedIntervalSeq $ \i js' -> let js = toList js' in fst (splitIntersecting i js) == filter (intersects i) js

foreveryPairOf genInterval genNonNestedIntervalSeq $ \i js' -> let js = toList js' in all (\j -> not (ub j < ub i)) (snd (splitIntersecting i js))

splitProperlyIntersecting :: (Interval e i, Interval e j) => i -> [j] -> ([j], [j])

Like splitIntersecting but disregards those intervals that merely touch the query. Retains overlapping intervals properly containing the ub of the query. When used as a state transformer on an ascending stream [i] of non-properly overlapping intervals, then one obtains the stream of blocks properly intersecting the stream of queries.

>>> splitProperlyIntersecting ((2,5) :: (Int,Int))  ([(0,1),(2,3),(2,2),(3,5),(5,6),(6,7)] :: [(Int,Int)])
([(2,3),(3,5)],[(5,6),(6,7)])

foreveryPairOf genInterval genNonNestedIntervalSeq $ \i js' -> let js = toList js' in fst (splitProperlyIntersecting i js) == filter (properlyIntersects i) js

foreveryPairOf genInterval genNonNestedIntervalSeq $ \i js' -> let js = toList js' in all (not.properlyContains i) (snd (splitProperlyIntersecting i js))

Interval search tree

data ITree e i

Search tree of intervals.

Instances

Functor (ITree e)

Defined in Data.Interval

Methods

fmap :: (a -> b) -> ITree e a -> ITree e b

(<$) :: a -> ITree e b -> ITree e a

Foldable (ITree e)

Defined in Data.Interval

Methods

fold :: Monoid m => ITree e m -> m

foldMap :: Monoid m => (a -> m) -> ITree e a -> m

foldr :: (a -> b -> b) -> b -> ITree e a -> b

foldr' :: (a -> b -> b) -> b -> ITree e a -> b

foldl :: (b -> a -> b) -> b -> ITree e a -> b

foldl' :: (b -> a -> b) -> b -> ITree e a -> b

foldr1 :: (a -> a -> a) -> ITree e a -> a

foldl1 :: (a -> a -> a) -> ITree e a -> a

toList :: ITree e a -> [a]

null :: ITree e a -> Bool

length :: ITree e a -> Int

elem :: Eq a => a -> ITree e a -> Bool

maximum :: Ord a => ITree e a -> a

minimum :: Ord a => ITree e a -> a

sum :: Num a => ITree e a -> a

product :: Num a => ITree e a -> a

Ord e => IntersectionQuery (ITree e) e Seq

Defined in Data.Interval

Methods

getIntersects :: (Interval e i, Interval e j) => i -> ITree e j -> Seq j

getProperIntersects :: (Interval e i, Interval e j) => i -> ITree e j -> Seq j

someIntersects :: (Interval e i, Interval e j) => i -> ITree e j -> Bool

someProperlyIntersects :: (Interval e i, Interval e j) => i -> ITree e j -> Bool

maybeBounds :: Interval e i => ITree e i -> Maybe (e, e)

storedIntervals :: Interval e i => ITree e i -> Seq i

itree :: Interval e i => Int -> Seq i -> ITree e i

Construct an interval tree with bins of maximal given size. The function first sorts the intervals, then splits into chunks of given size. The leftmost endpoints of the chunks define boundary points. Next, all intervals properly overlapping a boundary are removed from the chunks and kept separately. The chunks are arranged as the leaves of a binary search tree. Then the intervals overlapping boundaries are placed at internal nodes of the tree. Hence if all intervals are mutually non-overlapping properly, the resulting tree is a pure binary search tree with bins of given size as leaves.

emptyITree :: ITree e i

the empty ITree

insert :: Interval e i => i -> ITree e i -> ITree e i

insert the interval at the deepest possible location into the tree. Does not change the overall structure, in particular no re-balancing is performed.

hullOfTree :: Interval e i => ITree e i -> Maybe (e, e)

smallest interval covering the entire tree. Nothing if the tree is empty.

forevery genSortedIntervalSeq $ \xs -> hullSeq xs == hullOfTree (itree 4 xs)

Debug

invariant :: Interval e i => ITree e i -> Bool

invariant to be maintained for proper intersection queries

forevery genIntervalSeq $ \xs -> invariant . itree 4 $ xs

toTree :: Interval e i => ITree e i -> Tree (e, e)

transform the interval tree into the tree of hulls

Testing

intersecting :: (Interval e i, Interval e j) => j -> Seq i -> Seq i

O(n) Extract all intervals intersecting a given one.

intersectingProperly :: (Interval e i, Interval e j) => j -> Seq i -> Seq i

O(n) Extract all intervals properly intersecting a given one.

filterM :: (Applicative f, Traversable t, Alternative m) => (a -> f Bool) -> t a -> f (m a)

generalises Control.Monad.filterM

joinSeq :: SplitSeq a -> Seq a

re-assemble a split into a sequence

propSplit :: (Seq a -> Bool) -> SplitSeq a -> Bool

test if a sequence property holds for each sequence in the split.

splitSeq :: Seq a -> SplitSeq a

Split a Sequence in half, needed for the IntersectionQuery instance. prop> forevery genIntervalSeq $ is -> joinSeq (splitSeq is) == is