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. not |
16 |
object orientation) that are loosely modeled after the C++ STL's heap |
17 |
functions. They all take an array as argument, just like perl's built-in |
18 |
functions C<push>, C<pop> etc. |
19 |
|
20 |
The implementation itself is in C for maximum speed (although I doubt it |
21 |
makes that much of a difference). |
22 |
|
23 |
=head1 FUNCTIONS |
24 |
|
25 |
All of the following functions are being exported by default. |
26 |
|
27 |
=over 4 |
28 |
|
29 |
=cut |
30 |
|
31 |
package Array::Heap; |
32 |
|
33 |
BEGIN { |
34 |
$VERSION = "1.2"; |
35 |
|
36 |
require XSLoader; |
37 |
XSLoader::load Array::Heap, $VERSION; |
38 |
} |
39 |
|
40 |
use base Exporter; |
41 |
|
42 |
@EXPORT = qw(make_heap make_heap_lex make_heap_cmp push_heap push_heap_lex push_heap_cmp pop_heap pop_heap_lex pop_heap_cmp); |
43 |
|
44 |
=item make_heap @heap (\@) |
45 |
|
46 |
Reorders the elements in the array so they form a heap, with the lowest |
47 |
value "on top" of the heap (corresponding to the first array element). |
48 |
|
49 |
=item make_heap_lex @heap (\@) |
50 |
|
51 |
Just like C<make_heap>, but in string comparison order instead of numerical |
52 |
comparison order. |
53 |
|
54 |
=item make_heap_cmp { compare } @heap (&\@) |
55 |
|
56 |
Just like C<make_heap>, but takes a custom comparison function. |
57 |
|
58 |
=item push_heap @heap, $element, ... (\@@) |
59 |
|
60 |
Adds the given element(s) to the heap. |
61 |
|
62 |
=item push_heap_lex @heap, $element, ... (\@@) |
63 |
|
64 |
Just like C<push_heap>, but in string comparison order instead of numerical |
65 |
comparison order. |
66 |
|
67 |
=item push_heap_cmp { compare } @heap, $element, ... (&\@@) |
68 |
|
69 |
Just like C<push_heap>, but takes a custom comparison function. |
70 |
|
71 |
=item pop_heap @heap (\@) |
72 |
|
73 |
Removes the topmost (lowest) heap element and repairs the heap. |
74 |
|
75 |
=item pop_heap_lex @heap (\@) |
76 |
|
77 |
Just like C<pop_heap>, but in string comparison order instead of numerical |
78 |
comparison order. |
79 |
|
80 |
=item pop_heap_cmp { compare } @heap (&\@) |
81 |
|
82 |
Just like C<pop_heap>, but takes a custom comparison function. |
83 |
|
84 |
=cut |
85 |
|
86 |
1; |
87 |
|
88 |
=back |
89 |
|
90 |
=head2 COMPARISON FUNCTIONS |
91 |
|
92 |
All the functions come in two flavours: one that uses the built-in |
93 |
comparison function and one that uses a custom comparison function. |
94 |
|
95 |
The built-in comparison function can either compare scalar numerical |
96 |
values (string values for *_lex functions), or array refs. If the elements |
97 |
to compare are array refs, the first element of the array is used for |
98 |
comparison, i.e. |
99 |
|
100 |
1, 4, 6 |
101 |
|
102 |
will be sorted according to their numerical value, |
103 |
|
104 |
[1 => $obj1], [2 => $obj2], [3 => $obj3] |
105 |
|
106 |
will sort according to the first element of the arrays, i.e. C<1,2,3>. |
107 |
|
108 |
The custom comparison functions work similar to how C<sort> works: C<$a> |
109 |
and C<$b> are set to the elements to be compared, and the result should be |
110 |
either C<-1> if C<$a> is less than C<$b>, or C<< >= 0 >> otherwise. |
111 |
|
112 |
The first example above corresponds to this comparison "function": |
113 |
|
114 |
{ $a <=> $b } |
115 |
|
116 |
And the second example corresponds to this: |
117 |
|
118 |
{ $a->[0] <=> $b->[0] } |
119 |
|
120 |
Unlike C<sort>, the default sort is numerical and it is not possible to |
121 |
use normal subroutines. |
122 |
|
123 |
=head1 BUGS |
124 |
|
125 |
This module works not work with tied or magical arrays or array elements. |
126 |
|
127 |
=head1 AUTHOR |
128 |
|
129 |
Marc Lehmann <schmorp@schmorp.de> |
130 |
http://home.schmorp.de/ |
131 |
|
132 |
=cut |
133 |
|