1 /*
   2  * Copyright (c) 1998, 2006, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package sun.java2d.pipe;
  27 
  28 import java.awt.Rectangle;
  29 import java.awt.Shape;
  30 import java.awt.geom.AffineTransform;
  31 import java.awt.geom.RectangularShape;
  32 
  33 /**
  34  * This class encapsulates a definition of a two dimensional region which
  35  * consists of a number of Y ranges each containing multiple X bands.
  36  * <p>
  37  * A rectangular Region is allowed to have a null band list in which
  38  * case the rectangular shape is defined by the bounding box parameters
  39  * (lox, loy, hix, hiy).
  40  * <p>
  41  * The band list, if present, consists of a list of rows in ascending Y
  42  * order, ending at endIndex which is the index beyond the end of the
  43  * last row.  Each row consists of at least 3 + 2n entries (n >= 1)
  44  * where the first 3 entries specify the Y range as start, end, and
  45  * the number of X ranges in that Y range.  These 3 entries are
  46  * followed by pairs of X coordinates in ascending order:
  47  * <pre>
  48  * bands[rowstart+0] = Y0;        // starting Y coordinate
  49  * bands[rowstart+1] = Y1;        // ending Y coordinate - endY > startY
  50  * bands[rowstart+2] = N;         // number of X bands - N >= 1
  51  *
  52  * bands[rowstart+3] = X10;       // starting X coordinate of first band
  53  * bands[rowstart+4] = X11;       // ending X coordinate of first band
  54  * bands[rowstart+5] = X20;       // starting X coordinate of second band
  55  * bands[rowstart+6] = X21;       // ending X coordinate of second band
  56  * ...
  57  * bands[rowstart+3+N*2-2] = XN0; // starting X coord of last band
  58  * bands[rowstart+3+N*2-1] = XN1; // ending X coord of last band
  59  *
  60  * bands[rowstart+3+N*2] = ...    // start of next Y row
  61  * </pre>
  62  */
  63 public class Region {
  64     static final int INIT_SIZE = 50;
  65     static final int GROW_SIZE = 50;
  66 
  67     /**
  68      * Immutable Region.
  69      */
  70     private static final class ImmutableRegion extends Region {
  71         protected ImmutableRegion(int lox, int loy, int hix, int hiy) {
  72             super(lox, loy, hix, hiy);
  73         }
  74 
  75         // Override all the methods that mutate the object
  76         public void appendSpans(sun.java2d.pipe.SpanIterator si) {}
  77         public void setOutputArea(java.awt.Rectangle r) {}
  78         public void setOutputAreaXYWH(int x, int y, int w, int h) {}
  79         public void setOutputArea(int[] box) {}
  80         public void setOutputAreaXYXY(int lox, int loy, int hix, int hiy) {}
  81     }
  82 
  83     public static final Region EMPTY_REGION = new ImmutableRegion(0, 0, 0, 0);
  84     public static final Region WHOLE_REGION = new ImmutableRegion(
  85             Integer.MIN_VALUE,
  86             Integer.MIN_VALUE,
  87             Integer.MAX_VALUE,
  88             Integer.MAX_VALUE);
  89 
  90     int lox;
  91     int loy;
  92     int hix;
  93     int hiy;
  94 
  95     int endIndex;
  96     int[] bands;
  97 
  98     private static native void initIDs();
  99 
 100     static {
 101         initIDs();
 102     }
 103 
 104     /**
 105      * Adds the dimension <code>dim</code> to the coordinate
 106      * <code>start</code> with appropriate clipping.  If
 107      * <code>dim</code> is non-positive then the method returns
 108      * the start coordinate.  If the sum overflows an integer
 109      * data type then the method returns <code>Integer.MAX_VALUE</code>.
 110      */
 111     public static int dimAdd(int start, int dim) {
 112         if (dim <= 0) return start;
 113         if ((dim += start) < start) return Integer.MAX_VALUE;
 114         return dim;
 115     }
 116 
 117     /**
 118      * Adds the delta {@code dv} to the value {@code v} with
 119      * appropriate clipping to the bounds of Integer resolution.
 120      * If the answer would be greater than {@code Integer.MAX_VALUE}
 121      * then {@code Integer.MAX_VALUE} is returned.
 122      * If the answer would be less than {@code Integer.MIN_VALUE}
 123      * then {@code Integer.MIN_VALUE} is returned.
 124      * Otherwise the sum is returned.
 125      */
 126     public static int clipAdd(int v, int dv) {
 127         int newv = v + dv;
 128         if ((newv > v) != (dv > 0)) {
 129             newv = (dv < 0) ? Integer.MIN_VALUE : Integer.MAX_VALUE;
 130         }
 131         return newv;
 132     }
 133 
 134     /**
 135      * Multiply the scale factor {@code sv} and the value {@code v} with
 136      * appropriate clipping to the bounds of Integer resolution. If the answer
 137      * would be greater than {@code Integer.MAX_VALUE} then {@code
 138      * Integer.MAX_VALUE} is returned. If the answer would be less than {@code
 139      * Integer.MIN_VALUE} then {@code Integer.MIN_VALUE} is returned. Otherwise
 140      * the multiplication is returned.
 141      */
 142     public static int clipScale(final int v, final double sv) {
 143         if (sv == 1.0) {
 144             return v;
 145         }
 146         final double newv = v * sv;
 147         if (newv < Integer.MIN_VALUE) {
 148             return Integer.MIN_VALUE;
 149         }
 150         if (newv > Integer.MAX_VALUE) {
 151             return Integer.MAX_VALUE;
 152         }
 153         return (int) Math.round(newv);
 154     }
 155 
 156     protected Region(int lox, int loy, int hix, int hiy) {
 157         this.lox = lox;
 158         this.loy = loy;
 159         this.hix = hix;
 160         this.hiy = hiy;
 161     }
 162 
 163     /**
 164      * Returns a Region object covering the pixels which would be
 165      * touched by a fill or clip operation on a Graphics implementation
 166      * on the specified Shape object under the optionally specified
 167      * AffineTransform object.
 168      *
 169      * @param s a non-null Shape object specifying the geometry enclosing
 170      *          the pixels of interest
 171      * @param at an optional <code>AffineTransform</code> to be applied to the
 172      *          coordinates as they are returned in the iteration, or
 173      *          <code>null</code> if untransformed coordinates are desired
 174      */
 175     public static Region getInstance(Shape s, AffineTransform at) {
 176         return getInstance(WHOLE_REGION, false, s, at);
 177     }
 178 
 179     /**
 180      * Returns a Region object covering the pixels which would be
 181      * touched by a fill or clip operation on a Graphics implementation
 182      * on the specified Shape object under the optionally specified
 183      * AffineTransform object further restricted by the specified
 184      * device bounds.
 185      * <p>
 186      * Note that only the bounds of the specified Region are used to
 187      * restrict the resulting Region.
 188      * If devBounds is non-rectangular and clipping to the specific
 189      * bands of devBounds is needed, then an intersection of the
 190      * resulting Region with devBounds must be performed in a
 191      * subsequent step.
 192      *
 193      * @param devBounds a non-null Region specifying some bounds to
 194      *          clip the geometry to
 195      * @param s a non-null Shape object specifying the geometry enclosing
 196      *          the pixels of interest
 197      * @param at an optional <code>AffineTransform</code> to be applied to the
 198      *          coordinates as they are returned in the iteration, or
 199      *          <code>null</code> if untransformed coordinates are desired
 200      */
 201     public static Region getInstance(Region devBounds,
 202                                      Shape s, AffineTransform at)
 203     {
 204         return getInstance(devBounds, false, s, at);
 205     }
 206 
 207     /**
 208      * Returns a Region object covering the pixels which would be
 209      * touched by a fill or clip operation on a Graphics implementation
 210      * on the specified Shape object under the optionally specified
 211      * AffineTransform object further restricted by the specified
 212      * device bounds.
 213      * If the normalize parameter is true then coordinate normalization
 214      * is performed as per the 2D Graphics non-antialiasing implementation
 215      * of the VALUE_STROKE_NORMALIZE hint.
 216      * <p>
 217      * Note that only the bounds of the specified Region are used to
 218      * restrict the resulting Region.
 219      * If devBounds is non-rectangular and clipping to the specific
 220      * bands of devBounds is needed, then an intersection of the
 221      * resulting Region with devBounds must be performed in a
 222      * subsequent step.
 223      *
 224      * @param devBounds a non-null Region specifying some bounds to
 225      *          clip the geometry to
 226      * @param normalize a boolean indicating whether or not to apply
 227      *          normalization
 228      * @param s a non-null Shape object specifying the geometry enclosing
 229      *          the pixels of interest
 230      * @param at an optional <code>AffineTransform</code> to be applied to the
 231      *          coordinates as they are returned in the iteration, or
 232      *          <code>null</code> if untransformed coordinates are desired
 233      */
 234     public static Region getInstance(Region devBounds, boolean normalize,
 235                                      Shape s, AffineTransform at)
 236     {
 237         // Optimize for empty shapes to avoid involving the SpanIterator
 238         if (s instanceof RectangularShape &&
 239                 ((RectangularShape)s).isEmpty())
 240         {
 241             return EMPTY_REGION;
 242         }
 243 
 244         int box[] = new int[4];
 245         ShapeSpanIterator sr = new ShapeSpanIterator(normalize);
 246         try {
 247             sr.setOutputArea(devBounds);
 248             sr.appendPath(s.getPathIterator(at));
 249             sr.getPathBox(box);
 250             Region r = Region.getInstance(box);
 251             r.appendSpans(sr);
 252             return r;
 253         } finally {
 254             sr.dispose();
 255         }
 256     }
 257 
 258     /**
 259      * Returns a Region object with a rectangle of interest specified
 260      * by the indicated Rectangle object.
 261      * <p>
 262      * This method can also be used to create a simple rectangular
 263      * region.
 264      */
 265     public static Region getInstance(Rectangle r) {
 266         return Region.getInstanceXYWH(r.x, r.y, r.width, r.height);
 267     }
 268 
 269     /**
 270      * Returns a Region object with a rectangle of interest specified
 271      * by the indicated rectangular area in x, y, width, height format.
 272      * <p>
 273      * This method can also be used to create a simple rectangular
 274      * region.
 275      */
 276     public static Region getInstanceXYWH(int x, int y, int w, int h) {
 277         return Region.getInstanceXYXY(x, y, dimAdd(x, w), dimAdd(y, h));
 278     }
 279 
 280     /**
 281      * Returns a Region object with a rectangle of interest specified
 282      * by the indicated span array.
 283      * <p>
 284      * This method can also be used to create a simple rectangular
 285      * region.
 286      */
 287     public static Region getInstance(int box[]) {
 288         return new Region(box[0], box[1], box[2], box[3]);
 289     }
 290 
 291     /**
 292      * Returns a Region object with a rectangle of interest specified
 293      * by the indicated rectangular area in lox, loy, hix, hiy format.
 294      * <p>
 295      * This method can also be used to create a simple rectangular
 296      * region.
 297      */
 298     public static Region getInstanceXYXY(int lox, int loy, int hix, int hiy) {
 299         return new Region(lox, loy, hix, hiy);
 300     }
 301 
 302     /**
 303      * Sets the rectangle of interest for storing and returning
 304      * region bands.
 305      * <p>
 306      * This method can also be used to initialize a simple rectangular
 307      * region.
 308      */
 309     public void setOutputArea(Rectangle r) {
 310         setOutputAreaXYWH(r.x, r.y, r.width, r.height);
 311     }
 312 
 313     /**
 314      * Sets the rectangle of interest for storing and returning
 315      * region bands.  The rectangle is specified in x, y, width, height
 316      * format and appropriate clipping is performed as per the method
 317      * <code>dimAdd</code>.
 318      * <p>
 319      * This method can also be used to initialize a simple rectangular
 320      * region.
 321      */
 322     public void setOutputAreaXYWH(int x, int y, int w, int h) {
 323         setOutputAreaXYXY(x, y, dimAdd(x, w), dimAdd(y, h));
 324     }
 325 
 326     /**
 327      * Sets the rectangle of interest for storing and returning
 328      * region bands.  The rectangle is specified as a span array.
 329      * <p>
 330      * This method can also be used to initialize a simple rectangular
 331      * region.
 332      */
 333     public void setOutputArea(int box[]) {
 334         this.lox = box[0];
 335         this.loy = box[1];
 336         this.hix = box[2];
 337         this.hiy = box[3];
 338     }
 339 
 340     /**
 341      * Sets the rectangle of interest for storing and returning
 342      * region bands.  The rectangle is specified in lox, loy,
 343      * hix, hiy format.
 344      * <p>
 345      * This method can also be used to initialize a simple rectangular
 346      * region.
 347      */
 348     public void setOutputAreaXYXY(int lox, int loy, int hix, int hiy) {
 349         this.lox = lox;
 350         this.loy = loy;
 351         this.hix = hix;
 352         this.hiy = hiy;
 353     }
 354 
 355     /**
 356      * Appends the list of spans returned from the indicated
 357      * SpanIterator.  Each span must be at a higher starting
 358      * Y coordinate than the previous data or it must have a
 359      * Y range equal to the highest Y band in the region and a
 360      * higher X coordinate than any of the spans in that band.
 361      */
 362     public void appendSpans(SpanIterator si) {
 363         int[] box = new int[6];
 364 
 365         while (si.nextSpan(box)) {
 366             appendSpan(box);
 367         }
 368 
 369         endRow(box);
 370         calcBBox();
 371     }
 372 
 373     /**
 374      * Returns a Region object that represents the same list of rectangles as
 375      * the current Region object, scaled by the specified sx, sy factors.
 376      */
 377     public Region getScaledRegion(final double sx, final double sy) {
 378         if (sx == 0 || sy == 0 || this == EMPTY_REGION) {
 379             return EMPTY_REGION;
 380         }
 381         if ((sx == 1.0 && sy == 1.0) || (this == WHOLE_REGION)) {
 382             return this;
 383         }
 384 
 385         int tlox = clipScale(lox, sx);
 386         int tloy = clipScale(loy, sy);
 387         int thix = clipScale(hix, sx);
 388         int thiy = clipScale(hiy, sy);
 389         Region ret = new Region(tlox, tloy, thix, thiy);
 390         int bands[] = this.bands;
 391         if (bands != null) {
 392             int end = endIndex;
 393             int newbands[] = new int[end];
 394             int i = 0; // index for source bands
 395             int j = 0; // index for translated newbands
 396             int ncol;
 397             while (i < end) {
 398                 int y1, y2;
 399                 newbands[j++] = y1   = clipScale(bands[i++], sy);
 400                 newbands[j++] = y2   = clipScale(bands[i++], sy);
 401                 newbands[j++] = ncol = bands[i++];
 402                 int savej = j;
 403                 if (y1 < y2) {
 404                     while (--ncol >= 0) {
 405                         int x1 = clipScale(bands[i++], sx);
 406                         int x2 = clipScale(bands[i++], sx);
 407                         if (x1 < x2) {
 408                             newbands[j++] = x1;
 409                             newbands[j++] = x2;
 410                         }
 411                     }
 412                 } else {
 413                     i += ncol * 2;
 414                 }
 415                 // Did we get any non-empty bands in this row?
 416                 if (j > savej) {
 417                     newbands[savej-1] = (j - savej) / 2;
 418                 } else {
 419                     j = savej - 3;
 420                 }
 421             }
 422             if (j <= 5) {
 423                 if (j < 5) {
 424                     // No rows or bands were generated...
 425                     ret.lox = ret.loy = ret.hix = ret.hiy = 0;
 426                 } else {
 427                     // Only generated one single rect in the end...
 428                     ret.loy = newbands[0];
 429                     ret.hiy = newbands[1];
 430                     ret.lox = newbands[3];
 431                     ret.hix = newbands[4];
 432                 }
 433                 // ret.endIndex and ret.bands were never initialized...
 434                 // ret.endIndex = 0;
 435                 // ret.newbands = null;
 436             } else {
 437                 // Generated multiple bands and/or multiple rows...
 438                 ret.endIndex = j;
 439                 ret.bands = newbands;
 440             }
 441         }
 442         return ret;
 443     }
 444 
 445 
 446     /**
 447      * Returns a Region object that represents the same list of
 448      * rectangles as the current Region object, translated by
 449      * the specified dx, dy translation factors.
 450      */
 451     public Region getTranslatedRegion(int dx, int dy) {
 452         if ((dx | dy) == 0) {
 453             return this;
 454         }
 455         int tlox = lox + dx;
 456         int tloy = loy + dy;
 457         int thix = hix + dx;
 458         int thiy = hiy + dy;
 459         if ((tlox > lox) != (dx > 0) ||
 460             (tloy > loy) != (dy > 0) ||
 461             (thix > hix) != (dx > 0) ||
 462             (thiy > hiy) != (dy > 0))
 463         {
 464             return getSafeTranslatedRegion(dx, dy);
 465         }
 466         Region ret = new Region(tlox, tloy, thix, thiy);
 467         int bands[] = this.bands;
 468         if (bands != null) {
 469             int end = endIndex;
 470             ret.endIndex = end;
 471             int newbands[] = new int[end];
 472             ret.bands = newbands;
 473             int i = 0;
 474             int ncol;
 475             while (i < end) {
 476                 newbands[i] = bands[i] + dy; i++;
 477                 newbands[i] = bands[i] + dy; i++;
 478                 newbands[i] = ncol = bands[i]; i++;
 479                 while (--ncol >= 0) {
 480                     newbands[i] = bands[i] + dx; i++;
 481                     newbands[i] = bands[i] + dx; i++;
 482                 }
 483             }
 484         }
 485         return ret;
 486     }
 487 
 488     private Region getSafeTranslatedRegion(int dx, int dy) {
 489         int tlox = clipAdd(lox, dx);
 490         int tloy = clipAdd(loy, dy);
 491         int thix = clipAdd(hix, dx);
 492         int thiy = clipAdd(hiy, dy);
 493         Region ret = new Region(tlox, tloy, thix, thiy);
 494         int bands[] = this.bands;
 495         if (bands != null) {
 496             int end = endIndex;
 497             int newbands[] = new int[end];
 498             int i = 0; // index for source bands
 499             int j = 0; // index for translated newbands
 500             int ncol;
 501             while (i < end) {
 502                 int y1, y2;
 503                 newbands[j++] = y1   = clipAdd(bands[i++], dy);
 504                 newbands[j++] = y2   = clipAdd(bands[i++], dy);
 505                 newbands[j++] = ncol = bands[i++];
 506                 int savej = j;
 507                 if (y1 < y2) {
 508                     while (--ncol >= 0) {
 509                         int x1 = clipAdd(bands[i++], dx);
 510                         int x2 = clipAdd(bands[i++], dx);
 511                         if (x1 < x2) {
 512                             newbands[j++] = x1;
 513                             newbands[j++] = x2;
 514                         }
 515                     }
 516                 } else {
 517                     i += ncol * 2;
 518                 }
 519                 // Did we get any non-empty bands in this row?
 520                 if (j > savej) {
 521                     newbands[savej-1] = (j - savej) / 2;
 522                 } else {
 523                     j = savej - 3;
 524                 }
 525             }
 526             if (j <= 5) {
 527                 if (j < 5) {
 528                     // No rows or bands were generated...
 529                     ret.lox = ret.loy = ret.hix = ret.hiy = 0;
 530                 } else {
 531                     // Only generated one single rect in the end...
 532                     ret.loy = newbands[0];
 533                     ret.hiy = newbands[1];
 534                     ret.lox = newbands[3];
 535                     ret.hix = newbands[4];
 536                 }
 537                 // ret.endIndex and ret.bands were never initialized...
 538                 // ret.endIndex = 0;
 539                 // ret.newbands = null;
 540             } else {
 541                 // Generated multiple bands and/or multiple rows...
 542                 ret.endIndex = j;
 543                 ret.bands = newbands;
 544             }
 545         }
 546         return ret;
 547     }
 548 
 549     /**
 550      * Returns a Region object that represents the intersection of
 551      * this object with the specified Rectangle.  The return value
 552      * may be this same object if no clipping occurs.
 553      */
 554     public Region getIntersection(Rectangle r) {
 555         return getIntersectionXYWH(r.x, r.y, r.width, r.height);
 556     }
 557 
 558     /**
 559      * Returns a Region object that represents the intersection of
 560      * this object with the specified rectangular area.  The return
 561      * value may be this same object if no clipping occurs.
 562      */
 563     public Region getIntersectionXYWH(int x, int y, int w, int h) {
 564         return getIntersectionXYXY(x, y, dimAdd(x, w), dimAdd(y, h));
 565     }
 566 
 567     /**
 568      * Returns a Region object that represents the intersection of
 569      * this object with the specified rectangular area.  The return
 570      * value may be this same object if no clipping occurs.
 571      */
 572     public Region getIntersectionXYXY(int lox, int loy, int hix, int hiy) {
 573         if (isInsideXYXY(lox, loy, hix, hiy)) {
 574             return this;
 575         }
 576         Region ret = new Region((lox < this.lox) ? this.lox : lox,
 577                                 (loy < this.loy) ? this.loy : loy,
 578                                 (hix > this.hix) ? this.hix : hix,
 579                                 (hiy > this.hiy) ? this.hiy : hiy);
 580         if (bands != null) {
 581             ret.appendSpans(this.getSpanIterator());
 582         }
 583         return ret;
 584     }
 585 
 586     /**
 587      * Returns a Region object that represents the intersection of this
 588      * object with the specified Region object.
 589      * <p>
 590      * If {@code A} and {@code B} are both Region Objects and
 591      * <code>C = A.getIntersection(B);</code> then a point will
 592      * be contained in {@code C} iff it is contained in both
 593      * {@code A} and {@code B}.
 594      * <p>
 595      * The return value may be this same object or the argument
 596      * Region object if no clipping occurs.
 597      */
 598     public Region getIntersection(Region r) {
 599         if (this.isInsideQuickCheck(r)) {
 600             return this;
 601         }
 602         if (r.isInsideQuickCheck(this)) {
 603             return r;
 604         }
 605         Region ret = new Region((r.lox < this.lox) ? this.lox : r.lox,
 606                                 (r.loy < this.loy) ? this.loy : r.loy,
 607                                 (r.hix > this.hix) ? this.hix : r.hix,
 608                                 (r.hiy > this.hiy) ? this.hiy : r.hiy);
 609         if (!ret.isEmpty()) {
 610             ret.filterSpans(this, r, INCLUDE_COMMON);
 611         }
 612         return ret;
 613     }
 614 
 615     /**
 616      * Returns a Region object that represents the union of this
 617      * object with the specified Region object.
 618      * <p>
 619      * If {@code A} and {@code B} are both Region Objects and
 620      * <code>C = A.getUnion(B);</code> then a point will
 621      * be contained in {@code C} iff it is contained in either
 622      * {@code A} or {@code B}.
 623      * <p>
 624      * The return value may be this same object or the argument
 625      * Region object if no augmentation occurs.
 626      */
 627     public Region getUnion(Region r) {
 628         if (r.isEmpty() || r.isInsideQuickCheck(this)) {
 629             return this;
 630         }
 631         if (this.isEmpty() || this.isInsideQuickCheck(r)) {
 632             return r;
 633         }
 634         Region ret = new Region((r.lox > this.lox) ? this.lox : r.lox,
 635                                 (r.loy > this.loy) ? this.loy : r.loy,
 636                                 (r.hix < this.hix) ? this.hix : r.hix,
 637                                 (r.hiy < this.hiy) ? this.hiy : r.hiy);
 638         ret.filterSpans(this, r, INCLUDE_A | INCLUDE_B | INCLUDE_COMMON);
 639         return ret;
 640     }
 641 
 642     /**
 643      * Returns a Region object that represents the difference of the
 644      * specified Region object subtracted from this object.
 645      * <p>
 646      * If {@code A} and {@code B} are both Region Objects and
 647      * <code>C = A.getDifference(B);</code> then a point will
 648      * be contained in {@code C} iff it is contained in
 649      * {@code A} but not contained in {@code B}.
 650      * <p>
 651      * The return value may be this same object or the argument
 652      * Region object if no clipping occurs.
 653      */
 654     public Region getDifference(Region r) {
 655         if (!r.intersectsQuickCheck(this)) {
 656             return this;
 657         }
 658         if (this.isInsideQuickCheck(r)) {
 659             return EMPTY_REGION;
 660         }
 661         Region ret = new Region(this.lox, this.loy, this.hix, this.hiy);
 662         ret.filterSpans(this, r, INCLUDE_A);
 663         return ret;
 664     }
 665 
 666     /**
 667      * Returns a Region object that represents the exclusive or of this
 668      * object with the specified Region object.
 669      * <p>
 670      * If {@code A} and {@code B} are both Region Objects and
 671      * <code>C = A.getExclusiveOr(B);</code> then a point will
 672      * be contained in {@code C} iff it is contained in either
 673      * {@code A} or {@code B}, but not if it is contained in both.
 674      * <p>
 675      * The return value may be this same object or the argument
 676      * Region object if either is empty.
 677      */
 678     public Region getExclusiveOr(Region r) {
 679         if (r.isEmpty()) {
 680             return this;
 681         }
 682         if (this.isEmpty()) {
 683             return r;
 684         }
 685         Region ret = new Region((r.lox > this.lox) ? this.lox : r.lox,
 686                                 (r.loy > this.loy) ? this.loy : r.loy,
 687                                 (r.hix < this.hix) ? this.hix : r.hix,
 688                                 (r.hiy < this.hiy) ? this.hiy : r.hiy);
 689         ret.filterSpans(this, r, INCLUDE_A | INCLUDE_B);
 690         return ret;
 691     }
 692 
 693     static final int INCLUDE_A      = 1;
 694     static final int INCLUDE_B      = 2;
 695     static final int INCLUDE_COMMON = 4;
 696 
 697     private void filterSpans(Region ra, Region rb, int flags) {
 698         int abands[] = ra.bands;
 699         int bbands[] = rb.bands;
 700         if (abands == null) {
 701             abands = new int[] {ra.loy, ra.hiy, 1, ra.lox, ra.hix};
 702         }
 703         if (bbands == null) {
 704             bbands = new int[] {rb.loy, rb.hiy, 1, rb.lox, rb.hix};
 705         }
 706         int box[] = new int[6];
 707         int acolstart = 0;
 708         int ay1 = abands[acolstart++];
 709         int ay2 = abands[acolstart++];
 710         int acolend = abands[acolstart++];
 711         acolend = acolstart + 2 * acolend;
 712         int bcolstart = 0;
 713         int by1 = bbands[bcolstart++];
 714         int by2 = bbands[bcolstart++];
 715         int bcolend = bbands[bcolstart++];
 716         bcolend = bcolstart + 2 * bcolend;
 717         int y = loy;
 718         while (y < hiy) {
 719             if (y >= ay2) {
 720                 if (acolend < ra.endIndex) {
 721                     acolstart = acolend;
 722                     ay1 = abands[acolstart++];
 723                     ay2 = abands[acolstart++];
 724                     acolend = abands[acolstart++];
 725                     acolend = acolstart + 2 * acolend;
 726                 } else {
 727                     if ((flags & INCLUDE_B) == 0) break;
 728                     ay1 = ay2 = hiy;
 729                 }
 730                 continue;
 731             }
 732             if (y >= by2) {
 733                 if (bcolend < rb.endIndex) {
 734                     bcolstart = bcolend;
 735                     by1 = bbands[bcolstart++];
 736                     by2 = bbands[bcolstart++];
 737                     bcolend = bbands[bcolstart++];
 738                     bcolend = bcolstart + 2 * bcolend;
 739                 } else {
 740                     if ((flags & INCLUDE_A) == 0) break;
 741                     by1 = by2 = hiy;
 742                 }
 743                 continue;
 744             }
 745             int yend;
 746             if (y < by1) {
 747                 if (y < ay1) {
 748                     y = Math.min(ay1, by1);
 749                     continue;
 750                 }
 751                 // We are in a set of rows that belong only to A
 752                 yend = Math.min(ay2, by1);
 753                 if ((flags & INCLUDE_A) != 0) {
 754                     box[1] = y;
 755                     box[3] = yend;
 756                     int acol = acolstart;
 757                     while (acol < acolend) {
 758                         box[0] = abands[acol++];
 759                         box[2] = abands[acol++];
 760                         appendSpan(box);
 761                     }
 762                 }
 763             } else if (y < ay1) {
 764                 // We are in a set of rows that belong only to B
 765                 yend = Math.min(by2, ay1);
 766                 if ((flags & INCLUDE_B) != 0) {
 767                     box[1] = y;
 768                     box[3] = yend;
 769                     int bcol = bcolstart;
 770                     while (bcol < bcolend) {
 771                         box[0] = bbands[bcol++];
 772                         box[2] = bbands[bcol++];
 773                         appendSpan(box);
 774                     }
 775                 }
 776             } else {
 777                 // We are in a set of rows that belong to both A and B
 778                 yend = Math.min(ay2, by2);
 779                 box[1] = y;
 780                 box[3] = yend;
 781                 int acol = acolstart;
 782                 int bcol = bcolstart;
 783                 int ax1 = abands[acol++];
 784                 int ax2 = abands[acol++];
 785                 int bx1 = bbands[bcol++];
 786                 int bx2 = bbands[bcol++];
 787                 int x = Math.min(ax1, bx1);
 788                 if (x < lox) x = lox;
 789                 while (x < hix) {
 790                     if (x >= ax2) {
 791                         if (acol < acolend) {
 792                             ax1 = abands[acol++];
 793                             ax2 = abands[acol++];
 794                         } else {
 795                             if ((flags & INCLUDE_B) == 0) break;
 796                             ax1 = ax2 = hix;
 797                         }
 798                         continue;
 799                     }
 800                     if (x >= bx2) {
 801                         if (bcol < bcolend) {
 802                             bx1 = bbands[bcol++];
 803                             bx2 = bbands[bcol++];
 804                         } else {
 805                             if ((flags & INCLUDE_A) == 0) break;
 806                             bx1 = bx2 = hix;
 807                         }
 808                         continue;
 809                     }
 810                     int xend;
 811                     boolean appendit;
 812                     if (x < bx1) {
 813                         if (x < ax1) {
 814                             xend = Math.min(ax1, bx1);
 815                             appendit = false;
 816                         } else {
 817                             xend = Math.min(ax2, bx1);
 818                             appendit = ((flags & INCLUDE_A) != 0);
 819                         }
 820                     } else if (x < ax1) {
 821                         xend = Math.min(ax1, bx2);
 822                         appendit = ((flags & INCLUDE_B) != 0);
 823                     } else {
 824                         xend = Math.min(ax2, bx2);
 825                         appendit = ((flags & INCLUDE_COMMON) != 0);
 826                     }
 827                     if (appendit) {
 828                         box[0] = x;
 829                         box[2] = xend;
 830                         appendSpan(box);
 831                     }
 832                     x = xend;
 833                 }
 834             }
 835             y = yend;
 836         }
 837         endRow(box);
 838         calcBBox();
 839     }
 840 
 841     /**
 842      * Returns a Region object that represents the bounds of the
 843      * intersection of this object with the bounds of the specified
 844      * Region object.
 845      * <p>
 846      * The return value may be this same object if no clipping occurs
 847      * and this Region is rectangular.
 848      */
 849     public Region getBoundsIntersection(Rectangle r) {
 850         return getBoundsIntersectionXYWH(r.x, r.y, r.width, r.height);
 851     }
 852 
 853     /**
 854      * Returns a Region object that represents the bounds of the
 855      * intersection of this object with the bounds of the specified
 856      * rectangular area in x, y, width, height format.
 857      * <p>
 858      * The return value may be this same object if no clipping occurs
 859      * and this Region is rectangular.
 860      */
 861     public Region getBoundsIntersectionXYWH(int x, int y, int w, int h) {
 862         return getBoundsIntersectionXYXY(x, y, dimAdd(x, w), dimAdd(y, h));
 863     }
 864 
 865     /**
 866      * Returns a Region object that represents the bounds of the
 867      * intersection of this object with the bounds of the specified
 868      * rectangular area in lox, loy, hix, hiy format.
 869      * <p>
 870      * The return value may be this same object if no clipping occurs
 871      * and this Region is rectangular.
 872      */
 873     public Region getBoundsIntersectionXYXY(int lox, int loy,
 874                                             int hix, int hiy)
 875     {
 876         if (this.bands == null &&
 877             this.lox >= lox && this.loy >= loy &&
 878             this.hix <= hix && this.hiy <= hiy)
 879         {
 880             return this;
 881         }
 882         return new Region((lox < this.lox) ? this.lox : lox,
 883                           (loy < this.loy) ? this.loy : loy,
 884                           (hix > this.hix) ? this.hix : hix,
 885                           (hiy > this.hiy) ? this.hiy : hiy);
 886     }
 887 
 888     /**
 889      * Returns a Region object that represents the intersection of
 890      * this object with the bounds of the specified Region object.
 891      * <p>
 892      * The return value may be this same object or the argument
 893      * Region object if no clipping occurs and the Regions are
 894      * rectangular.
 895      */
 896     public Region getBoundsIntersection(Region r) {
 897         if (this.encompasses(r)) {
 898             return r;
 899         }
 900         if (r.encompasses(this)) {
 901             return this;
 902         }
 903         return new Region((r.lox < this.lox) ? this.lox : r.lox,
 904                           (r.loy < this.loy) ? this.loy : r.loy,
 905                           (r.hix > this.hix) ? this.hix : r.hix,
 906                           (r.hiy > this.hiy) ? this.hiy : r.hiy);
 907     }
 908 
 909     /**
 910      * Appends a single span defined by the 4 parameters
 911      * spanlox, spanloy, spanhix, spanhiy.
 912      * This span must be at a higher starting Y coordinate than
 913      * the previous data or it must have a Y range equal to the
 914      * highest Y band in the region and a higher X coordinate
 915      * than any of the spans in that band.
 916      */
 917     private void appendSpan(int box[]) {
 918         int spanlox, spanloy, spanhix, spanhiy;
 919         if ((spanlox = box[0]) < lox) spanlox = lox;
 920         if ((spanloy = box[1]) < loy) spanloy = loy;
 921         if ((spanhix = box[2]) > hix) spanhix = hix;
 922         if ((spanhiy = box[3]) > hiy) spanhiy = hiy;
 923         if (spanhix <= spanlox || spanhiy <= spanloy) {
 924             return;
 925         }
 926 
 927         int curYrow = box[4];
 928         if (endIndex == 0 || spanloy >= bands[curYrow + 1]) {
 929             if (bands == null) {
 930                 bands = new int[INIT_SIZE];
 931             } else {
 932                 needSpace(5);
 933                 endRow(box);
 934                 curYrow = box[4];
 935             }
 936             bands[endIndex++] = spanloy;
 937             bands[endIndex++] = spanhiy;
 938             bands[endIndex++] = 0;
 939         } else if (spanloy == bands[curYrow] &&
 940                    spanhiy == bands[curYrow + 1] &&
 941                    spanlox >= bands[endIndex - 1]) {
 942             if (spanlox == bands[endIndex - 1]) {
 943                 bands[endIndex - 1] = spanhix;
 944                 return;
 945             }
 946             needSpace(2);
 947         } else {
 948             throw new InternalError("bad span");
 949         }
 950         bands[endIndex++] = spanlox;
 951         bands[endIndex++] = spanhix;
 952         bands[curYrow + 2]++;
 953     }
 954 
 955     private void needSpace(int num) {
 956         if (endIndex + num >= bands.length) {
 957             int[] newbands = new int[bands.length + GROW_SIZE];
 958             System.arraycopy(bands, 0, newbands, 0, endIndex);
 959             bands = newbands;
 960         }
 961     }
 962 
 963     private void endRow(int box[]) {
 964         int cur = box[4];
 965         int prev = box[5];
 966         if (cur > prev) {
 967             int[] bands = this.bands;
 968             if (bands[prev + 1] == bands[cur] &&
 969                 bands[prev + 2] == bands[cur + 2])
 970             {
 971                 int num = bands[cur + 2] * 2;
 972                 cur += 3;
 973                 prev += 3;
 974                 while (num > 0) {
 975                     if (bands[cur++] != bands[prev++]) {
 976                         break;
 977                     }
 978                     num--;
 979                 }
 980                 if (num == 0) {
 981                     // prev == box[4]
 982                     bands[box[5] + 1] = bands[prev + 1];
 983                     endIndex = prev;
 984                     return;
 985                 }
 986             }
 987         }
 988         box[5] = box[4];
 989         box[4] = endIndex;
 990     }
 991 
 992     private void calcBBox() {
 993         int[] bands = this.bands;
 994         if (endIndex <= 5) {
 995             if (endIndex == 0) {
 996                 lox = loy = hix = hiy = 0;
 997             } else {
 998                 loy = bands[0];
 999                 hiy = bands[1];
1000                 lox = bands[3];
1001                 hix = bands[4];
1002                 endIndex = 0;
1003             }
1004             this.bands = null;
1005             return;
1006         }
1007         int lox = this.hix;
1008         int hix = this.lox;
1009         int hiyindex = 0;
1010 
1011         int i = 0;
1012         while (i < endIndex) {
1013             hiyindex = i;
1014             int numbands = bands[i + 2];
1015             i += 3;
1016             if (lox > bands[i]) {
1017                 lox = bands[i];
1018             }
1019             i += numbands * 2;
1020             if (hix < bands[i - 1]) {
1021                 hix = bands[i - 1];
1022             }
1023         }
1024 
1025         this.lox = lox;
1026         this.loy = bands[0];
1027         this.hix = hix;
1028         this.hiy = bands[hiyindex + 1];
1029     }
1030 
1031     /**
1032      * Returns the lowest X coordinate in the Region.
1033      */
1034     public final int getLoX() {
1035         return lox;
1036     }
1037 
1038     /**
1039      * Returns the lowest Y coordinate in the Region.
1040      */
1041     public final int getLoY() {
1042         return loy;
1043     }
1044 
1045     /**
1046      * Returns the highest X coordinate in the Region.
1047      */
1048     public final int getHiX() {
1049         return hix;
1050     }
1051 
1052     /**
1053      * Returns the highest Y coordinate in the Region.
1054      */
1055     public final int getHiY() {
1056         return hiy;
1057     }
1058 
1059     /**
1060      * Returns the width of this Region clipped to the range (0 - MAX_INT).
1061      */
1062     public final int getWidth() {
1063         if (hix < lox) return 0;
1064         int w;
1065         if ((w = hix - lox) < 0) {
1066             w = Integer.MAX_VALUE;
1067         }
1068         return w;
1069     }
1070 
1071     /**
1072      * Returns the height of this Region clipped to the range (0 - MAX_INT).
1073      */
1074     public final int getHeight() {
1075         if (hiy < loy) return 0;
1076         int h;
1077         if ((h = hiy - loy) < 0) {
1078             h = Integer.MAX_VALUE;
1079         }
1080         return h;
1081     }
1082 
1083     /**
1084      * Returns true iff this Region encloses no area.
1085      */
1086     public boolean isEmpty() {
1087         return (hix <= lox || hiy <= loy);
1088     }
1089 
1090     /**
1091      * Returns true iff this Region represents a single simple
1092      * rectangular area.
1093      */
1094     public boolean isRectangular() {
1095         return (bands == null);
1096     }
1097 
1098     /**
1099      * Returns true iff this Region contains the specified coordinate.
1100      */
1101     public boolean contains(int x, int y) {
1102         if (x < lox || x >= hix || y < loy || y >= hiy) return false;
1103         if (bands == null) return true;
1104         int i = 0;
1105         while (i < endIndex) {
1106             if (y < bands[i++]) {
1107                 return false;
1108             }
1109             if (y >= bands[i++]) {
1110                 int numspans = bands[i++];
1111                 i += numspans * 2;
1112             } else {
1113                 int end = bands[i++];
1114                 end = i + end * 2;
1115                 while (i < end) {
1116                     if (x < bands[i++]) return false;
1117                     if (x < bands[i++]) return true;
1118                 }
1119                 return false;
1120             }
1121         }
1122         return false;
1123     }
1124 
1125     /**
1126      * Returns true iff this Region lies inside the indicated
1127      * rectangular area specified in x, y, width, height format
1128      * with appropriate clipping performed as per the dimAdd method.
1129      */
1130     public boolean isInsideXYWH(int x, int y, int w, int h) {
1131         return isInsideXYXY(x, y, dimAdd(x, w), dimAdd(y, h));
1132     }
1133 
1134     /**
1135      * Returns true iff this Region lies inside the indicated
1136      * rectangular area specified in lox, loy, hix, hiy format.
1137      */
1138     public boolean isInsideXYXY(int lox, int loy, int hix, int hiy) {
1139         return (this.lox >= lox && this.loy >= loy &&
1140                 this.hix <= hix && this.hiy <= hiy);
1141 
1142     }
1143 
1144     /**
1145      * Quickly checks if this Region lies inside the specified
1146      * Region object.
1147      * <p>
1148      * This method will return false if the specified Region
1149      * object is not a simple rectangle.
1150      */
1151     public boolean isInsideQuickCheck(Region r) {
1152         return (r.bands == null &&
1153                 r.lox <= this.lox && r.loy <= this.loy &&
1154                 r.hix >= this.hix && r.hiy >= this.hiy);
1155     }
1156 
1157     /**
1158      * Quickly checks if this Region intersects the specified
1159      * rectangular area specified in lox, loy, hix, hiy format.
1160      * <p>
1161      * This method tests only against the bounds of this region
1162      * and does not bother to test if the rectangular region
1163      * actually intersects any bands.
1164      */
1165     public boolean intersectsQuickCheckXYXY(int lox, int loy,
1166                                             int hix, int hiy)
1167     {
1168         return (hix > this.lox && lox < this.hix &&
1169                 hiy > this.loy && loy < this.hiy);
1170     }
1171 
1172     /**
1173      * Quickly checks if this Region intersects the specified
1174      * Region object.
1175      * <p>
1176      * This method tests only against the bounds of this region
1177      * and does not bother to test if the rectangular region
1178      * actually intersects any bands.
1179      */
1180     public boolean intersectsQuickCheck(Region r) {
1181         return (r.hix > this.lox && r.lox < this.hix &&
1182                 r.hiy > this.loy && r.loy < this.hiy);
1183     }
1184 
1185     /**
1186      * Quickly checks if this Region surrounds the specified
1187      * Region object.
1188      * <p>
1189      * This method will return false if this Region object is
1190      * not a simple rectangle.
1191      */
1192     public boolean encompasses(Region r) {
1193         return (this.bands == null &&
1194                 this.lox <= r.lox && this.loy <= r.loy &&
1195                 this.hix >= r.hix && this.hiy >= r.hiy);
1196     }
1197 
1198     /**
1199      * Quickly checks if this Region surrounds the specified
1200      * rectangular area specified in x, y, width, height format.
1201      * <p>
1202      * This method will return false if this Region object is
1203      * not a simple rectangle.
1204      */
1205     public boolean encompassesXYWH(int x, int y, int w, int h) {
1206         return encompassesXYXY(x, y, dimAdd(x, w), dimAdd(y, h));
1207     }
1208 
1209     /**
1210      * Quickly checks if this Region surrounds the specified
1211      * rectangular area specified in lox, loy, hix, hiy format.
1212      * <p>
1213      * This method will return false if this Region object is
1214      * not a simple rectangle.
1215      */
1216     public boolean encompassesXYXY(int lox, int loy, int hix, int hiy) {
1217         return (this.bands == null &&
1218                 this.lox <= lox && this.loy <= loy &&
1219                 this.hix >= hix && this.hiy >= hiy);
1220     }
1221 
1222     /**
1223      * Gets the bbox of the available spans, clipped to the OutputArea.
1224      */
1225     public void getBounds(int pathbox[]) {
1226         pathbox[0] = lox;
1227         pathbox[1] = loy;
1228         pathbox[2] = hix;
1229         pathbox[3] = hiy;
1230     }
1231 
1232     /**
1233      * Clips the indicated bbox array to the bounds of this Region.
1234      */
1235     public void clipBoxToBounds(int bbox[]) {
1236         if (bbox[0] < lox) bbox[0] = lox;
1237         if (bbox[1] < loy) bbox[1] = loy;
1238         if (bbox[2] > hix) bbox[2] = hix;
1239         if (bbox[3] > hiy) bbox[3] = hiy;
1240     }
1241 
1242     /**
1243      * Gets an iterator object to iterate over the spans in this region.
1244      */
1245     public RegionIterator getIterator() {
1246         return new RegionIterator(this);
1247     }
1248 
1249     /**
1250      * Gets a span iterator object that iterates over the spans in this region
1251      */
1252     public SpanIterator getSpanIterator() {
1253         return new RegionSpanIterator(this);
1254     }
1255 
1256     /**
1257      * Gets a span iterator object that iterates over the spans in this region
1258      * but clipped to the bounds given in the argument (xlo, ylo, xhi, yhi).
1259      */
1260     public SpanIterator getSpanIterator(int bbox[]) {
1261         SpanIterator result = getSpanIterator();
1262         result.intersectClipBox(bbox[0], bbox[1], bbox[2], bbox[3]);
1263         return result;
1264     }
1265 
1266     /**
1267      * Returns a SpanIterator that is the argument iterator filtered by
1268      * this region.
1269      */
1270     public SpanIterator filter(SpanIterator si) {
1271         if (bands == null) {
1272             si.intersectClipBox(lox, loy, hix, hiy);
1273         } else {
1274             si = new RegionClipSpanIterator(this, si);
1275         }
1276         return si;
1277     }
1278 
1279     public String toString() {
1280         StringBuffer sb = new StringBuffer();
1281         sb.append("Region[[");
1282         sb.append(lox);
1283         sb.append(", ");
1284         sb.append(loy);
1285         sb.append(" => ");
1286         sb.append(hix);
1287         sb.append(", ");
1288         sb.append(hiy);
1289         sb.append("]");
1290         if (bands != null) {
1291             int col = 0;
1292             while (col < endIndex) {
1293                 sb.append("y{");
1294                 sb.append(bands[col++]);
1295                 sb.append(",");
1296                 sb.append(bands[col++]);
1297                 sb.append("}[");
1298                 int end = bands[col++];
1299                 end = col + end * 2;
1300                 while (col < end) {
1301                     sb.append("x(");
1302                     sb.append(bands[col++]);
1303                     sb.append(", ");
1304                     sb.append(bands[col++]);
1305                     sb.append(")");
1306                 }
1307                 sb.append("]");
1308             }
1309         }
1310         sb.append("]");
1311         return sb.toString();
1312     }
1313 
1314     public int hashCode() {
1315         return (isEmpty() ? 0 : (lox * 3 + loy * 5 + hix * 7 + hiy * 9));
1316     }
1317 
1318     public boolean equals(Object o) {
1319         if (!(o instanceof Region)) {
1320             return false;
1321         }
1322         Region r = (Region) o;
1323         if (this.isEmpty()) {
1324             return r.isEmpty();
1325         } else if (r.isEmpty()) {
1326             return false;
1327         }
1328         if (r.lox != this.lox || r.loy != this.loy ||
1329             r.hix != this.hix || r.hiy != this.hiy)
1330         {
1331             return false;
1332         }
1333         if (this.bands == null) {
1334             return (r.bands == null);
1335         } else if (r.bands == null) {
1336             return false;
1337         }
1338         if (this.endIndex != r.endIndex) {
1339             return false;
1340         }
1341         int abands[] = this.bands;
1342         int bbands[] = r.bands;
1343         for (int i = 0; i < endIndex; i++) {
1344             if (abands[i] != bbands[i]) {
1345                 return false;
1346             }
1347         }
1348         return true;
1349     }
1350 }