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

Comparing Array-Heap/README (file contents):
Revision 1.2 by root, Sun Jul 26 05:25:18 2009 UTC vs.
Revision 1.3 by root, Fri Apr 19 20:53:56 2013 UTC

… …
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. no 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 binary
15 functions. They all take an array as argument, just like perl's built-in 15 heap functions. They all take an array as argument, just like perl's
16 functions "push", "pop" etc. 16 built-in functions "push", "pop" etc.
17 17
18 The implementation itself is in C for maximum speed. 18 The implementation itself is in C for maximum speed.
19 19
20FUNCTIONS 20FUNCTIONS
21 All of the following functions are being exported by default. 21 All of the following functions are being exported by default.
… …
23 make_heap @heap (\@) 23 make_heap @heap (\@)
24 Reorders the elements in the array so they form a heap, with the 24 Reorders the elements in the array so they form a heap, with the
25 lowest value "on top" of the heap (corresponding to the first array 25 lowest value "on top" of the heap (corresponding to the first array
26 element). 26 element).
27 27
28 make_heap_idx @heap (\@)
29 Just like "make_heap", but updates the index (see INDEXED
30 OPERATIONS).
31
28 make_heap_lex @heap (\@) 32 make_heap_lex @heap (\@)
29 Just like "make_heap", but in string comparison order instead of 33 Just like "make_heap", but in string comparison order instead of
30 numerical comparison order. 34 numerical comparison order.
31 35
32 make_heap_cmp { compare } @heap (&\@) 36 make_heap_cmp { compare } @heap (&\@)
33 Just like "make_heap", but takes a custom comparison function. 37 Just like "make_heap", but takes a custom comparison function.
34 38
35 push_heap @heap, $element, ... (\@@) 39 push_heap @heap, $element, ... (\@@)
36 Adds the given element(s) to the heap. 40 Adds the given element(s) to the heap.
37 41
42 push_heap_idx @heap, $element, ... (\@@)
43 Just like "push_heap", but updates the index (see INDEXED
44 OPERATIONS).
45
38 push_heap_lex @heap, $element, ... (\@@) 46 push_heap_lex @heap, $element, ... (\@@)
39 Just like "push_heap", but in string comparison order instead of 47 Just like "push_heap", but in string comparison order instead of
40 numerical comparison order. 48 numerical comparison order.
41 49
42 push_heap_cmp { compare } @heap, $element, ... (&\@@) 50 push_heap_cmp { compare } @heap, $element, ... (&\@@)
43 Just like "push_heap", but takes a custom comparison function. 51 Just like "push_heap", but takes a custom comparison function.
44 52
45 pop_heap @heap (\@) 53 pop_heap @heap (\@)
46 Removes the topmost (lowest) heap element and repairs the heap. 54 Removes the topmost (lowest) heap element and repairs the heap.
55
56 pop_heap_idx @heap (\@)
57 Just like "pop_heap", but updates the index (see INDEXED
58 OPERATIONS).
47 59
48 pop_heap_lex @heap (\@) 60 pop_heap_lex @heap (\@)
49 Just like "pop_heap", but in string comparison order instead of 61 Just like "pop_heap", but in string comparison order instead of
50 numerical comparison order. 62 numerical comparison order.
51 63
… …
54 66
55 splice_heap @heap, $index (\@$) 67 splice_heap @heap, $index (\@$)
56 Similar to "pop_heap", but removes and returns the element at index 68 Similar to "pop_heap", but removes and returns the element at index
57 $index. 69 $index.
58 70
71 splice_heap_idx @heap, $index (\@$)
72 Just like "splice_heap", but updates the index (see INDEXED
73 OPERATIONS).
74
59 splice_heap_lex @heap, $index (\@$) 75 splice_heap_lex @heap, $index (\@$)
60 Just like "splice_heap", but in string comparison order instead of 76 Just like "splice_heap", but in string comparison order instead of
61 numerical comparison order. 77 numerical comparison order.
62 78
63 splice_heap_cmp { compare } @heap, $index (&\@$) 79 splice_heap_cmp { compare } @heap, $index (&\@$)
… …
65 81
66 adjust_heap @heap, $index (\@$) 82 adjust_heap @heap, $index (\@$)
67 Assuming you have only changed the element at index $index, repair 83 Assuming you have only changed the element at index $index, repair
68 the heap again. Can be used to remove elements, replace elements, 84 the heap again. Can be used to remove elements, replace elements,
69 adjust the priority of elements and more. 85 adjust the priority of elements and more.
86
87 adjust_heap_idx @heap, $index (\@$)
88 Just like "adjust_heap", but updates the index (see INDEXED
89 OPERATIONS).
70 90
71 adjust_heap_lex @heap, $index (\@$) 91 adjust_heap_lex @heap, $index (\@$)
72 Just like "adjust_heap", but in string comparison order instead of 92 Just like "adjust_heap", but in string comparison order instead of
73 numerical comparison order. 93 numerical comparison order.
74 94
… …
107 { $a->[0] <=> $b->[0] } 127 { $a->[0] <=> $b->[0] }
108 128
109 Unlike "sort", the default sort is numerical and it is not possible to 129 Unlike "sort", the default sort is numerical and it is not possible to
110 use normal subroutines. 130 use normal subroutines.
111 131
132 INDEXED OPERATIONS
133 The functions whose names end in "_idx" also "update the index". That
134 means that all elements must be array refs, with the first element being
135 the heap value, and the second value being the array index:
136
137 [$value, $index, ...]
138
139 This allows you to quickly locate an element in the array when all you
140 have is the array reference.
141
112BUGS 142BUGS
113 * Numerical comparison is always done using floatingpoint, which 143 * Numerical comparison is always done using floatingpoint, which
114 usually has less precision than a 64 bit integer that perl might use 144 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 145 for integers internally, resulting in precision loss on the built-in
116 comparison. 146 comparison.
… …
120 150
121 * This module can leak memory (or worse) when your comparison function 151 * This module can leak memory (or worse) when your comparison function
122 exits unexpectedly (e.g. "last") or throws an exception, so do not 152 exits unexpectedly (e.g. "last") or throws an exception, so do not
123 do that. 153 do that.
124 154
125AUTHOR 155AUTHOR AND CONTACT INFORMATION
126 Marc Lehmann <schmorp@schmorp.de> 156 Marc Lehmann <schmorp@schmorp.de>
127 http://home.schmorp.de/ 157 http://software.schmorp.de/pkg/Array-Heap
128 158

Diff Legend

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