trifecta-2.1: A modern parser combinator library with convenient diagnostics

Copyright (c) Edward Kmett 2011-2019(c) Ross Paterson 2008 BSD-style ekmett@gmail.com experimental non-portable (MPTCs, type families, functional dependencies) None Haskell2010

Text.Trifecta.Util.IntervalMap

Description

Interval maps implemented using the FingerTree type, following section 4.8 of

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

# Intervals

data Interval v Source #

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

Constructors

 Interval Fieldslow :: v high :: v
Instances
 Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsfmap :: (a -> b) -> Interval a -> Interval b #(<$) :: a -> Interval b -> Interval a # Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsfold :: Monoid m => Interval m -> 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 # Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodstraverse :: 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 detailsDefined in Text.Trifecta.Util.IntervalMap Methodsunit :: v -> Interval v #snoc :: Interval v -> v -> Interval v #cons :: v -> Interval v -> Interval v # Eq v => Eq (Interval v) Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methods(==) :: Interval v -> Interval v -> Bool #(/=) :: Interval v -> Interval v -> Bool # Ord v => Ord (Interval v) Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodscompare :: 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 detailsDefined in Text.Trifecta.Util.IntervalMap MethodsshowsPrec :: Int -> Interval v -> ShowS #show :: Interval v -> String #showList :: [Interval v] -> ShowS # Ord v => Semigroup (Interval v) Source # Instance detailsDefined 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 # Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsimap :: (Interval v -> a -> b) -> IntervalMap v a -> IntervalMap v b #imapped :: IndexedSetter (Interval v) (IntervalMap v a) (IntervalMap v b) a b # Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap MethodsifoldMap :: Monoid m => (Interval v -> a -> m) -> IntervalMap v a -> m #ifolded :: IndexedFold (Interval v) (IntervalMap v a) a #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 # Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsitraverse :: Applicative f => (Interval v -> a -> f b) -> IntervalMap v a -> f (IntervalMap v b) #itraversed :: IndexedTraversal (Interval v) (IntervalMap v a) (IntervalMap v b) a 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 FieldsrunIntervalMap :: FingerTree (IntInterval v) (Node v a) Instances  Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsfmap :: (a -> b) -> IntervalMap v a -> IntervalMap v b #(<$) :: a -> IntervalMap v b -> IntervalMap v a # Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsfold :: Monoid m => IntervalMap v m -> 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 # Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodstraverse :: 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) # Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsimap :: (Interval v -> a -> b) -> IntervalMap v a -> IntervalMap v b #imapped :: IndexedSetter (Interval v) (IntervalMap v a) (IntervalMap v b) a b # Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap MethodsifoldMap :: Monoid m => (Interval v -> a -> m) -> IntervalMap v a -> m #ifolded :: IndexedFold (Interval v) (IntervalMap v a) a #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 # Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsitraverse :: Applicative f => (Interval v -> a -> f b) -> IntervalMap v a -> f (IntervalMap v b) #itraversed :: IndexedTraversal (Interval v) (IntervalMap v a) (IntervalMap v b) a b # Ord v => Measured (IntInterval v) (IntervalMap v a) Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsmeasure :: IntervalMap v a -> IntInterval v # Ord v => Semigroup (IntervalMap v a) Source # Instance detailsDefined 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 detailsDefined in Text.Trifecta.Util.IntervalMap Methodsmempty :: 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 detailsDefined in Text.Trifecta.Util.IntervalMap Methodsunion :: IntervalMap v a -> IntervalMap v a -> IntervalMap v a # Ord v => HasUnion0 (IntervalMap v a) Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsempty :: 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
 Ord v => Semigroup (IntInterval v) Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methods(<>) :: IntInterval v -> IntInterval v -> IntInterval v #stimes :: Integral b => b -> IntInterval v -> IntInterval v # Ord v => Monoid (IntInterval v) Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsmappend :: IntInterval v -> IntInterval v -> IntInterval v #mconcat :: [IntInterval v] -> IntInterval v # Ord v => Measured (IntInterval v) (IntervalMap v a) Source # Instance detailsDefined in Text.Trifecta.Util.IntervalMap Methodsmeasure :: IntervalMap v a -> IntInterval v #

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