Copyright	(c) Edward Kmett 2011-2019 (c) Ross Paterson 2008
License	BSD-style
Maintainer	ekmett@gmail.com
Stability	experimental
Portability	non-portable (MPTCs, type families, functional dependencies)
Safe Haskell	Safe-Inferred
Language	Haskell2010

Text.Trifecta.Util.IntervalMap

Contents

Intervals
Interval maps
Searching
Prepending an offset onto every interval in the map
The result monoid

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://www.soi.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.

Unlike Data.IntervalMap.FingerTree, this version sorts things so that the largest interval from a given point comes first. This way if you have nested intervals, you get the outermost interval before the contained intervals.

Synopsis

data Interval v = Interval {
- low :: v
- high :: v
}
newtype IntervalMap v a = IntervalMap {
- runIntervalMap :: FingerTree (IntInterval v) (Node v a)
}
singleton :: Ord v => Interval v -> a -> IntervalMap v a
insert :: Ord v => v -> v -> a -> IntervalMap v a -> IntervalMap v a
search :: Ord v => v -> IntervalMap v a -> [(Interval v, a)]
intersections :: Ord v => v -> v -> IntervalMap v a -> [(Interval v, a)]
dominators :: Ord v => v -> v -> IntervalMap v a -> [(Interval v, a)]
offset :: (Ord v, Monoid v) => v -> IntervalMap v a -> IntervalMap v a
data IntInterval v
- = NoInterval
- | IntInterval (Interval v) v
fromList :: Ord v => [(v, v, a)] -> IntervalMap v a

Intervals

data Interval v Source #

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

Constructors

Interval
Fields low :: v high :: v

Instances

Instances details

