/usr/share/doc/libghc-psqueue-doc/html/Data-PSQueue.html is in libghc-psqueue-doc 1.1-4.
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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | <!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.PSQueue</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-PSQueue.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-PSQueue.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">PSQueue-1.1: Priority Search Queue</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr></table><p class="caption">Data.PSQueue</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Binding Type
</a></li><li><a href="#g:2">Priority Search Queue Type
</a></li><li><a href="#g:3">Query
</a></li><li><a href="#g:4">Construction
</a></li><li><a href="#g:5">Insertion
</a></li><li><a href="#g:6">Delete/Update
</a></li><li><a href="#g:7">Conversion
</a></li><li><a href="#g:8">Priority Queue
</a></li><li><a href="#g:9">Fold
</a></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>A <em>priority search queue</em> (henceforth <em>queue</em>) efficiently supports the
opperations of both a search tree and a priority queue. A <code><a href="Data-PSQueue.html#t:Binding">Binding</a></code> is a
product of a key and a priority. Bindings can be inserted, deleted, modified
and queried in logarithmic time, and the binding with the least priority can be
retrieved in constant time. A queue can be built from a list of bindings,
sorted by keys, in linear time.
</p><p>This implementation is due to Ralf Hinze.
</p><ul><li> Hinze, R., <em>A Simple Implementation Technique for Priority Search Queues</em>, ICFP 2001, pp. 110-121
</li></ul><p><a href="http://citeseer.ist.psu.edu/hinze01simple.html">http://citeseer.ist.psu.edu/hinze01simple.html</a>
</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:Binding">Binding</a> k p = k <a href="#v::-45--62-">:-></a> p</li><li class="src short"><a href="#v:key">key</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> k</li><li class="src short"><a href="#v:prio">prio</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> p</li><li class="src short"><span class="keyword">data</span> <a href="#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:size">size</a> :: <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:lookup">lookup</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> p</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> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</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> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</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> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:insertWith">insertWith</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (p -> p -> p) -> k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:delete">delete</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:adjust">adjust</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k) => (p -> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:adjustWithKey">adjustWithKey</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (k -> p -> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:update">update</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:updateWithKey">updateWithKey</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (k -> p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:alter">alter</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:keys">keys</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [k]</li><li class="src short"><a href="#v:toList">toList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]</li><li class="src short"><a href="#v:toAscList">toAscList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]</li><li class="src short"><a href="#v:toDescList">toDescList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]</li><li class="src short"><a href="#v:fromList">fromList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:fromAscList">fromAscList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:fromDistinctAscList">fromDistinctAscList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:findMin">findMin</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p)</li><li class="src short"><a href="#v:deleteMin">deleteMin</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:minView">minView</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p, <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p)</li><li class="src short"><a href="#v:atMost">atMost</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]</li><li class="src short"><a href="#v:atMostRange">atMostRange</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => p -> (k, k) -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]</li><li class="src short"><a href="#v:foldr">foldr</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> b -> b) -> b -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> b</li><li class="src short"><a href="#v:foldl">foldl</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (b -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> b) -> b -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> b</li></ul></div><div id="interface"><h1 id="g:1">Binding Type
</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Binding" class="def">Binding</a> k p <a href="src/Data-PSQueue.html#Binding" class="link">Source</a></p><div class="doc"><p><code>k :-> p</code> binds the key <code>k</code> with the priority <code>p</code>.
</p></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src">k <a name="v::-45--62-" class="def">:-></a> p</td><td class="doc empty"> </td></tr></table></div><div class="subs instances"><p id="control.i:Binding" class="caption collapser" onclick="toggleSection('i:Binding')">Instances</p><div id="section.i:Binding" 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> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> p) => <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p)</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> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p)</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-Read.html#t:Read">Read</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Text-Read.html#t:Read">Read</a> p) => <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Text-Read.html#t:Read">Read</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p)</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> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> p) => <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p)</td><td class="doc empty"> </td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:key" class="def">key</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> k<a href="src/Data-PSQueue.html#key" class="link">Source</a></p><div class="doc"><p>The key of a binding
</p></div></div><div class="top"><p class="src"><a name="v:prio" class="def">prio</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> p<a href="src/Data-PSQueue.html#prio" class="link">Source</a></p><div class="doc"><p>The priority of a binding
</p></div></div><h1 id="g:2">Priority Search Queue Type
</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:PSQ" class="def">PSQ</a> k p <a href="src/Data-PSQueue.html#PSQ" class="link">Source</a></p><div class="doc"><p>A mapping from keys <code>k</code> to priorites <code>p</code>.
</p></div><div class="subs instances"><p id="control.i:PSQ" class="caption collapser" onclick="toggleSection('i:PSQ')">Instances</p><div id="section.i:PSQ" class="show"><table><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> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> p, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p)</td><td class="doc empty"> </td></tr></table></div></div></div><h1 id="g:3">Query
</h1><div class="top"><p class="src"><a name="v:size" class="def">size</a> :: <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a><a href="src/Data-PSQueue.html#size" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> The number of bindings in a queue.
</p></div></div><div class="top"><p class="src"><a name="v:null" class="def">null</a> :: <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-PSQueue.html#null" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> True if the queue is empty.
</p></div></div><div class="top"><p class="src"><a name="v:lookup" class="def">lookup</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> p<a href="src/Data-PSQueue.html#lookup" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em> The priority of a given key, or Nothing if the key is not
bound.
</p></div></div><h1 id="g:4">Construction
</h1><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> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#empty" class="link">Source</a></p></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> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#singleton" class="link">Source</a></p><div class="doc"><p>O(1) Build a queue with one binding.
</p></div></div><h1 id="g:5">Insertion
</h1><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> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#insert" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em> Insert a binding into the queue.
</p></div></div><div class="top"><p class="src"><a name="v:insertWith" class="def">insertWith</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (p -> p -> p) -> k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#insertWith" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em> Insert a binding with a combining function.
</p></div></div><h1 id="g:6">Delete/Update
</h1><div class="top"><p class="src"><a name="v:delete" class="def">delete</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#delete" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em> Remove a binding from the queue.
</p></div></div><div class="top"><p class="src"><a name="v:adjust" class="def">adjust</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k) => (p -> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#adjust" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em> Adjust the priority of a key.
</p></div></div><div class="top"><p class="src"><a name="v:adjustWithKey" class="def">adjustWithKey</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (k -> p -> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#adjustWithKey" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em> Adjust the priority of a key.
</p></div></div><div class="top"><p class="src"><a name="v:update" class="def">update</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#update" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em> The expression (<code>update f k q</code>) updates the
priority <code>p</code> bound <code>k</code> (if it is in the queue). If (<code>f p</code>) is <code><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#v:Nothing">Nothing</a></code>,
the binding is deleted. If it is (<code><code><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#v:Just">Just</a></code> z</code>), the key <code>k</code> is bound
to the new priority <code>z</code>.
</p></div></div><div class="top"><p class="src"><a name="v:updateWithKey" class="def">updateWithKey</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (k -> p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#updateWithKey" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em>. The expression (<code>updateWithKey f k q</code>) updates the
priority <code>p</code> bound <code>k</code> (if it is in the queue). If (<code>f k p</code>) is <code><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#v:Nothing">Nothing</a></code>,
the binding is deleted. If it is (<code><code><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#v:Just">Just</a></code> z</code>), the key <code>k</code> is bound
to the new priority <code>z</code>.
</p></div></div><div class="top"><p class="src"><a name="v:alter" class="def">alter</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#alter" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em>. The expression (<code><code><a href="Data-PSQueue.html#v:alter">alter</a></code> f k q</code>) alters the priority <code>p</code> bound to <code>k</code>, or absence thereof.
alter can be used to insert, delete, or update a priority in a queue.
</p></div></div><h1 id="g:7">Conversion
</h1><div class="top"><p class="src"><a name="v:keys" class="def">keys</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [k]<a href="src/Data-PSQueue.html#keys" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> The keys of a priority queue
</p></div></div><div class="top"><p class="src"><a name="v:toList" class="def">toList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]<a href="src/Data-PSQueue.html#toList" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> Convert a queue to a list.
</p></div></div><div class="top"><p class="src"><a name="v:toAscList" class="def">toAscList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]<a href="src/Data-PSQueue.html#toAscList" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> Convert a queue to a list in ascending order of keys.
</p></div></div><div class="top"><p class="src"><a name="v:toDescList" class="def">toDescList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]<a href="src/Data-PSQueue.html#toDescList" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> Convert a queue to a list in descending order of keys.
</p></div></div><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#fromList" class="link">Source</a></p><div class="doc"><p><em>O(n log n)</em> Build a queue from a list of bindings.
</p></div></div><div class="top"><p class="src"><a name="v:fromAscList" class="def">fromAscList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#fromAscList" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> Build a queue from a list of bindings in order of
ascending keys. The precondition that the keys are ascending is not checked.
</p></div></div><div class="top"><p class="src"><a name="v:fromDistinctAscList" class="def">fromDistinctAscList</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#fromDistinctAscList" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> Build a queue from a list of distinct bindings in order of
ascending keys. The precondition that keys are distinct and ascending is not checked.
</p></div></div><h1 id="g:8">Priority Queue
</h1><div class="top"><p class="src"><a name="v:findMin" class="def">findMin</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p)<a href="src/Data-PSQueue.html#findMin" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> The binding with the lowest priority.
</p></div></div><div class="top"><p class="src"><a name="v:deleteMin" class="def">deleteMin</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p<a href="src/Data-PSQueue.html#deleteMin" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em> Remove the binding with the lowest priority.
</p></div></div><div class="top"><p class="src"><a name="v:minView" class="def">minView</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p, <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p)<a href="src/Data-PSQueue.html#minView" class="link">Source</a></p><div class="doc"><p><em>O(log n)</em> Retrieve the binding with the least priority, and the rest of
the queue stripped of that binding.
</p></div></div><div class="top"><p class="src"><a name="v:atMost" class="def">atMost</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]<a href="src/Data-PSQueue.html#atMost" class="link">Source</a></p><div class="doc"><p><em>O(r(log n - log r)</em> <code>atMost p q</code> is a list of all the bindings in <code>q</code> with
priority less than <code>p</code>, in order of ascending keys.
Effectively,
</p><pre>
atMost p' q = filter (\(k:->p) -> p<=p') . toList
</pre></div></div><div class="top"><p class="src"><a name="v:atMostRange" class="def">atMostRange</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => p -> (k, k) -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]<a href="src/Data-PSQueue.html#atMostRange" class="link">Source</a></p><div class="doc"><p><em>O(r(log n - log r))</em> <code>atMostRange p (l,u) q</code> is a list of all the bindings in
<code>q</code> with a priority less than <code>p</code> and a key in the range <code>(l,u)</code> inclusive.
Effectively,
</p><pre>
atMostRange p' (l,u) q = filter (\(k:->p) -> l<=k && k<=u ) . <code><a href="Data-PSQueue.html#v:atMost">atMost</a></code> p'
</pre></div></div><h1 id="g:9">Fold
</h1><div class="top"><p class="src"><a name="v:foldr" class="def">foldr</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> b -> b) -> b -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> b<a href="src/Data-PSQueue.html#foldr" class="link">Source</a></p><div class="doc"><p>Right fold over the bindings in the queue, in key order.
</p></div></div><div class="top"><p class="src"><a name="v:foldl" class="def">foldl</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> p) => (b -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> b) -> b -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> b<a href="src/Data-PSQueue.html#foldl" class="link">Source</a></p><div class="doc"><p>Left fold over the bindings in the queue, in key 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>
|