]> scm.dxcluster.org Git - spider.git/blob - perl/Chain.pm
c065d17a62305b6c9fb224f0eb51a45b5ab34c1b
[spider.git] / perl / Chain.pm
1 package Chain;
2
3 use strict;
4 use Carp;
5
6 use vars qw($VERSION $BRANCH);
7 $VERSION = sprintf( "%d.%03d", q$Revision$ =~ /(\d+)\.(\d+)/ );
8 $BRANCH = sprintf( "%d.%03d", q$Revision$ =~ /\d+\.\d+\.(\d+)\.(\d+)/  || (0,0));
9 $main::build += $VERSION;
10 $main::branch += $BRANCH;
11
12 use constant NEXT => 0;
13 use constant PREV => 1;
14 use constant OBJ => 2;
15
16 use vars qw($docheck);
17
18 $docheck = 1;
19                         
20 sub _check
21 {
22         confess("chain broken $_[1]") unless ref $_[0] && $_[0]->isa('Chain') &&
23                 $_[0]->[PREV]->[NEXT] == $_[0] &&
24                         $_[0]->[NEXT]->[PREV] == $_[0];
25         return 1;
26 }
27
28 # set internal checking
29 sub setcheck
30 {
31         $docheck = shift;
32 }
33
34 # constructor                   
35 sub new
36 {
37         my $pkg = shift;
38         my $name = ref $pkg || $pkg;
39
40         my $self = [];
41         push @$self, $self, $self, @_;
42         return bless $self, $name;
43 }
44
45 # Insert before this point of the chain
46 sub ins
47 {
48         my ($p, $ref) = @_;
49         
50         $docheck && _check($p);
51         
52         my $q = ref $ref && $ref->isa('Chain') ? $ref : Chain->new($ref);
53         $q->[PREV] = $p->[PREV];
54         $q->[NEXT] = $p;
55         $p->[PREV]->[NEXT] = $q;
56         $p->[PREV] = $q;
57 }
58
59 # Insert after this point of the chain
60 sub add  
61 {
62         my ($p, $ref) = @_;
63         
64         $docheck && _check($p);
65         
66         $p->[NEXT]->ins($ref);
67 }
68
69 # Delete this item from the chain, returns the NEXT item in the chain
70 sub del
71 {
72         my $p = shift;
73         
74         $docheck && _check($p);
75         
76         my $q = $p->[PREV]->[NEXT] = $p->[NEXT];
77         $p->[NEXT]->[PREV] = $p->[PREV];
78         $p->[NEXT] = $p->[PREV] = undef;
79         return $q;
80 }
81
82 # Is this chain empty?
83 sub isempty
84 {
85         my $p = shift;
86         
87         $docheck && _check($p);
88         
89         return $p->[NEXT] == $p;
90 }
91
92 # return next item or undef if end of chain
93 sub next
94 {
95         my ($base, $p) = @_;
96         
97         $docheck && _check($base);
98         
99         return $base->[NEXT] == $base ? undef : $base->[NEXT] unless $p; 
100         
101         $docheck && _check($p);
102         
103         return $p->[NEXT] != $base ? $p->[NEXT] : undef; 
104 }
105
106 # return previous item or undef if end of chain
107 sub prev
108 {
109         my ($base, $p) = @_;
110         
111         $docheck && _check($base);
112         
113         return $base->[PREV] == $base ? undef : $base->[PREV] unless $p; 
114         
115         $docheck && _check($p);
116         
117         return $p->[PREV] != $base ? $p->[PREV] : undef; 
118 }
119
120 # return (and optionally replace) the object in this chain item
121 sub obj
122 {
123         my ($p, $ref) = @_;
124         $p->[OBJ] = $ref if $ref;
125         return $p->[OBJ];
126 }
127
128 # clear out the chain
129 sub flush
130 {
131         my $base = shift;
132         while (!$base->isempty) {
133                 $base->[NEXT]->del;
134         }
135 }
136
137 # move this item after the 'base' item
138 sub rechain
139 {
140         my ($base, $p) = @_;
141         
142         $docheck && _check($base, "base") && _check($p, "rechained ref");
143         
144         $p->del;
145         $base->add($p);
146 }
147
148 # count the no of items in a chain
149 sub count
150 {
151         my $base = shift;
152         my $count;
153         my $p;
154         
155         ++$count while ($p = $base->next($p));
156         return $count;
157 }
158
159 sub close
160 {
161         my $base = shift;
162         $base->flush;
163         $base->[PREV] = $base->[NEXT] = undef;
164 }
165
166 1;
167 __END__
168 # Below is the stub of documentation for your module. You better edit it!
169
170 =head1 NAME
171
172 Chain - Double linked circular chain handler
173
174 =head1 SYNOPSIS
175
176   use Chain;
177   $base = new Chain [$obj];
178   $p->ins($ref [,$obj]);
179   $p->add($ref [,$obj]);
180   $ref = $p->obj or $p->obj($ref);
181   $q = $base->next($p);
182   $q = $base->prev($p);
183   $base->isempty;                       
184   $q = $p->del;
185   $base->flush;
186   $base->rechain($p);                   
187   $base->count;
188
189   Chain::setcheck(0);
190
191 =head1 DESCRIPTION
192
193 A module to handle those nasty jobs where a perl list simply will
194 not do what is required.
195
196 This module is a transliteration from a C routine I wrote in 1987, which
197 in turn was taken directly from the doubly linked list handling in ICL
198 George 3 originally written in GIN5 circa 1970. 
199
200 The type of list this module manipulates is circularly doubly linked
201 with a base.  This means that you can traverse the list backwards or
202 forwards from any point.  
203
204 The particular quality that makes this sort of list useful is that you
205 can insert and delete items anywhere in the list without having to
206 worry about end effects. 
207
208 The list has a I<base> but it doesn't have any real end!  The I<base> is
209 really just another (invisible) list member that you choose to
210 remember the position of and is the reference point that determines
211 what is an I<end>.
212
213 There is nothing special about a I<base>. You can choose another member 
214 of the list to be a I<base> whenever you like.
215
216 The difference between this module and a normal list is that it allows
217 one to create persistant arbitrary directed graphs reasonably
218 efficiently that are easy to traverse, insert and delete objects. You
219 will never need to use I<splice>, I<grep> or I<map> again (for this
220 sort of thing).
221
222 A particular use of B<Chain> is for connection maps that come and go
223 during the course of execution of your program.
224
225 An artificial example of this is:-
226
227   use Chain;
228
229   my $base = new Chain;
230   $base->ins({call=>'GB7BAA', users => new Chain});
231   $base->ins({call=>'GB7DJK', users => new Chain});
232   $base->ins({call=>'GB7MRS', users => new Chain});
233
234   # order is now GB7BAA, GB7DJK, GB7MRS
235   
236   my $p;
237   while ($p = $base->next($p)) {
238     my $obj = $p->obj;
239     if ($obj->{call} eq 'GB7DJK') {
240       my $ubase = $obj->{users};
241       $ubase->ins( {call => 'G1TLH'} );
242       $ubase->ins( {call => 'G7BRN'} );
243     } elsif ($obj->{call} eq 'GB7MRS') {
244       my $ubase = $obj->{users};
245       $ubase->ins( {call => 'G4BAH'} );
246       $ubase->ins( {call => 'G4PIQ'} );
247     } elsif ($obj->{call} eq 'GB7BAA') {
248       my $ubase = $obj->{users};
249       $ubase->ins( {call => 'G8TIC'} );
250       $ubase->ins( {call => 'M0VHF'} );
251     }
252   }
253
254   # move the one on the end to the beginning (LRU on a stick :-).
255   $base->rechain($base->prev);
256
257   # order is now GB7MRS, GB7BAA, GB7DJK
258
259   # this is exactly equivalent to :
260   my $p = $base->prev;
261   $p->del;
262   $base->add($p);
263
264   # order is now GB7DJK, GB7MRS, GB7BAA
265
266   # disconnect (ie remove) GB7MRS
267   for ($p = 0; $p = $base->next($p); ) {
268     if ($p->obj->{call} eq 'GB7MRS') {
269       $p->del;                     # remove this 'branch' from the tree
270       $p->obj->{users}->flush;     # get rid of all its users
271       last;
272     }
273   }
274  
275   
276     
277 =head1 AUTHOR
278
279 Dirk Koopman <djk@tobit.co.uk>
280
281 =head1 SEE ALSO
282
283 ICL George 3 internals reference manual (a.k.a the source)
284
285 =cut