| 1 |
=head1 NAME |
| 2 |
|
| 3 |
Array::Heap - treat perl arrays as heaps (priority queues) |
| 4 |
|
| 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 |
This module takes a different approach: It exports functions (i.e. no |
| 16 |
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 |
|
| 20 |
The implementation itself is in C for maximum speed. |
| 21 |
|
| 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 |
$VERSION = '3.0'; |
| 34 |
|
| 35 |
require XSLoader; |
| 36 |
XSLoader::load ("Array::Heap", $VERSION); |
| 37 |
} |
| 38 |
|
| 39 |
use base Exporter; |
| 40 |
|
| 41 |
@EXPORT = qw( |
| 42 |
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 |
); |
| 48 |
|
| 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 |
=item make_heap_idx @heap (\@) |
| 55 |
|
| 56 |
Just like C<make_heap>, but updates the index (see INDEXED OPERATIONS). |
| 57 |
|
| 58 |
=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 |
=item push_heap_idx @heap, $element, ... (\@@) |
| 72 |
|
| 73 |
Just like C<push_heap>, but updates the index (see INDEXED OPERATIONS). |
| 74 |
|
| 75 |
=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 |
=item pop_heap_idx @heap (\@) |
| 89 |
|
| 90 |
Just like C<pop_heap>, but updates the index (see INDEXED OPERATIONS). |
| 91 |
|
| 92 |
=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 |
=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 |
=item splice_heap_idx @heap, $index (\@$) |
| 107 |
|
| 108 |
Just like C<splice_heap>, but updates the index (see INDEXED OPERATIONS). |
| 109 |
|
| 110 |
=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 |
=item adjust_heap_idx @heap, $index (\@$) |
| 126 |
|
| 127 |
Just like C<adjust_heap>, but updates the index (see INDEXED OPERATIONS). |
| 128 |
|
| 129 |
=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 |
=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 |
greater than zero then $a is greater than $b, C<0> otherwise. This means |
| 165 |
that you cna use the same function as for sorting the array, but you could |
| 166 |
also use a simpler function that just does C<< $a > $b >>. |
| 167 |
|
| 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 |
=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 |
=head1 BUGS |
| 191 |
|
| 192 |
=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 |
|
| 210 |
=head1 AUTHOR AND CONTACT INFORMATION |
| 211 |
|
| 212 |
Marc Lehmann <schmorp@schmorp.de> |
| 213 |
http://software.schmorp.de/pkg/Array-Heap |
| 214 |
|
| 215 |
=cut |
| 216 |
|
