Haskell IntervalMap

An implementation of maps from intervals to values. The key intervals may overlap, and the implementation supports efficient queries for all intervals containing a point or intersecting a given interval.

You should normally install it from Hackage with cabal install IntervalMap.
I try to keep the interface stable between minor releases, so if you have this as a dependency in a cabal project, use constraints like this:

    Build-depends: IntervalMap >= 0.4 < 0.5

Here is the documentation.

A simple example. (Old version not requiring language extensions)

Source on Darcs Hub.

If IntervalMap does not fit your needs, you might want to look at these packages on Hackage: SegmentTree FingerTree SplayTree Ranged-sets

Version history 2014-08-29 Documentation updated and portability info fixed. 2014-08-29 Major update. It is now possible to use any type as key interval by making it an instance of Data.IntervalMap.Generic.Interval. This requires the languages extensions MultiParamTypeClasses and FlexibleInstances. The old interface is still supported for compatibility. 2014-08-11 Updated benchmark to use Criterion 1.0; tested with ghc 7.8.3. 2013-08-08 Dropped upper constraint on criterion; tested with ghc 7.6.3; migrated repo to Darcs Hub. 2012-08-07 Bugfixes: Lazy was too strict, Strict too lazy. 2012-08-03 Split into Lazy and Strict modules, following containers. 2012-04-24 Fixed error when building benchmarks with ghc 7.4.1.
Improved performance of deleteMin family of functions by about 30%.
Added benchmarks for deleteMin family of functions.
Reduced benchmark data size for more reasonable run times.
Added source-repository section to cabal spec. 2012-04-20 Added benchmarks, including a benchmark section in the cabal spec, so you can use cabal bench to run the benchmark. Here is a sample report.
Fixed cabal spec so that the test suites no longer require installing the package first. 2012-02-15 Improved documentation.
Removed ineffective INLINE pragmas.
0.2.3 2012-01-09 Added minView... family of functions.
Added isSubmap... family of functions.
Rewrote mapKeysMonotonic te be O(n).
0.2.2 2012-01-05 Improved performance of insert... and fromList... functions.
Added some example code.
0.2.1 2012-01-03 Documentation update: Added Big-O annotations.
0.2.0 2011-12-14 Changed argument order and name: searchPoint -> containing, searchInterval -> intersecting.
Added functions: within, findLast, updateMin/Max....
0.1.2 2011-12-12 Initial release.

Copyright © 2012-2014 Christoph Breitkopf
Blog · Google+ · Programming