Closed intervals of totally ordered types

## root

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