Debian Codegraph @

texmf-dist/scripts/pedigree-perl/Pedigree/Area.pm

raw
1 =pod
2
3 =head1 NAME
4
5 Pedigree::Area - Calculate the area taken by a tree or a clump
6
7 =head1 SYNOPSIS
8
9 use Pedigree::Area;
10
11 $area = new Pedigree::Area($node);
12
13 $Ymin=$area->GetYmin();
14
15 $area->SetYmin($Ymin);
16
17 $Ymax=$area->GetYmax();
18
19 $area->SetYmax($Ymax);
20
21 $Xmin=$area->GetXmin($y);
22
23 $area->SetXmin($y,$x);
24
25 $Xmax=$area->GetXmax($y);
26
27 $area->SetXmax($y,$x);
28
29 $area->AddRight($otherarea);
30
31 $area->AddLeft($otherarea);
32
33 $rootnode=$area->GetRootNode();
34
35 $area->MoveLowerLayers($x);
36
37 =head1 DESCRIPTION
38
39 The algorithm of pedigree(1) uses the notion of area: a part of
40 a picture taken by a tree or a clump. This package implements this
41 notion.
42
43 Each Area has B<rootnode> - the reference node for all calculations.
44 All distances are calculated as relative to the coordinates of the
45 B<rootnode>.
46
47 The units are distances between the nodes in X and Y direction. The
48 Y axis is I<downward>: the earlier generations have smaller Y
49 coordinates.
50
51
52 =cut
53
54 ####################################################################
55 # Define the package #
56 ####################################################################
57
58 package Pedigree::Area;
59 use strict;
60
61
62 ####################################################################
63 # new #
64 ####################################################################
65
66 =pod
67
68 =over 4
69
70 =item B<new>(I<$rootnode>);
71
72 Construct a new area around the given rootnode
73
74 =cut
75
76 sub new {
77 my ($class, $node) = @_;
78 my $self={};
79 #
80 # Top and bottom in the Y direction
81 #
82 $self->{'Ymin'}=0;
83 $self->{'Ymax'}=0;
84 #
85 # Hashes of Xmin and Xmax
86 #
87 $self->{'Xmin'}->{0}=0;
88 $self->{'Xmax'}->{0}=0;
89 $self->{'RootNode'}=$node;
90 bless ($self, $class);
91 return $self;
92
93 }
94
95 ####################################################################
96 # GetYmin #
97 ####################################################################
98
99 =pod
100
101 =item B<GetYmin>();
102
103 Get the lower bound of the area.
104
105 =cut
106
107 sub GetYmin {
108 my $self = shift;
109 return $self->{'Ymin'};
110 }
111
112 ####################################################################
113 # SetYmin #
114 ####################################################################
115
116 =pod
117
118 =item B<SetYmin>(I<$y>);
119
120 Set the lower bound of the area.
121
122 =cut
123
124 sub SetYmin {
125 my $self = shift;
126 my $y=shift;
127 $self->{'Ymin'}=$y;
128 return $y;
129 }
130
131 ####################################################################
132 # GetYmax #
133 ####################################################################
134
135 =pod
136
137 =item B<GetYmax>();
138
139 Get the upper bound of the area.
140
141 =cut
142
143 sub GetYmax {
144 my $self = shift;
145 return $self->{'Ymax'};
146 }
147
148 ####################################################################
149 # SetYmax #
150 ####################################################################
151
152 =pod
153
154 =item B<SetYmax>(I<$y>);
155
156 Set the upper bound of the area.
157
158 =cut
159
160 sub SetYmax {
161 my $self = shift;
162 my $y=shift;
163 $self->{'Ymax'}=$y;
164 return $y;
165 }
166
167 ####################################################################
168 # GetXmin #
169 ####################################################################
170
171 =pod
172
173 =item B<GetXmin>(I<$y>);
174
175 Get the minimal X coordinate of the area on the level Y.
176
177 =cut
178
179 sub GetXmin {
180 my $self = shift;
181 my $y=shift;
182 return $self->{'Xmin'}->{$y};
183 }
184
185 ####################################################################
186 # SetXmin #
187 ####################################################################
188
189 =pod
190
191 =item B<SetXmin>(I<$y, $x>);
192
193 Set the minimal X coordinate of the area on the level Y.
194
195 =cut
196
197 sub SetXmin {
198 my $self = shift;
199 my $y=shift;
200 my $x=shift;
201 $self->{'Xmin'}->{$y}=$x;
202 return $x;
203 }
204
205 ####################################################################
206 # GetXmax #
207 ####################################################################
208
209 =pod
210
211 =item B<GetXmax>(I<$y>);
212
213 Get the maximal X coordinate of the area the the level Y.
214
215 =cut
216
217 sub GetXmax {
218 my $self = shift;
219 my $y=shift;
220 return $self->{'Xmax'}->{$y};
221 }
222
223 ####################################################################
224 # SetXmax #
225 ####################################################################
226
227 =pod
228
229 =item B<SetXmax>(I<$y, $x>);
230
231 Set the maximal X coordinate of the area the the level Y.
232
233 =cut
234
235 sub SetXmax {
236 my $self = shift;
237 my $y=shift;
238 my $x=shift;
239 $self->{'Xmax'}->{$y}=$x;
240 return $x;
241 }
242
243
244 ####################################################################
245 # AddRight #
246 ####################################################################
247
248 =pod
249
250 =item B<AddRight>(I<$otherarea>);
251
252 Add the new area I<$otherarea> to the given area at the right. The
253 "other area" should have a root node that is relative to our root
254 node. The relative Y of the other root node is used, the relative
255 X is set.
256
257 =cut
258
259 sub AddRight {
260 my ($self, $other) = @_;
261 my $deltaY = $other->GetRootNode()->GetRelY();
262
263 #
264 # First, we calculate the intersection of two areas
265 # It is between max(Y_{min,1}, Y_{min,2}+deltaY)
266 # and min(Y_{max,1}, Y_{max,2}+deltaY)
267 #
268 my $intMin=$self->GetYmin();
269 if ($other->GetYmin()+$deltaY > $intMin) {
270 $intMin = $other->GetYmin()+$deltaY;
271 }
272 my $intMax = $self->GetYmax();
273 if ($other->GetYmax()+$deltaY < $intMax) {
274 $intMax=$other->GetYmax()+$deltaY;
275 }
276
277 #
278 # Now we are ready to calculate relative X shift
279 #
280 my $deltaX=0;
281 for (my $y=$intMin; $y<=$intMax; $y++) {
282 my $x0 = $self->GetXmax($y);
283 my $x1 = $other->GetXmin($y-$deltaY);
284 if ($x1 + $deltaX - $x0 <1) {
285 $deltaX = 1 + $x0 - $x1;
286 }
287 }
288 #
289 # And set the relative X
290 #
291 $other->GetRootNode()->SetRelX($deltaX);
292
293 #
294 # Now we recalculate our area
295 #
296 for (my $y=$intMin; $y<=$intMax; $y++) {
297 $self->SetXmax($y, $other->GetXmax($y-$deltaY) + $deltaX);
298 }
299 if ($other->GetYmin()+$deltaY < $self->GetYmin()) {
300 for (my $y=$other->GetYmin()+$deltaY; $y<$self->GetYmin(); $y++) {
301 $self->SetXmin($y, $other->GetXmin($y-$deltaY)+$deltaX);
302 $self->SetXmax($y, $other->GetXmax($y-$deltaY)+$deltaX);
303 }
304 $self->SetYmin($other->GetYmin()+$deltaY);
305 }
306 if ($other->GetYmax()+$deltaY > $self->GetYmax()) {
307 for (my $y=$self->GetYmax()+1; $y<=$other->GetYmax()+$deltaY; $y++) {
308 $self->SetXmin($y, $other->GetXmin($y-$deltaY)+$deltaX);
309 $self->SetXmax($y, $other->GetXmax($y-$deltaY)+$deltaX);
310 }
311 $self->SetYmax($other->GetYmax()+$deltaY);
312 }
313 }
314
315 ####################################################################
316 # AddLeft #
317 ####################################################################
318
319 =pod
320
321 =item B<AddLeft>(I<$otherarea>);
322
323 Add the new area I<$otherarea> to the given area at the left. The
324 "other area" should have a root node that is relative to our root
325 node. The relative Y of the other root node is used, the relative
326 X is set.
327
328 =cut
329
330 sub AddLeft {
331 my ($self, $other) = @_;
332 my $deltaY = $other->GetRootNode()->GetRelY();
333
334 #
335 # First, we calculate the intersection of two areas
336 # It is between max(Y_{min,1}, Y_{min,2}+deltaY)
337 # and min(Y_{max,1}, Y_{max,2}+deltaY)
338 #
339 my $intMin=$self->GetYmin();
340 if ($other->GetYmin()+$deltaY > $intMin) {
341 $intMin = $other->GetYmin()+$deltaY;
342 }
343 my $intMax = $self->GetYmax();
344 if ($other->GetYmax()+$deltaY < $intMax) {
345 $intMax=$other->GetYmax()+$deltaY;
346 }
347
348 #
349 # Now we are ready to calculate relative X shift
350 #
351 my $deltaX=0;
352 for (my $y=$intMin; $y<=$intMax; $y++) {
353 my $x0 = $other->GetXmax($y-$deltaY);
354 my $x1 = $self->GetXmin($y);
355 if ($x1 + $deltaX - $x0 <1) {
356 $deltaX = 1 + $x0 - $x1;
357 }
358 }
359 #
360 # And set the relative X
361 #
362 $other->GetRootNode()->SetRelX(-$deltaX);
363
364 #
365 # Now we recalculate our area
366 #
367 for (my $y=$intMin; $y<=$intMax; $y++) {
368 $self->SetXmin($y, $other->GetXmin($y-$deltaY) - $deltaX);
369 }
370 if ($other->GetYmin()+$deltaY < $self->GetYmin()) {
371 for (my $y=$other->GetYmin()+$deltaY; $y<$self->GetYmin(); $y++) {
372 $self->SetXmin($y, $other->GetXmin($y-$deltaY)-$deltaX);
373 $self->SetXmax($y, $other->GetXmax($y-$deltaY)-$deltaX);
374 }
375 $self->SetYmin($other->GetYmin()+$deltaY);
376 }
377 if ($other->GetYmax()+$deltaY > $self->GetYmax()) {
378 for (my $y=$self->GetYmax()+1; $y<=$other->GetYmax()+$deltaY; $y++) {
379 $self->SetXmin($y, $other->GetXmin($y-$deltaY)-$deltaX);
380 $self->SetXmax($y, $other->GetXmax($y-$deltaY)-$deltaX);
381 }
382 $self->SetYmax($other->GetYmax()+$deltaY);
383 }
384 }
385
386 ####################################################################
387 # GetRootNode #
388 ####################################################################
389
390 =pod
391
392 =item B<GetRootNode>();
393
394 Return the root node of the area.
395
396 =cut
397
398 sub GetRootNode {
399 my $self = shift;
400 return $self->{'RootNode'};
401 }
402
403 ####################################################################
404 # MoveLowerLayers #
405 ####################################################################
406
407 =pod
408
409 =item B<MoveLowerLayers>(I<$x>);
410
411 Shift the lower layers (>0) of the area in the X direction by I<$x>
412
413 =cut
414
415 sub MoveLowerLayers {
416 my $self = shift;
417 my $x=shift;
418 for (my $y=-1; $y>=$self->GetYmin; $y--) {
419 $self->SetXmin($y, $self->GetXmin($y)+$x);
420 $self->SetXmax($y, $self->GetXmax($y)+$x);
421 }
422 return 0;
423 }
424
425
426
427 ####################################################################
428 # THE END #
429 ####################################################################
430
431
432 =pod
433
434 =back
435
436 =head1 ENVIRONMENT
437
438 The calling program should define B<$main::DEBUG> and set it to 0
439 or 1.
440
441 =head1 SEE ALSO
442
443 pedigree(1), Pedigree(3)
444
445 =head1 AUTHOR
446
447 Boris Veytsman, Leila Akhmadeeva, 2006, 2007
448
449
450
451 =cut
452
453 1;