perllib/Heap071/Elem.pm

   1 package Heap071::Elem;
   2
   3 use strict;
   4 use vars qw($VERSION @ISA @EXPORT @EXPORT_OK);
   5
   6 require Exporter;
   7 require 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.
  24 sub new {
  25     my $self = shift;
  26     my $class = ref($self) || $self;
  27
  28     return bless { heap=>undef, @_ }, $class;
  29 }
  30
  31 sub heap {
  32     my $self = shift;
  33     @_ ? ($self->{heap} = shift) : $self->{heap};
  34 }
  35
  36 sub 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
  42 1;
  43 __END__
  44 # Below is the stub of documentation for your module. You better edit it!
  45
  46 =head1 NAME
  47
  48 Heap::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
  63 This is an inheritable class for Heap Elements.  It provides
  64 the interface documentation and some inheritable methods.
  65 Only 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
  73 Creates a new Elem.
  74
  75 =item $elem->heap( $val ); $elem->heap;
  76
  77 Provides a method for use by the Heap processing routines.
  78 If a value argument is provided, it will be saved.  The
  79 new saved value is always returned.  If no value argument
  80 is provided, the old saved value is returned.
  81
  82 The Heap processing routines use this method to map an element
  83 into its internal structure.  This is needed to support the
  84 Heap methods that affect elements that are not are the top
  85 of the heap - I<decrease_key> and I<delete>.
  86
  87 The Heap processing routines will ensure that this value is
  88 undef when this elem is removed from a heap, and is not undef
  89 after it is inserted into a heap.  This means that you can
  90 check whether an element is currently contained within a heap
  91 or not.  (It cannot be used to determine which heap an element
  92 is contained in, if you have multiple heaps.  Keeping that
  93 information accurate would make the operation of merging two
  94 heaps into a single one take longer - it would have to traverse
  95 all of the elements in the merged heap to update them; for
  96 Binomial and Fibonacci heaps that would turn an O(1) operation
  97 into an O(n) one.)
  98
  99 =item $elem1->cmp($elem2)
 100
 101 A routine to compare two elements.  It must return a negative
 102 value if this element should go higher on the heap than I<$elem2>,
 103 0 if they are equal, or a positive value if this element should
 104 go lower on the heap than I<$elem2>.  Just as with sort, the
 105 Perl operators <=> and cmp cause the smaller value to be returned
 106 first; similarly you can negate the meaning to reverse the order
 107 - causing the heap to always return the largest element instead
 108 of the smallest.
 109
 110 =back
 111
 112 =head1 INHERITING
 113
 114 This class can be inherited to provide an oject with the
 115 ability to be heaped.  If the object is implemented as
 116 a hash, and if it can deal with a key of I<heap>, leaving
 117 it unchanged for use by the heap routines, then the following
 118 implemetation 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
 146 John Macdonald, jmm@perlwolf.com
 147
 148 =head1 COPYRIGHT
 149
 150 Copyright 1998-2003, O'Reilly & Associates.
 151
 152 This code is distributed under the same copyright terms as perl itself.
 153
 154 =head1 SEE ALSO
 155
 156 Heap(3), Heap::Elem::Num(3), Heap::Elem::NumRev(3),
 157 Heap::Elem::Str(3), Heap::Elem::StrRev(3).
 158
 159 =cut