1package Heap::Elem; 2 3use strict; 4use vars qw($VERSION); 5 6$VERSION = '0.80'; 7 8sub new { 9 my $class = shift; 10 $class = ref($class) || $class; 11 12 # value is undef, single scalar, or hash depending upon args 13 my $val = (@_ > 1) ? { @_ } 14 : @_ ? $_[0] 15 : undef; 16 17 # two slot array, 0 for the element's own value, 1 for use by Heap 18 my $self = [ $val, undef ]; 19 20 return bless $self, $class; 21} 22 23 24# get or set value slot 25sub val { 26 @_ > 1 ? ($_[0][0] = $_[1]) : $_[0][0]; 27} 28 29# get or set heap slot 30sub heap { 31 @_ > 1 ? ($_[0][1] = $_[1]) : $_[0][1]; 32} 33 34sub cmp { 35 die "This cmp method must be superceded by one that knows how to compare elements." 36} 37 381; 39__END__ 40 41=head1 NAME 42 43Heap::Elem - Base class for elements in a Heap 44 45=head1 SYNOPSIS 46 47 use Heap::Elem::SomeInheritor; 48 49 use Heap::SomeHeapClass; 50 51 $elem = Heap::Elem::SomeInheritor->new( $value ); 52 $heap = Heap::SomeHeapClass->new; 53 54 $heap->add($elem); 55 56=head1 DESCRIPTION 57 58This is an inheritable class for Heap Elements. It provides 59the interface documentation and some inheritable methods. 60Only a child classes can be used - this class is not complete. 61 62=head1 METHODS 63 64=over 4 65 66=item $elem = Heap::Elem::SomeInheritor->new( [args] ); 67 68Creates a new Elem. 69If there is exactly one arg, the Elem's value will be set 70to that value. 71If there is more than one arg provided, the Elem's value will be set 72to an anonymous hash initialized to the provided args (which must 73have an even number, of course). 74 75=item $elem->heap( $val ); $elem->heap; 76 77Provides a method for use by the Heap processing routines. 78If a value argument is provided, it will be saved. The 79new saved value is always returned. If no value argument 80is provided, the old saved value is returned. 81 82The Heap processing routines use this method to map an element 83into its internal structure. This is needed to support the 84Heap methods that affect elements that are not are the top 85of the heap - I<decrease_key> and I<delete>. 86 87The Heap processing routines will ensure that this value is 88undef when this elem is removed from a heap, and is not undef 89after it is inserted into a heap. This means that you can 90check whether an element is currently contained within a heap 91or not. (It cannot be used to determine which heap an element 92is contained in, if you have multiple heaps. Keeping that 93information accurate would make the operation of merging two 94heaps into a single one take longer - it would have to traverse 95all of the elements in the merged heap to update them; for 96Binomial and Fibonacci heaps that would turn an O(1) operation 97into an O(n) one.) 98 99=item $elem->val( $val ); $elem->val; 100 101Provides a method to get and/or set the value of the element. 102 103=item $elem1->cmp($elem2) 104 105A routine to compare two elements. It must return a negative 106value if this element should go higher on the heap than I<$elem2>, 1070 if they are equal, or a positive value if this element should 108go lower on the heap than I<$elem2>. Just as with sort, the 109Perl operators <=> and cmp cause the smaller value to be returned 110first; similarly you can negate the meaning to reverse the order 111- causing the heap to always return the largest element instead 112of the smallest. 113 114=back 115 116=head1 INHERITING 117 118This class can be inherited to provide an object with the 119ability to be heaped. If the object is implemented as 120a hash, and if it can deal with a key of I<heap>, leaving 121it unchanged for use by the heap routines, then the following 122implemetation will work. 123 124 package myObject; 125 126 require Exporter; 127 128 @ISA = qw(Heap::Elem); 129 130 sub new { 131 my $self = shift; 132 my $class = ref($self) || $self; 133 134 my $self = SUPER::new($class); 135 136 # set $self->{key} = $value; 137 } 138 139 sub cmp { 140 my $self = shift; 141 my $other = shift; 142 143 $self->{key} cmp $other->{key}; 144 } 145 146 # other methods for the rest of myObject's functionality 147 148=head1 AUTHOR 149 150John Macdonald, john@perlwolf.com 151 152=head1 COPYRIGHT 153 154Copyright 1998-2007, O'Reilly & Associates. 155 156This code is distributed under the same copyright terms as perl itself. 157 158=head1 SEE ALSO 159 160Heap(3), Heap::Elem::Num(3), Heap::Elem::NumRev(3), 161Heap::Elem::Str(3), Heap::Elem::StrRev(3). 162 163=cut 164