Revision: | 1.3 |

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.2: |
+35 -5 lines |

Log Message: | 3.0 |

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

1 | NAME |

2 | Array::Heap - treat perl arrays as heaps (priority queues) |

3 | |

4 | SYNOPSIS |

5 | use Array::Heap; |

6 | |

7 | DESCRIPTION |

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 |

10 | more or less fancy datastructures that might well be what you are |

11 | looking for. |

12 | |

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

15 | heap functions. They all take an array as argument, just like perl's |

16 | built-in functions "push", "pop" etc. |

17 | |

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

19 | |

20 | FUNCTIONS |

21 | All of the following functions are being exported by default. |

22 | |

23 | make_heap @heap (\@) |

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 |

26 | element). |

27 | |

28 | make_heap_idx @heap (\@) |

29 | Just like "make_heap", but updates the index (see INDEXED |

30 | OPERATIONS). |

31 | |

32 | make_heap_lex @heap (\@) |

33 | Just like "make_heap", but in string comparison order instead of |

34 | numerical comparison order. |

35 | |

36 | make_heap_cmp { compare } @heap (&\@) |

37 | Just like "make_heap", but takes a custom comparison function. |

38 | |

39 | push_heap @heap, $element, ... (\@@) |

40 | Adds the given element(s) to the heap. |

41 | |

42 | push_heap_idx @heap, $element, ... (\@@) |

43 | Just like "push_heap", but updates the index (see INDEXED |

44 | OPERATIONS). |

45 | |

46 | push_heap_lex @heap, $element, ... (\@@) |

47 | Just like "push_heap", but in string comparison order instead of |

48 | numerical comparison order. |

49 | |

50 | push_heap_cmp { compare } @heap, $element, ... (&\@@) |

51 | Just like "push_heap", but takes a custom comparison function. |

52 | |

53 | pop_heap @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). |

59 | |

60 | pop_heap_lex @heap (\@) |

61 | Just like "pop_heap", but in string comparison order instead of |

62 | numerical comparison order. |

63 | |

64 | pop_heap_cmp { compare } @heap (&\@) |

65 | Just like "pop_heap", but takes a custom comparison function. |

66 | |

67 | splice_heap @heap, $index (\@$) |

68 | Similar to "pop_heap", but removes and returns the element at index |

69 | $index. |

70 | |

71 | splice_heap_idx @heap, $index (\@$) |

72 | Just like "splice_heap", but updates the index (see INDEXED |

73 | OPERATIONS). |

74 | |

75 | splice_heap_lex @heap, $index (\@$) |

76 | Just like "splice_heap", but in string comparison order instead of |

77 | numerical comparison order. |

78 | |

79 | splice_heap_cmp { compare } @heap, $index (&\@$) |

80 | Just like "splice_heap", but takes a custom comparison function. |

81 | |

82 | adjust_heap @heap, $index (\@$) |

83 | Assuming you have only changed the element at index $index, repair |

84 | the heap again. Can be used to remove elements, replace elements, |

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). |

90 | |

91 | adjust_heap_lex @heap, $index (\@$) |

92 | Just like "adjust_heap", but in string comparison order instead of |

93 | numerical comparison order. |

94 | |

95 | adjust_heap_cmp { compare } @heap, $index (&\@$) |

96 | Just like "adjust_heap", but takes a custom comparison function. |

97 | |

98 | COMPARISON FUNCTIONS |

99 | All the functions come in two flavours: one that uses the built-in |

100 | comparison function and one that uses a custom comparison function. |

101 | |

102 | The built-in comparison function can either compare scalar numerical |

103 | values (string values for *_lex functions), or array refs. If the |

104 | elements to compare are array refs, the first element of the array is |

105 | used for comparison, i.e. |

106 | |

107 | 1, 4, 6 |

108 | |

109 | will be sorted according to their numerical value, |

110 | |

111 | [1 => $obj1], [2 => $obj2], [3 => $obj3] |

112 | |

113 | will sort according to the first element of the arrays, i.e. "1,2,3". |

114 | |

115 | The custom comparison functions work similar to how "sort" works: $a and |

116 | $b are set to the elements to be compared, and the result should be |

117 | greater than zero then $a is greater than $b, 0 otherwise. This means |

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

119 | could also use a simpler function that just does "$a > $b". |

120 | |

121 | The first example above corresponds to this comparison "function": |

122 | |

123 | { $a <=> $b } |

124 | |

125 | And the second example corresponds to this: |

126 | |

127 | { $a->[0] <=> $b->[0] } |

128 | |

129 | Unlike "sort", the default sort is numerical and it is not possible to |

130 | use normal subroutines. |

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

142 | BUGS |

143 | * Numerical comparison is always done using floatingpoint, which |

144 | usually has less precision than a 64 bit integer that perl might use |

145 | for integers internally, resulting in precision loss on the built-in |

146 | comparison. |

147 | |

148 | * This module does not work with tied or magical arrays or array |

149 | elements, and, in fact, will even crash when you use those. |

150 | |

151 | * This module can leak memory (or worse) when your comparison function |

152 | exits unexpectedly (e.g. "last") or throws an exception, so do not |

153 | do that. |

154 | |

155 | AUTHOR AND CONTACT INFORMATION |

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

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

158 |