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

Comparing Array-Heap/README (file contents):
Revision 1.1 by root, Wed Jul 1 08:31:34 2009 UTC vs.
Revision 1.2 by root, Sun Jul 26 05:25:18 2009 UTC

… …
8 There are a multitude of heap and heap-like modules on CPAN, you might 8 There are a multitude of heap and heap-like modules on CPAN, you might
9 want to search for /Heap/ and /Priority/ to find many. They implement 9 want to search for /Heap/ and /Priority/ to find many. They implement
10 more or less fancy datastructures that might well be what you are 10 more or less fancy datastructures that might well be what you are
11 looking for. 11 looking for.
12 12
13 This module takes a different approach: It exports functions (i.e. not 13 This module takes a different approach: It exports functions (i.e. no
14 object orientation) that are loosely modeled after the C++ STL's heap 14 object orientation) that are loosely modeled after the C++ STL's heap
15 functions. They all take an array as argument, just like perl's built-in 15 functions. They all take an array as argument, just like perl's built-in
16 functions "push", "pop" etc. 16 functions "push", "pop" etc.
17 17
18 The implementation itself is in C for maximum speed (although I doubt it 18 The implementation itself is in C for maximum speed.
19 makes that much of a difference).
20 19
21FUNCTIONS 20FUNCTIONS
22 All of the following functions are being exported by default. 21 All of the following functions are being exported by default.
23 22
24 make_heap @heap (\@) 23 make_heap @heap (\@)
… …
51 numerical comparison order. 50 numerical comparison order.
52 51
53 pop_heap_cmp { compare } @heap (&\@) 52 pop_heap_cmp { compare } @heap (&\@)
54 Just like "pop_heap", but takes a custom comparison function. 53 Just like "pop_heap", but takes a custom comparison function.
55 54
55 splice_heap @heap, $index (\@$)
56 Similar to "pop_heap", but removes and returns the element at index
57 $index.
58
59 splice_heap_lex @heap, $index (\@$)
60 Just like "splice_heap", but in string comparison order instead of
61 numerical comparison order.
62
63 splice_heap_cmp { compare } @heap, $index (&\@$)
64 Just like "splice_heap", but takes a custom comparison function.
65
66 adjust_heap @heap, $index (\@$)
67 Assuming you have only changed the element at index $index, repair
68 the heap again. Can be used to remove elements, replace elements,
69 adjust the priority of elements and more.
70
71 adjust_heap_lex @heap, $index (\@$)
72 Just like "adjust_heap", but in string comparison order instead of
73 numerical comparison order.
74
75 adjust_heap_cmp { compare } @heap, $index (&\@$)
76 Just like "adjust_heap", but takes a custom comparison function.
77
56 COMPARISON FUNCTIONS 78 COMPARISON FUNCTIONS
57 All the functions come in two flavours: one that uses the built-in 79 All the functions come in two flavours: one that uses the built-in
58 comparison function and one that uses a custom comparison function. 80 comparison function and one that uses a custom comparison function.
59 81
60 The built-in comparison function can either compare scalar numerical 82 The built-in comparison function can either compare scalar numerical
… …
70 92
71 will sort according to the first element of the arrays, i.e. "1,2,3". 93 will sort according to the first element of the arrays, i.e. "1,2,3".
72 94
73 The custom comparison functions work similar to how "sort" works: $a and 95 The custom comparison functions work similar to how "sort" works: $a and
74 $b are set to the elements to be compared, and the result should be 96 $b are set to the elements to be compared, and the result should be
75 either -1 if $a is less than $b, or ">= 0" otherwise. 97 greater than zero then $a is greater than $b, 0 otherwise. This means
98 that you cna use the same function as for sorting the array, but you
99 could also use a simpler function that just does "$a > $b".
76 100
77 The first example above corresponds to this comparison "function": 101 The first example above corresponds to this comparison "function":
78 102
79 { $a <=> $b } 103 { $a <=> $b }
80 104
… …
84 108
85 Unlike "sort", the default sort is numerical and it is not possible to 109 Unlike "sort", the default sort is numerical and it is not possible to
86 use normal subroutines. 110 use normal subroutines.
87 111
88BUGS 112BUGS
113 * Numerical comparison is always done using floatingpoint, which
114 usually has less precision than a 64 bit integer that perl might use
115 for integers internally, resulting in precision loss on the built-in
116 comparison.
117
89 This module works not work with tied or magical arrays or array 118 * This module does not work with tied or magical arrays or array
90 elements. 119 elements, and, in fact, will even crash when you use those.
120
121 * This module can leak memory (or worse) when your comparison function
122 exits unexpectedly (e.g. "last") or throws an exception, so do not
123 do that.
91 124
92AUTHOR 125AUTHOR
93 Marc Lehmann <schmorp@schmorp.de> 126 Marc Lehmann <schmorp@schmorp.de>
94 http://home.schmorp.de/ 127 http://home.schmorp.de/
95 128

Diff Legend

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