Array-Heap/Heap.pm

=head1 NAME

Array::Heap - treat perl arrays as heaps (priority queues)

=head1 SYNOPSIS

 use Array::Heap;

=head1 DESCRIPTION

There are a multitude of heap and heap-like modules on CPAN, you might
want to search for /Heap/ and /Priority/ to find many. They implement more
or less fancy datastructures that might well be what you are looking for.

This module takes a different approach: It exports functions (i.e. no
object orientation) that are loosely modeled after the C++ STL's heap
functions. They all take an array as argument, just like perl's built-in
functions C<push>, C<pop> etc.

The implementation itself is in C for maximum speed.

=head1 FUNCTIONS

All of the following functions are being exported by default.

=over 4

=cut

package Array::Heap;

BEGIN {
   $VERSION = '2.0';

   require XSLoader;
   XSLoader::load ("Array::Heap", $VERSION);
}

use base Exporter;

@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
   splice_heap splice_heap_lex splice_heap_cmp
   adjust_heap adjust_heap_lex adjust_heap_cmp
);

=item make_heap @heap                                   (\@)

Reorders the elements in the array so they form a heap, with the lowest
value "on top" of the heap (corresponding to the first array element).

=item make_heap_lex @heap                               (\@)

Just like C<make_heap>, but in string comparison order instead of numerical
comparison order.

=item make_heap_cmp { compare } @heap                   (&\@)

Just like C<make_heap>, but takes a custom comparison function.

=item push_heap @heap, $element, ...                    (\@@)

Adds the given element(s) to the heap.

=item push_heap_lex @heap, $element, ...                (\@@)

Just like C<push_heap>, but in string comparison order instead of numerical
comparison order.

=item push_heap_cmp { compare } @heap, $element, ...    (&\@@)

Just like C<push_heap>, but takes a custom comparison function.

=item pop_heap @heap                                    (\@)

Removes the topmost (lowest) heap element and repairs the heap.

=item pop_heap_lex @heap                                (\@)

Just like C<pop_heap>, but in string comparison order instead of numerical
comparison order.

=item pop_heap_cmp { compare } @heap                    (&\@)

Just like C<pop_heap>, but takes a custom comparison function.

=item splice_heap @heap, $index                         (\@$)

Similar to C<pop_heap>, but removes and returns the element at index
C<$index>.

=item splice_heap_lex @heap, $index                     (\@$)

Just like C<splice_heap>, but in string comparison order instead of
numerical comparison order.

=item splice_heap_cmp { compare } @heap, $index         (&\@$)

Just like C<splice_heap>, but takes a custom comparison function.

=item adjust_heap @heap, $index                         (\@$)

Assuming you have only changed the element at index C<$index>, repair the
heap again. Can be used to remove elements, replace elements, adjust the
priority of elements and more.

=item adjust_heap_lex @heap, $index                     (\@$)

Just like C<adjust_heap>, but in string comparison order instead of
numerical comparison order.

=item adjust_heap_cmp { compare } @heap, $index         (&\@$)

Just like C<adjust_heap>, but takes a custom comparison function.

=cut

1;

=back

=head2 COMPARISON FUNCTIONS

All the functions come in two flavours: one that uses the built-in
comparison function and one that uses a custom comparison function.

The built-in comparison function can either compare scalar numerical
values (string values for *_lex functions), or array refs. If the elements
to compare are array refs, the first element of the array is used for
comparison, i.e.

  1, 4, 6

will be sorted according to their numerical value,

  [1 => $obj1], [2 => $obj2], [3 => $obj3]

will sort according to the first element of the arrays, i.e. C<1,2,3>.

The custom comparison functions work similar to how C<sort> works: C<$a>
and C<$b> are set to the elements to be compared, and the result should be
greater than zero then $a is greater than $b, C<0> otherwise. This means
that you cna use the same function as for sorting the array, but you could
also use a simpler function that just does C<< $a > $b >>.

The first example above corresponds to this comparison "function":

  { $a <=> $b }

And the second example corresponds to this:

  { $a->[0] <=> $b->[0] }

Unlike C<sort>, the default sort is numerical and it is not possible to
use normal subroutines.

=head1 BUGS

=over 4

=item * Numerical comparison is always done using floatingpoint, which
usually has less precision than a 64 bit integer that perl might use
for integers internally, resulting in precision loss on the built-in
comparison.

=item * This module does not work with tied or magical arrays or array
elements, and, in fact, will even crash when you use those.

=item * This module can leak memory (or worse) when your comparison
function exits unexpectedly (e.g. C<last>) or throws an exception, so do
not do that.

=back

=cut

=head1 AUTHOR

 Marc Lehmann <schmorp@schmorp.de>
 http://home.schmorp.de/

=cut

Revision:	1.2
Committed:	Sun Jul 26 04:50:02 2009 UTC (14 years, 9 months ago) by root
Branch:	MAIN
CVS Tags:	rel-2_0
Changes since 1.1:	+60 -8 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.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	root	1.2	This module takes a different approach: It exports functions (i.e. no
16	root	1.1	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	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.2	$VERSION = '2.0';
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			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			);
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			=item make_heap_lex @heap (\@)
55
56			Just like C<make_heap>, but in string comparison order instead of numerical
57			comparison order.
58
59			=item make_heap_cmp { compare } @heap (&\@)
60
61			Just like C<make_heap>, but takes a custom comparison function.
62
63			=item push_heap @heap, $element, ... (\@@)
64
65			Adds the given element(s) to the heap.
66
67			=item push_heap_lex @heap, $element, ... (\@@)
68
69			Just like C<push_heap>, but in string comparison order instead of numerical
70			comparison order.
71
72			=item push_heap_cmp { compare } @heap, $element, ... (&\@@)
73
74			Just like C<push_heap>, but takes a custom comparison function.
75
76			=item pop_heap @heap (\@)
77
78			Removes the topmost (lowest) heap element and repairs the heap.
79
80			=item pop_heap_lex @heap (\@)
81
82			Just like C<pop_heap>, but in string comparison order instead of numerical
83			comparison order.
84
85			=item pop_heap_cmp { compare } @heap (&\@)
86
87			Just like C<pop_heap>, but takes a custom comparison function.
88
89	root	1.2	=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
118	root	1.1	=cut
119
120			1;
121
122			=back
123
124			=head2 COMPARISON FUNCTIONS
125
126			All the functions come in two flavours: one that uses the built-in
127			comparison function and one that uses a custom comparison function.
128
129			The built-in comparison function can either compare scalar numerical
130			values (string values for *_lex functions), or array refs. If the elements
131			to compare are array refs, the first element of the array is used for
132			comparison, i.e.
133
134			1, 4, 6
135
136			will be sorted according to their numerical value,
137
138			[1 => $obj1], [2 => $obj2], [3 => $obj3]
139
140			will sort according to the first element of the arrays, i.e. C<1,2,3>.
141
142			The custom comparison functions work similar to how C<sort> works: C<$a>
143			and C<$b> are set to the elements to be compared, and the result should be
144	root	1.2	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 >>.
147	root	1.1
148			The first example above corresponds to this comparison "function":
149
150			{ $a <=> $b }
151
152			And the second example corresponds to this:
153
154			{ $a->[0] <=> $b->[0] }
155
156			Unlike C<sort>, the default sort is numerical and it is not possible to
157			use normal subroutines.
158
159			=head1 BUGS
160
161	root	1.2	=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
178	root	1.1
179			=head1 AUTHOR
180
181			Marc Lehmann <schmorp@schmorp.de>
182			http://home.schmorp.de/
183
184			=cut
185