| Copyright | (c) Ross Paterson 2008 |
|---|---|
| License | BSD-style |
| Maintainer | R.Paterson@city.ac.uk |
| Stability | experimental |
| Portability | non-portable (MPTCs and functional dependencies) |
| Safe Haskell | Safe |
| Language | Haskell98 |
Data.IntervalMap.FingerTree
Contents
Description
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://staff.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.
Instances
| Functor (IntervalMap v) | |
| Foldable (IntervalMap v) | |
| Traversable (IntervalMap v) | |
| Ord v => Monoid (IntervalMap v a) |
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.