1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 /** 18 * @author Denis M. Kishenko 19 * @version $Revision$ 20 */ 21 package org.apache.harmony.awt.gl; 22 23 import java.awt.Rectangle; 24 25 public class MultiRectAreaOp { 26 27 /** 28 * Rectangle buffer capacity 29 */ 30 public static final int RECT_CAPACITY = 16; 31 32 /** 33 * If number of rectangle in MultiRectArea object less than MAX_SIMPLE simple algorithm applies 34 */ 35 private static final int MAX_SIMPLE = 8; 36 37 /** 38 * Create buffer 39 */ 40 public static int[] createBuf(int capacity) { 41 if (capacity == 0) { 42 capacity = RECT_CAPACITY; 43 } 44 int[] buf = new int[capacity]; 45 buf[0] = 1; 46 return buf; 47 } 48 49 /** 50 * Checks buffer size and reallocate if necessary 51 */ 52 public static int[] checkBufSize(int[] buf, int capacity) { 53 if (buf[0] + capacity >= buf.length) { 54 int length = buf[0] + (capacity > RECT_CAPACITY ? capacity : RECT_CAPACITY); 55 int[] tmp = new int[length]; 56 System.arraycopy(buf, 0, tmp, 0, buf[0]); 57 buf = tmp; 58 } 59 buf[0] += capacity; 60 return buf; 61 } 62 63 /** 64 * Region class provides basic functionlity for MultiRectArea objects to make logical operations 65 */ 66 static class Region { 67 68 int[] region; 69 int[] active; 70 int[] bottom; 71 int index; 72 73 public Region(int[] region) { 74 this.region = region; 75 active = new int[RECT_CAPACITY]; 76 bottom = new int[RECT_CAPACITY]; 77 active[0] = 1; 78 bottom[0] = 1; 79 index = 1; 80 } 81 82 void addActive(int index) { 83 int length = active[0]; 84 active = checkBufSize(active, 4); 85 int i = 1; 86 87 while(i < length) { 88 if (region[index] < active[i]) { 89 // Insert 90 System.arraycopy(active, i, active, i + 4, length - i); 91 length = i; 92 break; 93 } 94 i += 4; 95 } 96 System.arraycopy(region, index, active, length, 4); 97 98 } 99 100 void findActive(int top, int bottom) { 101 while(index < region[0]) { 102 if (region[index + 1] > bottom) { // y1 > bottom 103 return; 104 } 105 if (region[index + 3] >= top) { // y2 >= top 106 addActive(index); 107 } 108 index += 4; 109 } 110 } 111 112 void deleteActive(int bottom) { 113 int length = active[0]; 114 for(int i = 1; i < length;) { 115 if (active[i + 3] == bottom) { 116 length -= 4; 117 if (i < length) { 118 System.arraycopy(active, i + 4, active, i, length - i); 119 } 120 } else { 121 i += 4; 122 } 123 } 124 active[0] = length; 125 } 126 127 void deleteActive() { 128 int length = active[0]; 129 for(int i = length - 4; i > 0; i -= 4) { 130 if (active[i + 1] > active[i + 3]) { 131 length -= 4; 132 if (i < length) { 133 System.arraycopy(active, i + 4, active, i, length - i); 134 } 135 } 136 } 137 active[0] = length; 138 } 139 140 void createLevel(int[] level) { 141 int levelCount = 1; 142 int topIndex = 1; 143 int i = 1; 144 while(i < region[0]) { 145 146 int top = region[i + 1]; 147 int bottom = region[i + 3] + 1; 148 int j = topIndex; 149 150 addTop: { 151 while(j < levelCount) { 152 if (level[j] == top) { 153 break addTop; 154 } 155 if (level[j] > top) { 156 System.arraycopy(level, j, level, j + 1, levelCount - j); 157 break; 158 } 159 j++; 160 } 161 162 level[j] = top; 163 levelCount++; 164 topIndex = j; 165 } 166 167 addBottom: { 168 while(j < levelCount) { 169 if (level[j] == bottom) { 170 break addBottom; 171 } 172 if (level[j] > bottom) { 173 System.arraycopy(level, j, level, j + 1, levelCount - j); 174 break; 175 } 176 j++; 177 }; 178 179 level[j] = bottom; 180 levelCount++; 181 } 182 183 i += 4; 184 } 185 level[0] = levelCount; 186 } 187 188 static void sortOrdered(int[] src1, int[] src2, int[] dst) { 189 int length1 = src1[0]; 190 int length2 = src2[0]; 191 int count = 1; 192 int i1 = 1; 193 int i2 = 1; 194 int v1 = src1[1]; 195 int v2 = src2[1]; 196 while(true) { 197 198 LEFT: { 199 while(i1 < length1) { 200 v1 = src1[i1]; 201 if (v1 >= v2) { 202 break LEFT; 203 } 204 dst[count++] = v1; 205 i1++; 206 } 207 while(i2 < length2) { 208 dst[count++] = src2[i2++]; 209 } 210 dst[0] = count; 211 return; 212 } 213 214 RIGHT: { 215 while(i2 < length2) { 216 v2 = src2[i2]; 217 if (v2 >= v1) { 218 break RIGHT; 219 } 220 dst[count++] = v2; 221 i2++; 222 } 223 while(i1 < length1) { 224 dst[count++] = src1[i1++]; 225 } 226 dst[0] = count; 227 return; 228 } 229 230 if (v1 == v2) { 231 dst[count++] = v1; 232 i1++; 233 i2++; 234 if (i1 < length1) { 235 v1 = src1[i1]; 236 } 237 if (i2 < length2 - 1) { 238 v2 = src2[i2]; 239 } 240 } 241 } 242 // UNREACHABLE 243 } 244 245 } 246 247 /** 248 * Intersection class provides intersection of two MultiRectAre aobjects 249 */ 250 static class Intersection { 251 252 static void intersectRegions(int[] reg1, int[] reg2, MultiRectArea.RectCash dst, int height1, int height2) { 253 254 Region d1 = new Region(reg1); 255 Region d2 = new Region(reg2); 256 257 int[] level = new int[height1 + height2]; 258 int[] level1 = new int[height1]; 259 int[] level2 = new int[height2]; 260 d1.createLevel(level1); 261 d2.createLevel(level2); 262 Region.sortOrdered(level1, level2, level); 263 264 int top; 265 int bottom = level[1] - 1; 266 for(int i = 2; i < level[0]; i++) { 267 268 top = bottom + 1; 269 bottom = level[i] - 1; 270 271 d1.findActive(top, bottom); 272 d2.findActive(top, bottom); 273 274 int i1 = 1; 275 int i2 = 1; 276 277 while(i1 < d1.active[0] && i2 < d2.active[0]) { 278 279 int x11 = d1.active[i1]; 280 int x12 = d1.active[i1 + 2]; 281 int x21 = d2.active[i2]; 282 int x22 = d2.active[i2 + 2]; 283 284 if (x11 <= x21) { 285 if (x12 >= x21) { 286 if (x12 <= x22) { 287 dst.addRectCashed(x21, top, x12, bottom); 288 i1 += 4; 289 } else { 290 dst.addRectCashed(x21, top, x22, bottom); 291 i2 += 4; 292 } 293 } else { 294 i1 += 4; 295 } 296 } else { 297 if (x22 >= x11) { 298 if (x22 <= x12) { 299 dst.addRectCashed(x11, top, x22, bottom); 300 i2 += 4; 301 } else { 302 dst.addRectCashed(x11, top, x12, bottom); 303 i1 += 4; 304 } 305 } else { 306 i2 += 4; 307 } 308 } 309 } 310 311 d1.deleteActive(bottom); 312 d2.deleteActive(bottom); 313 } 314 } 315 316 static int[] simpleIntersect(MultiRectArea src1, MultiRectArea src2) { 317 int[] rect1 = src1.rect; 318 int[] rect2 = src2.rect; 319 int[] rect = createBuf(0); 320 321 int k = 1; 322 for(int i = 1; i < rect1[0];) { 323 324 int x11 = rect1[i++]; 325 int y11 = rect1[i++]; 326 int x12 = rect1[i++]; 327 int y12 = rect1[i++]; 328 329 for(int j = 1; j < rect2[0];) { 330 331 int x21 = rect2[j++]; 332 int y21 = rect2[j++]; 333 int x22 = rect2[j++]; 334 int y22 = rect2[j++]; 335 336 if (x11 <= x22 && x12 >= x21 && 337 y11 <= y22 && y12 >= y21) 338 { 339 rect = checkBufSize(rect, 4); 340 rect[k++] = x11 > x21 ? x11 : x21; 341 rect[k++] = y11 > y21 ? y11 : y21; 342 rect[k++] = x12 > x22 ? x22 : x12; 343 rect[k++] = y12 > y22 ? y22 : y12; 344 } 345 } 346 } 347 348 rect[0] = k; 349 return rect; 350 } 351 352 public static MultiRectArea getResult(MultiRectArea src1, MultiRectArea src2) { 353 354 if (src1 == null || src2 == null || src1.isEmpty() || src2.isEmpty()) { 355 return new MultiRectArea(); 356 } 357 358 MultiRectArea.RectCash dst = new MultiRectArea.RectCash(); 359 360 if (!src1.sorted || !src2.sorted || 361 src1.getRectCount() <= MAX_SIMPLE || src2.getRectCount() <= MAX_SIMPLE) 362 { 363 dst.setRect(simpleIntersect(src1, src2), false); 364 } else { 365 Rectangle bounds1 = src1.getBounds(); 366 Rectangle bounds2 = src2.getBounds(); 367 Rectangle bounds3 = bounds1.intersection(bounds2); 368 if (bounds3.width > 0 && bounds3.height > 0) { 369 intersectRegions(src1.rect, src2.rect, dst, bounds1.height + 2, bounds2.height + 2); 370 } 371 } 372 373 return dst; 374 } 375 376 } 377 378 /** 379 * Union class provides union of two MultiRectAre aobjects 380 */ 381 static class Union { 382 383 int rx1, rx2; 384 int top, bottom; 385 MultiRectArea.RectCash dst; 386 387 boolean next(Region d, int index) { 388 int x1 = d.active[index]; 389 int x2 = d.active[index + 2]; 390 boolean res = false; 391 392 if (x2 < rx1 - 1) { 393 res = true; 394 dst.addRectCashed(x1, top, x2, bottom); 395 } else 396 if (x1 > rx2 + 1) { 397 res = false; 398 dst.addRectCashed(rx1, top, rx2, bottom); 399 rx1 = x1; 400 rx2 = x2; 401 } else { 402 res = x2 <= rx2; 403 rx1 = Math.min(x1, rx1); 404 rx2 = Math.max(x2, rx2); 405 } 406 407 // Top 408 if (d.active[index + 1] < top) { 409 dst.addRectCashed(x1, d.active[index + 1], x2, top - 1); 410 } 411 // Bottom 412 if (d.active[index + 3] > bottom) { 413 d.active[index + 1] = bottom + 1; 414 } 415 return res; 416 } 417 418 void check(Region d, int index, boolean t) { 419 int x1 = d.active[index]; 420 int x2 = d.active[index + 2]; 421 // Top 422 if (d.active[index + 1] < top) { 423 dst.addRectCashed(x1, d.active[index + 1], x2, top - 1); 424 } 425 if (t) { 426 dst.addRectCashed(x1, top, x2, bottom); 427 } 428 // Bottom 429 if (d.active[index + 3] > bottom) { 430 d.active[index + 1] = bottom + 1; 431 } 432 } 433 434 void unionRegions(int[] reg1, int[] reg2, int height1, int height2) { 435 Region d1 = new Region(reg1); 436 Region d2 = new Region(reg2); 437 438 int[] level = new int[height1 + height2]; 439 int[] level1 = new int[height1]; 440 int[] level2 = new int[height2]; 441 d1.createLevel(level1); 442 d2.createLevel(level2); 443 Region.sortOrdered(level1, level2, level); 444 445 bottom = level[1] - 1; 446 for(int i = 2; i < level[0]; i++) { 447 448 top = bottom + 1; 449 bottom = level[i] - 1; 450 451 d1.findActive(top, bottom); 452 d2.findActive(top, bottom); 453 454 int i1 = 1; 455 int i2 = 1; 456 boolean res1, res2; 457 458 if (d1.active[0] > 1) { 459 check(d1, 1, false); 460 rx1 = d1.active[1]; 461 rx2 = d1.active[3]; 462 i1 += 4; 463 res1 = false; 464 res2 = true; 465 } else 466 if (d2.active[0] > 1) { 467 check(d2, 1, false); 468 rx1 = d2.active[1]; 469 rx2 = d2.active[3]; 470 i2 += 4; 471 res1 = true; 472 res2 = false; 473 } else { 474 continue; 475 } 476 477 outer: 478 while(true) { 479 480 while (res1) { 481 if (i1 >= d1.active[0]) { 482 dst.addRectCashed(rx1, top, rx2, bottom); 483 while(i2 < d2.active[0]) { 484 check(d2, i2, true); 485 i2 += 4; 486 } 487 break outer; 488 } 489 res1 = next(d1, i1); 490 i1 += 4; 491 } 492 493 while (res2) { 494 if (i2 >= d2.active[0]) { 495 dst.addRectCashed(rx1, top, rx2, bottom); 496 while(i1 < d1.active[0]) { 497 check(d1, i1, true); 498 i1 += 4; 499 } 500 break outer; 501 } 502 res2 = next(d2, i2); 503 i2 += 4; 504 } 505 506 res1 = true; 507 res2 = true; 508 } // while 509 510 d1.deleteActive(bottom); 511 d2.deleteActive(bottom); 512 513 } 514 } 515 516 static void simpleUnion(MultiRectArea src1, MultiRectArea src2, MultiRectArea dst) { 517 if (src1.getRectCount() < src2.getRectCount()) { 518 simpleUnion(src2, src1, dst); 519 } else { 520 Subtraction.simpleSubtract(src1, src2, dst); 521 int pos = dst.rect[0]; 522 int size = src2.rect[0] - 1; 523 dst.rect = checkBufSize(dst.rect, size); 524 System.arraycopy(src2.rect,1, dst.rect, pos, size); 525 dst.resort(); 526 } 527 } 528 529 MultiRectArea getResult(MultiRectArea src1, MultiRectArea src2) { 530 531 if (src1 == null || src1.isEmpty()) { 532 return new MultiRectArea(src2); 533 } 534 535 if (src2 == null || src2.isEmpty()) { 536 return new MultiRectArea(src1); 537 } 538 539 dst = new MultiRectArea.RectCash(); 540 541 if (!src1.sorted || !src2.sorted || 542 src1.getRectCount() <= MAX_SIMPLE || src2.getRectCount() <= MAX_SIMPLE) 543 { 544 simpleUnion(src1, src2, dst); 545 } else { 546 Rectangle bounds1 = src1.getBounds(); 547 Rectangle bounds2 = src2.getBounds(); 548 Rectangle bounds3 = bounds1.intersection(bounds2); 549 550 if (bounds3.width < 0 || bounds3.height < 0) { 551 if (bounds1.y + bounds1.height < bounds2.y) { 552 dst.setRect(addVerRegion(src1.rect, src2.rect), false); 553 } else 554 if (bounds2.y + bounds2.height < bounds1.y) { 555 dst.setRect(addVerRegion(src2.rect, src1.rect), false); 556 } else 557 if (bounds1.x < bounds2.x) { 558 dst.setRect(addHorRegion(src1.rect, src2.rect), false); 559 } else { 560 dst.setRect(addHorRegion(src2.rect, src1.rect), false); 561 } 562 } else { 563 unionRegions(src1.rect, src2.rect, bounds1.height + 2, bounds2.height + 2); 564 } 565 } 566 567 return dst; 568 } 569 570 int[] addVerRegion(int[] top, int[] bottom) { 571 int length = top[0] + bottom[0] - 1; 572 int[] dst = new int[length]; 573 dst[0] = length; 574 System.arraycopy(top, 1, dst, 1, top[0] - 1); 575 System.arraycopy(bottom, 1, dst, top[0], bottom[0] - 1); 576 return dst; 577 } 578 579 int[] addHorRegion(int[] left, int[] right) { 580 int count1 = left[0]; 581 int count2 = right[0]; 582 int[] dst = new int[count1 + count2 + 1]; 583 int count = 1; 584 int index1 = 1; 585 int index2 = 1; 586 587 int top1 = left[2]; 588 int top2 = right[2]; 589 int pos1, pos2; 590 591 while(true) { 592 593 if (index1 >= count1) { 594 System.arraycopy(right, index2, dst, count, count2 - index2); 595 count += count2 - index2; 596 break; 597 } 598 if (index2 >= count2) { 599 System.arraycopy(left, index1, dst, count, count1 - index1); 600 count += count1 - index1; 601 break; 602 } 603 604 if (top1 < top2) { 605 pos1 = index1; 606 do { 607 index1 += 4; 608 } while (index1 < count1 && (top1 = left[index1 + 1]) < top2); 609 System.arraycopy(left, pos1, dst, count, index1 - pos1); 610 count += index1 - pos1; 611 continue; 612 } 613 614 if (top1 > top2) { 615 pos2 = index2; 616 do { 617 index2 += 4; 618 } while (index2 < count2 && (top2 = right[index2 + 1]) < top1); 619 System.arraycopy(right, pos2, dst, count, index2 - pos2); 620 count += index2 - pos2; 621 continue; 622 } 623 624 int top = top1; 625 pos1 = index1; 626 pos2 = index2; 627 do { 628 index1 += 4; 629 } while(index1 < count1 && (top1 = left[index1 + 1]) == top); 630 do { 631 index2 += 4; 632 } while(index2 < count2 && (top2 = right[index2 + 1]) == top); 633 634 System.arraycopy(left, pos1, dst, count, index1 - pos1); 635 count += index1 - pos1; 636 System.arraycopy(right, pos2, dst, count, index2 - pos2); 637 count += index2 - pos2; 638 } 639 640 dst[0] = count; 641 return dst; 642 } 643 644 } 645 646 /** 647 * Subtraction class provides subtraction of two MultiRectAre aobjects 648 */ 649 static class Subtraction { 650 651 static void subtractRegions(int[] reg1, int[] reg2, MultiRectArea.RectCash dst, int height1, int height2) { 652 Region d1 = new Region(reg1); 653 Region d2 = new Region(reg2); 654 655 int[] level = new int[height1 + height2]; 656 int[] level1 = new int[height1]; 657 int[] level2 = new int[height2]; 658 d1.createLevel(level1); 659 d2.createLevel(level2); 660 Region.sortOrdered(level1, level2, level); 661 662 int top; 663 int bottom = level[1] - 1; 664 for(int i = 2; i < level[0]; i++) { 665 666 top = bottom + 1; 667 bottom = level[i] - 1; 668 669 d1.findActive(top, bottom); 670 if (d1.active[0] == 1) { 671 d2.deleteActive(bottom); 672 continue; 673 } 674 675 d2.findActive(top, bottom); 676 677 int i1 = 1; 678 int i2 = 1; 679 680 int rx1 = 0; 681 int rx2 = 0; 682 683 boolean next = true; 684 685 while(true) { 686 687 if (next) { 688 next = false; 689 if (i1 >= d1.active[0]) { 690 break; 691 } 692 // Bottom 693 d1.active[i1 + 1] = bottom + 1; 694 rx1 = d1.active[i1]; 695 rx2 = d1.active[i1 + 2]; 696 i1 += 4; 697 } 698 699 if (i2 >= d2.active[0]) { 700 dst.addRectCashed(rx1, top, rx2, bottom); 701 for(int j = i1; j < d1.active[0]; j += 4) { 702 dst.addRectCashed(d1.active[j], top, d1.active[j + 2], bottom); 703 d1.active[j + 1] = bottom + 1; 704 } 705 break; 706 } 707 708 int x1 = d2.active[i2]; 709 int x2 = d2.active[i2 + 2]; 710 711 if (rx1 < x1) { 712 if (rx2 >= x1) { 713 if (rx2 <= x2) { 714 // [-----------] 715 // [-------------] 716 dst.addRectCashed(rx1, top, x1 - 1, bottom); 717 next = true; 718 } else { 719 // [-----------------] 720 // [------] 721 dst.addRectCashed(rx1, top, x1 - 1, bottom); 722 rx1 = x2 + 1; 723 i2 += 4; 724 } 725 } else { 726 // [-----] 727 // [----] 728 dst.addRectCashed(rx1, top, rx2, bottom); 729 next = true; 730 } 731 } else { 732 if (rx1 <= x2) { 733 if (rx2 <= x2) { 734 // [------] 735 // [-----------] 736 next = true; 737 } else { 738 // [------------] 739 // [---------] 740 rx1 = x2 + 1; 741 i2 += 4; 742 } 743 } else { 744 // [----] 745 // [-----] 746 i2 += 4; 747 } 748 } 749 750 } 751 d1.deleteActive(); 752 d2.deleteActive(bottom); 753 } 754 } 755 756 static void subtractRect(int x11, int y11, int x12, int y12, int[] rect, int index, MultiRectArea dst) { 757 758 for(int i = index; i < rect[0]; i += 4) { 759 int x21 = rect[i + 0]; 760 int y21 = rect[i + 1]; 761 int x22 = rect[i + 2]; 762 int y22 = rect[i + 3]; 763 764 if (x11 <= x22 && x12 >= x21 && y11 <= y22 && y12 >= y21) { 765 int top, bottom; 766 if (y11 < y21) { 767 subtractRect(x11, y11, x12, y21 - 1, rect, i + 4, dst); 768 top = y21; 769 } else { 770 top = y11; 771 } 772 if (y12 > y22) { 773 subtractRect(x11, y22 + 1, x12, y12, rect, i + 4, dst); 774 bottom = y22; 775 } else { 776 bottom = y12; 777 } 778 if (x11 < x21) { 779 subtractRect(x11, top, x21 - 1, bottom, rect, i + 4, dst); 780 } 781 if (x12 > x22) { 782 subtractRect(x22 + 1, top, x12, bottom, rect, i + 4, dst); 783 } 784 return; 785 } 786 } 787 dst.addRect(x11, y11, x12, y12); 788 } 789 790 static void simpleSubtract(MultiRectArea src1, MultiRectArea src2, MultiRectArea dst) { 791 for(int i = 1; i < src1.rect[0]; i += 4) { 792 subtractRect( 793 src1.rect[i + 0], 794 src1.rect[i + 1], 795 src1.rect[i + 2], 796 src1.rect[i + 3], 797 src2.rect, 798 1, 799 dst); 800 } 801 dst.resort(); 802 } 803 804 public static MultiRectArea getResult(MultiRectArea src1, MultiRectArea src2) { 805 806 if (src1 == null || src1.isEmpty()) { 807 return new MultiRectArea(); 808 } 809 810 if (src2 == null || src2.isEmpty()) { 811 return new MultiRectArea(src1); 812 } 813 814 MultiRectArea.RectCash dst = new MultiRectArea.RectCash(); 815 816 if (!src1.sorted || !src2.sorted || 817 src1.getRectCount() <= MAX_SIMPLE || src2.getRectCount() <= MAX_SIMPLE) 818 { 819 simpleSubtract(src1, src2, dst); 820 } else { 821 Rectangle bounds1 = src1.getBounds(); 822 Rectangle bounds2 = src2.getBounds(); 823 Rectangle bounds3 = bounds1.intersection(bounds2); 824 825 if (bounds3.width > 0 && bounds3.height > 0) { 826 subtractRegions(src1.rect, src2.rect, dst, bounds1.height + 2, bounds2.height + 2); 827 } else { 828 dst.setRect(src1.rect, true); 829 } 830 } 831 832 return dst; 833 } 834 835 } 836 837 } 838
