… | |
… | |
10 | |
10 | |
11 | There are a multitude of heap and heap-like modules on CPAN, you might |
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 |
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. |
13 | or less fancy datastructures that might well be what you are looking for. |
14 | |
14 | |
15 | This module takes a different approach: It exports functions (i.e. not |
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 heap |
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 |
17 | functions. They all take an array as argument, just like perl's built-in |
18 | functions C<push>, C<pop> etc. |
18 | functions C<push>, C<pop> etc. |
19 | |
19 | |
20 | The implementation itself is in C for maximum speed (although I doubt it |
20 | The implementation itself is in C for maximum speed. |
21 | makes that much of a difference). |
|
|
22 | |
21 | |
23 | =head1 FUNCTIONS |
22 | =head1 FUNCTIONS |
24 | |
23 | |
25 | All of the following functions are being exported by default. |
24 | All of the following functions are being exported by default. |
26 | |
25 | |
… | |
… | |
29 | =cut |
28 | =cut |
30 | |
29 | |
31 | package Array::Heap; |
30 | package Array::Heap; |
32 | |
31 | |
33 | BEGIN { |
32 | BEGIN { |
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 | |
40 | use base Exporter; |
39 | use 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 | |
46 | Reorders the elements in the array so they form a heap, with the lowest |
51 | 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). |
52 | value "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 | |
82 | Just like C<pop_heap>, but takes a custom comparison function. |
87 | Just like C<pop_heap>, but takes a custom comparison function. |
83 | |
88 | |
|
|
89 | =item splice_heap @heap, $index (\@$) |
|
|
90 | |
|
|
91 | Similar to C<pop_heap>, but removes and returns the element at index |
|
|
92 | C<$index>. |
|
|
93 | |
|
|
94 | =item splice_heap_lex @heap, $index (\@$) |
|
|
95 | |
|
|
96 | Just like C<splice_heap>, but in string comparison order instead of |
|
|
97 | numerical comparison order. |
|
|
98 | |
|
|
99 | =item splice_heap_cmp { compare } @heap, $index (&\@$) |
|
|
100 | |
|
|
101 | Just like C<splice_heap>, but takes a custom comparison function. |
|
|
102 | |
|
|
103 | =item adjust_heap @heap, $index (\@$) |
|
|
104 | |
|
|
105 | Assuming you have only changed the element at index C<$index>, repair the |
|
|
106 | heap again. Can be used to remove elements, replace elements, adjust the |
|
|
107 | priority of elements and more. |
|
|
108 | |
|
|
109 | =item adjust_heap_lex @heap, $index (\@$) |
|
|
110 | |
|
|
111 | Just like C<adjust_heap>, but in string comparison order instead of |
|
|
112 | numerical comparison order. |
|
|
113 | |
|
|
114 | =item adjust_heap_cmp { compare } @heap, $index (&\@$) |
|
|
115 | |
|
|
116 | Just like C<adjust_heap>, but takes a custom comparison function. |
|
|
117 | |
84 | =cut |
118 | =cut |
85 | |
119 | |
86 | 1; |
120 | 1; |
87 | |
121 | |
88 | =back |
122 | =back |
… | |
… | |
105 | |
139 | |
106 | will sort according to the first element of the arrays, i.e. C<1,2,3>. |
140 | will sort according to the first element of the arrays, i.e. C<1,2,3>. |
107 | |
141 | |
108 | The custom comparison functions work similar to how C<sort> works: C<$a> |
142 | 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 |
143 | 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. |
144 | greater than zero then $a is greater than $b, C<0> otherwise. This means |
|
|
145 | that you cna use the same function as for sorting the array, but you could |
|
|
146 | also use a simpler function that just does C<< $a > $b >>. |
111 | |
147 | |
112 | The first example above corresponds to this comparison "function": |
148 | The first example above corresponds to this comparison "function": |
113 | |
149 | |
114 | { $a <=> $b } |
150 | { $a <=> $b } |
115 | |
151 | |
… | |
… | |
120 | Unlike C<sort>, the default sort is numerical and it is not possible to |
156 | Unlike C<sort>, the default sort is numerical and it is not possible to |
121 | use normal subroutines. |
157 | use normal subroutines. |
122 | |
158 | |
123 | =head1 BUGS |
159 | =head1 BUGS |
124 | |
160 | |
125 | This 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 |
|
|
164 | usually has less precision than a 64 bit integer that perl might use |
|
|
165 | for integers internally, resulting in precision loss on the built-in |
|
|
166 | comparison. |
|
|
167 | |
|
|
168 | =item * This module does not work with tied or magical arrays or array |
|
|
169 | elements, and, in fact, will even crash when you use those. |
|
|
170 | |
|
|
171 | =item * This module can leak memory (or worse) when your comparison |
|
|
172 | function exits unexpectedly (e.g. C<last>) or throws an exception, so do |
|
|
173 | not 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/ |