Copyright  (c) Lackmann Phymetric 

License  GPL3 
Maintainer  olaf.klinke@phymetric.de 
Stability  experimental 
Safe Haskell  Safe 
Language  Haskell2010 
This module provides the twoparameter type class Interval
of types
that represent closed intervals (meaning the endpoints 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 endpoints only,
one can simply use a sequence ordered by left endpoint 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 endpoint is less than or equal to the right endpoint.
The functionality provided is similar to the Interval data type in the datainterval package but we focus on closed intervals and let the user decide which concrete data type to use.
Most functions are propertychecked for correctness. Checks were implemented by Henning Thielemann.
Synopsis
 class Ord e => Interval e i  i > e where
 class Foldable f => IntersectionQuery t e f  t > f where
 class Interval e i => Adjust e i  i > e where
 class TimeDifference t where
 newtype NonNestedSeq a = FromSortedSeq {}
 intersects :: (Interval e i, Interval e j) => i > j > Bool
 properlyIntersects :: (Interval e i, Interval e j) => i > j > Bool
 contains :: (Interval e i, Interval e j) => i > j > Bool
 properlyContains :: (Interval e i, Interval e j) => i > j > Bool
 covered :: (Interval e i, Interval e j, Adjust e j) => i > Seq j > Seq j
 coveredBy :: (Interval e i, Interval e j, Foldable f) => i > f j > Bool
 overlap :: (Interval e i, Interval e j) => i > j > Ordering
 properOverlap :: (Interval e i, Interval e j) => i > j > Ordering
 overlapTime :: (TimeDifference t, Interval t i, Interval t j) => i > j > NominalDiffTime
 fractionCovered :: (TimeDifference t, Interval t i, Interval t j, Fractional a) => j > Seq i > a
 prevailing :: (Interval t i, Interval t j, TimeDifference t) => i > Seq (a, j) > Maybe a
 intervalDuration :: (TimeDifference t, Interval t i) => i > NominalDiffTime
 maybeUnion :: (Interval e j, Interval e i, Adjust e i) => j > i > Maybe i
 maybeIntersection :: (Interval e j, Interval e i, Adjust e i) => j > i > Maybe i
 hull :: (Interval e i, Foldable f, Functor f) => f i > Maybe (e, e)
 hullSeq :: Interval e i => Seq i > Maybe (e, e)
 hullSeqNonNested :: Interval e i => Seq i > Maybe (e, e)
 without :: (Adjust e i, Interval e j) => i > j > [i]
 contiguous :: Interval e i => [i] > [[i]]
 components :: (Interval e i, Adjust e i) => [i] > [i]
 componentsSeq :: (Interval e i, Adjust e i) => Seq i > Seq i
 sortByRight :: Interval e i => Seq i > Seq i
 fromEndPoints :: Ord e => [e] > Seq (e, e)
 splitIntersecting :: (Interval e i, Interval e j) => i > [j] > ([j], [j])
 splitProperlyIntersecting :: (Interval e i, Interval e j) => i > [j] > ([j], [j])
 data ITree e i
 itree :: Interval e i => Int > Seq i > ITree e i
 emptyITree :: ITree e i
 insert :: Interval e i => i > ITree e i > ITree e i
 hullOfTree :: Interval e i => ITree e i > Maybe (e, e)
 invariant :: Interval e i => ITree e i > Bool
 toTree :: Interval e i => ITree e i > Tree (e, e)
 intersecting :: (Interval e i, Interval e j) => j > Seq i > Seq i
 intersectingProperly :: (Interval e i, Interval e j) => j > Seq i > Seq i
 filterM :: (Applicative f, Traversable t, Alternative m) => (a > f Bool) > t a > f (m a)
 joinSeq :: SplitSeq a > Seq a
 propSplit :: (Seq a > Bool) > SplitSeq a > Bool
 splitSeq :: Seq a > SplitSeq a
Types and type classes
class Ord e => Interval e i  i > e where Source #
class of intervals with end points in a totally ordered type
:: i  
> e  lower bound 
:: i  
> e  upper bound 
:: i  
> (e, e)  end points (inclusive) 
class Foldable f => IntersectionQuery t e f  t > f where Source #
class of search structures for interval intersection queries,
returning a Foldable
of intervals.
getIntersects, getProperIntersects, someIntersects, someProperlyIntersects, maybeBounds, storedIntervals
getIntersects :: (Interval e i, Interval e j) => i > t j > f j Source #
all intervalls touching the first one
getProperIntersects :: (Interval e i, Interval e j) => i > t j > f j Source #
all intervals properly intersecting the first one
someIntersects :: (Interval e i, Interval e j) => i > t j > Bool Source #
does any interval touch the first one?
someProperlyIntersects :: (Interval e i, Interval e j) => i > t j > Bool Source #
does any interval properly intersect the first one?
maybeBounds :: Interval e i => t i > Maybe (e, e) Source #
the convex hull of the contents
storedIntervals :: Interval e i => t i > f i Source #
dump the entire search structure's content
Instances
class Interval e i => Adjust e i  i > e where Source #
class of Intervals whose bounds can be adjusted
:: (e > e)  
> (e > e)  
> i  
> i  adjust lower and upper bound 
:: (e > e)  
> i  
> i  change both bounds using the same function 
class TimeDifference t where Source #
Time types supporting differences
diffTime :: t > t > NominalDiffTime Source #
addTime :: NominalDiffTime > t > t Source #
Instances
TimeDifference ZonedTime Source # 

Defined in Data.Interval  
TimeDifference LocalTime Source #  
Defined in Data.Interval  
TimeDifference UTCTime Source #  
Defined in Data.Interval 
newtype NonNestedSeq a Source #
Seq
uences support IntersectionQuery
efficiently only in the case
when the sequence has the property that for
any split xs = ys <> zs
into nonempty 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)
Instances
Comparing intervals
intersects :: (Interval e i, Interval e j) => i > j > Bool Source #
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 Source #
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 Source #
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 Source #
proper subset containment
covered :: (Interval e i, Interval e j, Adjust e j) => i > Seq j > Seq j Source #
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 Source #
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 Source #
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 Source #
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 Source #
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 Source #
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 Source #
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 Source #
Operations on intervals
maybeUnion :: (Interval e j, Interval e i, Adjust e i) => j > i > Maybe i Source #
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 Source #
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) Source #
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) Source #
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) Source #
O(1) bounds of an ordered, nonnested sequence of intervals. Nothing
, if empty.
forevery genNonNestedIntervalSeq $ \xs > hullSeqNonNested xs == hullSeq xs
without :: (Adjust e i, Interval e j) => i > j > [i] Source #
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]] Source #
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] Source #
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 Source #
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 Source #
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) Source #
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]) Source #
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 nonproperly 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]) Source #
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 nonproperly 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
Search tree of intervals.
Instances
Functor (ITree e) Source #  
Foldable (ITree e) Source #  
Defined in Data.Interval 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 # elem :: Eq a => a > ITree e a > Bool # maximum :: Ord a => ITree e a > a # minimum :: Ord a => ITree e a > a #  
Ord e => IntersectionQuery (ITree e) e Seq Source #  
Defined in Data.Interval getIntersects :: (Interval e i, Interval e j) => i > ITree e j > Seq j Source # getProperIntersects :: (Interval e i, Interval e j) => i > ITree e j > Seq j Source # someIntersects :: (Interval e i, Interval e j) => i > ITree e j > Bool Source # someProperlyIntersects :: (Interval e i, Interval e j) => i > ITree e j > Bool Source # maybeBounds :: Interval e i => ITree e i > Maybe (e, e) Source # storedIntervals :: Interval e i => ITree e i > Seq i Source # 
itree :: Interval e i => Int > Seq i > ITree e i Source #
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 nonoverlapping properly, the resulting tree is a pure binary search tree with bins of given size as leaves.
emptyITree :: ITree e i Source #
the empty ITree
insert :: Interval e i => i > ITree e i > ITree e i Source #
insert the interval at the deepest possible location into the tree. Does not change the overall structure, in particular no rebalancing is performed.
hullOfTree :: Interval e i => ITree e i > Maybe (e, e) Source #
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 Source #
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) Source #
transform the interval tree into the tree of hulls
Testing
intersecting :: (Interval e i, Interval e j) => j > Seq i > Seq i Source #
O(n) Extract all intervals intersecting a given one.
intersectingProperly :: (Interval e i, Interval e j) => j > Seq i > Seq i Source #
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) Source #
generalises Control.Monad.filterM
propSplit :: (Seq a > Bool) > SplitSeq a > Bool Source #
test if a sequence property holds for each sequence in the split.
splitSeq :: Seq a > SplitSeq a Source #
Split a Sequence in half, needed for the IntersectionQuery
instance.
prop> forevery genIntervalSeq $ is > joinSeq (splitSeq is) == is