Modulefingertree-0.1.6.2Haskell2010

Data.IntervalMap.FingerTree

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. https://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.

2 types
13 values

Packagefingertree-0.1.6.2
Exports15
LanguageHaskell2010
LicenceBSD-3-Clause
SourceFingerTree.hs

Intervals

4 declarations

datadata Interval v

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

Constructors

Interval v v
Lower and upper bounds of the interval.

Instances7Eq, Ord, Read, Show, Generic, NFData, …

Eq v => Eq (Interval v)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
Ord v => Ord (Interval v)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
Read v => Read (Interval v)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
Show v => Show (Interval v)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
Generic (Interval v)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
NFData v => NFData (Interval v)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
type Rep (Interval v) = D1 ('MetaData "Interval" "Data.IntervalMap.FingerTree" "fingertree-0.1.6.2-3XyR23ghISVIyxrvBYcDXO" 'False) (C1 ('MetaCons "Interval" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 v) :*: S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 v)))Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree

valuelow :: Interval v -> v

Lower bound of the interval

valuehigh :: Interval v -> v

Upper bound of the interval

valuepoint :: v -> Interval v

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

Interval maps

5 declarations

newtypenewtype IntervalMap v a

Map of closed intervals, possibly with duplicates.

Instances11Functor, Foldable, Traversable, Eq, Ord, Show, …

Functor (IntervalMap v)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
Foldable (IntervalMap v)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
Values in lexicographical order of intervals.
Traversable (IntervalMap v)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
Traverse the intervals in lexicographical order.
(Eq v, Eq a) => Eq (IntervalMap v a)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
(Ord v, Ord a) => Ord (IntervalMap v a)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
Lexicographical ordering
(Show v, Show a) => Show (IntervalMap v a)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
Generic (IntervalMap v a)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
Ord v => Semigroup (IntervalMap v a)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
union.
Ord v => Monoid (IntervalMap v a)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
empty and union.
(NFData a, NFData v) => NFData (IntervalMap v a)Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree
type Rep (IntervalMap v a) = D1 ('MetaData "IntervalMap" "Data.IntervalMap.FingerTree" "fingertree-0.1.6.2-3XyR23ghISVIyxrvBYcDXO" 'True) (C1 ('MetaCons "IntervalMap" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (FingerTree (IntInterval v) (Node v a)))))Defined in fingertree-0.1.6.2 · Data.IntervalMap.FingerTree

valueempty :: Ord v => IntervalMap v a

O(1). The empty interval map.

valuesingleton :: Ord v => Interval v -> a -> IntervalMap v a

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

valueinsert :: Ord v => Interval v -> a -> IntervalMap v a -> IntervalMap v a

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

valueunion :: Ord v => IntervalMap v a -> IntervalMap v a -> IntervalMap v a

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

3 declarations

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

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

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

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

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

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

Extraction

3 declarations

valuebounds :: Ord v => IntervalMap v a -> Maybe (Interval v)

O(1). bounds m returns Nothing if m is empty, and otherwise Just i, where i is the smallest interval containing all the intervals in the map.

valueleastView

:: Ord v
=> IntervalMap v a
-> Maybe ((Interval v, a), IntervalMap v a)

O(1). leastView m returns Nothing if m is empty, and otherwise Just ((i, x), m'), where i is the least interval, x is the associated value, and m' is the rest of the map.

valuesplitAfter

:: Ord v
=> v
-> IntervalMap v a
-> (IntervalMap v a, IntervalMap v a)

O(log(min(i,n-i))). splitAfter k m returns a pair of submaps, one consisting of intervals whose lower bound is less than or equal to k, and the other of those whose lower bound is greater.