/
pqueue2.html
143 lines (124 loc) · 8.06 KB
/
pqueue2.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
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
<!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 pqueue2</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 pqueue2</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="Skew_Heap_Priority_Queue.">Skew Heap Priority Queue.</a></h3>
Ulf Wiger suggested pursuing a skew heap as an optimal Erlang priority
queue implementation.
<p>Copyright © 2011 Michael Truog</p>
<p><b>Version:</b> 0.1.9 May 7 2013 15:51: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="Skew_Heap_Priority_Queue.">Skew Heap Priority Queue.</a></h3>
Ulf Wiger suggested pursuing a skew heap as an optimal Erlang priority
queue implementation. Unfortunately, testing has shown this solution to
be more than 2 times slower than pqueue.
<h2><a name="types">Data Types</a></h2>
<h3 class="typedecl"><a name="type-pqueue2">pqueue2()</a></h3>
<p><tt>pqueue2() = empty | {integer(), <a href="#type-pqueue2">pqueue2()</a>, <a href="#type-pqueue2">pqueue2()</a>, element, term()} | {integer(), <a href="#type-pqueue2">pqueue2()</a>, <a href="#type-pqueue2">pqueue2()</a>, queue, queue()}</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>.</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>.</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>.</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>.</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>.</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>.</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>.</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>.</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="#test-0">test/0</a></td><td>
<h4><a name="Regression_test.">Regression test.</a></h4>.</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>.</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(), H::<a href="#type-pqueue2">pqueue2()</a>) -> <a href="#type-pqueue2">pqueue2()</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>
</p>
<h3 class="function"><a name="in-3">in/3</a></h3>
<div class="spec">
<p><tt>in(Value::term(), P::integer(), H::<a href="#type-pqueue2">pqueue2()</a>) -> <a href="#type-pqueue2">pqueue2()</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>
</p>
<h3 class="function"><a name="is_empty-1">is_empty/1</a></h3>
<div class="spec">
<p><tt>is_empty(X1::<a href="#type-pqueue2">pqueue2()</a>) -> 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>
</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-pqueue2">pqueue2()</a>) -> 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>
</p>
<h3 class="function"><a name="len-1">len/1</a></h3>
<div class="spec">
<p><tt>len(H::<a href="#type-pqueue2">pqueue2()</a>) -> 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>
</p>
<h3 class="function"><a name="new-0">new/0</a></h3>
<div class="spec">
<p><tt>new() -> <a href="#type-pqueue2">pqueue2()</a></tt><br></p>
</div><p>
<h4><a name="Create_a_new_priority_queue.">Create a new priority queue.</a></h4>
</p>
<h3 class="function"><a name="out-1">out/1</a></h3>
<div class="spec">
<p><tt>out(X1::<a href="#type-pqueue2">pqueue2()</a>) -> {{value, term()}, <a href="#type-pqueue2">pqueue2()</a>} | {empty, <a href="#type-pqueue2">pqueue2()</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>
</p>
<h3 class="function"><a name="out-2">out/2</a></h3>
<div class="spec">
<p><tt>out(P::integer(), H::<a href="#type-pqueue2">pqueue2()</a>) -> {{value, term()}, <a href="#type-pqueue2">pqueue2()</a>} | {empty, <a href="#type-pqueue2">pqueue2()</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>
</p>
<h3 class="function"><a name="pout-1">pout/1</a></h3>
<div class="spec">
<p><tt>pout(X1::<a href="#type-pqueue2">pqueue2()</a>) -> {{value, term(), integer()}, <a href="#type-pqueue2">pqueue2()</a>} | {empty, <a href="#type-pqueue2">pqueue2()</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.</p>
<h3 class="function"><a name="test-0">test/0</a></h3>
<div class="spec">
<p><tt>test() -> any()</tt></p>
</div><p>
<h4><a name="Regression_test.">Regression test.</a></h4>
</p>
<h3 class="function"><a name="to_list-1">to_list/1</a></h3>
<div class="spec">
<p><tt>to_list(H::<a href="#type-pqueue2">pqueue2()</a>) -> [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>
</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, May 7 2013, 15:51:11.</i></p>
</body>
</html>