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