1 /*
   2  * Copyright (c) 2009, 2011, 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.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 /*
  25  * @test %W% %E%
  26  * @bug 6504874
  27  * @summary This test verifies the operation (and performance) of the
  28  *          various CAG operations on the internal Region class.
  29  * @run main RegionOps
  30  */
  31 
  32 import java.awt.Rectangle;
  33 import java.awt.geom.Area;
  34 import java.awt.geom.AffineTransform;
  35 import java.awt.image.BufferedImage;
  36 import java.util.Random;
  37 import sun.java2d.pipe.Region;
  38 
  39 public class RegionOps {
  40     public static final int DEFAULT_NUMREGIONS = 50;
  41     public static final int DEFAULT_MINSUBRECTS = 1;
  42     public static final int DEFAULT_MAXSUBRECTS = 10;
  43 
  44     public static final int MINCOORD = -20;
  45     public static final int MAXCOORD = 20;
  46 
  47     public static boolean useArea;
  48 
  49     static int numops;
  50     static int numErrors;
  51     static Random rand = new Random();
  52     static boolean skipCheck;
  53     static boolean countErrors;
  54 
  55     static {
  56         // Instantiating BufferedImage initializes sun.java2d
  57         BufferedImage bimg =
  58             new BufferedImage(1, 1, BufferedImage.TYPE_INT_RGB);
  59     }
  60 
  61     public static void usage(String error) {
  62         if (error != null) {
  63             System.err.println("Error: "+error);
  64         }
  65         System.err.println("Usage: java RegionOps "+
  66                            "[-regions N] [-rects M] "+
  67                            "[-[min|max]rects M] [-area]");
  68         System.err.println("                      "+
  69                            "[-add|union] [-sub|diff] "+
  70                            "[-int[ersect]] [-xor]");
  71         System.err.println("                      "+
  72                            "[-seed S] [-nocheck] [-count[errors]] [-help]");
  73         System.exit((error != null) ? 1 : 0);
  74     }
  75 
  76     public static void error(RectListImpl a, RectListImpl b, String problem) {
  77         System.err.println("Operating on:  "+a);
  78         if (b != null) {
  79             System.err.println("and:  "+b);
  80         }
  81         if (countErrors) {
  82             System.err.println(problem);
  83             numErrors++;
  84         } else {
  85             throw new RuntimeException(problem);
  86         }
  87     }
  88 
  89     public static void main(String argv[]) {
  90         int numregions = DEFAULT_NUMREGIONS;
  91         int minsubrects = DEFAULT_MINSUBRECTS;
  92         int maxsubrects = DEFAULT_MAXSUBRECTS;
  93         boolean doUnion = false;
  94         boolean doIntersect = false;
  95         boolean doSubtract = false;
  96         boolean doXor = false;
  97 
  98         for (int i = 0; i < argv.length; i++) {
  99             String arg = argv[i];
 100             if (arg.equalsIgnoreCase("-regions")) {
 101                 if (i+1 >= argv.length) {
 102                     usage("missing arg for -regions");
 103                 }
 104                 numregions = Integer.parseInt(argv[++i]);
 105             } else if (arg.equalsIgnoreCase("-rects")) {
 106                 if (i+1 >= argv.length) {
 107                     usage("missing arg for -rects");
 108                 }
 109                 minsubrects = maxsubrects = Integer.parseInt(argv[++i]);
 110             } else if (arg.equalsIgnoreCase("-minrects")) {
 111                 if (i+1 >= argv.length) {
 112                     usage("missing arg for -minrects");
 113                 }
 114                 minsubrects = Integer.parseInt(argv[++i]);
 115             } else if (arg.equalsIgnoreCase("-maxrects")) {
 116                 if (i+1 >= argv.length) {
 117                     usage("missing arg for -maxrects");
 118                 }
 119                 maxsubrects = Integer.parseInt(argv[++i]);
 120             } else if (arg.equalsIgnoreCase("-area")) {
 121                 useArea = true;
 122             } else if (arg.equalsIgnoreCase("-add") ||
 123                        arg.equalsIgnoreCase("-union"))
 124             {
 125                 doUnion = true;
 126             } else if (arg.equalsIgnoreCase("-sub") ||
 127                        arg.equalsIgnoreCase("-diff"))
 128             {
 129                 doSubtract = true;
 130             } else if (arg.equalsIgnoreCase("-int") ||
 131                        arg.equalsIgnoreCase("-intersect"))
 132             {
 133                 doIntersect = true;
 134             } else if (arg.equalsIgnoreCase("-xor")) {
 135                 doXor = true;
 136             } else if (arg.equalsIgnoreCase("-seed")) {
 137                 if (i+1 >= argv.length) {
 138                     usage("missing arg for -seed");
 139                 }
 140                 rand.setSeed(Long.decode(argv[++i]).longValue());
 141             } else if (arg.equalsIgnoreCase("-nocheck")) {
 142                 skipCheck = true;
 143             } else if (arg.equalsIgnoreCase("-count") ||
 144                        arg.equalsIgnoreCase("-counterrors"))
 145             {
 146                 countErrors = true;
 147             } else if (arg.equalsIgnoreCase("-help")) {
 148                 usage(null);
 149             } else {
 150                 usage("Unknown argument: "+arg);
 151             }
 152         }
 153 
 154         if (maxsubrects < minsubrects) {
 155             usage("maximum number of subrectangles less than minimum");
 156         }
 157 
 158         if (minsubrects <= 0) {
 159             usage("minimum number of subrectangles must be positive");
 160         }
 161 
 162         if (!doUnion && !doSubtract && !doIntersect && !doXor) {
 163             doUnion = doSubtract = doIntersect = doXor = true;
 164         }
 165 
 166         long start = System.currentTimeMillis();
 167         RectListImpl rlist[] = new RectListImpl[numregions];
 168         int totalrects = 0;
 169         for (int i = 0; i < rlist.length; i++) {
 170             RectListImpl rli = RectListImpl.getInstance();
 171             int numsubrects =
 172                 minsubrects + rand.nextInt(maxsubrects - minsubrects + 1);
 173             for (int j = 0; j < numsubrects; j++) {
 174                 addRectTo(rli);
 175                 totalrects++;
 176             }
 177             rlist[i] = rli;
 178         }
 179         long end = System.currentTimeMillis();
 180         System.out.println((end-start)+"ms to create "+
 181                            rlist.length+" regions containing "+
 182                            totalrects+" subrectangles");
 183 
 184         start = System.currentTimeMillis();
 185         for (int i = 0; i < rlist.length; i++) {
 186             RectListImpl a = rlist[i];
 187             testTranslate(a);
 188             for (int j = i; j < rlist.length; j++) {
 189                 RectListImpl b = rlist[j];
 190                 if (doUnion) testUnion(a, b);
 191                 if (doSubtract) testDifference(a, b);
 192                 if (doIntersect) testIntersection(a, b);
 193                 if (doXor) testExclusiveOr(a, b);
 194             }
 195         }
 196         end = System.currentTimeMillis();
 197         System.out.println(numops+" ops took "+(end-start)+"ms");
 198 
 199         if (numErrors > 0) {
 200             throw new RuntimeException(numErrors+" errors encountered");
 201         }
 202     }
 203 
 204     public static void addRectTo(RectListImpl rli) {
 205         int lox = MINCOORD + rand.nextInt(MAXCOORD - MINCOORD + 1);
 206         int hix = MINCOORD + rand.nextInt(MAXCOORD - MINCOORD + 1);
 207         int loy = MINCOORD + rand.nextInt(MAXCOORD - MINCOORD + 1);
 208         int hiy = MINCOORD + rand.nextInt(MAXCOORD - MINCOORD + 1);
 209         rli.addRect(lox, loy, hix, hiy);
 210     }
 211 
 212     public static void checkEqual(RectListImpl a, RectListImpl b,
 213                                   String optype)
 214     {
 215         if (a.hashCode() != b.hashCode()) {
 216             error(a, b, "hashcode failed for "+optype);
 217         }
 218         if (!a.equals(b)) {
 219             error(a, b, "equals failed for "+optype);
 220         }
 221     }
 222 
 223     public static void testTranslate(RectListImpl a) {
 224         RectListImpl maxTrans =
 225             a.getTranslation(Integer.MAX_VALUE, Integer.MAX_VALUE)
 226             .getTranslation(Integer.MAX_VALUE, Integer.MAX_VALUE)
 227             .getTranslation(Integer.MAX_VALUE, Integer.MAX_VALUE);
 228         if (!maxTrans.checkTransEmpty()) {
 229             error(maxTrans, null, "overflow translated RectList not empty");
 230         }
 231         RectListImpl minTrans =
 232             a.getTranslation(Integer.MIN_VALUE, Integer.MIN_VALUE)
 233             .getTranslation(Integer.MIN_VALUE, Integer.MIN_VALUE)
 234             .getTranslation(Integer.MIN_VALUE, Integer.MIN_VALUE);
 235         if (!minTrans.checkTransEmpty()) {
 236             error(minTrans, null, "overflow translated RectList not empty");
 237         }
 238         testTranslate(a, Integer.MAX_VALUE, Integer.MAX_VALUE, false,
 239                       MINCOORD, 0, MINCOORD, 0);
 240         testTranslate(a, Integer.MAX_VALUE, Integer.MIN_VALUE, false,
 241                       MINCOORD, 0, 0, MAXCOORD);
 242         testTranslate(a, Integer.MIN_VALUE, Integer.MAX_VALUE, false,
 243                       0, MAXCOORD, MINCOORD, 0);
 244         testTranslate(a, Integer.MIN_VALUE, Integer.MIN_VALUE, false,
 245                       0, MAXCOORD, 0, MAXCOORD);
 246         for (int dy = -100; dy <= 100; dy += 50) {
 247             for (int dx = -100; dx <= 100; dx += 50) {
 248                 testTranslate(a, dx, dy, true,
 249                               MINCOORD, MAXCOORD,
 250                               MINCOORD, MAXCOORD);
 251             }
 252         }
 253     }
 254 
 255     public static void testTranslate(RectListImpl a, int dx, int dy,
 256                                      boolean isNonDestructive,
 257                                      int xmin, int xmax,
 258                                      int ymin, int ymax)
 259     {
 260         RectListImpl theTrans = a.getTranslation(dx, dy); numops++;
 261         if (skipCheck) return;
 262         RectListImpl unTrans = theTrans.getTranslation(-dx, -dy);
 263         if (isNonDestructive) checkEqual(a, unTrans, "Translate");
 264         for (int x = xmin; x < xmax; x++) {
 265             for (int y = ymin; y < ymax; y++) {
 266                 boolean inside = a.contains(x, y);
 267                 if (theTrans.contains(x+dx, y+dy) != inside) {
 268                     error(a, null, "translation failed for "+
 269                           dx+", "+dy+" at "+x+", "+y);
 270                 }
 271             }
 272         }
 273     }
 274 
 275     public static void testUnion(RectListImpl a, RectListImpl b) {
 276         RectListImpl aUb = a.getUnion(b); numops++;
 277         RectListImpl bUa = b.getUnion(a); numops++;
 278         if (skipCheck) return;
 279         checkEqual(aUb, bUa, "Union");
 280         testUnion(a, b, aUb);
 281         testUnion(a, b, bUa);
 282     }
 283 
 284     public static void testUnion(RectListImpl a, RectListImpl b,
 285                                  RectListImpl theUnion)
 286     {
 287         for (int x = MINCOORD; x < MAXCOORD; x++) {
 288             for (int y = MINCOORD; y < MAXCOORD; y++) {
 289                 boolean inside = (a.contains(x, y) || b.contains(x, y));
 290                 if (theUnion.contains(x, y) != inside) {
 291                     error(a, b, "union failed at "+x+", "+y);
 292                 }
 293             }
 294         }
 295     }
 296 
 297     public static void testDifference(RectListImpl a, RectListImpl b) {
 298         RectListImpl aDb = a.getDifference(b); numops++;
 299         RectListImpl bDa = b.getDifference(a); numops++;
 300         if (skipCheck) return;
 301         // Note that difference is not commutative so we cannot check equals
 302         // checkEqual(a, b, "Difference");
 303         testDifference(a, b, aDb);
 304         testDifference(b, a, bDa);
 305     }
 306 
 307     public static void testDifference(RectListImpl a, RectListImpl b,
 308                                       RectListImpl theDifference)
 309     {
 310         for (int x = MINCOORD; x < MAXCOORD; x++) {
 311             for (int y = MINCOORD; y < MAXCOORD; y++) {
 312                 boolean inside = (a.contains(x, y) && !b.contains(x, y));
 313                 if (theDifference.contains(x, y) != inside) {
 314                     error(a, b, "difference failed at "+x+", "+y);
 315                 }
 316             }
 317         }
 318     }
 319 
 320     public static void testIntersection(RectListImpl a, RectListImpl b) {
 321         RectListImpl aIb = a.getIntersection(b); numops++;
 322         RectListImpl bIa = b.getIntersection(a); numops++;
 323         if (skipCheck) return;
 324         checkEqual(aIb, bIa, "Intersection");
 325         testIntersection(a, b, aIb);
 326         testIntersection(a, b, bIa);
 327     }
 328 
 329     public static void testIntersection(RectListImpl a, RectListImpl b,
 330                                         RectListImpl theIntersection)
 331     {
 332         for (int x = MINCOORD; x < MAXCOORD; x++) {
 333             for (int y = MINCOORD; y < MAXCOORD; y++) {
 334                 boolean inside = (a.contains(x, y) && b.contains(x, y));
 335                 if (theIntersection.contains(x, y) != inside) {
 336                     error(a, b, "intersection failed at "+x+", "+y);
 337                 }
 338             }
 339         }
 340     }
 341 
 342     public static void testExclusiveOr(RectListImpl a, RectListImpl b) {
 343         RectListImpl aXb = a.getExclusiveOr(b); numops++;
 344         RectListImpl bXa = b.getExclusiveOr(a); numops++;
 345         if (skipCheck) return;
 346         checkEqual(aXb, bXa, "ExclusiveOr");
 347         testExclusiveOr(a, b, aXb);
 348         testExclusiveOr(a, b, bXa);
 349     }
 350 
 351     public static void testExclusiveOr(RectListImpl a, RectListImpl b,
 352                                        RectListImpl theExclusiveOr)
 353     {
 354         for (int x = MINCOORD; x < MAXCOORD; x++) {
 355             for (int y = MINCOORD; y < MAXCOORD; y++) {
 356                 boolean inside = (a.contains(x, y) != b.contains(x, y));
 357                 if (theExclusiveOr.contains(x, y) != inside) {
 358                     error(a, b, "xor failed at "+x+", "+y);
 359                 }
 360             }
 361         }
 362     }
 363 
 364     public abstract static class RectListImpl {
 365         public static RectListImpl getInstance() {
 366             if (useArea) {
 367                 return new AreaImpl();
 368             } else {
 369                 return new RegionImpl();
 370             }
 371         }
 372 
 373         public abstract void addRect(int lox, int loy, int hix, int hiy);
 374 
 375         public abstract RectListImpl getTranslation(int dx, int dy);
 376 
 377         public abstract RectListImpl getIntersection(RectListImpl rli);
 378         public abstract RectListImpl getExclusiveOr(RectListImpl rli);
 379         public abstract RectListImpl getDifference(RectListImpl rli);
 380         public abstract RectListImpl getUnion(RectListImpl rli);
 381 
 382         // Used for making sure that 3xMAX translates yields an empty region
 383         public abstract boolean checkTransEmpty();
 384 
 385         public abstract boolean contains(int x, int y);
 386 
 387         public abstract int hashCode();
 388         public abstract boolean equals(RectListImpl other);
 389     }
 390 
 391     public static class AreaImpl extends RectListImpl {
 392         Area theArea;
 393 
 394         public AreaImpl() {
 395         }
 396 
 397         public AreaImpl(Area a) {
 398             theArea = a;
 399         }
 400 
 401         public void addRect(int lox, int loy, int hix, int hiy) {
 402             Area a2 = new Area(new Rectangle(lox, loy, hix-lox, hiy-loy));
 403             if (theArea == null) {
 404                 theArea = a2;
 405             } else {
 406                 theArea.add(a2);
 407             }
 408         }
 409 
 410         public RectListImpl getTranslation(int dx, int dy) {
 411             AffineTransform at = AffineTransform.getTranslateInstance(dx, dy);
 412             return new AreaImpl(theArea.createTransformedArea(at));
 413         }
 414 
 415         public RectListImpl getIntersection(RectListImpl rli) {
 416             Area a2 = new Area(theArea);
 417             a2.intersect(((AreaImpl) rli).theArea);
 418             return new AreaImpl(a2);
 419         }
 420 
 421         public RectListImpl getExclusiveOr(RectListImpl rli) {
 422             Area a2 = new Area(theArea);
 423             a2.exclusiveOr(((AreaImpl) rli).theArea);
 424             return new AreaImpl(a2);
 425         }
 426 
 427         public RectListImpl getDifference(RectListImpl rli) {
 428             Area a2 = new Area(theArea);
 429             a2.subtract(((AreaImpl) rli).theArea);
 430             return new AreaImpl(a2);
 431         }
 432 
 433         public RectListImpl getUnion(RectListImpl rli) {
 434             Area a2 = new Area(theArea);
 435             a2.add(((AreaImpl) rli).theArea);
 436             return new AreaImpl(a2);
 437         }
 438 
 439         // Used for making sure that 3xMAX translates yields an empty region
 440         public boolean checkTransEmpty() {
 441             // Area objects will actually survive 3 MAX translates so just
 442             // pretend that it had the intended effect...
 443             return true;
 444         }
 445 
 446         public boolean contains(int x, int y) {
 447             return theArea.contains(x, y);
 448         }
 449 
 450         public int hashCode() {
 451             // Area does not override hashCode...
 452             return 0;
 453         }
 454 
 455         public boolean equals(RectListImpl other) {
 456             return theArea.equals(((AreaImpl) other).theArea);
 457         }
 458 
 459         public String toString() {
 460             return theArea.toString();
 461         }
 462     }
 463 
 464     public static class RegionImpl extends RectListImpl {
 465         Region theRegion;
 466 
 467         public RegionImpl() {
 468         }
 469 
 470         public RegionImpl(Region r) {
 471             theRegion = r;
 472         }
 473 
 474         public void addRect(int lox, int loy, int hix, int hiy) {
 475             Region r2 = Region.getInstanceXYXY(lox, loy, hix, hiy);
 476             if (theRegion == null) {
 477                 theRegion = r2;
 478             } else {
 479                 theRegion = theRegion.getUnion(r2);
 480             }
 481         }
 482 
 483         public RectListImpl getTranslation(int dx, int dy) {
 484             return new RegionImpl(theRegion.getTranslatedRegion(dx, dy));
 485         }
 486 
 487         public RectListImpl getIntersection(RectListImpl rli) {
 488             Region r2 = ((RegionImpl) rli).theRegion;
 489             r2 = theRegion.getIntersection(r2);
 490             return new RegionImpl(r2);
 491         }
 492 
 493         public RectListImpl getExclusiveOr(RectListImpl rli) {
 494             Region r2 = ((RegionImpl) rli).theRegion;
 495             r2 = theRegion.getExclusiveOr(r2);
 496             return new RegionImpl(r2);
 497         }
 498 
 499         public RectListImpl getDifference(RectListImpl rli) {
 500             Region r2 = ((RegionImpl) rli).theRegion;
 501             r2 = theRegion.getDifference(r2);
 502             return new RegionImpl(r2);
 503         }
 504 
 505         public RectListImpl getUnion(RectListImpl rli) {
 506             Region r2 = ((RegionImpl) rli).theRegion;
 507             r2 = theRegion.getUnion(r2);
 508             return new RegionImpl(r2);
 509         }
 510 
 511         // Used for making sure that 3xMAX translates yields an empty region
 512         public boolean checkTransEmpty() {
 513             // Region objects should be empty after 3 MAX translates...
 514             return theRegion.isEmpty();
 515         }
 516 
 517         public boolean contains(int x, int y) {
 518             return theRegion.contains(x, y);
 519         }
 520 
 521         public int hashCode() {
 522             return theRegion.hashCode();
 523         }
 524 
 525         public boolean equals(RectListImpl other) {
 526             return theRegion.equals(((RegionImpl) other).theRegion);
 527         }
 528 
 529         public String toString() {
 530             return theRegion.toString();
 531         }
 532     }
 533 }