[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 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_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_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_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_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_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.

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
     Marc Lehmann <schmorp@schmorp.de>
     http://home.schmorp.de/

Revision:	1.2
Committed:	Sun Jul 26 05:25:18 2009 UTC (14 years, 9 months ago) by root
Branch:	MAIN
CVS Tags:	rel-2_0
Changes since 1.1:	+39 -6 lines
Log Message:	2.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.1	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
16			functions "push", "pop" etc.
17
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			make_heap_lex @heap (\@)
29			Just like "make_heap", but in string comparison order instead of
30			numerical comparison order.
31
32			make_heap_cmp { compare } @heap (&\@)
33			Just like "make_heap", but takes a custom comparison function.
34
35			push_heap @heap, $element, ... (\@@)
36			Adds the given element(s) to the heap.
37
38			push_heap_lex @heap, $element, ... (\@@)
39			Just like "push_heap", but in string comparison order instead of
40			numerical comparison order.
41
42			push_heap_cmp { compare } @heap, $element, ... (&\@@)
43			Just like "push_heap", but takes a custom comparison function.
44
45			pop_heap @heap (\@)
46			Removes the topmost (lowest) heap element and repairs the heap.
47
48			pop_heap_lex @heap (\@)
49			Just like "pop_heap", but in string comparison order instead of
50			numerical comparison order.
51
52			pop_heap_cmp { compare } @heap (&\@)
53			Just like "pop_heap", but takes a custom comparison function.
54
55	root	1.2	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
78	root	1.1	COMPARISON FUNCTIONS
79			All the functions come in two flavours: one that uses the built-in
80			comparison function and one that uses a custom comparison function.
81
82			The built-in comparison function can either compare scalar numerical
83			values (string values for *_lex functions), or array refs. If the
84			elements to compare are array refs, the first element of the array is
85			used for comparison, i.e.
86
87			1, 4, 6
88
89			will be sorted according to their numerical value,
90
91			[1 => $obj1], [2 => $obj2], [3 => $obj3]
92
93			will sort according to the first element of the arrays, i.e. "1,2,3".
94
95			The custom comparison functions work similar to how "sort" works: $a and
96			$b are set to the elements to be compared, and the result should be
97	root	1.2	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".
100	root	1.1
101			The first example above corresponds to this comparison "function":
102
103			{ $a <=> $b }
104
105			And the second example corresponds to this:
106
107			{ $a->[0] <=> $b->[0] }
108
109			Unlike "sort", the default sort is numerical and it is not possible to
110			use normal subroutines.
111
112			BUGS
113	root	1.2	* 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
118			* This module does not work with tied or magical arrays or array
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.
124	root	1.1
125			AUTHOR
126			Marc Lehmann <schmorp@schmorp.de>
127			http://home.schmorp.de/
128