Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

159 lines (139 sloc) 8.861 kB
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Module pqueue3</title>
<link rel="stylesheet" type="text/css" href="stylesheet.css" title="EDoc">
</head>
<body bgcolor="white">
<div class="navbar"><a name="#navbar_top"></a><table width="100%" border="0" cellspacing="0" cellpadding="2" summary="navigation bar"><tr><td><a href="overview-summary.html" target="overviewFrame">Overview</a></td><td><a href="http://www.erlang.org/"><img src="erlang.png" align="right" border="0" alt="erlang logo"></a></td></tr></table></div>
<hr>
<h1>Module pqueue3</h1>
<ul class="index"><li><a href="#description">Description</a></li><li><a href="#types">Data Types</a></li><li><a href="#index">Function Index</a></li><li><a href="#functions">Function Details</a></li></ul>
<h3><a name="A_Large_Priority_Queue.">A Large Priority Queue.</a></h3>
This priority queue implementation depends on layered tuples, so that tuple
access times can be exploited for quick in/out priority queue operations
when using 64 or more total priorities.
<p>Copyright © 2011-2013 Michael Truog</p>
<p><b>Version:</b> 1.2.2 Dec 20 2014 14:10:11
------------------------------------------------------------------------</p>
<p><b>Authors:</b> Michael Truog (<a href="mailto:mjtruog [at] gmail (dot) com"><tt>mjtruog [at] gmail (dot) com</tt></a>).</p>
<h2><a name="description">Description</a></h2>
<h3><a name="A_Large_Priority_Queue.">A Large Priority Queue.</a></h3>
This priority queue implementation depends on layered tuples, so that tuple
access times can be exploited for quick in/out priority queue operations
when using 64 or more total priorities. This implementation was created
to avoid the slowness within the priority queue used by
both RabbitMQ and Riak
(https://github.com/basho/riak_core/blob/master/src/priority_queue.erl).
<h2><a name="types">Data Types</a></h2>
<h3 class="typedecl"><a name="type-pqueue3">pqueue3()</a></h3>
<p><tt>pqueue3() = {integer(), integer(), empty | integer(), tuple()}</tt></p>
<h2><a name="index">Function Index</a></h2>
<table width="100%" border="1" cellspacing="0" cellpadding="2" summary="function index"><tr><td valign="top"><a href="#in-2">in/2</a></td><td>
<h4><a name="Append_an_item_to_the_tail_of_the_0_priority_queue.">Append an item to the tail of the 0 priority queue.</a></h4>
O(1).</td></tr>
<tr><td valign="top"><a href="#in-3">in/3</a></td><td>
<h4><a name="Append_an_item_to_the_tail_of_a_specific_priority_queue.">Append an item to the tail of a specific priority queue.</a></h4>
O(1).</td></tr>
<tr><td valign="top"><a href="#is_empty-1">is_empty/1</a></td><td>
<h4><a name="Check_if_the_priority_queue_is_empty.">Check if the priority queue is empty.</a></h4>
O(1).</td></tr>
<tr><td valign="top"><a href="#is_queue-1">is_queue/1</a></td><td>
<h4><a name="Check_if_the_priority_queue_type_is_as_expected.">Check if the priority queue type is as expected.</a></h4>
O(1).</td></tr>
<tr><td valign="top"><a href="#len-1">len/1</a></td><td>
<h4><a name="Determine_the_length_of_a_priority_queue.">Determine the length of a priority queue.</a></h4>
O(N).</td></tr>
<tr><td valign="top"><a href="#new-0">new/0</a></td><td>
<h4><a name="Create_a_new_priority_queue.">Create a new priority queue.</a></h4>
O(1).</td></tr>
<tr><td valign="top"><a href="#new-1">new/1</a></td><td>
<h4><a name="Create_a_new_priority_queue_with_customization_options.">Create a new priority queue with customization options.</a></h4>
O(1).</td></tr>
<tr><td valign="top"><a href="#out-1">out/1</a></td><td>
<h4><a name="Take_an_item_from_the_head_of_the_priority_queue.">Take an item from the head of the priority queue.</a></h4>
O(1) amortized, O(N) worst case.</td></tr>
<tr><td valign="top"><a href="#out-2">out/2</a></td><td>
<h4><a name="Take_an_item_of_a_specific_priority_from_the_head_of_the_queue.">Take an item of a specific priority from the head of the queue.</a></h4>
O(1) amortized, O(N) worst case.</td></tr>
<tr><td valign="top"><a href="#pout-1">pout/1</a></td><td>
<h4><a name="Take_an_item_from_the_head_of_the_priority_queue.">Take an item from the head of the priority queue.</a></h4>
Includes the priority in the return value.</td></tr>
<tr><td valign="top"><a href="#to_list-1">to_list/1</a></td><td>
<h4><a name="Convert_the_priority_queue_to_a_list.">Convert the priority queue to a list.</a></h4>
O(N).</td></tr>
</table>
<h2><a name="functions">Function Details</a></h2>
<h3 class="function"><a name="in-2">in/2</a></h3>
<div class="spec">
<p><tt>in(Value::term(), Q::<a href="#type-pqueue3">pqueue3()</a>) -&gt; <a href="#type-pqueue3">pqueue3()</a></tt><br></p>
</div><p>
<h4><a name="Append_an_item_to_the_tail_of_the_0_priority_queue.">Append an item to the tail of the 0 priority queue.</a></h4>
O(1)</p>
<h3 class="function"><a name="in-3">in/3</a></h3>
<div class="spec">
<p><tt>in(Value::term(), P::integer(), X3::<a href="#type-pqueue3">pqueue3()</a>) -&gt; <a href="#type-pqueue3">pqueue3()</a></tt><br></p>
</div><p>
<h4><a name="Append_an_item_to_the_tail_of_a_specific_priority_queue.">Append an item to the tail of a specific priority queue.</a></h4>
O(1)</p>
<h3 class="function"><a name="is_empty-1">is_empty/1</a></h3>
<div class="spec">
<p><tt>is_empty(Q::<a href="#type-pqueue3">pqueue3()</a>) -&gt; true | false</tt><br></p>
</div><p>
<h4><a name="Check_if_the_priority_queue_is_empty.">Check if the priority queue is empty.</a></h4>
O(1)</p>
<h3 class="function"><a name="is_queue-1">is_queue/1</a></h3>
<div class="spec">
<p><tt>is_queue(X1::<a href="#type-pqueue3">pqueue3()</a>) -&gt; true | false</tt><br></p>
</div><p>
<h4><a name="Check_if_the_priority_queue_type_is_as_expected.">Check if the priority queue type is as expected.</a></h4>
O(1)</p>
<h3 class="function"><a name="len-1">len/1</a></h3>
<div class="spec">
<p><tt>len(Q::<a href="#type-pqueue3">pqueue3()</a>) -&gt; non_neg_integer()</tt><br></p>
</div><p>
<h4><a name="Determine_the_length_of_a_priority_queue.">Determine the length of a priority queue.</a></h4>
O(N)</p>
<h3 class="function"><a name="new-0">new/0</a></h3>
<div class="spec">
<p><tt>new() -&gt; <a href="#type-pqueue3">pqueue3()</a></tt><br></p>
</div><p>
<h4><a name="Create_a_new_priority_queue.">Create a new priority queue.</a></h4>
O(1)</p>
<h3 class="function"><a name="new-1">new/1</a></h3>
<div class="spec">
<p><tt>new(Options::[{atom(), term()}]) -&gt; <a href="#type-pqueue3">pqueue3()</a></tt><br></p>
</div><p>
<h4><a name="Create_a_new_priority_queue_with_customization_options.">Create a new priority queue with customization options.</a></h4>
O(1)</p>
<h3 class="function"><a name="out-1">out/1</a></h3>
<div class="spec">
<p><tt>out(Q::<a href="#type-pqueue3">pqueue3()</a>) -&gt; {{value, term()}, <a href="#type-pqueue3">pqueue3()</a>} | {empty, <a href="#type-pqueue3">pqueue3()</a>}</tt><br></p>
</div><p>
<h4><a name="Take_an_item_from_the_head_of_the_priority_queue.">Take an item from the head of the priority queue.</a></h4>
O(1) amortized, O(N) worst case</p>
<h3 class="function"><a name="out-2">out/2</a></h3>
<div class="spec">
<p><tt>out(P::integer(), Q::<a href="#type-pqueue3">pqueue3()</a>) -&gt; {{value, term()}, <a href="#type-pqueue3">pqueue3()</a>} | {empty, <a href="#type-pqueue3">pqueue3()</a>}</tt><br></p>
</div><p>
<h4><a name="Take_an_item_of_a_specific_priority_from_the_head_of_the_queue.">Take an item of a specific priority from the head of the queue.</a></h4>
O(1) amortized, O(N) worst case</p>
<h3 class="function"><a name="pout-1">pout/1</a></h3>
<div class="spec">
<p><tt>pout(Q::<a href="#type-pqueue3">pqueue3()</a>) -&gt; {{value, term(), integer()}, <a href="#type-pqueue3">pqueue3()</a>} | {empty, <a href="#type-pqueue3">pqueue3()</a>}</tt><br></p>
</div><p>
<h4><a name="Take_an_item_from_the_head_of_the_priority_queue.">Take an item from the head of the priority queue.</a></h4>
Includes the priority in the return value.
O(1) amortized, O(N) worst case</p>
<h3 class="function"><a name="to_list-1">to_list/1</a></h3>
<div class="spec">
<p><tt>to_list(Q::<a href="#type-pqueue3">pqueue3()</a>) -&gt; [term()]</tt><br></p>
</div><p>
<h4><a name="Convert_the_priority_queue_to_a_list.">Convert the priority queue to a list.</a></h4>
O(N)</p>
<hr>
<div class="navbar"><a name="#navbar_bottom"></a><table width="100%" border="0" cellspacing="0" cellpadding="2" summary="navigation bar"><tr><td><a href="overview-summary.html" target="overviewFrame">Overview</a></td><td><a href="http://www.erlang.org/"><img src="erlang.png" align="right" border="0" alt="erlang logo"></a></td></tr></table></div>
<p><i>Generated by EDoc, Dec 20 2014, 14:10:11.</i></p>
</body>
</html>
Jump to Line
Something went wrong with that request. Please try again.