Copyright | (c) Arbor Networks 2017 |
---|---|
License | BSD-style |
Maintainer | mayhem@arbor.net |
Stability | experimental |
Portability | non-portable (MPTCs and functional dependencies) |
Safe Haskell | Safe |
Language | Haskell2010 |
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 map. 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
- newtype IntervalMap v a = IntervalMap (FingerTree (IntInterval v) (Node 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
newtype IntervalMap v a Source #
Map of closed intervals, possibly with duplicates.
The Foldable
and Traversable
instances process the intervals in
lexicographical order.
IntervalMap (FingerTree (IntInterval v) (Node v a)) |
Functor (IntervalMap v) Source # | |
Foldable (IntervalMap v) Source # | |
Traversable (IntervalMap v) Source # | |
Ord v => Monoid (IntervalMap v a) Source # | |
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.