# 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:
```haskell
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](https://hackage.haskell.org/package/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](https://hackage.haskell.org/package/data-interval) package
but we focus on closed intervals and let the user decide which
concrete data type to use.