1 |
root |
1.1 |
=head1 NAME |
2 |
|
|
|
3 |
root |
1.6 |
Array::Heap - treat perl arrays as binary heaps/priority queues |
4 |
root |
1.1 |
|
5 |
|
|
=head1 SYNOPSIS |
6 |
|
|
|
7 |
|
|
use Array::Heap; |
8 |
|
|
|
9 |
|
|
=head1 DESCRIPTION |
10 |
|
|
|
11 |
|
|
There are a multitude of heap and heap-like modules on CPAN, you might |
12 |
|
|
want to search for /Heap/ and /Priority/ to find many. They implement more |
13 |
|
|
or less fancy datastructures that might well be what you are looking for. |
14 |
|
|
|
15 |
root |
1.2 |
This module takes a different approach: It exports functions (i.e. no |
16 |
root |
1.3 |
object orientation) that are loosely modeled after the C++ STL's binary |
17 |
|
|
heap functions. They all take an array as argument, just like perl's |
18 |
|
|
built-in functions C<push>, C<pop> etc. |
19 |
root |
1.1 |
|
20 |
root |
1.2 |
The implementation itself is in C for maximum speed. |
21 |
root |
1.1 |
|
22 |
|
|
=head1 FUNCTIONS |
23 |
|
|
|
24 |
|
|
All of the following functions are being exported by default. |
25 |
|
|
|
26 |
|
|
=over 4 |
27 |
|
|
|
28 |
|
|
=cut |
29 |
|
|
|
30 |
|
|
package Array::Heap; |
31 |
|
|
|
32 |
|
|
BEGIN { |
33 |
root |
1.8 |
$VERSION = 3.2; |
34 |
root |
1.1 |
|
35 |
|
|
require XSLoader; |
36 |
root |
1.2 |
XSLoader::load ("Array::Heap", $VERSION); |
37 |
root |
1.1 |
} |
38 |
|
|
|
39 |
|
|
use base Exporter; |
40 |
|
|
|
41 |
root |
1.2 |
@EXPORT = qw( |
42 |
root |
1.4 |
make_heap make_heap_lex make_heap_cmp make_heap_idx |
43 |
|
|
push_heap push_heap_lex push_heap_cmp push_heap_idx |
44 |
|
|
pop_heap pop_heap_lex pop_heap_cmp pop_heap_idx |
45 |
|
|
splice_heap splice_heap_lex splice_heap_cmp splice_heap_idx |
46 |
|
|
adjust_heap adjust_heap_lex adjust_heap_cmp adjust_heap_idx |
47 |
root |
1.2 |
); |
48 |
root |
1.1 |
|
49 |
|
|
=item make_heap @heap (\@) |
50 |
|
|
|
51 |
|
|
Reorders the elements in the array so they form a heap, with the lowest |
52 |
|
|
value "on top" of the heap (corresponding to the first array element). |
53 |
|
|
|
54 |
root |
1.4 |
=item make_heap_idx @heap (\@) |
55 |
|
|
|
56 |
|
|
Just like C<make_heap>, but updates the index (see INDEXED OPERATIONS). |
57 |
|
|
|
58 |
root |
1.1 |
=item make_heap_lex @heap (\@) |
59 |
|
|
|
60 |
|
|
Just like C<make_heap>, but in string comparison order instead of numerical |
61 |
|
|
comparison order. |
62 |
|
|
|
63 |
|
|
=item make_heap_cmp { compare } @heap (&\@) |
64 |
|
|
|
65 |
|
|
Just like C<make_heap>, but takes a custom comparison function. |
66 |
|
|
|
67 |
|
|
=item push_heap @heap, $element, ... (\@@) |
68 |
|
|
|
69 |
|
|
Adds the given element(s) to the heap. |
70 |
|
|
|
71 |
root |
1.4 |
=item push_heap_idx @heap, $element, ... (\@@) |
72 |
|
|
|
73 |
|
|
Just like C<push_heap>, but updates the index (see INDEXED OPERATIONS). |
74 |
|
|
|
75 |
root |
1.1 |
=item push_heap_lex @heap, $element, ... (\@@) |
76 |
|
|
|
77 |
|
|
Just like C<push_heap>, but in string comparison order instead of numerical |
78 |
|
|
comparison order. |
79 |
|
|
|
80 |
|
|
=item push_heap_cmp { compare } @heap, $element, ... (&\@@) |
81 |
|
|
|
82 |
|
|
Just like C<push_heap>, but takes a custom comparison function. |
83 |
|
|
|
84 |
|
|
=item pop_heap @heap (\@) |
85 |
|
|
|
86 |
|
|
Removes the topmost (lowest) heap element and repairs the heap. |
87 |
|
|
|
88 |
root |
1.4 |
=item pop_heap_idx @heap (\@) |
89 |
|
|
|
90 |
|
|
Just like C<pop_heap>, but updates the index (see INDEXED OPERATIONS). |
91 |
|
|
|
92 |
root |
1.1 |
=item pop_heap_lex @heap (\@) |
93 |
|
|
|
94 |
|
|
Just like C<pop_heap>, but in string comparison order instead of numerical |
95 |
|
|
comparison order. |
96 |
|
|
|
97 |
|
|
=item pop_heap_cmp { compare } @heap (&\@) |
98 |
|
|
|
99 |
|
|
Just like C<pop_heap>, but takes a custom comparison function. |
100 |
|
|
|
101 |
root |
1.2 |
=item splice_heap @heap, $index (\@$) |
102 |
|
|
|
103 |
|
|
Similar to C<pop_heap>, but removes and returns the element at index |
104 |
|
|
C<$index>. |
105 |
|
|
|
106 |
root |
1.4 |
=item splice_heap_idx @heap, $index (\@$) |
107 |
|
|
|
108 |
|
|
Just like C<splice_heap>, but updates the index (see INDEXED OPERATIONS). |
109 |
|
|
|
110 |
root |
1.2 |
=item splice_heap_lex @heap, $index (\@$) |
111 |
|
|
|
112 |
|
|
Just like C<splice_heap>, but in string comparison order instead of |
113 |
|
|
numerical comparison order. |
114 |
|
|
|
115 |
|
|
=item splice_heap_cmp { compare } @heap, $index (&\@$) |
116 |
|
|
|
117 |
|
|
Just like C<splice_heap>, but takes a custom comparison function. |
118 |
|
|
|
119 |
|
|
=item adjust_heap @heap, $index (\@$) |
120 |
|
|
|
121 |
|
|
Assuming you have only changed the element at index C<$index>, repair the |
122 |
|
|
heap again. Can be used to remove elements, replace elements, adjust the |
123 |
|
|
priority of elements and more. |
124 |
|
|
|
125 |
root |
1.4 |
=item adjust_heap_idx @heap, $index (\@$) |
126 |
|
|
|
127 |
|
|
Just like C<adjust_heap>, but updates the index (see INDEXED OPERATIONS). |
128 |
|
|
|
129 |
root |
1.2 |
=item adjust_heap_lex @heap, $index (\@$) |
130 |
|
|
|
131 |
|
|
Just like C<adjust_heap>, but in string comparison order instead of |
132 |
|
|
numerical comparison order. |
133 |
|
|
|
134 |
|
|
=item adjust_heap_cmp { compare } @heap, $index (&\@$) |
135 |
|
|
|
136 |
|
|
Just like C<adjust_heap>, but takes a custom comparison function. |
137 |
|
|
|
138 |
root |
1.1 |
=cut |
139 |
|
|
|
140 |
|
|
1; |
141 |
|
|
|
142 |
|
|
=back |
143 |
|
|
|
144 |
|
|
=head2 COMPARISON FUNCTIONS |
145 |
|
|
|
146 |
|
|
All the functions come in two flavours: one that uses the built-in |
147 |
|
|
comparison function and one that uses a custom comparison function. |
148 |
|
|
|
149 |
|
|
The built-in comparison function can either compare scalar numerical |
150 |
|
|
values (string values for *_lex functions), or array refs. If the elements |
151 |
|
|
to compare are array refs, the first element of the array is used for |
152 |
|
|
comparison, i.e. |
153 |
|
|
|
154 |
|
|
1, 4, 6 |
155 |
|
|
|
156 |
|
|
will be sorted according to their numerical value, |
157 |
|
|
|
158 |
|
|
[1 => $obj1], [2 => $obj2], [3 => $obj3] |
159 |
|
|
|
160 |
|
|
will sort according to the first element of the arrays, i.e. C<1,2,3>. |
161 |
|
|
|
162 |
|
|
The custom comparison functions work similar to how C<sort> works: C<$a> |
163 |
|
|
and C<$b> are set to the elements to be compared, and the result should be |
164 |
root |
1.2 |
greater than zero then $a is greater than $b, C<0> otherwise. This means |
165 |
root |
1.8 |
that you can use the same function as for sorting the array, but you could |
166 |
root |
1.2 |
also use a simpler function that just does C<< $a > $b >>. |
167 |
root |
1.1 |
|
168 |
|
|
The first example above corresponds to this comparison "function": |
169 |
|
|
|
170 |
|
|
{ $a <=> $b } |
171 |
|
|
|
172 |
|
|
And the second example corresponds to this: |
173 |
|
|
|
174 |
|
|
{ $a->[0] <=> $b->[0] } |
175 |
|
|
|
176 |
|
|
Unlike C<sort>, the default sort is numerical and it is not possible to |
177 |
|
|
use normal subroutines. |
178 |
|
|
|
179 |
root |
1.4 |
=head2 INDEXED OPERATIONS |
180 |
|
|
|
181 |
|
|
The functions whose names end in C<_idx> also "update the index". That |
182 |
|
|
means that all elements must be array refs, with the first element being |
183 |
|
|
the heap value, and the second value being the array index: |
184 |
|
|
|
185 |
|
|
[$value, $index, ...] |
186 |
|
|
|
187 |
|
|
This allows you to quickly locate an element in the array when all you |
188 |
|
|
have is the array reference. |
189 |
|
|
|
190 |
root |
1.1 |
=head1 BUGS |
191 |
|
|
|
192 |
root |
1.2 |
=over 4 |
193 |
|
|
|
194 |
|
|
=item * Numerical comparison is always done using floatingpoint, which |
195 |
|
|
usually has less precision than a 64 bit integer that perl might use |
196 |
|
|
for integers internally, resulting in precision loss on the built-in |
197 |
|
|
comparison. |
198 |
|
|
|
199 |
|
|
=item * This module does not work with tied or magical arrays or array |
200 |
|
|
elements, and, in fact, will even crash when you use those. |
201 |
|
|
|
202 |
|
|
=item * This module can leak memory (or worse) when your comparison |
203 |
|
|
function exits unexpectedly (e.g. C<last>) or throws an exception, so do |
204 |
|
|
not do that. |
205 |
|
|
|
206 |
|
|
=back |
207 |
|
|
|
208 |
|
|
=cut |
209 |
root |
1.1 |
|
210 |
root |
1.4 |
=head1 AUTHOR AND CONTACT INFORMATION |
211 |
root |
1.1 |
|
212 |
|
|
Marc Lehmann <schmorp@schmorp.de> |
213 |
root |
1.4 |
http://software.schmorp.de/pkg/Array-Heap |
214 |
root |
1.1 |
|
215 |
|
|
=cut |
216 |
|
|
|