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.3 < 0.4

Here is the documentation.

A simple example.

Current release: IntervalMap-

Darcs repository: http://hub.darcs.net/bokesan/IntervalMap

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

Version history 2013-08-08 Dropped upper constraint on criterion; tested with ghc 7.6.3; migrated repo to hub.darcs.net. 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 Christoph Breitkopf
Blog · Google+ · Programming