HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

Moduletrifecta-2.1.4Haskell2010

Text.Trifecta.Util.IntervalMap

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.

  • 3 types
  • 7 values
  • Packagetrifecta-2.1.4
  • Exports10
  • LanguageHaskell2010
  • LicenceBSD-3-Clause
  • SourceIntervalMap.hs

Intervals

1 declaration
datadata Interval v
#

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

Constructors

Instances14Functor, Foldable, Traversable, Reducer, Eq, Ord, …

Interval maps

3 declarations
newtypenewtype IntervalMap v a
#

Map of closed intervals, possibly with duplicates. The Foldable and Traversable instances process the intervals in lexicographical order.

Constructors

Instances11Functor, Foldable, Traversable, FoldableWithIndex, FunctorWithIndex, TraversableWithIndex, …
valueinsert :: Ord v => v -> v -> a -> IntervalMap v a -> IntervalMap v a
#

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

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.

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

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

Prepending an offset onto every interval in the map

1 declaration

The result monoid

2 declarations
datadata IntInterval v
#

Constructors

Instances4Semigroup, Monoid, Measured