closed-intervals: Closed intervals of totally ordered types

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]



[Skip to Readme]


Change log
Dependencies base (>=4.7 && <5), containers (>=, time (<1.12) [details]
License GPL-3.0-only
Copyright Lackmann Phymetric GmbH
Author Olaf Klinke, Henning Thielemann
Category Data Mining
Uploaded by olf at 2021-03-24T13:03:51Z




Maintainer's Corner

For package maintainers and hackage trustees

Readme for closed-intervals-

[back to package description]


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.

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.