/
Text-Trifecta-Util-IntervalMap.html
49 lines (49 loc) · 23.6 KB
/
Text-Trifecta-Util-IntervalMap.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Text.Trifecta.Util.IntervalMap</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_Text-Trifecta-Util-IntervalMap.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Text-Trifecta-Util-IntervalMap.html">Source</a></li><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">trifecta-1.1: A modern parser combinator library with convenient diagnostics</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Portability</th><td>non-portable (MPTCs, type families, functional dependencies)</td></tr><tr><th>Stability</th><td>experimental</td></tr><tr><th>Maintainer</th><td>ekmett@gmail.com</td></tr><tr><th>Safe Haskell</th><td>Safe-Infered</td></tr></table><p class="caption">Text.Trifecta.Util.IntervalMap</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Intervals
</a></li><li><a href="#g:2">Interval maps
</a></li><li><a href="#g:3">Searching
</a></li><li><a href="#g:4">Prepending an offset onto every interval in the map
</a></li><li><a href="#g:5">The result monoid
</a></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Interval maps implemented using the <code>FingerTree</code> type, following
section 4.8 of
</p><ul><li> Ralf Hinze and Ross Paterson,
"Finger trees: a simple general-purpose data structure",
<em>Journal of Functional Programming</em> 16:2 (2006) pp 197-217.
<a href="http://www.soi.city.ac.uk/~ross/papers/FingerTree.html">http://www.soi.city.ac.uk/~ross/papers/FingerTree.html</a>
</li></ul><p>An amortized running time is given for each operation, with <em>n</em>
referring to the size of the priority queue. These bounds hold even
in a persistent (shared) setting.
</p><p><em>Note</em>: Many of these operations have the same names as similar
operations on lists in the <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Prelude.html">Prelude</a>. The ambiguity may be resolved
using either qualification or the <code>hiding</code> clause.
</p><p>Unlike <a href="Data-IntervalMap-FingerTree.html">Data.IntervalMap.FingerTree</a>, 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.
</p></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><span class="keyword">data</span> <a href="#t:Interval">Interval</a> v = <a href="#v:Interval">Interval</a> {<ul class="subs"><li><a href="#v:low">low</a> :: v</li><li><a href="#v:high">high</a> :: v</li></ul>}</li><li class="src short"><span class="keyword">newtype</span> <a href="#t:IntervalMap">IntervalMap</a> v a = <a href="#v:IntervalMap">IntervalMap</a> {<ul class="subs"><li><a href="#v:runIntervalMap">runIntervalMap</a> :: FingerTree (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntInterval">IntInterval</a> v) (Node v a)</li></ul>}</li><li class="src short"><a href="#v:singleton">singleton</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => <a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v -> a -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a</li><li class="src short"><a href="#v:insert">insert</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => v -> v -> a -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a</li><li class="src short"><a href="#v:search">search</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => v -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v, a)]</li><li class="src short"><a href="#v:intersections">intersections</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => v -> v -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v, a)]</li><li class="src short"><a href="#v:dominators">dominators</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => v -> v -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v, a)]</li><li class="src short"><a href="#v:offset">offset</a> :: (<a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v, <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Monoid.html#t:Monoid">Monoid</a> v) => v -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a</li><li class="src short"><span class="keyword">data</span> <a href="#t:IntInterval">IntInterval</a> v<ul class="subs"><li>= <a href="#v:NoInterval">NoInterval</a> </li><li>| <a href="#v:IntInterval">IntInterval</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v) v </li></ul></li><li class="src short"><a href="#v:fromList">fromList</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => [(v, v, a)] -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a</li></ul></div><div id="interface"><h1 id="g:1">Intervals
</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Interval" class="def">Interval</a> v <a href="src/Text-Trifecta-Util-IntervalMap.html#Interval" class="link">Source</a></p><div class="doc"><p>A closed interval. The lower bound should be less than or equal
to the higher bound.
</p></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a name="v:Interval" class="def">Interval</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><div class="subs fields"><p class="caption">Fields</p><dl><dt class="src"><a name="v:low" class="def">low</a> :: v</dt><dd class="doc empty"> </dd><dt class="src"><a name="v:high" class="def">high</a> :: v</dt><dd class="doc empty"> </dd></dl><div class="clear"></div></div></td></tr></table></div><div class="subs instances"><p id="control.i:Interval" class="caption collapser" onclick="toggleSection('i:Interval')">Instances</p><div id="section.i:Interval" class="show"><table><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Control-Monad.html#t:Functor">Functor</a> <a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Traversable.html#t:Traversable">Traversable</a> <a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a></td><td class="doc empty"> </td></tr><tr><td class="src">(<a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v, <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Monoid.html#t:Monoid">Monoid</a> v) => Reducer v (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Eq.html#t:Eq">Eq</a> v => <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Eq.html#t:Eq">Eq</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Text-Show.html#t:Show">Show</a> v => <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Text-Show.html#t:Show">Show</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => Semigroup (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Users/ekmett/.cabal/share/doc/lens-3.10/html/Control-Lens-Indexed.html#t:FunctorWithIndex">FunctorWithIndex</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v) (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Users/ekmett/.cabal/share/doc/lens-3.10/html/Control-Lens-Indexed.html#t:FunctorWithIndex">FunctorWithIndex</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v) (Node v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Users/ekmett/.cabal/share/doc/lens-3.10/html/Control-Lens-Indexed.html#t:FoldableWithIndex">FoldableWithIndex</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v) (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Users/ekmett/.cabal/share/doc/lens-3.10/html/Control-Lens-Indexed.html#t:FoldableWithIndex">FoldableWithIndex</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v) (Node v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Users/ekmett/.cabal/share/doc/lens-3.10/html/Control-Lens-Indexed.html#t:TraversableWithIndex">TraversableWithIndex</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v) (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Users/ekmett/.cabal/share/doc/lens-3.10/html/Control-Lens-Indexed.html#t:TraversableWithIndex">TraversableWithIndex</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v) (Node v)</td><td class="doc empty"> </td></tr></table></div></div></div><h1 id="g:2">Interval maps
</h1><div class="top"><p class="src"><span class="keyword">newtype</span> <a name="t:IntervalMap" class="def">IntervalMap</a> v a <a href="src/Text-Trifecta-Util-IntervalMap.html#IntervalMap" class="link">Source</a></p><div class="doc"><p>Map of closed intervals, possibly with duplicates.
The <code><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Foldable.html#t:Foldable">Foldable</a></code> and <code><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Traversable.html#t:Traversable">Traversable</a></code> instances process the intervals in
lexicographical order.
</p></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a name="v:IntervalMap" class="def">IntervalMap</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><div class="subs fields"><p class="caption">Fields</p><dl><dt class="src"><a name="v:runIntervalMap" class="def">runIntervalMap</a> :: FingerTree (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntInterval">IntInterval</a> v) (Node v a)</dt><dd class="doc empty"> </dd></dl><div class="clear"></div></div></td></tr></table></div><div class="subs instances"><p id="control.i:IntervalMap" class="caption collapser" onclick="toggleSection('i:IntervalMap')">Instances</p><div id="section.i:IntervalMap" class="show"><table><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Control-Monad.html#t:Functor">Functor</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Foldable.html#t:Foldable">Foldable</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Traversable.html#t:Traversable">Traversable</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Users/ekmett/.cabal/share/doc/lens-3.10/html/Control-Lens-Indexed.html#t:FunctorWithIndex">FunctorWithIndex</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v) (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Users/ekmett/.cabal/share/doc/lens-3.10/html/Control-Lens-Indexed.html#t:FoldableWithIndex">FoldableWithIndex</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v) (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Users/ekmett/.cabal/share/doc/lens-3.10/html/Control-Lens-Indexed.html#t:TraversableWithIndex">TraversableWithIndex</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v) (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => Measured (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntInterval">IntInterval</a> v) (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Monoid.html#t:Monoid">Monoid</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => HasUnion0 (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => HasUnion (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a)</td><td class="doc"><p><em>O(m log (n</em>/<em>m))</em>. Merge two interval maps.
The map may contain duplicate intervals; entries with equal intervals
are kept in the original order.
</p></td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:singleton" class="def">singleton</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => <a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v -> a -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a<a href="src/Text-Trifecta-Util-IntervalMap.html#singleton" class="link">Source</a></p><div class="doc"><p><em>O(1)</em>. Interval map with a single entry.
</p></div></div><div class="top"><p class="src"><a name="v:insert" class="def">insert</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => v -> v -> a -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a<a href="src/Text-Trifecta-Util-IntervalMap.html#insert" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em>. 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.
</p></div></div><h1 id="g:3">Searching
</h1><div class="top"><p class="src"><a name="v:search" class="def">search</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => v -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v, a)]<a href="src/Text-Trifecta-Util-IntervalMap.html#search" class="link">Source</a></p><div class="doc"><p><em>O(k log (n</em>/<em>k))</em>. All intervals that contain the given point,
in lexicographical order.
</p></div></div><div class="top"><p class="src"><a name="v:intersections" class="def">intersections</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => v -> v -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v, a)]<a href="src/Text-Trifecta-Util-IntervalMap.html#intersections" class="link">Source</a></p><div class="doc"><p><em>O(k log (n</em>/<em>k))</em>. All intervals that intersect with the given
interval, in lexicographical order.
</p></div></div><div class="top"><p class="src"><a name="v:dominators" class="def">dominators</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => v -> v -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v, a)]<a href="src/Text-Trifecta-Util-IntervalMap.html#dominators" class="link">Source</a></p><div class="doc"><p><em>O(k log (n</em>/<em>k))</em>. All intervals that contain the given interval,
in lexicographical order.
</p></div></div><h1 id="g:4">Prepending an offset onto every interval in the map
</h1><div class="top"><p class="src"><a name="v:offset" class="def">offset</a> :: (<a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v, <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Monoid.html#t:Monoid">Monoid</a> v) => v -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a<a href="src/Text-Trifecta-Util-IntervalMap.html#offset" class="link">Source</a></p><div class="doc"><p><em>O(n)</em>. Add a delta to each interval in the map
</p></div></div><h1 id="g:5">The result monoid
</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:IntInterval" class="def">IntInterval</a> v <a href="src/Text-Trifecta-Util-IntervalMap.html#IntInterval" class="link">Source</a></p><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a name="v:NoInterval" class="def">NoInterval</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a name="v:IntInterval" class="def">IntInterval</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:Interval">Interval</a> v) v</td><td class="doc empty"> </td></tr></table></div><div class="subs instances"><p id="control.i:IntInterval" class="caption collapser" onclick="toggleSection('i:IntInterval')">Instances</p><div id="section.i:IntInterval" class="show"><table><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Monoid.html#t:Monoid">Monoid</a> (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntInterval">IntInterval</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => Measured (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntInterval">IntInterval</a> v) (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => Measured (<a href="Text-Trifecta-Util-IntervalMap.html#t:IntInterval">IntInterval</a> v) (Node v a)</td><td class="doc empty"> </td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</a> :: <a href="/Library/Frameworks/GHC.framework/Versions/7.4.1-x86_64/usr/share/doc/ghc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> v => [(v, v, a)] -> <a href="Text-Trifecta-Util-IntervalMap.html#t:IntervalMap">IntervalMap</a> v a<a href="src/Text-Trifecta-Util-IntervalMap.html#fromList" class="link">Source</a></p></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.10.0</p></div></body></html>