1package Heap::Elem; 2 3use strict; 4use vars qw($VERSION @ISA @EXPORT @EXPORT_OK); 5 6require Exporter; 7require AutoLoader; 8 9@ISA = qw(Exporter AutoLoader); 10 11# No names exported. 12# No names available for export. 13 14@EXPORT = ( ); 15 16$VERSION = '0.71'; 17 18 19# Preloaded methods go here. 20 21# new will usually be superceded by child, 22# but provide an empty hash as default and 23# accept any provided filling for it. 24sub new { 25 my $self = shift; 26 my $class = ref($self) || $self; 27 28 return bless { heap=>undef, @_ }, $class; 29} 30 31sub heap { 32 my $self = shift; 33 @_ ? ($self->{heap} = shift) : $self->{heap}; 34} 35 36sub cmp { 37 die "This cmp method must be superceded by one that knows how to compare elements." 38} 39 40# Autoload methods go after =cut, and are processed by the autosplit program. 41 421; 43__END__ 44# Below is the stub of documentation for your module. You better edit it! 45 46=head1 NAME 47 48Heap::Elem - Perl extension for elements to be put in Heaps 49 50=head1 SYNOPSIS 51 52 use Heap::Elem::SomeInheritor; 53 54 use Heap::SomeHeapClass; 55 56 $elem = Heap::Elem::SomeInheritor->new( $value ); 57 $heap = Heap::SomeHeapClass->new; 58 59 $heap->add($elem); 60 61=head1 DESCRIPTION 62 63This is an inheritable class for Heap Elements. It provides 64the interface documentation and some inheritable methods. 65Only a child classes can be used - this class is not complete. 66 67=head1 METHODS 68 69=over 4 70 71=item $elem = Heap::Elem::SomeInheritor->new( [args] ); 72 73Creates a new Elem. 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 $elem1->cmp($elem2) 100 101A routine to compare two elements. It must return a negative 102value if this element should go higher on the heap than I<$elem2>, 1030 if they are equal, or a positive value if this element should 104go lower on the heap than I<$elem2>. Just as with sort, the 105Perl operators <=> and cmp cause the smaller value to be returned 106first; similarly you can negate the meaning to reverse the order 107- causing the heap to always return the largest element instead 108of the smallest. 109 110=back 111 112=head1 INHERITING 113 114This class can be inherited to provide an oject with the 115ability to be heaped. If the object is implemented as 116a hash, and if it can deal with a key of I<heap>, leaving 117it unchanged for use by the heap routines, then the following 118implemetation will work. 119 120 package myObject; 121 122 require Exporter; 123 124 @ISA = qw(Heap::Elem); 125 126 sub new { 127 my $self = shift; 128 my $class = ref($self) || $self; 129 130 my $self = SUPER::new($class); 131 132 # set $self->{key} = $value; 133 } 134 135 sub cmp { 136 my $self = shift; 137 my $other = shift; 138 139 $self->{key} cmp $other->{key}; 140 } 141 142 # other methods for the rest of myObject's functionality 143 144=head1 AUTHOR 145 146John Macdonald, jmm@perlwolf.com 147 148=head1 COPYRIGHT 149 150Copyright 1998-2003, O'Reilly & Associates. 151 152This code is distributed under the same copyright terms as perl itself. 153 154=head1 SEE ALSO 155 156Heap(3), Heap::Elem::Num(3), Heap::Elem::NumRev(3), 157Heap::Elem::Str(3), Heap::Elem::StrRev(3). 158 159=cut 160