Functor Interval Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods fmap :: (a -> b) -> Interval a -> Interval b # (<$) :: a -> Interval b -> Interval a #
Foldable Interval Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods fold :: Monoid m => Interval m -> m # foldMap :: Monoid m => (a -> m) -> Interval a -> m # foldMap' :: Monoid m => (a -> m) -> Interval a -> m # foldr :: (a -> b -> b) -> b -> Interval a -> b # foldr' :: (a -> b -> b) -> b -> Interval a -> b # foldl :: (b -> a -> b) -> b -> Interval a -> b # foldl' :: (b -> a -> b) -> b -> Interval a -> b # foldr1 :: (a -> a -> a) -> Interval a -> a # foldl1 :: (a -> a -> a) -> Interval a -> a # toList :: Interval a -> [a] # null :: Interval a -> Bool # length :: Interval a -> Int # elem :: Eq a => a -> Interval a -> Bool # maximum :: Ord a => Interval a -> a # minimum :: Ord a => Interval a -> a # sum :: Num a => Interval a -> a # product :: Num a => Interval a -> a #
Traversable Interval Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods traverse :: Applicative f => (a -> f b) -> Interval a -> f (Interval b) # sequenceA :: Applicative f => Interval (f a) -> f (Interval a) # mapM :: Monad m => (a -> m b) -> Interval a -> m (Interval b) # sequence :: Monad m => Interval (m a) -> m (Interval a) #
(Ord v, Monoid v) => Reducer v (Interval v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods unit :: v -> Interval v # snoc :: Interval v -> v -> Interval v # cons :: v -> Interval v -> Interval v #
Eq v => Eq (Interval v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods (==) :: Interval v -> Interval v -> Bool # (/=) :: Interval v -> Interval v -> Bool #
Ord v => Ord (Interval v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods compare :: Interval v -> Interval v -> Ordering # (<) :: Interval v -> Interval v -> Bool # (<=) :: Interval v -> Interval v -> Bool # (>) :: Interval v -> Interval v -> Bool # (>=) :: Interval v -> Interval v -> Bool # max :: Interval v -> Interval v -> Interval v # min :: Interval v -> Interval v -> Interval v #
Show v => Show (Interval v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods showsPrec :: Int -> Interval v -> ShowS # show :: Interval v -> String # showList :: [Interval v] -> ShowS #
Ord v => Semigroup (Interval v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods (<>) :: Interval v -> Interval v -> Interval v # sconcat :: NonEmpty (Interval v) -> Interval v # stimes :: Integral b => b -> Interval v -> Interval v #
FunctorWithIndex (Interval v) (IntervalMap v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods imap :: (Interval v -> a -> b) -> IntervalMap v a -> IntervalMap v b #
FoldableWithIndex (Interval v) (IntervalMap v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods ifoldMap :: Monoid m => (Interval v -> a -> m) -> IntervalMap v a -> m # ifoldMap' :: Monoid m => (Interval v -> a -> m) -> IntervalMap v a -> m # ifoldr :: (Interval v -> a -> b -> b) -> b -> IntervalMap v a -> b # ifoldl :: (Interval v -> b -> a -> b) -> b -> IntervalMap v a -> b # ifoldr' :: (Interval v -> a -> b -> b) -> b -> IntervalMap v a -> b # ifoldl' :: (Interval v -> b -> a -> b) -> b -> IntervalMap v a -> b #
TraversableWithIndex (Interval v) (IntervalMap v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods itraverse :: Applicative f => (Interval v -> a -> f b) -> IntervalMap v a -> f (IntervalMap v b) #

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.

Constructors

IntervalMap
Fields runIntervalMap :: FingerTree (IntInterval v) (Node v a)

Instances

Instances details

Functor (IntervalMap v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods fmap :: (a -> b) -> IntervalMap v a -> IntervalMap v b # (<$) :: a -> IntervalMap v b -> IntervalMap v a #
Foldable (IntervalMap v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods fold :: Monoid m => IntervalMap v m -> m # foldMap :: Monoid m => (a -> m) -> IntervalMap v a -> m # foldMap' :: Monoid m => (a -> m) -> IntervalMap v a -> m # foldr :: (a -> b -> b) -> b -> IntervalMap v a -> b # foldr' :: (a -> b -> b) -> b -> IntervalMap v a -> b # foldl :: (b -> a -> b) -> b -> IntervalMap v a -> b # foldl' :: (b -> a -> b) -> b -> IntervalMap v a -> b # foldr1 :: (a -> a -> a) -> IntervalMap v a -> a # foldl1 :: (a -> a -> a) -> IntervalMap v a -> a # toList :: IntervalMap v a -> [a] # null :: IntervalMap v a -> Bool # length :: IntervalMap v a -> Int # elem :: Eq a => a -> IntervalMap v a -> Bool # maximum :: Ord a => IntervalMap v a -> a # minimum :: Ord a => IntervalMap v a -> a # sum :: Num a => IntervalMap v a -> a # product :: Num a => IntervalMap v a -> a #
Traversable (IntervalMap v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods traverse :: Applicative f => (a -> f b) -> IntervalMap v a -> f (IntervalMap v b) # sequenceA :: Applicative f => IntervalMap v (f a) -> f (IntervalMap v a) # mapM :: Monad m => (a -> m b) -> IntervalMap v a -> m (IntervalMap v b) # sequence :: Monad m => IntervalMap v (m a) -> m (IntervalMap v a) #
FunctorWithIndex (Interval v) (IntervalMap v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods imap :: (Interval v -> a -> b) -> IntervalMap v a -> IntervalMap v b #
FoldableWithIndex (Interval v) (IntervalMap v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods ifoldMap :: Monoid m => (Interval v -> a -> m) -> IntervalMap v a -> m # ifoldMap' :: Monoid m => (Interval v -> a -> m) -> IntervalMap v a -> m # ifoldr :: (Interval v -> a -> b -> b) -> b -> IntervalMap v a -> b # ifoldl :: (Interval v -> b -> a -> b) -> b -> IntervalMap v a -> b # ifoldr' :: (Interval v -> a -> b -> b) -> b -> IntervalMap v a -> b # ifoldl' :: (Interval v -> b -> a -> b) -> b -> IntervalMap v a -> b #
TraversableWithIndex (Interval v) (IntervalMap v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods itraverse :: Applicative f => (Interval v -> a -> f b) -> IntervalMap v a -> f (IntervalMap v b) #
Ord v => Measured (IntInterval v) (IntervalMap v a) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods measure :: IntervalMap v a -> IntInterval v #
Ord v => Semigroup (IntervalMap v a) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods (<>) :: IntervalMap v a -> IntervalMap v a -> IntervalMap v a # sconcat :: NonEmpty (IntervalMap v a) -> IntervalMap v a # stimes :: Integral b => b -> IntervalMap v a -> IntervalMap v a #
Ord v => Monoid (IntervalMap v a) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods mempty :: IntervalMap v a # mappend :: IntervalMap v a -> IntervalMap v a -> IntervalMap v a # mconcat :: [IntervalMap v a] -> IntervalMap v a #
Ord v => HasUnion (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.
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods union :: IntervalMap v a -> IntervalMap v a -> IntervalMap v a #
Ord v => HasUnion0 (IntervalMap v a) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods empty :: IntervalMap v a #

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

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

insert :: Ord v => v -> 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.

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 => v -> 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 => v -> v -> IntervalMap v a -> [(Interval v, a)] Source #

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

Prepending an offset onto every interval in the map

offset :: (Ord v, Monoid v) => v -> IntervalMap v a -> IntervalMap v a Source #

O(n). Add a delta to each interval in the map

The result monoid

data IntInterval v Source #

Constructors

NoInterval
IntInterval (Interval v) v

Instances

Instances details

Ord v => Semigroup (IntInterval v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods (<>) :: IntInterval v -> IntInterval v -> IntInterval v # sconcat :: NonEmpty (IntInterval v) -> IntInterval v # stimes :: Integral b => b -> IntInterval v -> IntInterval v #
Ord v => Monoid (IntInterval v) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods mempty :: IntInterval v # mappend :: IntInterval v -> IntInterval v -> IntInterval v # mconcat :: [IntInterval v] -> IntInterval v #
Ord v => Measured (IntInterval v) (IntervalMap v a) Source #
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods measure :: IntervalMap v a -> IntInterval v #

fromList :: Ord v => [(v, v, a)] -> IntervalMap v a Source #