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.

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.

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

Instances

Ord e => IntersectionQuery Seq e Seq

Defined in Data.Interval

Methods

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

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

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

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

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

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)

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

class of Intervals whose bounds can be adjusted

Minimal complete definition

adjustBounds

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

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

Comparing intervals

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

intersection query.

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

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.

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

genInterval /\ \i -> i `contains` i

genInterval /\* \i j -> (i `contains` j && j `contains` i) == (i==j)

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.

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

genInterval /\ \i -> genIntervalSeq /\ \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

genInterval /\* \i j -> j `contains` i == i `coveredBy` [j]

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

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

Find out the overlap of two time intervals.

genInterval /\ \i -> overlapTime i i == intervalDuration i

genInterval /\* \i j -> not (i `properlyIntersects` j) ==> overlapTime i j == 0

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

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

Prevailing annotation in the first time interval

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

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

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

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

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

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

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.

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.

genInterval /\* \i j -> i `properlyIntersects` j  ==  (properOverlap i j == EQ)

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.

genInterval /\* \i j -> isJust (maybeUnion i j) ==> fromJust (maybeUnion i j) `contains` i && fromJust (maybeUnion i j) `contains` j

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.

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)

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)

convex hull of a sorted sequence of intervals. the lower bound is guaranteed to be in the leftmost interval, but we have no guarantee of the upper bound.

genSortedIntervalSeq /\ \xs -> hullSeq xs == hull (toList 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)]

genInterval /\* \i j -> length (i `without` j) <= 2

genInterval /\ \i -> i `without` i == []

genInterval /\* \i j -> all (contains i) (i `without` j)

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.

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

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

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

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

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

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

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

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

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

genInterval /\ \i -> genSortedIntervalSeq /\ \js -> toList (getIntersects i js) `List.isSubsequenceOf` toList js

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

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

genSortedList /\ \xs -> (components $ toList $ fromEndPoints xs) == if length xs < 2 then [] else [(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, see sortByLeft) 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,3),(2,2),(3,6),(6,7)] :: [(Int,Int)])
([(2,3),(2,2),(3,6)],[(3,6),(6,7)])

genInterval /\ \i -> genSortedIntervals /\ \js -> fst (splitIntersecting i js) == filter (intersects i) js

genInterval /\ \i -> genSortedIntervals /\ \js -> 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)])

genInterval /\ \i -> genSortedIntervals /\ \js -> fst (splitProperlyIntersecting i js) == filter (properlyIntersects i) js

genInterval /\ \i -> genSortedIntervals /\ \js -> all (not.contains 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

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)

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.

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

extract all intervals intersecting a given one.

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

Intersection query. O(binsize+log(n/binsize)).

genInterval /\ \i -> genIntervalSeq /\ \t -> on (==) sortByLeft (getIntersectsIT i $ itree 2 t) (i `intersecting` t)

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

Intersection query. O(binsize+log(n/binsize)).

genInterval /\ \i -> genIntervalSeq /\ \t -> on (==) sortByLeft (getProperIntersectsIT i $ itree 2 t) (i `intersectingProperly` t)

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

When the actual result of getIntersectsIT is not important, only whether there are intersections.

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

When the actual result of getIntersectsIT is not important, only whether there are intersections.

leftmostInterval :: Interval e i => ITree e i -> Maybe i

retrieve the left-most interval from the tree, or Nothing if it is empty.

Non-overlapping intervals

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

Query an ordered Sequence of non-overlapping intervals for a predicate p that has the property

j contains k && p i k ==> p i j

and return all elements satisfying the predicate.

genInterval /\ \i -> genDisjointIntervalSeq /\ \js -> findSeq intersects i js == intersecting i js

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

Query an ordered Sequence of non-overlapping intervals for a predicate p that has the property

j contains k && p i k ==> p i j

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

O(log n) bounds of an ordered sequence of intervals. Nothing, if empty.

genDisjointIntervalSeq /\ \xs -> hullSeqNonOverlap xs == hullSeq xs

Debug

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

invariant to be maintained for proper intersection queries

invariant . itree 4 . fmap (\(x,y) -> (x, x + QC.getNonNegative y :: Integer))

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

transform the interval tree into the tree of hulls

Testing

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

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

splitSeq :: Seq a -> SplitSeq a

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