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