ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/Array-Heap/Heap.pm
(Generate patch)

Comparing Array-Heap/Heap.pm (file contents):
Revision 1.1 by root, Wed Jul 1 08:31:34 2009 UTC vs.
Revision 1.2 by root, Sun Jul 26 04:50:02 2009 UTC

… …
10 10
11There are a multitude of heap and heap-like modules on CPAN, you might 11There are a multitude of heap and heap-like modules on CPAN, you might
12want to search for /Heap/ and /Priority/ to find many. They implement more 12want to search for /Heap/ and /Priority/ to find many. They implement more
13or less fancy datastructures that might well be what you are looking for. 13or less fancy datastructures that might well be what you are looking for.
14 14
15This module takes a different approach: It exports functions (i.e. not 15This module takes a different approach: It exports functions (i.e. no
16object orientation) that are loosely modeled after the C++ STL's heap 16object orientation) that are loosely modeled after the C++ STL's heap
17functions. They all take an array as argument, just like perl's built-in 17functions. They all take an array as argument, just like perl's built-in
18functions C<push>, C<pop> etc. 18functions C<push>, C<pop> etc.
19 19
20The implementation itself is in C for maximum speed (although I doubt it 20The implementation itself is in C for maximum speed.
21makes that much of a difference).
22 21
23=head1 FUNCTIONS 22=head1 FUNCTIONS
24 23
25All of the following functions are being exported by default. 24All of the following functions are being exported by default.
26 25
… …
29=cut 28=cut
30 29
31package Array::Heap; 30package Array::Heap;
32 31
33BEGIN { 32BEGIN {
34 $VERSION = "1.2"; 33 $VERSION = '2.0';
35 34
36 require XSLoader; 35 require XSLoader;
37 XSLoader::load Array::Heap, $VERSION; 36 XSLoader::load ("Array::Heap", $VERSION);
38} 37}
39 38
40use base Exporter; 39use base Exporter;
41 40
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); 41@EXPORT = qw(
42 make_heap make_heap_lex make_heap_cmp
43 push_heap push_heap_lex push_heap_cmp
44 pop_heap pop_heap_lex pop_heap_cmp
45 splice_heap splice_heap_lex splice_heap_cmp
46 adjust_heap adjust_heap_lex adjust_heap_cmp
47);
43 48
44=item make_heap @heap (\@) 49=item make_heap @heap (\@)
45 50
46Reorders the elements in the array so they form a heap, with the lowest 51Reorders the elements in the array so they form a heap, with the lowest
47value "on top" of the heap (corresponding to the first array element). 52value "on top" of the heap (corresponding to the first array element).
… …
79 84
80=item pop_heap_cmp { compare } @heap (&\@) 85=item pop_heap_cmp { compare } @heap (&\@)
81 86
82Just like C<pop_heap>, but takes a custom comparison function. 87Just like C<pop_heap>, but takes a custom comparison function.
83 88
89=item splice_heap @heap, $index (\@$)
90
91Similar to C<pop_heap>, but removes and returns the element at index
92C<$index>.
93
94=item splice_heap_lex @heap, $index (\@$)
95
96Just like C<splice_heap>, but in string comparison order instead of
97numerical comparison order.
98
99=item splice_heap_cmp { compare } @heap, $index (&\@$)
100
101Just like C<splice_heap>, but takes a custom comparison function.
102
103=item adjust_heap @heap, $index (\@$)
104
105Assuming you have only changed the element at index C<$index>, repair the
106heap again. Can be used to remove elements, replace elements, adjust the
107priority of elements and more.
108
109=item adjust_heap_lex @heap, $index (\@$)
110
111Just like C<adjust_heap>, but in string comparison order instead of
112numerical comparison order.
113
114=item adjust_heap_cmp { compare } @heap, $index (&\@$)
115
116Just like C<adjust_heap>, but takes a custom comparison function.
117
84=cut 118=cut
85 119
861; 1201;
87 121
88=back 122=back
… …
105 139
106will sort according to the first element of the arrays, i.e. C<1,2,3>. 140will sort according to the first element of the arrays, i.e. C<1,2,3>.
107 141
108The custom comparison functions work similar to how C<sort> works: C<$a> 142The custom comparison functions work similar to how C<sort> works: C<$a>
109and C<$b> are set to the elements to be compared, and the result should be 143and C<$b> are set to the elements to be compared, and the result should be
110either C<-1> if C<$a> is less than C<$b>, or C<< >= 0 >> otherwise. 144greater than zero then $a is greater than $b, C<0> otherwise. This means
145that you cna use the same function as for sorting the array, but you could
146also use a simpler function that just does C<< $a > $b >>.
111 147
112The first example above corresponds to this comparison "function": 148The first example above corresponds to this comparison "function":
113 149
114 { $a <=> $b } 150 { $a <=> $b }
115 151
… …
120Unlike C<sort>, the default sort is numerical and it is not possible to 156Unlike C<sort>, the default sort is numerical and it is not possible to
121use normal subroutines. 157use normal subroutines.
122 158
123=head1 BUGS 159=head1 BUGS
124 160
125This module works not work with tied or magical arrays or array elements. 161=over 4
162
163=item * Numerical comparison is always done using floatingpoint, which
164usually has less precision than a 64 bit integer that perl might use
165for integers internally, resulting in precision loss on the built-in
166comparison.
167
168=item * This module does not work with tied or magical arrays or array
169elements, and, in fact, will even crash when you use those.
170
171=item * This module can leak memory (or worse) when your comparison
172function exits unexpectedly (e.g. C<last>) or throws an exception, so do
173not do that.
174
175=back
176
177=cut
126 178
127=head1 AUTHOR 179=head1 AUTHOR
128 180
129 Marc Lehmann <schmorp@schmorp.de> 181 Marc Lehmann <schmorp@schmorp.de>
130 http://home.schmorp.de/ 182 http://home.schmorp.de/

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines