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