File Coverage

blib/lib/Array/Heap2.pm

Criterion	Covered	Total	%
statement	6	6	100.0
branch			n/a
condition			n/a
subroutine	2	2	100.0
pod			n/a
total	8	8	100.0

line	stmt	sub	time	code
1				=head1 NAME
2
3				Array::Heap2 - treat perl arrays as heaps (priority queues)
4
5				=head1 SYNOPSIS
6
7				use Array::Heap2;
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, C 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::Heap2;
32
33				BEGIN {
34	1	1	762	$VERSION = "1.1";
35
36	1		6	require XSLoader;
37	1		592	XSLoader::load Array::Heap2, $VERSION;
38				}
39
40	1	1	6	use base Exporter;
	1		2
	1		160
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, but in string comparison order instead of numerical
52				comparison order.
53
54				=item make_heap_cmp { compare } @heap (&\@)
55
56				Just like C, 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, 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, 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, but in string comparison order instead of numerical
78				comparison order.
79
80				=item pop_heap_cmp { compare } @heap (&\@)
81
82				Just like C, 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 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, 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
130				http://home.schmorp.de/
131
132				=cut
133