[ViewVC] Annotation of: cvs/Array-Heap/README

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

SYNOPSIS
     use Array::Heap;

DESCRIPTION
    There are a multitude of heap and heap-like modules on CPAN, you might
    want to search for /Heap/ and /Priority/ to find many. They implement
    more or less fancy datastructures that might well be what you are
    looking for.

    This module takes a different approach: It exports functions (i.e. no
    object orientation) that are loosely modeled after the C++ STL's binary
    heap functions. They all take an array as argument, just like perl's
    built-in functions "push", "pop" etc.

    The implementation itself is in C for maximum speed.

FUNCTIONS
    All of the following functions are being exported by default.

    make_heap @heap (\@)
        Reorders the elements in the array so they form a heap, with the
        lowest value "on top" of the heap (corresponding to the first array
        element).

    make_heap_idx @heap (\@)
        Just like "make_heap", but updates the index (see INDEXED
        OPERATIONS).

    make_heap_lex @heap (\@)
        Just like "make_heap", but in string comparison order instead of
        numerical comparison order.

    make_heap_cmp { compare } @heap (&\@)
        Just like "make_heap", but takes a custom comparison function.

    push_heap @heap, $element, ... (\@@)
        Adds the given element(s) to the heap.

    push_heap_idx @heap, $element, ... (\@@)
        Just like "push_heap", but updates the index (see INDEXED
        OPERATIONS).

    push_heap_lex @heap, $element, ... (\@@)
        Just like "push_heap", but in string comparison order instead of
        numerical comparison order.

    push_heap_cmp { compare } @heap, $element, ... (&\@@)
        Just like "push_heap", but takes a custom comparison function.

    pop_heap @heap (\@)
        Removes the topmost (lowest) heap element and repairs the heap.

    pop_heap_idx @heap (\@)
        Just like "pop_heap", but updates the index (see INDEXED
        OPERATIONS).

    pop_heap_lex @heap (\@)
        Just like "pop_heap", but in string comparison order instead of
        numerical comparison order.

    pop_heap_cmp { compare } @heap (&\@)
        Just like "pop_heap", but takes a custom comparison function.

    splice_heap @heap, $index (\@$)
        Similar to "pop_heap", but removes and returns the element at index
        $index.

    splice_heap_idx @heap, $index (\@$)
        Just like "splice_heap", but updates the index (see INDEXED
        OPERATIONS).

    splice_heap_lex @heap, $index (\@$)
        Just like "splice_heap", but in string comparison order instead of
        numerical comparison order.

    splice_heap_cmp { compare } @heap, $index (&\@$)
        Just like "splice_heap", but takes a custom comparison function.

    adjust_heap @heap, $index (\@$)
        Assuming you have only changed the element at index $index, repair
        the heap again. Can be used to remove elements, replace elements,
        adjust the priority of elements and more.

    adjust_heap_idx @heap, $index (\@$)
        Just like "adjust_heap", but updates the index (see INDEXED
        OPERATIONS).

    adjust_heap_lex @heap, $index (\@$)
        Just like "adjust_heap", but in string comparison order instead of
        numerical comparison order.

    adjust_heap_cmp { compare } @heap, $index (&\@$)
        Just like "adjust_heap", but takes a custom comparison function.

  COMPARISON FUNCTIONS
    All the functions come in two flavours: one that uses the built-in
    comparison function and one that uses a custom comparison function.

    The built-in comparison function can either compare scalar numerical
    values (string values for *_lex functions), or array refs. If the
    elements to compare are array refs, the first element of the array is
    used for comparison, i.e.

      1, 4, 6

    will be sorted according to their numerical value,

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

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

    The custom comparison functions work similar to how "sort" works: $a and
    $b are set to the elements to be compared, and the result should be
    greater than zero then $a is greater than $b, 0 otherwise. This means
    that you cna use the same function as for sorting the array, but you
    could also use a simpler function that just does "$a > $b".

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

      { $a <=> $b }

    And the second example corresponds to this:

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

    Unlike "sort", the default sort is numerical and it is not possible to
    use normal subroutines.

  INDEXED OPERATIONS
    The functions whose names end in "_idx" also "update the index". That
    means that all elements must be array refs, with the first element being
    the heap value, and the second value being the array index:

      [$value, $index, ...]

    This allows you to quickly locate an element in the array when all you
    have is the array reference.

BUGS
    *   Numerical comparison is always done using floatingpoint, which
        usually has less precision than a 64 bit integer that perl might use
        for integers internally, resulting in precision loss on the built-in
        comparison.

    *   This module does not work with tied or magical arrays or array
        elements, and, in fact, will even crash when you use those.

    *   This module can leak memory (or worse) when your comparison function
        exits unexpectedly (e.g. "last") or throws an exception, so do not
        do that.

AUTHOR AND CONTACT INFORMATION
     Marc Lehmann <schmorp@schmorp.de>
     http://software.schmorp.de/pkg/Array-Heap

Revision:	1.3
Committed:	Fri Apr 19 20:53:56 2013 UTC (11 years, 1 month ago) by root
Branch:	MAIN
CVS Tags:	rel-3_0
Changes since 1.2:	+35 -5 lines
Log Message:	3.0
#	User	Rev	Content
1	root	1.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	root	1.2	This module takes a different approach: It exports functions (i.e. no
14	root	1.3	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	root	1.1
18	root	1.2	The implementation itself is in C for maximum speed.
19	root	1.1
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	root	1.3	make_heap_idx @heap (\@)
29			Just like "make_heap", but updates the index (see INDEXED
30			OPERATIONS).
31
32	root	1.1	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	root	1.3	push_heap_idx @heap, $element, ... (\@@)
43			Just like "push_heap", but updates the index (see INDEXED
44			OPERATIONS).
45
46	root	1.1	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	root	1.3	pop_heap_idx @heap (\@)
57			Just like "pop_heap", but updates the index (see INDEXED
58			OPERATIONS).
59
60	root	1.1	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	root	1.2	splice_heap @heap, $index (\@$)
68			Similar to "pop_heap", but removes and returns the element at index
69			$index.
70
71	root	1.3	splice_heap_idx @heap, $index (\@$)
72			Just like "splice_heap", but updates the index (see INDEXED
73			OPERATIONS).
74
75	root	1.2	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	root	1.3	adjust_heap_idx @heap, $index (\@$)
88			Just like "adjust_heap", but updates the index (see INDEXED
89			OPERATIONS).
90
91	root	1.2	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	root	1.1	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	root	1.2	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	root	1.1
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	root	1.3	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	root	1.1	BUGS
143	root	1.2	* 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	root	1.1
155	root	1.3	AUTHOR AND CONTACT INFORMATION
156	root	1.1	Marc Lehmann <schmorp@schmorp.de>
157	root	1.3	http://software.schmorp.de/pkg/Array-Heap
158	root	1.1