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