Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | package Heap::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.70'; | |
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 |