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