Array-Heap/Heap.pm

=head1 NAME

Array::Heap - treat perl arrays as binary 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 binary
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 = 3.2;

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

use base Exporter;

@EXPORT = qw(
   make_heap   make_heap_lex   make_heap_cmp   make_heap_idx
   push_heap   push_heap_lex   push_heap_cmp   push_heap_idx
   pop_heap    pop_heap_lex    pop_heap_cmp    pop_heap_idx
   splice_heap splice_heap_lex splice_heap_cmp splice_heap_idx
   adjust_heap adjust_heap_lex adjust_heap_cmp adjust_heap_idx
);

=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_idx @heap                               (\@)

Just like C<make_heap>, but updates the index (see INDEXED OPERATIONS).

=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_idx @heap, $element, ...                (\@@)

Just like C<push_heap>,  but updates the index (see INDEXED OPERATIONS).

=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_idx @heap                                (\@)

Just like C<pop_heap>, but updates the index (see INDEXED OPERATIONS).

=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_idx @heap, $index                     (\@$)

Just like C<splice_heap>, but updates the index (see INDEXED OPERATIONS).

=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_idx @heap, $index                     (\@$)

Just like C<adjust_heap>, but updates the index (see INDEXED OPERATIONS).

=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 can 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.

=head2 INDEXED OPERATIONS

The functions whose names end in C<_idx> also "update the index". That
means that all elements must be array refs, with the first element being
the heap value, and the second value being the array index:

  [$value, $index, ...]

This allows you to quickly locate an element in the array when all you
have is the array reference.

=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 AND CONTACT INFORMATION

 Marc Lehmann <schmorp@schmorp.de>
 http://software.schmorp.de/pkg/Array-Heap

=cut

Revision:	1.8
Committed:	Tue Jul 14 23:28:10 2015 UTC (8 years, 10 months ago) by root
Branch:	MAIN
CVS Tags:	rel-3_2
Changes since 1.7:	+2 -2 lines
Log Message:	3.2
#	User	Rev	Content
1	root	1.1	=head1 NAME
2
3	root	1.6	Array::Heap - treat perl arrays as binary heaps/priority queues
4	root	1.1
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.3	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	root	1.1
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.8	$VERSION = 3.2;
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	root	1.4	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	root	1.2	);
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	root	1.4	=item make_heap_idx @heap (\@)
55
56			Just like C<make_heap>, but updates the index (see INDEXED OPERATIONS).
57
58	root	1.1	=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	root	1.4	=item push_heap_idx @heap, $element, ... (\@@)
72
73			Just like C<push_heap>, but updates the index (see INDEXED OPERATIONS).
74
75	root	1.1	=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	root	1.4	=item pop_heap_idx @heap (\@)
89
90			Just like C<pop_heap>, but updates the index (see INDEXED OPERATIONS).
91
92	root	1.1	=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	root	1.2	=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	root	1.4	=item splice_heap_idx @heap, $index (\@$)
107
108			Just like C<splice_heap>, but updates the index (see INDEXED OPERATIONS).
109
110	root	1.2	=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	root	1.4	=item adjust_heap_idx @heap, $index (\@$)
126
127			Just like C<adjust_heap>, but updates the index (see INDEXED OPERATIONS).
128
129	root	1.2	=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	root	1.1	=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	root	1.2	greater than zero then $a is greater than $b, C<0> otherwise. This means
165	root	1.8	that you can use the same function as for sorting the array, but you could
166	root	1.2	also use a simpler function that just does C<< $a > $b >>.
167	root	1.1
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	root	1.4	=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	root	1.1	=head1 BUGS
191
192	root	1.2	=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	root	1.1
210	root	1.4	=head1 AUTHOR AND CONTACT INFORMATION
211	root	1.1
212			Marc Lehmann <schmorp@schmorp.de>
213	root	1.4	http://software.schmorp.de/pkg/Array-Heap
214	root	1.1
215			=cut
216