001: /*
002: * @(#)YXBandList.java 1.13 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package sun.porting.utils;
029:
030: /**
031: * Implementation of Y-X bounded rectangles. The band lists are
032: * circular and doubly-linked, with a dummy element separating the
033: * head from the tail; this makes insertion and deletion extremely cheap.
034: *
035: * @version 1.9, 08/19/02
036: * @author Richard Berlin
037: */
038: class YXBandList {
039: YXBand bandList;
040:
041: // static {
042: // Coverage.cover(17, "(removed)");
043: // }
044:
045: // static {
046: // mark these covered, (a) so that they don't show as gaps, and
047: // (b) so we get an error message if they ever get called.
048: // // Coverage.cover(44, "(error case)");
049: // // Coverage.cover(47, "(error case)");
050: // // Coverage.cover(132, "(error case)");
051: // // Coverage.cover(135, "(error case)");
052: // }
053:
054: public YXBandList() {
055: // // Coverage.cover(43, "YXBandList default constructor");
056: bandList = null;
057: }
058:
059: public YXBandList(int x, int y, int w, int h) {
060: // // Coverage.cover(44, "YXBandList(x,y,w,h)");
061: if ((w > 0) && (h > 0)) {
062: init(x, y, w, h);
063: }
064: }
065:
066: public void init(int x, int y, int w, int h) {
067: if ((w < 0) || (h < 0)) {
068: throw new IllegalArgumentException("Width or height is < 0");
069: }
070: // // Coverage.cover(45, "init(x,y,w,h)");
071: bandList = new YXBand(0, -1, null); // dummy element
072: if ((w > 0) && (h > 0)) {
073: bandList.next = new YXBand(x, y, w, h, bandList, bandList);
074: bandList.prev = bandList.next;
075: } else {
076: bandList.next = bandList.prev = bandList;
077: }
078: }
079:
080: /*
081: * Circular, doubly-linked lists are central to the implementation.
082: *
083: * The idiom for creating a new list is to start by building the
084: * following structure, in which a dummy element and the real
085: * first element have their prev and next pointers all pointing at
086: * each other. In this example we're making an initial X band
087: * which goes from 10 to 18. Dummy elements are usually set with
088: * their start as 0 and their span as negative.
089: *
090: * --------
091: * |x = 0 |
092: * head --->|w = -1 |
093: * |next = -+---+
094: * +---+- = prev| |
095: * | | | |
096: * | -------- |
097: * | ^ ^ |
098: * | | | |
099: * | +---+ +----+ |
100: * | | | |
101: * | | -------- | |
102: * | | |x = 10 | | |
103: * | | |w = 8 | | |
104: * | | |next = -+-+ |
105: * | +-+- = prev| |
106: * +-->| |<--+
107: * --------
108: *
109: * Once this structure is set up, appending to the list is a general
110: * and very simple insertion before the dummy head element and after
111: * the last real element. The code for appending a new element which
112: * extends from 21 to 24 is
113: *
114: * head.prev.next = head.prev = new XSpan(21, 3, head.prev, head);
115: *
116: * In the first stage of execution (calling the constructor)
117: * a new element is created and its links correctly set:
118: *
119: * --------
120: * |x = 0 |
121: * head --->|w = -1 |<--------------------+
122: * |next = -+---+ |
123: * +---+- = prev| | |
124: * | | | | |
125: * | -------- | |
126: * | ^ ^ | |
127: * | | | | |
128: * | +---+ +----+ | |
129: * | | | | |
130: * | | -------- | | -------- |
131: * | | |x = 10 | | | |x = 21 | |
132: * | | |w = 8 | | | |w = 3 | |
133: * | | |next = -+-+ | |next = -+--+
134: * | +-+- = prev| | +-+- = prev|
135: * +-->| |<--+ | | |
136: * -------- | --------
137: * ^ |
138: * +-------------+
139: *
140: * and in the second phase (the assigments) the pointers are adjusted:
141: *
142: * --------
143: * |x = 0 |
144: * head --->|w = -1 |<--------------------+
145: * +---+- = next| |
146: * | |prev = -+----------------+ |
147: * | | | | |
148: * | -------- | |
149: * | ^ | |
150: * | | | |
151: * | +---+ | |
152: * | | V |
153: * | | -------- -------- |
154: * | | |x = 10 | |x = 21 | |
155: * | | |w = 8 | |w = 3 | |
156: * | | |next = -+-------->|next = -+--+
157: * | +-+- = prev|<--------+- = prev|
158: * +-->| | | |
159: * -------- --------
160: *
161: * Analogous code will work for inserting between any two
162: * elements of the list. For example, to prepend a band
163: * running from 3 to 5 we insert after the head and before the
164: * first real element:
165: *
166: * head.next.prev = head.next = new XSpan(3, 2, head, head.next);
167: */
168:
169: /*
170: * Simple copy of the elements of a doubly-linked list.
171: */
172: protected void copyBands(YXBandList src) {
173: // // Coverage.cover(46, "copyBands(YXBandList)");
174: if (src.bandList == null) {
175: // // Coverage.cover(47, "source bandlist is null");
176: bandList = null;
177: return;
178: } else {
179: // // Coverage.cover(48, "create dummy head");
180: bandList = new YXBand(0, -1, null);
181: }
182: YXBand q = bandList; // dummy element
183: // // Coverage.cover(49, "Copy first element");
184: // copy first real element
185: YXBand p = src.bandList.next;
186: q.next = new YXBand(p.y, p.h, XSpan.copy(p.children), q, q);
187: q.prev = q.next;
188: // copy remainder of list
189: for (p = p.next; p != src.bandList; p = p.next) {
190: // // Coverage.cover(50, "Copy remainder");
191: q.prev = q.prev.next = new YXBand(p.y, p.h, XSpan
192: .copy(p.children), q.prev, q);
193: }
194: }
195:
196: public boolean isRectangle() {
197: if (bandList.next == bandList.prev) {
198: XSpan kids = bandList.next.children;
199: return (kids.next == kids.prev);
200: }
201: return false;
202: }
203:
204: /*
205: * Subtract a rectangle from a region. This is done in 3 stages:
206: * 1) If the first y band in the range overlaps the edge
207: * of the rectangle, and some of its x spans extend outside
208: * the rectangle, split the first band; if y overlaps but
209: * x does not, just shorten the band.
210: * 2) clear out the x range of any band wholly within the y range.
211: * if all spans are within the rectangle for a given band, delete
212: * the entire band.
213: * 3) If the last y band overlaps the edge, perform an operation
214: * analogous to step 1.
215: */
216: protected void subtract(int x, int y, int w, int h) {
217: if ((w < 0) || (h < 0)) {
218: throw new IllegalArgumentException("Width or height is < 0");
219: }
220: // // Coverage.cover(51, "subtract(x,y,w,h)");
221: int x2 = x + w;
222: int y2 = y + h;
223: YXBand yb = YXBand.findBand(y, y2, bandList);
224: if (yb == null) {
225: // // Coverage.cover(52, "no pertinent bands found");
226: return;
227: }
228: // yb now points to the first relevant band
229: if (yb.y < y) {
230: // // Coverage.cover(53, "yb < y");
231: int yEnd = yb.y + yb.h;
232: // first band crosses the rectangle--we may have to split bands
233: XSpan oldKids = yb.children;
234: XSpan newKids = XSpan.copyOutside(x, x2, yb.children);
235: if (newKids == null) {
236: // // Coverage.cover(54, "newKids == null (shorten band)");
237: // the newly split-off band would have no children, so
238: // we can just shorten this band
239: yb.h = y - yb.y;
240: if (yEnd <= y2) {
241: yb = yb.next;
242: }
243: } else {
244: // // Coverage.cover(55, "newKids != null (split band)");
245: // do the split.
246: // --create a new band from y..(yb.y + yb.h)
247: int newEnd = yEnd;
248: if (yEnd > y2) {
249: // // Coverage.cover(56, "decrease newEnd");
250: newEnd = y2;
251: }
252: yb.next = yb.next.prev = new YXBand(y, newEnd - y,
253: newKids, yb, yb.next);
254: yb.h = y - yb.y;
255: yb = yb.next;
256: }
257: if (yEnd > y2) {
258: // // Coverage.cover(57, "yEnd > y2");
259: yb.next = yb.next.prev = new YXBand(y2, yEnd - y2,
260: XSpan.copy(oldKids), yb, yb.next);
261: return;
262: }
263: }
264: while (yb != bandList) {
265: if (yb.y >= y2) {
266: // // Coverage.cover(58, "yb.y > y2 (exit)");
267: return;
268: }
269: int yEnd = yb.y + yb.h;
270: XSpan prev = yb.children.prev;
271: if ((yb.children.next.x >= x) && ((prev.x + prev.w) <= x2)) {
272: if (yEnd > y2) {
273: // // Coverage.cover(59, "yEnd > y2 (shorten last band)");
274: // we can just shorten the last band to y2..(yb.y + yb.h)
275: yb.y = y2;
276: yb.h = yEnd - y2;
277: return;
278: } else {
279: // // Coverage.cover(60, "delete last band");
280: // delete this band
281: yb.next.prev = yb.prev;
282: yb.prev.next = yb.next;
283: yb = yb.next;
284: }
285: } else {
286: if (yEnd > y2) {
287: // // Coverage.cover(61, "yEnd > y2 (split bands)");
288: // last band must be split
289: XSpan newKids = XSpan.copyOutside(x, x2,
290: yb.children);
291: if (newKids != null) {
292: yb.prev = yb.prev.next = new YXBand(yb.y, y2
293: - yb.y, newKids, yb.prev, yb);
294: }
295: yb.y = y2;
296: yb.h = yEnd - y2;
297: return;
298: } else {
299: // // Coverage.cover(62, "call deleteInside()");
300: XSpan.deleteInside(x, x2, yb.children);
301: yb = yb.next;
302: }
303: }
304: }
305: }
306:
307: /*
308: * Destructively intersect a rectangle from a region.
309: * This is done in several steps:
310: * 1) Delete y bands that end above the rectangle.
311: * 2) If the first y band in the range overlaps the edge
312: * of the rectangle, shorten it.
313: * 3) For each band, remove spans outside the rectangle. If this
314: * is all spans, delete the band.
315: * 4) If the last y band overlaps the edge, shorten it.
316: * 5) Delete bands that begin below the rectangle.
317: */
318: protected void intersect(int x, int y, int w, int h) {
319: if ((w < 0) || (h < 0)) {
320: throw new IllegalArgumentException("Width or height is < 0");
321: }
322: // // Coverage.cover(63, "intersect(x,y,w,h)");
323: int x2 = x + w;
324: int y2 = y + h;
325: YXBand yb = YXBand.findBand(y, y2, bandList);
326: if (yb == null) {
327: // // Coverage.cover(64, "no pertinent bands (null out list and return)");
328: bandList.next = bandList;
329: bandList.prev = bandList;
330: return;
331: }
332: // yb now points to the first relevant band
333: // delete anything in front of it
334: yb.prev = bandList;
335: bandList.next = yb;
336: // shorten the first band if necessary
337: int yEnd = yb.y + yb.h;
338: if (y2 < yEnd) {
339: // // Coverage.cover(65, "decrease yEnd");
340: yEnd = y2;
341: }
342: if (y > yb.y) {
343: // // Coverage.cover(66, "increase yb.y");
344: yb.y = y;
345: }
346: yb.h = yEnd - yb.y;
347: // trim the x spans of each relevant band
348: while ((yb != bandList) && (yb.y < y2)) {
349: XSpan prv = yb.children.prev;
350: if ((yb.children.next.x < x) || ((prv.x + prv.w) > x2)) {
351: // // Coverage.cover(67, "call deleteOutside()");
352: XSpan.deleteOutside(x, x2, yb.children);
353: if (yb.children.next == yb.children) {
354: // // Coverage.cover(68, "delete empty band");
355: // delete empty band
356: yb.prev.next = yb.next;
357: yb.next.prev = yb.prev;
358: }
359: }
360: yb = yb.next;
361: }
362: // yb points past the last relevant band; back it up one.
363: // then shorten the last band if necessary.
364: yb = yb.prev;
365: yEnd = y2 - yb.y;
366: if (yEnd < yb.h) {
367: // // Coverage.cover(69, "decrease yb.h");
368: yb.h = yEnd;
369: }
370: // Delete anything beyond the last relevant band.
371: yb.next = bandList;
372: bandList.prev = yb;
373: }
374:
375: /*
376: * Destructively union a rectangle into a region. This is a relatively
377: * simple operation requiring creation of new bands wherever a band does
378: * not exist in the range y..y+h. Where bands do exist, an XSpan must be
379: * merged in to cover the range x..x+w. Only two possible split bands are
380: * required: if the first overlapping band starts before y, and if the
381: * last overlapping band extends beyond y+h;
382: */
383: protected void union(int x, int y, int w, int h) {
384: if ((w < 0) || (h < 0)) {
385: throw new IllegalArgumentException("Width or height is < 0");
386: }
387: int yEnd = y + h;
388: // find first overlapping band
389: YXBand yb;
390: for (yb = bandList.next; yb != bandList; yb = yb.next) {
391: if ((yb.y + yb.h) > y) {
392: break;
393: }
394: }
395: if ((yb != bandList) && (y > yb.y)) {
396: // split bands, and operate (below) on the second one
397: // Coverage.cover(11, "split bands");
398: yb.next = yb.next.prev = new YXBand(y, yb.y + yb.h - y,
399: XSpan.copy(yb.children), yb, yb.next);
400: yb.h = y - yb.y;
401: yb = yb.next;
402: }
403: while ((yb != bandList) && (yb.y < yEnd)) {
404: if (yb.y > y) {
405: // Coverage.cover(12, "insert band");
406: // insert a band from x,y to x+h,yb.y
407: yb.prev = yb.prev.next = new YXBand(x, y, w, yb.y - y,
408: yb.prev, yb);
409: }
410: y = yb.y + yb.h;
411: if (y > yEnd) {
412: // Coverage.cover(13, "split again");
413: // split bands, and operate (below) on the first one
414: yb.next = yb.next.prev = new YXBand(yEnd, y - yEnd,
415: XSpan.copy(yb.children), yb, yb.next);
416: yb.h = yEnd - yb.y;
417: }
418: // now insert XSpan to cover x,yb.y to x+h,yb.y+yb.h
419: XSpan.cover(yb.children, x, w);
420: yb = yb.next;
421: }
422: ;
423: if (y < yEnd) {
424: // Coverage.cover(14, "handle last band");
425: // yb is the first band that comes after yEnd
426: // insert a band (in front) from x,y to x+h,yEnd
427: yb.prev = yb.prev.next = new YXBand(x, y, w, yEnd - y,
428: yb.prev, yb);
429: }
430: }
431:
432: /*
433: * Operations on a pair of regions are done by case analysis. There
434: * are eleven cases:
435: *
436: * 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
437: * A: -- -- --- ---- ----- -- --- ---- --- --- ---
438: * B: -- -- --- -- --- ---- --- --- --- ---- -----
439: *
440: * The first two cases (no overlap) are typically handled specially--
441: * bands are either skipped or deleted.
442: *
443: * Cases 3-5 are reduced to cases 6-8 by shortening or splitting bands.
444: * Case 8 is further reducible to case 7 and case 9 reducible to case
445: * 10 by shortening or splitting.
446: *
447: * For subtraction and intersection, the only difference in handling
448: * cases 6, 7, 10, 11 is whether band b has to be re-examined.
449: */
450:
451: /*
452: * destructively subtract two band structures
453: */
454: protected void subtract(YXBand l) {
455: // // Coverage.cover(70, "subtract(YXBand)");
456: YXBand a = bandList.next;
457: YXBand b = l.next;
458: while ((a != bandList) && (b != l)) {
459: int aEnd = a.y + a.h;
460: if (aEnd <= b.y) {
461: // // Coverage.cover(71, "no overlap (skip a)");
462: // no overlap -- skip
463: a = a.next;
464: continue;
465: }
466: int bEnd = b.y + b.h;
467: if (bEnd <= a.y) {
468: // // Coverage.cover(72, "no overlap (skip b)");
469: // no overlap -- skip
470: b = b.next;
471: continue;
472: }
473: if ((a.y == b.y) && (aEnd == bEnd)) {
474: // // Coverage.cover(73, "y bands are equal - subtract kids");
475: // special case this because it's so common
476: XSpan.subtract(a.children, b.children);
477: if (a.children.next == a.children) {
478: // // Coverage.cover(74, "delete empty band");
479: // band is empty--delete it
480: a.prev.next = a.next;
481: a.next.prev = a.prev;
482: }
483: a = a.next;
484: b = b.next;
485: continue;
486: }
487: XSpan newKids;
488: if (a.y < b.y) {
489: // // Coverage.cover(75, "a.y < b.y (trim and split bands)");
490: // keep the non-overlap area preceding the overlap
491: newKids = XSpan.copy(a.children);
492: a.next = a.next.prev = new YXBand(b.y, aEnd - b.y,
493: newKids, a, a.next);
494: a.h = b.y - a.y;
495: a = a.next;
496: }
497: if (aEnd > bEnd) {
498: // // Coverage.cover(76, "aEnd > bEnd (trim and split bands)");
499: // keep the non-overlap area following the overlap
500: newKids = XSpan.copy(a.children);
501: a.next = a.next.prev = new YXBand(bEnd, aEnd - bEnd,
502: newKids, a, a.next);
503: a.h = bEnd - a.y;
504: }
505: XSpan.subtract(a.children, b.children);
506: if (a.children.next == a.children) {
507: // // Coverage.cover(77, "delete empty band");
508: // band is empty--delete it
509: a.prev.next = a.next;
510: a.next.prev = a.prev;
511: }
512: a = a.next;
513: }
514: }
515:
516: /*
517: * destructively intersect two band structures
518: */
519: protected void intersect(YXBand l, int x1, int x2) {
520: // // Coverage.cover(78, "intersect(YXBand, x1, x2)");
521: YXBand a = bandList.next;
522: YXBand b = l.next;
523: while ((a != bandList) && (b != l)) {
524: int aEnd = a.y + a.h;
525: if (aEnd <= b.y) {
526: // // Coverage.cover(79, "no overlap (delete a)");
527: // no overlap -- delete
528: a.prev.next = a.next;
529: a.next.prev = a.prev;
530: a = a.next;
531: continue;
532: }
533: int bEnd = b.y + b.h;
534: if (bEnd <= a.y) {
535: // // Coverage.cover(80, "no overlap (skip b)");
536: // no overlap -- skip
537: b = b.next;
538: continue;
539: }
540: if (a.y <= b.y) {
541: // // Coverage.cover(81, "a.y <= b.y (trim band)");
542: // we're not interested in the non-overlap.
543: // begin by shortening the band.
544: a.y = b.y;
545: a.h = aEnd - a.y;
546: }
547: if (aEnd > bEnd) {
548: // // Coverage.cover(82, "aEnd > bEnd");
549: if ((b.next != l) && (b.next.y < aEnd)) {
550: // may need to split
551: XSpan newKids = XSpan
552: .copyInside(x1, x2, a.children);
553: if (newKids == null) {
554: // // Coverage.cover(83, "newKids == null (delete band)");
555: // we've discovered that this band can't contribute
556: // to overlap at all. Delete it and don't bother
557: // with the split.
558: a.prev.next = a.next;
559: a.next.prev = a.prev;
560: a = a.next;
561: b = b.next;
562: continue;
563: } else {
564: // // Coverage.cover(84, "split band");
565: a.next = a.next.prev = new YXBand(b.next.y,
566: aEnd - b.next.y, newKids, a, a.next);
567: }
568: }
569: // now shorten the band
570: a.h = bEnd - a.y;
571: }
572: // intersect the x spans
573: XSpan.intersect(a.children, b.children);
574: if (a.children.next == a.children) {
575: // // Coverage.cover(85, "delete empty band");
576: // band is empty--delete it
577: a.prev.next = a.next;
578: a.next.prev = a.prev;
579: }
580: a = a.next;
581: }
582: // delete any remaining a elements which don't overlap.
583: a.prev.next = bandList;
584: bandList.prev = a.prev;
585: }
586:
587: /*
588: * destructively union two band structures
589: */
590: protected void union(YXBand l) {
591: YXBand a = bandList.next;
592: YXBand b = l.next;
593: while ((a != bandList) && (b != l)) {
594: int aEnd = a.y + a.h;
595: if (aEnd <= b.y) {
596: // Coverage.cover(15, "no overlap -- skip");
597: // no overlap -- skip
598: a = a.next;
599: continue;
600: }
601: int bEnd = b.y + b.h;
602: if (bEnd <= a.y) {
603: // Coverage.cover(16, "no overlap -- insert part of b");
604: // no overlap -- simple insertion of (part of) b
605: int start = (a.prev == bandList) ? b.y
606: : (a.prev.y + a.prev.h);
607: if (b.y > start) {
608: start = b.y;
609: }
610: a.prev = a.prev.next = new YXBand(start, bEnd - start,
611: XSpan.copy(b.children), a.prev, a);
612: b = b.next;
613: continue;
614: }
615: if (b.y < a.y) {
616: // Coverage.cover(40, "add non-overlap which precedes overlap");
617:
618: int start = (a.prev == bandList) ? b.y
619: : (a.prev.y + a.prev.h);
620: if (b.y > start) {
621: start = b.y;
622: }
623: if (a.y > start) {
624: a.prev = a.prev.next = new YXBand(start, a.y
625: - start, XSpan.copy(b.children), a.prev, a);
626: }
627: }
628: if ((a.y < b.y) && (aEnd > b.y)) {
629: // Coverage.cover(18, "keep non-overlap which precedes overlap");
630: // keep the non-overlap area preceding the overlap
631: a.next = a.next.prev = new YXBand(b.y, aEnd - b.y,
632: XSpan.copy(a.children), a, a.next);
633: a.h = b.y - a.y;
634: a = a.next;
635: }
636: if (aEnd > bEnd) {
637: // Coverage.cover(19, "keep non-overlap which follows overlap");
638: // keep the non-overlap area following the overlap
639: a.next = a.next.prev = new YXBand(bEnd, aEnd - bEnd,
640: XSpan.copy(a.children), a, a.next);
641: a.h = bEnd - a.y;
642: }
643: XSpan.merge(a.children, b.children);
644: a = a.next;
645: if (aEnd >= bEnd) {
646: // Coverage.cover(20, "aEnd >= bEnd");
647: b = b.next;
648: }
649: }
650: if (b != l) {
651: int start = (a.prev == bandList) ? b.y
652: : (a.prev.y + a.prev.h);
653: if (b.y > start) {
654: start = b.y;
655: }
656: a.prev = a.prev.next = new YXBand(start, b.y + b.h - start,
657: XSpan.copy(b.children), a.prev, a);
658: b = b.next;
659: while (b != l) {
660: a.prev = a.prev.next = new YXBand(b.y, b.h, XSpan
661: .copy(b.children), a.prev, a);
662: b = b.next;
663: }
664: }
665: }
666:
667: /* Scan the band list. If two adjacent y bands have identical
668: * lists of children, coalesce the bands.
669: */
670: public void deFragment() {
671: // // Coverage.cover(86, "deFragment");
672: for (YXBand yb = bandList.next; yb != bandList.prev; yb = yb.next) {
673: while ((yb.h == 0) && (yb != bandList)) {
674: yb.prev.next = yb.next;
675: yb.next.prev = yb.prev;
676: yb = yb.next;
677: }
678: if ((yb.y + yb.h) != yb.next.y) {
679: // // Coverage.cover(87, "non-adjacent");
680: continue; // not adjacent
681: }
682: XSpan aHead = yb.children;
683: XSpan bHead = yb.next.children;
684: XSpan a = aHead.next;
685: XSpan b = bHead.next;
686: while ((a != aHead) && (b != bHead)) {
687: if ((a.x == b.x) && (a.w == b.w)) {
688: // // Coverage.cover(88, "spans are equal");
689: a = a.next;
690: b = b.next;
691: } else {
692: // // Coverage.cover(89, "spans not equal");
693: break;
694: }
695: }
696: if ((a == aHead) && (b == bHead)) {
697: // // Coverage.cover(90, "coalesce");
698: // children match--coalesce
699: yb.h += yb.next.h;
700: yb.next = yb.next.next;
701: yb.next.prev = yb;
702: yb = yb.prev;
703: }
704: }
705: }
706:
707: /*
708: * See if the rectangle x,y,w,h is all within the band structure.
709: */
710: protected boolean contains(int x, int y, int w, int h) {
711: if ((w < 0) || (h < 0)) {
712: throw new IllegalArgumentException("Width or height is < 0");
713: }
714: // // Coverage.cover(91, "contains(x,y,w,h)");
715: YXBand yb;
716: XSpan xs;
717: int x2 = x + w;
718: int y2 = y + h;
719: int xEnd, yEnd;
720: yb = YXBand.findBand(y, y2, bandList);
721: if (yb == null) {
722: // // Coverage.cover(92, "no relevant bands");
723: return false;
724: }
725: // before we loop, check first band
726: if (yb.y > y) {
727: // // Coverage.cover(93, "end uncovered");
728: return false; // end uncovered
729: }
730: // now scan all bands between y and y2, checking for
731: // discontiguity and making sure x range is covered
732: for (yEnd = yb.y; (yb != bandList) && (yEnd < y2); yb = yb.next) {
733: if (yb.y > yEnd) {
734: // // Coverage.cover(94, "y discontiguous");
735: return false; // discontigous
736: }
737: // before we loop, check last band
738: XSpan xHead = yb.children;
739: if ((xHead.prev.x + xHead.prev.w) < x2) {
740: // // Coverage.cover(95, "end uncovered");
741: return false; // end uncovered
742: }
743: // search for first overlapping band
744: for (xs = xHead.next; xs != xHead; xs = xs.next) {
745: if (xs.x > x) {
746: // // Coverage.cover(96, "end uncovered");
747: return false; // end uncovered
748: } else if (xs.x + xs.w > x) {
749: // // Coverage.cover(97, "found band");
750: break;
751: }
752: }
753: // now scan all bands between x and x2 for discontiguity
754:
755: // NOTE: we really should be able to dispense with this loop,
756: // because we coalesce XSpans at every step. Either there is
757: // a single XSpan which contains all of x..xEnd, or we can
758: // return false. But for now I'll let it stand because it's
759: // only a minor ineffeciency in practice.
760: for (xEnd = xs.x; (xs != xHead) && (xEnd < x2); xs = xs.next) {
761: if (xs.x > xEnd) {
762: // // Coverage.cover(98, "discontiguous");
763: return false; // discontiguous
764: }
765: xEnd = xs.x + xs.w;
766: }
767: // // Coverage.cover(99, "update yEnd");
768: yEnd = yb.y + yb.h;
769: }
770: return true;
771: }
772:
773: public boolean equals(YXBandList head) {
774: YXBand aBand = bandList.next;
775: YXBand bBand = head.bandList.next;
776: while ((aBand != bandList) || (bBand != head.bandList)) {
777: if ((aBand.y != bBand.y) || (aBand.h != bBand.h)) {
778: return false;
779: }
780: XSpan aHead = aBand.children;
781: XSpan bHead = bBand.children;
782: XSpan a = aHead.next;
783: XSpan b = bHead.next;
784: while ((a != aHead) || (b != bHead)) {
785: if ((a.x != b.x) || (a.w != b.w)) {
786: return false;
787: }
788: a = a.next;
789: b = b.next;
790: }
791: aBand = aBand.next;
792: bBand = bBand.next;
793: }
794: return true;
795: }
796:
797: /*
798: * find the smallest rectangle which contains the whole band structure.
799: */
800: public java.awt.Rectangle getBounds() {
801: // // Coverage.cover(100, "getBounds");
802: if ((bandList == null) || (bandList.next == bandList)) {
803: // // Coverage.cover(101, "null bandList");
804: bandList = null;
805: return new Rectangle();
806: }
807: XSpan firstX = bandList.next.children;
808: int x1 = firstX.next.x;
809: int x2 = firstX.prev.x + firstX.prev.w;
810: int tmp;
811: for (YXBand l = bandList.next.next; l != bandList; l = l.next) {
812: tmp = l.children.next.x;
813: if (x1 > tmp) {
814: // // Coverage.cover(102, "increase x1");
815: x1 = tmp;
816: }
817: XSpan lastX = l.children.prev;
818: tmp = lastX.x + lastX.w;
819: if (x2 < tmp) {
820: // // Coverage.cover(103, "decrease x2");
821: x2 = tmp;
822: }
823: // // Coverage.cover(104, "(spans examined)");
824:
825: }
826: YXBand prev = bandList.prev;
827: return new Rectangle(x1, bandList.next.y, x2 - x1, prev.y
828: + prev.h - bandList.next.y);
829: }
830:
831: /*
832: * translate all bands by dx, dy
833: */
834: protected void translate(int dx, int dy) {
835: // // Coverage.cover(105, "translate(dx,dy)");
836: for (YXBand yb = bandList.next; yb != bandList; yb = yb.next) {
837: yb.y += dy;
838: // // Coverage.cover(106, "bands processed");
839: XSpan xHead = yb.children;
840: for (XSpan xs = xHead.next; xs != xHead; xs = xs.next) {
841: // // Coverage.cover(107, "spans processed");
842: xs.x += dx;
843: }
844: }
845: }
846:
847: // no test coverage for toString
848: public String toString() {
849: return YXBand.makeString(bandList);
850: }
851: }
|