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

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 Source # (<$) :: a -> Interval b -> Interval a Source #
Foldable Interval Source # |

Instance details

Defined in Text.Trifecta.Util.IntervalMap

Methods

fold :: Monoid m => Interval m -> m Source #

foldMap :: Monoid m => (a -> m) -> Interval a -> m Source #

foldMap' :: Monoid m => (a -> m) -> Interval a -> m Source #

foldr :: (a -> b -> b) -> b -> Interval a -> b Source #

foldr' :: (a -> b -> b) -> b -> Interval a -> b Source #

foldl :: (b -> a -> b) -> b -> Interval a -> b Source #

foldl' :: (b -> a -> b) -> b -> Interval a -> b Source #

foldr1 :: (a -> a -> a) -> Interval a -> a Source #

foldl1 :: (a -> a -> a) -> Interval a -> a Source #

toList :: Interval a -> [a] Source #

null :: Interval a -> Bool Source #

length :: Interval a -> Int Source #

elem :: Eq a => a -> Interval a -> Bool Source #

maximum :: Ord a => Interval a -> a Source #

minimum :: Ord a => Interval a -> a Source #

sum :: Num a => Interval a -> a Source #

product :: Num a => Interval a -> a Source #

Traversable Interval Source # |
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods traverse :: Applicative f => (a -> f b) -> Interval a -> f (Interval b) Source # sequenceA :: Applicative f => Interval (f a) -> f (Interval a) Source # mapM :: Monad m => (a -> m b) -> Interval a -> m (Interval b) Source # sequence :: Monad m => Interval (m a) -> m (Interval a) Source #
(Ord v, Monoid v) => Reducer v (Interval v) Source # |
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods unit :: v -> Interval v Source # snoc :: Interval v -> v -> Interval v Source # cons :: v -> Interval v -> Interval v Source #
Ord v => Semigroup (Interval v) Source # |
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods (<>) :: Interval v -> Interval v -> Interval v Source # sconcat :: NonEmpty (Interval v) -> Interval v Source # stimes :: Integral b => b -> Interval v -> Interval v Source #
Show v => Show (Interval v) Source # |
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods showsPrec :: Int -> Interval v -> ShowS Source # show :: Interval v -> String Source # showList :: [Interval v] -> ShowS Source #
Eq v => Eq (Interval v) Source # |
Instance details Defined in Text.Trifecta.Util.IntervalMap Methods (==) :: Interval v -> Interval v -> Bool Source # (/=) :: Interval v -> Interval v -> Bool Source #
Ord v => Ord (Interval v) Source # |

Instance details

Defined in Text.Trifecta.Util.IntervalMap

Methods

compare :: Interval v -> Interval v -> Ordering Source #

(<) :: Interval v -> Interval v -> Bool Source #

(<=) :: Interval v -> Interval v -> Bool Source #

(>) :: Interval v -> Interval v -> Bool Source #

(>=) :: Interval v -> Interval v -> Bool Source #

max :: Interval v -> Interval v -> Interval v Source #

min :: Interval v -> Interval v -> Interval v Source #

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 Source #

ifoldMap' :: Monoid m => (Interval v -> a -> m) -> IntervalMap v a -> m Source #

ifoldr :: (Interval v -> a -> b -> b) -> b -> IntervalMap v a -> b Source #

ifoldl :: (Interval v -> b -> a -> b) -> b -> IntervalMap v a -> b Source #

ifoldr' :: (Interval v -> a -> b -> b) -> b -> IntervalMap v a -> b Source #

ifoldl' :: (Interval v -> b -> a -> b) -> b -> IntervalMap v a -> b Source #

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 Source #
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) Source #

# 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 Source # (<$) :: a -> IntervalMap v b -> IntervalMap v a Source #
Foldable (IntervalMap v) Source # |

Instance details

Defined in Text.Trifecta.Util.IntervalMap

Methods

fold :: Monoid m => IntervalMap v m -> m Source #

foldMap :: Monoid m => (a -> m) -> IntervalMap v a -> m Source #

foldMap' :: Monoid m => (a -> m) -> IntervalMap v a -> m Source #

foldr :: (a -> b -> b) -> b -> IntervalMap v a -> b Source #

foldr' :: (a -> b -> b) -> b -> IntervalMap v a -> b Source #

foldl :: (b -> a -> b) -> b -> IntervalMap v a -> b Source #

foldl' :: (b -> a -> b) -> b -> IntervalMap v a -> b Source #

foldr1 :: (a -> a -> a) -> IntervalMap v a -> a Source #

foldl1 :: (a -> a -> a) -> IntervalMap v a -> a Source #

toList :: IntervalMap v a -> [a] Source #

null :: IntervalMap v a -> Bool Source #

length :: IntervalMap v a -> Int Source #

elem :: Eq a => a -> IntervalMap v a -> Bool Source #

maximum :: Ord a => IntervalMap v a -> a Source #

minimum :: Ord a => IntervalMap v a -> a Source #

sum :: Num a => IntervalMap v a -> a Source #

product :: Num a => IntervalMap v a -> a Source #

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) Source # sequenceA :: Applicative f => IntervalMap v (f a) -> f (IntervalMap v a) Source # mapM :: Monad m => (a -> m b) -> IntervalMap v a -> m (IntervalMap v b) Source # sequence :: Monad m => IntervalMap v (m a) -> m (IntervalMap v a) Source #
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 Source #

ifoldMap' :: Monoid m => (Interval v -> a -> m) -> IntervalMap v a -> m Source #

ifoldr :: (Interval v -> a -> b -> b) -> b -> IntervalMap v a -> b Source #

ifoldl :: (Interval v -> b -> a -> b) -> b -> IntervalMap v a -> b Source #

ifoldr' :: (Interval v -> a -> b -> b) -> b -> IntervalMap v a -> b Source #

ifoldl' :: (Interval v -> b -> a -> b) -> b -> IntervalMap v a -> b Source #

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

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

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