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 }