Portability | non-portable (MPTCs and functional dependencies) |
---|---|

Stability | experimental |

Maintainer | ross@soi.city.ac.uk |

Safe Haskell | Safe-Infered |

Interval maps implemented using the `FingerTree`

type, following
section 4.8 of

- Ralf Hinze and Ross Paterson,
"Finger trees: a simple general-purpose data structure",
*Journal of Functional Programming*16:2 (2006) pp 197-217. http://www.soi.city.ac.uk/~ross/papers/FingerTree.html

An amortized running time is given for each operation, with *n*
referring to the size of the priority queue. These bounds hold even
in a persistent (shared) setting.

*Note*: Many of these operations have the same names as similar
operations on lists in the Prelude. The ambiguity may be resolved
using either qualification or the `hiding`

clause.

- data Interval v = Interval {}
- point :: v -> Interval v
- data IntervalMap v a
- empty :: Ord v => IntervalMap v a
- singleton :: Ord v => Interval v -> a -> IntervalMap v a
- insert :: Ord v => Interval v -> a -> IntervalMap v a -> IntervalMap v a
- union :: Ord v => IntervalMap v a -> IntervalMap v a -> IntervalMap v a
- search :: Ord v => v -> IntervalMap v a -> [(Interval v, a)]
- intersections :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)]
- dominators :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)]

# Intervals

A closed interval. The lower bound should be less than or equal to the higher bound.

# Interval maps

data IntervalMap v a Source

Map of closed intervals, possibly with duplicates.
The `Foldable`

and `Traversable`

instances process the intervals in
lexicographical order.

Functor (IntervalMap v) | |

Foldable (IntervalMap v) | |

Traversable (IntervalMap v) |

empty :: Ord v => IntervalMap v aSource

*O(1)*. The empty interval map.

singleton :: Ord v => Interval v -> a -> IntervalMap v aSource

*O(1)*. Interval map with a single entry.

insert :: Ord v => Interval v -> a -> IntervalMap v a -> IntervalMap v aSource

*O(log n)*. Insert an interval into a map.
The map may contain duplicate intervals; the new entry will be inserted
before any existing entries for the same interval.

union :: Ord v => IntervalMap v a -> IntervalMap v a -> IntervalMap v aSource

*O(m log (n*/*m))*. Merge two interval maps.
The map may contain duplicate intervals; entries with equal intervals
are kept in the original order.

# Searching

search :: Ord v => v -> IntervalMap v a -> [(Interval v, a)]Source

*O(k log (n*/*k))*. All intervals that contain the given point,
in lexicographical order.

intersections :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)]Source

*O(k log (n*/*k))*. All intervals that intersect with the given
interval, in lexicographical order.

dominators :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)]Source

*O(k log (n*/*k))*. All intervals that contain the given interval,
in lexicographical order.