IntervalMap

Containers for intervals, with efficient search. http://www.chr-breitkopf.de/comp/IntervalMap

Version on this page:0.6.1.0
LTS Haskell 16.4:0.6.1.2
Stackage Nightly 2020-07-04:0.6.1.2
Latest on Hackage:0.6.1.2

See all snapshots IntervalMap appears in

BSD-3-Clause licensed by Christoph Breitkopf
Maintained by Christoph Breitkopf

Module documentation for 0.6.1.0

This version can be pinned in stack with:[email protected]:3c9f2020ecb7b179020009ff0e6e2f6c232ddd22e47daff61b6b3684a555f75d,4563

IntervalMap Hackage Build Status

Containers for intervals. Like Data.Set and Data.Map with Intervals as keys and functions for efficiently getting the subset of all intervals containing a point, intersecting an interval, and more.

Home page and documentation: http://www.chr-breitkopf.de/comp/IntervalMap/index.html

Getting started

Enable necessary language extensions:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

In most cases, you should use the value-strict version:

import qualified Data.IntervalMap.Generic.Strict as IM

Make tuples an instance of Interval:

instance Ord e => IM.Interval (e,e) e where
    lowerBound (a,_) = a
    upperBound (_,b) = b
    rightClosed _ = False

By using rightClosed _ = False we have defined tuples to be half-open intervals - they include the starting value, but not the end value.

Let’s create a map from (Int,Int) intervals to strings:

type MyMap = IM.IntervalMap (Int,Int) String

sample :: MyMap
sample = IM.fromList [((1,6), "Foo"), ((2,4), "Bar"), ((4,7), "Baz")]

Lookup intervals containing a given point (“stabbing query”):

> IM.toAscList (sample `IM.containing` 3)
[((1,6),"Foo"),((2,4),"Bar")]
> IM.toAscList (sample `IM.containing` 4)
[((1,6),"Foo"),((4,7),"Baz")]