| 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; |