blib/lib/Bio/Graphics/Layout.pm untested

filter: Statementstmt 0.0% 0 / 211 Branchbran 0.0% 0 / 56 Conditioncond 0.0% 0 / 26 MC/DCmcdc n/a Subroutinesub 0.0% 0 / 19 Podpod 0.0% 0 / 17 totaltotal 0.0% 0 / 329 CC 29 SCAR 34.0
CC
29
Cov
0%
addRect
56.0
unionWith
56.0
addExisting
42.0
CRAP 29.9
1 package Bio::Graphics::Layout;
2  
3 # shamelessly stolen from Mitch Skinner's JBrowse package and ported to perl.
4 # Original copyright here
5 #Copyright (c) 2007-2010 The Evolutionary Software Foundation
6 #
7 #Created by Mitchell Skinner <mitch_skinner@berkeley.edu>
8 #
9 #This package and its accompanying libraries are free software; you can
10 #redistribute it and/or modify it under the terms of the LGPL (either
11 #version 2.1, or at your option, any later version) or the Artistic
12 #License 2.0. Refer to LICENSE for the full license text.
13  
14 use strict;
15  
16 # /*
17 # * Code for laying out rectangles, given that layout is also happening
18 # * in adjacent blocks at the same time
19 # *
20 # * This code does a lot of linear searching; n should be low enough that
21 # * it's not a problem but if it turns out to be, some of it can be changed to
22 # * binary searching without too much work. Another possibility is to merge
23 # * contour spans and give up some packing closeness in exchange for speed
24 # * (the code already merges spans that have the same x-coord and are vertically
25 # * contiguous).
26 # */
27  
28 sub new {
29 my $class = shift;
30 my ($leftBound, $rightBound) = @_;
31 my $self = bless {},ref $class || $class;
32 $self->{leftBound} = $leftBound;
33 $self->{rightBound} = $rightBound;
34 # a Layout contains a left contour and a right contour;
35 # the area between the contours is allocated, and the
36 # area outside the contours is free.
37 $self->{leftContour} = Bio::Graphics::Layout::Contour->new();
38 $self->{rightContour} = Bio::Graphics::Layout::Contour->new();
39 $self->{seen} = {};
40 $self->{leftOverlaps} = [];
41 $self->{rightOverlaps} = [];
42 $self->{totalHeight} = 0;
43 return $self;
44 }
45  
46 sub totalHeight {shift->{totalHeight}}
47  
48 sub addRect {
49 my $self = shift;
50 my ($id,$left,$right,$height) = @_;
51  
52 if (defined $self->{seen}{$id}) {return $self->{seen}{$id}};
53
54 # for each contour, we test the fit on the near side of the given rect,
55 my $leftFit = $self->tryLeftFit($left, $right, $height, 0);
56 my $rightFit = $self->tryRightFit($left, $right, $height, 0);
57  
58 my $top;
59  
60 # and insert the far side from the side we tested
61 # (we want to make sure the near side fits, but we want to extend
62 # the contour to cover the far side)
63 if ($leftFit->{top} < $rightFit->{top}) {
64 $top = $leftFit->{top};
65 $self->{leftContour}->insertFit($leftFit->{fit}, $self->{rightBound} - $left,
66 $top, $height);
67 $self->{rightContour}->unionWith($right - $self->{leftBound}, $top, $height);
68 } else {
69 $top = $rightFit->{top};
70 $self->{rightContour}->insertFit($rightFit->{fit}, $right - $self->{leftBound},
71 $top, $height);
72 $self->{leftContour}->unionWith($self->{rightBound} - $left, $top, $height);
73 }
74  
75 my $existing = {id => $id,
76 left => $left,
77 right => $right,
78 top => $top,
79 height => $height};
80 $self->{seen}{$id} = $top;
81 if ($left <= $self->{leftBound}) {
82 push(@{$self->{leftOverlaps}},$existing);
83 if ($self->{leftLayout}) {
84 $self->{leftLayout}->addExisting($existing);
85 }
86 }
87 if ($right >= $self->{rightBound}) {
88 push(@{$self->{rightOverlaps}},$existing);
89 if ($self->{rightLayout}) {
90 $self->{rightLayout}->addExisting($existing);
91 }
92 }
93 $self->{seen}{$id} = $top;
94 $self->{totalHeight} = Bio::Graphics::Math::max($self->{totalHeight}, $top + $height);
95 return $top;
96 }
97  
98 # this method is called by the block to the left to see if a given fit works
99 # in this layout
100 # takes: proposed rectangle
101 # returns: {top: value that makes the rectangle fit in this layout,
102 # fit: "fit" for passing to insertFit}
103 sub tryLeftFit {
104 my $self = shift;
105 my ($left,$right,$height,$top) = @_;
106  
107 my ($fit, $nextFit);
108 my $curTop = $top;
109  
110 while (1) {
111 # check if the rectangle fits at curTop
112 $fit = $self->{leftContour}->getFit($self->{rightBound} - $right, $height, $curTop);
113 $curTop = Bio::Graphics::Math::max($self->{leftContour}->getNextTop($fit), $curTop);
114 # if the rectangle extends onto the next block to the right;
115 if ($self->{rightLayout} && ($right >= $self->{rightBound})) {
116 # check if the rectangle fits into that block at this position
117 $nextFit = $self->{rightLayout}->tryLeftFit($left, $right, $height, $curTop);
118 # if not, nextTop will be the next y-value where the rectangle
119 # fits into that block
120 if ($nextFit->{top} > $curTop) {
121 # in that case, try again to see if that y-value works
122 $curTop = $nextFit->{top};
123 next;
124 }
125 }
126 last;
127 }
128 return {top=> $curTop, fit=> $fit};
129 }
130  
131 # this method is called by the block to the right to see if a given fit works
132 # in this layout
133 # takes: proposed rectangle
134 # returns: {top: value that makes the rectangle fit in this layout,
135 # fit: "fit" for passing to insertFit}
136 sub tryRightFit {
137 my $self = shift;
138 my ($left,$right,$height,$top) = @_;
139
140 my ($fit, $nextFit);
141 my $curTop = $top;
142  
143 while (1) {
144 # check if the rectangle fits at curTop
145 $fit = $self->{rightContour}->getFit($left - $self->{leftBound}, $height, $curTop);
146 $curTop = Bio::Graphics::Math::max($self->{rightContour}->getNextTop($fit), $curTop);
147 # if the rectangle extends onto the next block to the left;
148 if ($self->{leftLayout} && ($left <= $self->{leftBound})) {
149 # check if the rectangle fits into that block at this position
150 $nextFit = $self->{leftLayout}->tryRightFit($left, $right, $height, $curTop);
151 # if not, nextTop will be the next y-value where the rectangle
152 # fits into that block
153 if ($nextFit->{top} > $curTop) {
154 # in that case, try again to see if that y-value works
155 $curTop = $nextFit->{top};
156 next;
157 }
158 }
159 last
160 }
161 return {top => $curTop, fit => $fit};
162 }
163  
164 sub hasSeen {
165 my $self = shift;
166 my $id = shift;
167 return defined $self->{seen}{$id};
168 }
169  
170 sub setLeftLayout {
171 my $self = shift;
172 my $left = shift;
173  
174 for (my $i = 0; $i < @{$self->{leftOverlaps}}; $i++) {
175 $left->addExisting($self->{leftOverlaps}[$i]);
176 }
177  
178 $self->{leftLayout} = $left;
179 };
180  
181 sub setRightLayout {
182 my $self = shift;
183 my $right = shift;
184  
185 for (my $i = 0; $i < @{$self->{rightOverlaps}}; $i++) {
186 $right->addExisting($self->{rightOverlaps}[$i]);
187 }
188 $self->{rightLayout} = $right;
189 };
190  
191 sub cleanup {
192 my $self = shift;
193 undef $self->{leftLayout};
194 undef $self->{rightLayout};
195 };
196  
197 # expects an {id, left, right, height, top} object
198 sub addExisting {
199 my $self = shift;
200 my $existing = shift;
201  
202 if (defined $self->{seen}[$existing->{id}]) {return};
203 $self->{seen}{$existing->{id}} = $existing->{top};
204  
205 $self->{totalHeight} =
206 Bio::Graphics::Math::max($self->{totalHeight}, $existing->{top} + $existing->{height});
207
208 if ($existing->{left} <= $self->{leftBound}) {
209 push(@{$self->{leftOverlaps}},$existing);
210 if ($self->{leftLayout}) {
211 $self->{leftLayout}->addExisting($existing);
212 }
213 }
214 if ($existing->{right} >= $self->{rightBound}) {
215 push(@{$self->{rightOverlaps}},$existing);
216 if ($self->{rightLayout}) {
217 $self->{rightLayout}->addExisting($existing);
218 }
219 }
220  
221 $self->{leftContour}->unionWith($self->{rightBound} - $existing->left,
222 $existing->{top},
223 $existing->{height});
224 $self->rightContour->unionWith($existing->{right} - $self->{leftBound},
225 $existing->{top},
226 $existing->{height});
227 }
228  
229 package Bio::Graphics::Layout::Contour;
230 use constant INF => 1<<16;
231  
232 sub new {
233 my $class = shift;
234 my $top = shift;
235  
236 # /*
237 # * A contour is described by a set of vertical lines of varying heights,
238 # * like this:
239 # * |
240 # * |
241 # * |
242 # * |
243 # * |
244 # * |
245 # *
246 # * The contour is the union of the rectangles ending on the right side
247 # * at those lines, and extending leftward toward negative infinity.
248 # *
249 # * <=======================|
250 # * <=======================|
251 # * <==========|
252 # * <=================|
253 # * <=================|
254 # * <=================|
255 # *
256 # * x -->
257 # *
258 # * As we add new vertical spans, the contour expands, either downward
259 # * or in the direction of increasing x.
260 # */
261 # // takes: top, a number indicating where the first span of the contour
262 # // will go
263  
264 $top ||= 0;
265  
266 # // spans is an array of {top, x, height} objects representing
267 # // the boundaries of the contour
268 # // they're always sorted by top
269 return bless {spans =>
270 [
271 {top=> $top,
272 x => INF,
273 height => 0}
274 ]
275 },ref $class || $class;
276 }
277  
278 sub spans {shift->{spans}}
279  
280 # // finds a space in the contour into which the given span fits
281 # // (i.e., the given span has higher x than the contour over its vertical span)
282 # // returns an ojbect {above, count}; above is the index of the last span above
283 # // where the given span will fit, count is the number of spans being
284 # // replaced by the given span
285 sub getFit {
286 my $self = shift;
287 my ($x,$height,$minTop) = @_;
288
289 my ($aboveBottom, $curSpan);
290 my $above = 0;
291 my $spans = $self->spans;
292  
293 if ($minTop) {
294 # set above = (index of the first span that starts below minTop)
295 for (; $spans->[$above]{top} < $minTop; $above++) {
296 if ($above >= (@$spans - 1)) {
297 return {above=> @$spans - 1, count=> 0};
298 }
299 }
300 }
301  
302 # slide down the contour
303 my $count;
304 ABOVE:
305 for (; $above < @$spans; $above++) {
306 $aboveBottom = $spans->[$above]{top} + $spans->[$above]{height};
307 for ($count = 1; $above + $count < @$spans; $count++) {
308 $curSpan = $spans->[$above + $count];
309 if (($aboveBottom + $height) <= $curSpan->{top}) {
310 # the given span fits between span[above] and
311 # curSpan, keeping curSpan
312 return {above=> $above, count=> $count - 1};
313 }
314 if ($curSpan->{x} > $x) {
315 # the span at [above + count] overlaps the given span,
316 # so we continue down the contour
317 next ABOVE;
318 }
319 if (($curSpan->{x} <= $x) &&
320 (($aboveBottom + $height) < ($curSpan->{top} + $curSpan->{height}))) {
321 # the given span partially covers curSpan, and
322 # will overlap it, so we keep curSpan
323 return {above=> $above, count=> $count - 1};
324 }
325 }
326 # the given span fits below span[above], replacing any
327 # lower spans in the contour
328 return {above=> $above, count => $count - 1};
329 }
330 # the given span fits at the end of the contour, replacing no spans
331 return {above => $above, count => 0};
332 }
333  
334 # add the given span to this contour where it fits, as given
335 # by getFit
336 sub insertFit {
337 my $self = shift;
338 my ($fit,$x,$top,$height) = @_;
339  
340 my $spans = $self->spans;
341  
342 # if the previous span and the current span have the same x-coord,
343 # and are vertically contiguous, merge them.
344 my $prevSpan = $spans->[$fit->{above}];
345 if ((abs($prevSpan->{x} - $x) < 1)
346 && (abs(($prevSpan->{top} + $prevSpan->{height}) - $top) < 1) ) {
347 $prevSpan->{height} = ($top + $height) - $prevSpan->{top};
348 # a bit of slop here is conservative if we take the max
349 # (means things might get laid out slightly farther apart
350 # than they would otherwise)
351 $prevSpan->{x} = Bio::Graphics::Math::max($prevSpan->{x}, $x);
352 splice(@$spans,$fit->{above} + 1, $fit->{count});
353 } else {
354 splice(@$spans,$fit->{above} + 1, $fit->{count},
355 {
356 top => $top,
357 x => $x,
358 height => $height
359 });
360 }
361 }
362  
363 # add the given span to this contour at the given location, if
364 # it would extend the contour
365 sub unionWith {
366 my $self = shift;
367 my ($x,$top,$height) = @_;
368
369 my ($startBottom, $startIndex, $endIndex, $startSpan, $endSpan);
370 my $bottom = $top + $height;
371 my $spans = $self->spans;
372  
373 START:
374 for ($startIndex = 0; $startIndex < @$spans; $startIndex++) {
375 $startSpan = $spans->[$startIndex];
376 $startBottom = $startSpan->{top} + $startSpan->{height};
377 if ($startSpan->{top} > $top) {
378 # the given span extends above an existing span
379 $endIndex = $startIndex;
380 last START;
381 }
382 if ($startBottom > $top) {
383 # if startSpan covers (at least some of) the given span,
384 if ($startSpan->{x} >= $x) {
385 my $covered = $startBottom - $top;
386 # we don't have to worry about the covered area any more
387 $top += $covered;
388 $height -= $covered;
389 # if we've eaten up the whole span, then it's submerged
390 # and we don't have to do anything
391 if ($top >= $bottom) { return };
392 next;
393 } else {
394 # find the first span not covered by the given span
395 for ($endIndex = $startIndex;
396 $endIndex < @$spans;
397 $endIndex++) {
398 $endSpan = $spans->[$endIndex];
399 # if endSpan extends below or to the right
400 # of the given span, then we need to keep it
401 if ((($endSpan->{top} + $endSpan->{height}) > $bottom)
402 || $endSpan->{x} > $x) {
403 last START;
404 }
405 }
406 last START;
407 }
408 }
409 }
410  
411 # if the previous span and the current span have the same x-coord,
412 # and are vertically contiguous, merge them.
413 my $prevSpan = $spans->[$startIndex - 1];
414 if ((abs($prevSpan->{x} - $x) < 1)
415 && (abs(($prevSpan->{top} + $prevSpan->{height}) - $top) < 1) ) {
416 $prevSpan->{height} = ($top + $height) - $prevSpan->{top};
417 $prevSpan->{x} = Bio::Graphics::Math::max($prevSpan->{x}, $x);
418 splice(@$spans,$startIndex, $endIndex - $startIndex);
419 } else {
420 splice(@$spans,$startIndex, $endIndex - $startIndex,
421 {
422 top => $top,
423 x => $x,
424 height => $height
425 });
426 }
427 }
428  
429 # returns the top of the to-be-added span that fits into "fit"
430 # (as returned by getFit)
431 sub getNextTop {
432 my $self = shift;
433 my $fit = shift;
434 return $self->spans->[$fit->{above}]{top} + $self->spans->[$fit->{above}]{height};
435 };
436  
437 package Bio::Graphics::Math;
438  
439 sub max {$_[0] > $_[1] ? $_[0] : $_[1]}
440  
441  
442  
443 1;