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