Revision: | 1.5 |

Committed: | Fri Apr 19 20:53:56 2013 UTC (11 years, 3 months ago) by root |

Branch: | MAIN |

CVS Tags: | rel-3_0 |

Changes since 1.4: |
+1 -1 lines |

Log Message: | 3.0 |

# | Content |
---|---|

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 | This module takes a different approach: It exports functions (i.e. no |

16 | 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 | |

20 | The implementation itself is in C for maximum speed. |

21 | |

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 | $VERSION = '3.0'; |

34 | |

35 | require XSLoader; |

36 | XSLoader::load ("Array::Heap", $VERSION); |

37 | } |

38 | |

39 | use base Exporter; |

40 | |

41 | @EXPORT = qw( |

42 | 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 | ); |

48 | |

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

55 | |

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

57 | |

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

72 | |

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

74 | |

75 | =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 | =item pop_heap_idx @heap (\@) |

89 | |

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

91 | |

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

107 | |

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

109 | |

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

126 | |

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

128 | |

129 | =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 | =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 | greater than zero then $a is greater than $b, C<0> otherwise. This means |

165 | that you cna use the same function as for sorting the array, but you could |

166 | also use a simpler function that just does C<< $a > $b >>. |

167 | |

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 | =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 | =head1 BUGS |

191 | |

192 | =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 | |

210 | =head1 AUTHOR AND CONTACT INFORMATION |

211 | |

212 | Marc Lehmann <schmorp@schmorp.de> |

213 | http://software.schmorp.de/pkg/Array-Heap |

214 | |

215 | =cut |

216 |