# 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.