fingertree-0.1.1.0: Generic finger-tree structure, with example instances

Copyright (c) Ross Paterson 2008 BSD-style R.Paterson@city.ac.uk experimental non-portable (MPTCs and functional dependencies) Safe Haskell98

Data.IntervalMap.FingerTree

Contents

Description

Interval maps implemented using the `FingerTree` type, following section 4.8 of

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.

Synopsis

Intervals

data Interval v Source

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

Constructors

 Interval Fieldslow :: v high :: v

Instances

 Eq v => Eq (Interval v) Ord v => Ord (Interval v) Show v => Show (Interval v)

point :: v -> Interval v Source

An interval in which the lower and upper bounds are equal.

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.

Instances

 Functor (IntervalMap v) Foldable (IntervalMap v) Traversable (IntervalMap v) Ord v => Monoid (IntervalMap v a) `empty` and `union`.

empty :: Ord v => IntervalMap v a Source

O(1). The empty interval map.

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

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

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

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 a Source

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.