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 | None |
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 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
- 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.
Instances
Eq v => Eq (Interval v) Source # | |
Ord v => Ord (Interval v) Source # | |
Defined in HaskellWorks.Data.IntervalMap.FingerTree | |
Show v => Show (Interval v) Source # | |
Generic (Interval v) Source # | |
NFData v => NFData (Interval v) Source # | |
Defined in HaskellWorks.Data.IntervalMap.FingerTree | |
type Rep (Interval v) Source # | |
Defined in HaskellWorks.Data.IntervalMap.FingerTree type Rep (Interval v) = D1 ('MetaData "Interval" "HaskellWorks.Data.IntervalMap.FingerTree" "hw-fingertree-0.1.2.1-7DVjKwK8BqoETwS3vQ6f1i" 'False) (C1 ('MetaCons "Interval" 'PrefixI 'True) (S1 ('MetaSel ('Just "low") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 v) :*: S1 ('MetaSel ('Just "high") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 v))) |
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)) |
Instances
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.