closed-intervals

This package provides the two-parameter type class Interval of types that represent closed intervals (meaning the end-points are included) possibly with some extra annotation. 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). A more complicated type could be a record containing two fields of the end-point type:

	data Status = Status {
		statusText  :: String,
		statusBegin :: UTCTime,
		statusEnd   :: UTCTime}
	instance Interval UTCTime Status where
		lb = statusBegin
		ub = statusEnd
	instance Adjust Status where
		adjustBounds f g s = s {
			statusBegin = f (statusBegin s),
			statusEnd   = g (statusEnd   s)}	

The functions exported from this package 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.

In addition to the Interval class we provide a sub-class Adjust comprising the interval types whose end-points can be adjusted in a Bifunctor-like manner. This is necessary for set operations like union, intersection and difference.

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.

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

Related packages

The Interval type class is shared by the Data.IntervalMap.Generic.Interval module of the IntervalMap package. IntervalMap provides augmented red-black trees as the search structure.

The overlap 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.