001: /*
002: * @(#)XSpan.java 1.11 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: * A class which stores an X span.
032: *
033: * @version 1.6, 08/19/02
034: */
035: class XSpan {
036: int x, w;
037: XSpan next, prev;
038:
039: public XSpan(int x, int w) {
040: // // Coverage.cover(114, "XSpan(x,w)");
041: this .x = x;
042: this .w = w;
043: }
044:
045: public XSpan(int x, int w, XSpan prev, XSpan next) {
046: // // Coverage.cover(115, "XSpan(x,w,prev,next)");
047: this .x = x;
048: this .w = w;
049: this .prev = prev;
050: this .next = next;
051: }
052:
053: /*
054: static void validateList(String msg, XSpan head) {
055: for (XSpan p = head.next; p != head.prev; p = p.next) {
056: if ((p.x + p.w) >= p.next.x) {
057: System.err.println(msg + ": Bands are out of order??");
058: System.err.println(" " +p.next+ " is after " +p);
059: System.err.println("Whole span list: ");
060: p = head.next;
061: while (p != head) {
062: System.err.println(" " +p);
063: p = p.next;
064: }
065: throw new RuntimeException("invalid XSpans");
066: }
067: }
068: }
069: */
070:
071: /*
072: * Destructively add a span between x and x+w. This
073: * replaces (or is merged with) any spans currently in
074: * that region.
075: */
076: static void cover(XSpan head, int x, int w) {
077: // validateList("+cover",head);
078:
079: XSpan x1, x2;
080: int xEnd = x + w;
081: // one simple, special case, because append is not uncommon
082: int endOfBand = head.prev.x + head.prev.w;
083: if (x >= endOfBand) {
084: // Coverage.cover(21, "x >= endOfBand");
085: if (x == endOfBand) {
086: // Coverage.cover(22, "x == endOfBand");
087: head.prev.w += w;
088: } else {
089: // Coverage.cover(23, "x != endOfBand");
090: head.prev = head.prev.next = new XSpan(x, w, head.prev,
091: head);
092: }
093: return;
094: }
095: // find first overlapping span
096: for (x1 = head.next; x1 != head; x1 = x1.next) {
097: if ((x1.x + x1.w) >= x) {
098: break;
099: }
100: }
101: if ((x1 != head) && (x1.x < x)) {
102: // Coverage.cover(24, "x1.x < x");
103: x = x1.x;
104: }
105: // and last overlapping span
106: if (x1 == head) {
107: // Coverage.cover(25, "x1 == head");
108: x2 = x1.prev;
109: } else {
110: // Coverage.cover(26, "scan for x2");
111: for (x2 = x1; x2.next != head; x2 = x2.next) {
112: if ((x2.x + x2.w) >= xEnd) {
113: break;
114: }
115: }
116: }
117: if (x2.x > xEnd) {
118: // Coverage.cover(27, "x2.x > xEnd");
119: x2 = x2.prev;
120: }
121: if ((x2.x + x2.w) > xEnd) {
122: // Coverage.cover(28, "(x2.x + x2.w) > xEnd");
123: xEnd = x2.x + x2.w;
124: }
125: x2.next.prev = x1.prev.next = new XSpan(x, xEnd - x, x1.prev,
126: x2.next);
127: // validateList("-cover", head);
128: }
129:
130: /*
131: * Utility function which destructively deletes from the
132: * list any span that is inside x..x2
133: */
134: static void deleteInside(int x, int x2, XSpan head) {
135: // validateList("+deleteInside", head);
136: // // Coverage.cover(116, "deleteInside(x,x2,head)");
137: XSpan xs;
138: for (xs = head.next; xs != head; xs = xs.next) {
139: if (xs.x >= x2) {
140: // // Coverage.cover(117, "no spans in range");
141: return;
142: } else if ((xs.x + xs.w) > x) {
143: // // Coverage.cover(118, "found span");
144: break;
145: }
146: }
147: if (xs == head) {
148: // // Coverage.cover(119, "ran off end");
149: return;
150: }
151: while (xs != head) {
152: int xEnd = (xs.x + xs.w);
153: if (xs.x < x) {
154: // // Coverage.cover(120, "shorten band");
155: // shorten band
156: xs.w = x - xs.x;
157: if (xEnd > x2) {
158: // split
159: // // Coverage.cover(121, "xEnd > x2 (split)");
160: xs.next = xs.next.prev = new XSpan(x2, xEnd - x2,
161: xs, xs.next);
162: }
163: } else if (xs.x >= x2) {
164: // // Coverage.cover(122, "out of range (return)");
165: return;
166: } else if (xEnd > x2) {
167: // // Coverage.cover(123, "xEnd > x2 (shorten)");
168: // shorten band
169: xs.x = x2;
170: xs.w = xEnd - x2;
171: return;
172: } else {
173: // // Coverage.cover(124, "delete band");
174: xs.prev.next = xs.next;
175: xs.next.prev = xs.prev;
176: }
177: // // Coverage.cover(125, "band advanced");
178: xs = xs.next;
179: }
180: // validateList("-deleteInside", head);
181: }
182:
183: /*
184: * Utility function which destructively deletes from the
185: * list any span that is outside x..x2
186: */
187: static void deleteOutside(int x, int x2, XSpan head) {
188: // validateList("+deleteOutside", head);
189: // // Coverage.cover(126, "deleteOutside(x,x2,head)");
190: XSpan xs = head.next;
191: while ((xs != head) && ((xs.x + xs.w) <= x)) {
192: // // Coverage.cover(127, "scan forwards");
193: xs = xs.next;
194: }
195: if (xs.x < x) {
196: // // Coverage.cover(128, "shorten first band");
197: xs.w = xs.x + xs.w - x;
198: xs.x = x;
199: }
200: xs.prev = head;
201: head.next = xs;
202: xs = head.prev;
203: while ((xs != head) && (xs.x > x2)) {
204: // // Coverage.cover(129, "scan backwards");
205: xs = xs.prev;
206: }
207: if ((xs.x + xs.w) > x2) {
208: // // Coverage.cover(130, "shorten last band");
209: xs.w = x2 - xs.x;
210: if (xs.w <= 0) {
211: // // Coverage.cover(183,"Delete band that was shortened to 0");
212: xs.prev.next = xs.next;
213: xs.next.prev = xs.prev;
214: }
215: }
216: xs.next = head;
217: head.prev = xs;
218: // validateList("-deleteOutside", head);
219: }
220:
221: /*
222: * Copy a list of spans
223: */
224: static XSpan copy(XSpan head) {
225: // validateList("+copy", head);
226: // // Coverage.cover(131, "copy(XSpan)");
227: if (head == null) {
228: throw new RuntimeException("copy: head == null");
229: // // Coverage.cover(132, "head == null");
230: // return null;
231: }
232: // create dummy list head
233: XSpan q = new XSpan(0, -1);
234: // copy first real element
235: XSpan p = head.next;
236: q.next = new XSpan(p.x, p.w, q, q);
237: q.prev = q.next;
238: // copy remainder of list
239: for (p = p.next; p != head; p = p.next) {
240: // // Coverage.cover(133, "scan list");
241: q.prev = q.prev.next = new XSpan(p.x, p.w, q.prev, q);
242: }
243: // validateList("-copy", q);
244: return q;
245: }
246:
247: /*
248: * make a copy of spans, only considering those inside x..x2
249: */
250: static XSpan copyInside(int x, int x2, XSpan head) {
251: // validateList("+copyInside", head);
252: // // Coverage.cover(134, "copyInside(x,x2,head)");
253:
254: if (head == null) {
255: // // Coverage.cover(135, "head == null");
256: return null;
257: }
258: XSpan xs = head.next;
259: XSpan last = head.prev;
260: int start = xs.x;
261: int end = (last.x + last.w);
262: if ((end <= x) || (start >= x2)) {
263: // // Coverage.cover(136, "everything to one side or other");
264: // everything is to one side or the other
265: return null;
266: } else if ((start >= x) && (end <= x2)) {
267: // // Coverage.cover(137, "all inside");
268: // save some overhead -- they're all inside!
269: return XSpan.copy(head);
270: }
271: // find the last child that could be in the region
272: for (; last != head; last = last.prev) {
273: // // Coverage.cover(138, "scan list");
274: if (last.x < x2) {
275: // // Coverage.cover(139, "found one");
276: break;
277: }
278: }
279: // if the last candidate is left of x, there are none.
280: if ((last.x + last.w) <= x) {
281: // // Coverage.cover(140, "last candidate is left of x");
282: return null;
283: }
284: // now search forward for the first span in x..x2
285: for (; xs != last; xs = xs.next) {
286: // // Coverage.cover(141, "scan list");
287: if ((xs.x + xs.w) > x) {
288: // // Coverage.cover(142, "found one");
289: break;
290: }
291: }
292: // special case code to build the list head
293: int newX = xs.x;
294: if (x > newX) {
295: // // Coverage.cover(143, "increase newX");
296: newX = x;
297: }
298: int xEnd = xs.x + xs.w;
299: if (x2 < xEnd) {
300: // // Coverage.cover(144, "decrease xEnd");
301: xEnd = x2;
302: }
303: XSpan newHead = new XSpan(0, -1);
304: newHead.next = new XSpan(newX, xEnd - newX, newHead, newHead);
305: newHead.prev = newHead.next;
306: if (xs == last) {
307: // // Coverage.cover(145, "only one span");
308: // there was only one span in x..x2
309: return newHead;
310: }
311: xs = xs.next;
312: while (xs != last) {
313: // // Coverage.cover(146, "scan list");
314: newHead.prev = newHead.prev.next = new XSpan(xs.x, xs.w,
315: newHead.prev, newHead);
316: xs = xs.next;
317: }
318: if ((xs.x + xs.w) > x2) {
319: // // Coverage.cover(147, "xs.x + xs.w > x2 (add new span)");
320: newHead.prev = newHead.prev.next = new XSpan(xs.x, x2
321: - xs.x, newHead.prev, newHead);
322: } else {
323: // // Coverage.cover(148, "xs.x + xs.w <= x2 (add new span)");
324: newHead.prev = newHead.prev.next = new XSpan(xs.x, xs.w,
325: newHead.prev, newHead);
326: }
327: // validateList("-copyInside", newHead);
328: return newHead;
329: }
330:
331: /*
332: * make a copy of spans, only considering those outside x..x2
333: */
334: static XSpan copyOutside(int x, int x2, XSpan head) {
335: // validateList("+copyOutside", head);
336:
337: // // Coverage.cover(149, "copyOutside(x,x2,head)");
338: // don't bother if all spans are inside x..x2
339: if ((head == null)
340: || ((head.next.x >= x) && ((head.prev.x + head.prev.w) <= x2))) {
341: // // Coverage.cover(150, "all inside");
342: return null;
343: }
344: // search for the first child that is outside x..x2
345: // (this is in case they're all on the x2 side)
346: XSpan xs = head.next;
347: if (xs.x >= x) {
348: // // Coverage.cover(151, "xs.x >= x");
349: while ((xs.next != head) && ((xs.x + xs.w) <= x2)) {
350: // // Coverage.cover(152, "scan list");
351: xs = xs.next;
352: }
353: }
354: // now set up the list
355: XSpan newHead = new XSpan(0, -1);
356: int xEnd = xs.x + xs.w;
357: if (xEnd > x) {
358: if (xs.x < x) {
359: // // Coverage.cover(153, "xEnd > x && xs.x < x");
360: newHead.next = new XSpan(xs.x, x - xs.x, newHead,
361: newHead);
362: } else if ((xs.x < x2) && (xEnd > x2)) {
363: // // Coverage.cover(154, "xEnd > x2 && xs.x < x2");
364: newHead.next = new XSpan(x2, xEnd - x2, newHead,
365: newHead);
366: } else {
367: // xs.x must be >= x2
368: // // Coverage.cover(155, "copy span verbatim");
369: newHead.next = new XSpan(xs.x, xs.w, newHead, newHead);
370: }
371: } else {
372: // // Coverage.cover(156, "xEnd <= x");
373: newHead.next = new XSpan(xs.x, xs.w, newHead, newHead);
374: }
375: newHead.prev = newHead.next;
376: if ((newHead.prev.x >= x2) && (xs.next == head)) {
377: // // Coverage.cover(157, "only one element?");
378: return newHead;
379: }
380: if ((xs.x < x) && (xEnd > x2)) {
381: // // Coverage.cover(158, "one element splits x..x2");
382: // it covers all of x..x2
383: newHead.prev = newHead.prev.next = new XSpan(x2, xEnd - x2,
384: newHead.prev, newHead);
385: }
386: if (xs.x < x) {
387: // // Coverage.cover(159, "xs.x < x");
388: for (xs = xs.next; xs != head; xs = xs.next) {
389: if (xs.x >= x) {
390: // // Coverage.cover(160, "xs.x >= x");
391: break;
392: } else if ((xs.x + xs.w) > x) {
393: // // Coverage.cover(161, "xs.x + xs.w > x");
394: newHead.prev = newHead.prev.next = new XSpan(xs.x,
395: x - xs.x, newHead.prev, newHead);
396: break;
397: } else {
398: // // Coverage.cover(162, "default case");
399: newHead.prev = newHead.prev.next = new XSpan(xs.x,
400: xs.w, newHead.prev, newHead);
401: }
402: }
403: } else if (newHead.prev.x >= x2) {
404: xs = xs.next;
405: }
406: // skip over children that are inside x..x2
407: for (; xs != head; xs = xs.next) {
408: // // Coverage.cover(163, "skip ");
409: if ((xs.x + xs.w) > x2) {
410: // // Coverage.cover(164, "found one that crosses x2");
411: break;
412: }
413: }
414: if ((xs != head) && (xs.x < x2)) {
415: // // Coverage.cover(165, "insert new span");
416: newHead.prev = newHead.prev.next = new XSpan(x2, xs.x
417: + xs.w - x2, newHead.prev, newHead);
418: xs = xs.next;
419: }
420: for (; xs != head; xs = xs.next) {
421: // // Coverage.cover(166, "copy end of list");
422: newHead.prev = newHead.prev.next = new XSpan(xs.x, xs.w,
423: newHead.prev, newHead);
424: }
425: // validateList("-copyOutside("+x+", "+x2+")", newHead);
426: return newHead;
427: }
428:
429: /*
430: * Utility function to subtract span lists. Case analysis is
431: * identical to intersection of YX lists, but simpler as there
432: * are no children and no need to split spans.
433: */
434: static void subtract(XSpan headA, XSpan headB) {
435: // validateList("+subtract", headA);
436: // validateList("+subtract", headB);
437: // // Coverage.cover(167, "subtract(XSpan, XSpan)");
438: XSpan a = headA.next;
439: XSpan b = headB.next;
440: while ((a != headA) && (b != headB)) {
441: if ((a.x == b.x) && (a.w == b.w)) {
442: // // Coverage.cover(168, "equal spans");
443: // special case this in order to speed up common case
444: // where large number of objects are equal
445: XSpan saveA = a.prev;
446: do {
447: a = a.next;
448: b = b.next;
449: } while ((a != headA) && (b != headB) && (a.x == b.x)
450: && (a.w == b.w));
451: a.prev = saveA;
452: saveA.next = a;
453: if ((a == headA) || (b == headB)) {
454: // // Coverage.cover(169, "all spans equal");
455: return;
456: }
457: }
458: int aEnd = a.x + a.w;
459: if (aEnd <= b.x) {
460: // // Coverage.cover(170, "no overlap (skip a)");
461: // no overlap -- skip
462: a = a.next;
463: continue;
464: }
465: int bEnd = b.x + b.w;
466: if (bEnd <= a.x) {
467: // // Coverage.cover(171, "no overlap (skip b)");
468: // no overlap -- skip
469: b = b.next;
470: continue;
471: }
472: if (a.x < b.x) {
473: // // Coverage.cover(172, "a.x < b.x (trim)");
474: // keep the non-overlap area preceding the overlap
475: a.w = b.x - a.x;
476: if (aEnd > bEnd) {
477: // // Coverage.cover(173, "aEnd > bEnd (split band)");
478: // make a new band for the area following the overlap
479: a.next = a.next.prev = new XSpan(bEnd, aEnd - bEnd,
480: a, a.next);
481: }
482: a = a.next;
483: } else if (aEnd > bEnd) {
484: // // Coverage.cover(174, "aEnd > bEnd (trim)");
485: // set the band to the non-overlap area following the overlap
486: a.w = aEnd - bEnd;
487: a.x = bEnd;
488: b = b.next;
489: } else {
490: // // Coverage.cover(175, "delete overlapping band");
491: // it all overlaps--delete it
492: a.prev.next = a.next;
493: a.next.prev = a.prev;
494: a = a.next;
495: }
496: }
497: // validateList("-subtract", headA);
498: }
499:
500: /*
501: * Utility function to intersect span lists. Case analysis is
502: * identical to intersection of YX lists, but simpler as there are
503: * no children to deal with. There is one case where we must split
504: * a span, changing
505: *
506: * A ----------
507: * B ----- --------
508: *
509: * to
510: *
511: * A --- ---
512: * B ----- --------
513: */
514: static void intersect(XSpan headA, XSpan headB) {
515: // validateList("+intersect", headA);
516: // validateList("+intersect", headB);
517: // // Coverage.cover(176, "intersect(XSpan,XSpan)");
518:
519: XSpan a = headA.next;
520: XSpan b = headB.next;
521: while ((a != headA) && (b != headB)) {
522: int aEnd = a.x + a.w;
523: if (aEnd <= b.x) {
524: // // Coverage.cover(177, "no overlap (delete a)");
525: // no overlap -- delete
526: a.prev.next = a.next;
527: a.next.prev = a.prev;
528: a = a.next;
529: continue;
530: }
531: int bEnd = b.x + b.w;
532: if (bEnd <= a.x) {
533: // // Coverage.cover(178, "no overlap (skip b)");
534: // no overlap -- skip
535: b = b.next;
536: continue;
537: }
538: if (a.x <= b.x) {
539: // // Coverage.cover(179, "a.x <= b.x (shorten band)");
540: // we're not interested in the non-overlap.
541: // begin by shortening the band.
542: a.x = b.x;
543: a.w = aEnd - a.x;
544: }
545: if (aEnd > bEnd) {
546: // // Coverage.cover(180, "aEnd > bEnd (shorten band)");
547: // shorten the band
548: a.w = bEnd - a.x;
549: b = b.next;
550: if ((b != headB) && (b.x < aEnd)) {
551: // // Coverage.cover(181, "split band");
552: // split the band
553: a.next = a.next.prev = new XSpan(b.x, aEnd - b.x,
554: a, a.next);
555: // re-examine this band--it might overlap several b's
556: }
557: }
558: // // Coverage.cover(182, "advance a");
559: a = a.next;
560: }
561: // delete any remaining a elements which don't overlap.
562: a.prev.next = headA;
563: headA.prev = a.prev;
564: // validateList("-intersect", headA);
565: }
566:
567: static void merge(XSpan headA, XSpan headB) {
568: // validateList("+merge", headA);
569: // validateList("+merge", headB);
570: XSpan a = headA.next;
571: XSpan b = headB.next;
572: while ((a != headA) && (b != headB)) {
573: int aEnd = a.x + a.w;
574: // no overlap
575: if (aEnd < b.x) {
576: // Coverage.cover(29, "no overlap -- advance a");
577: a = a.next;
578: continue;
579: }
580: int bEnd = b.x + b.w;
581: // no overlap
582: if (bEnd < a.x) {
583: // Coverage.cover(30, "no overlap -- insert (part of) b");
584: a.prev = a.prev.next = new XSpan(b.x, b.w, a.prev, a);
585: b = b.next;
586: continue;
587: }
588: if (a.x > b.x) {
589: // Coverage.cover(31, "a.x > b.x");
590: a.x = b.x;
591: a.w = aEnd - a.x;
592: if ((a.prev != headA) && (a.prev.x + a.prev.w >= a.x)) {
593: // Coverage.cover(32, "merge with previous span");
594: // merge with the previous span
595: a.prev.w = aEnd - a.prev.x;
596: a.next.prev = a.prev;
597: a.prev.next = a.next;
598: a = a.prev;
599: }
600: }
601: b = b.next; // from this point on we only need bEnd
602: if (bEnd > aEnd) {
603: // Coverage.cover(33, "bEnd > aEnd");
604: a.w = bEnd - a.x;
605: aEnd = a.x + a.w;
606: a = a.next;
607: if ((a != headA) && (aEnd >= a.x)) {
608: // Coverage.cover(34, "merge with previous span");
609: // merge with the new previous span
610: a.prev.w = a.x + a.w - a.prev.x;
611: a.next.prev = a.prev;
612: a.prev.next = a.next;
613: a = a.prev;
614: }
615: } else {
616: // Coverage.cover(35, "advance a");
617: a = a.next;
618: }
619: }
620: if (b == headB) {
621: // Coverage.cover(36, "no more elements in b");
622: return;
623: }
624: // handle leftovers in b. If they overlap, must extend a
625: a = headA.prev;
626: int aEnd = a.x + a.w;
627: while ((aEnd >= b.x) && (b != headB)) {
628: int bEnd = b.x + b.w;
629: // Coverage.cover(37, "overlapping leftover");
630: if (bEnd > aEnd) {
631: // Coverage.cover(38, "extend a");
632: a.w = bEnd - a.x;
633: }
634: b = b.next;
635: }
636: // now all that's left is things to append to the list.
637: while (b != headB) {
638: // Coverage.cover(39, "nonoverlapping leftover");
639: a.next = headA.prev = new XSpan(b.x, b.w, a, headA);
640: a = a.next;
641: b = b.next;
642: }
643: // validateList("-merge", headA);
644: }
645:
646: // no test coverage
647: public static String makeString(XSpan head) {
648: String ret = "[";
649: for (XSpan xs = head.next; xs != head; xs = xs.next) {
650: if (xs != head.next) {
651: ret += " ";
652: }
653: String s = "(" + xs.x + "," + xs.w + ")";
654: ret += s;
655: }
656: return ret + "]";
657: }
658:
659: // no test coverage
660: public String toString() {
661: return "(x = " + x + ", w = " + w + ")";
662: }
663: }
|