/usr/share/doc/libghc-fingertree-doc/html/Data-IntervalMap-FingerTree.html is in libghc-fingertree-doc 0.1.0.0-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 | <!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>Data.IntervalMap.FingerTree</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_Data-IntervalMap-FingerTree.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-IntervalMap-FingerTree.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">fingertree-0.1.0.0: Generic finger-tree structure, with example instances</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Portability</th><td>non-portable (MPTCs and functional dependencies)</td></tr><tr><th>Stability</th><td>experimental</td></tr><tr><th>Maintainer</th><td>ross@soi.city.ac.uk</td></tr><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr></table><p class="caption">Data.IntervalMap.FingerTree</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></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Interval maps implemented using the <code><a href="Data-FingerTree.html#t:FingerTree">FingerTree</a></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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Prelude.html">Prelude</a>. The ambiguity may be resolved
using either qualification or the <code>hiding</code> clause.
</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"><a href="#v:point">point</a> :: v -> <a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v</li><li class="src short"><span class="keyword">data</span> <a href="#t:IntervalMap">IntervalMap</a> v a</li><li class="src short"><a href="#v:empty">empty</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a</li><li class="src short"><a href="#v:singleton">singleton</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v -> a -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a</li><li class="src short"><a href="#v:insert">insert</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v -> a -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a</li><li class="src short"><a href="#v:union">union</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a</li><li class="src short"><a href="#v:search">search</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => v -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v, a)]</li><li class="src short"><a href="#v:intersections">intersections</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v, a)]</li><li class="src short"><a href="#v:dominators">dominators</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</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/Data-IntervalMap-FingerTree.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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> v => <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> (<a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> (<a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> v => <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v)</td><td class="doc empty"> </td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:point" class="def">point</a> :: v -> <a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v<a href="src/Data-IntervalMap-FingerTree.html#point" class="link">Source</a></p><div class="doc"><p>An interval in which the lower and upper bounds are equal.
</p></div></div><h1 id="g:2">Interval maps
</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:IntervalMap" class="def">IntervalMap</a> v a <a href="src/Data-IntervalMap-FingerTree.html#IntervalMap" class="link">Source</a></p><div class="doc"><p>Map of closed intervals, possibly with duplicates.
The <code><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Foldable.html#t:Foldable">Foldable</a></code> and <code><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Traversable.html#t:Traversable">Traversable</a></code> instances process the intervals in
lexicographical order.
</p></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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad.html#t:Functor">Functor</a> (<a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Foldable.html#t:Foldable">Foldable</a> (<a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Traversable.html#t:Traversable">Traversable</a> (<a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> (<a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a)</td><td class="doc"><p><code><a href="Data-IntervalMap-FingerTree.html#v:empty">empty</a></code> and <code><a href="Data-IntervalMap-FingerTree.html#v:union">union</a></code>.
</p></td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a<a href="src/Data-IntervalMap-FingerTree.html#empty" class="link">Source</a></p><div class="doc"><p><em>O(1)</em>. The empty interval map.
</p></div></div><div class="top"><p class="src"><a name="v:singleton" class="def">singleton</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v -> a -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a<a href="src/Data-IntervalMap-FingerTree.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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v -> a -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a<a href="src/Data-IntervalMap-FingerTree.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><div class="top"><p class="src"><a name="v:union" class="def">union</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a<a href="src/Data-IntervalMap-FingerTree.html#union" class="link">Source</a></p><div 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></div></div><h1 id="g:3">Searching
</h1><div class="top"><p class="src"><a name="v:search" class="def">search</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => v -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v, a)]<a href="src/Data-IntervalMap-FingerTree.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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v, a)]<a href="src/Data-IntervalMap-FingerTree.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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> v => <a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v -> <a href="Data-IntervalMap-FingerTree.html#t:IntervalMap">IntervalMap</a> v a -> [(<a href="Data-IntervalMap-FingerTree.html#t:Interval">Interval</a> v, a)]<a href="src/Data-IntervalMap-FingerTree.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></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.13.2</p></div></body></html>
|