1 19 package bak.pcj.set; 20 21 import bak.pcj.ByteIterator; 22 import bak.pcj.ByteCollection; 23 import bak.pcj.util.Exceptions; 24 25 import java.util.ArrayList ; 26 import java.util.NoSuchElementException ; 27 import java.io.Serializable ; 28 29 44 public class ByteRangeSet extends AbstractByteSet implements ByteSortedSet, Cloneable , Serializable { 45 46 50 private ArrayList ranges; 51 52 56 private int size; 57 58 61 public ByteRangeSet() { 62 ranges = new ArrayList (); 63 size = 0; 64 } 65 66 75 public ByteRangeSet(byte[] a) { 76 this(); 77 addAll(a); 78 } 79 80 91 public ByteRangeSet(ByteCollection c) { 92 this(); 93 addAll(c); 94 } 95 96 100 110 private ByteRange range(int index) { 111 return (ByteRange)ranges.get(index); 112 } 113 114 124 private ByteRange getRangeOf(byte v) { 125 int index = getRangeIndexOf(v); 126 return index >= 0 ? range(index) : null; 127 } 128 129 139 private int getRangeIndexOf(byte v) { 140 if (size == 0) 141 return -1; 142 ByteRange r; 144 int lo = 0; 145 int hi = ranges.size()-1; 146 int mid; 147 while (lo <= hi) { 148 mid = (lo+hi)/2; 149 r = (ByteRange)ranges.get(mid); 150 if (r.contains(v)) 151 return mid; 152 if (v < r.first()) { 153 hi = mid-1; 154 } else { lo = mid+1; 156 } 157 } 158 return -(lo+1); 159 } 160 161 170 private int insertRange(ByteRange range) { 171 ByteRange r; 173 int lo = 0; 174 int hi = ranges.size()-1; 175 int mid; 176 while (lo <= hi) { 177 mid = (lo+hi)/2; 178 r = range(mid); 179 int compare = range.compareTo(r); 180 if (compare == 0) 181 return -1; 182 if (compare < 0) { 183 hi = mid-1; 184 } else { lo = mid+1; 186 } 187 } 188 ranges.add(lo, range); 189 return lo; 190 } 191 192 201 private void normalize(int index) { 202 while (index < ranges.size()-1) { 203 ByteRange r1 = range(index); 204 ByteRange r2 = range(index+1); 205 ByteRange r3 = r1.tryMergeWith(r2); 206 if (r3 == null) 207 break; 208 ranges.set(index, r3); 209 ranges.remove(index+1); 210 size -= r1.intersectionLength(r2); 211 } 212 } 213 214 215 221 private void normalize() { 222 int index = 0; 223 size = 0; 224 ByteRange r1, r2, r3; 225 while (index < ranges.size()-1) { 226 r1 = range(index); 227 r2 = range(index+1); 228 r3 = r1.tryMergeWith(r2); 229 if (r3 != null) { 230 ranges.set(index, r3); 231 ranges.remove(index+1); 232 } else { 233 size += r1.length(); 234 index++; 235 } 236 } 237 r3 = range(ranges.size()-1); 238 size += r3.length(); 239 } 240 241 245 public boolean add(byte v) { 246 int index = getRangeIndexOf(v); 247 if (index >= 0) 248 return false; 249 int insertionIndex = -index-1; 250 ranges.add(insertionIndex, new ByteRange(v, v)); 251 if (insertionIndex > 0) 252 insertionIndex--; 253 size++; 254 normalize(insertionIndex); 255 return true; 256 } 257 258 public ByteIterator iterator() { 259 return new ByteIterator() { 260 int nextIndex = 0; 261 int lastIndex = -1; 262 int currRange = 0; 263 int currOffset = 0; 264 byte lastValue; 265 266 public boolean hasNext() { 267 return nextIndex < size; 268 } 269 270 public byte next() { 271 if (nextIndex >= size) 272 Exceptions.endOfIterator(); 273 lastIndex = nextIndex; 274 lastValue = curr(); 275 nextIndex++; 276 if (nextIndex < size) { 277 if (currOffset == range(currRange).length()-1) { 278 currRange++; 279 currOffset = 0; 280 } else { 281 currOffset++; 282 } 283 } 284 return lastValue; 285 } 286 287 public void remove() { 288 if (lastIndex == -1) 289 Exceptions.noElementToRemove(); 290 ByteRangeSet.this.remove(lastValue); 291 nextIndex--; 292 if (nextIndex < size) 293 recalc(); 294 lastIndex = -1; 295 } 296 297 private byte curr() { 298 return (byte)(range(currRange).first() + currOffset); 299 } 300 301 private void recalc() { 302 currRange = 0; 303 currOffset = nextIndex; 304 for (;;) { 305 int rs = range(currRange).length(); 306 if (currOffset < rs) 307 break; 308 currOffset -= rs; 309 currRange++; 310 } 311 } 312 313 }; 314 } 315 316 319 public byte first() { 320 if (size == 0) 321 Exceptions.setNoFirst(); 322 return range(0).first(); 323 } 324 325 private byte firstFrom(byte v) { 326 int index = getRangeIndexOf(v); 327 if (index >= 0) 328 return v; 329 index = -index - 1; 333 if (index >= ranges.size()) 334 Exceptions.setNoFirst(); 335 return range(index).first(); 336 } 337 338 341 public byte last() { 342 if (size == 0) 343 Exceptions.setNoLast(); 344 return range(ranges.size()-1).last(); 345 } 346 347 private byte lastFrom(byte v) { 348 int index = getRangeIndexOf(v); 349 if (index >= 0) 350 return v; 351 index = -index - 1; 355 index--; 356 if (index < 0 || index >= ranges.size()) 357 Exceptions.setNoLast(); 358 return range(index).last(); 359 } 360 361 364 public ByteSortedSet headSet(byte to) { 365 return new SubSet(false, (byte)0, true, to); 366 } 367 368 371 public ByteSortedSet tailSet(byte from) { 372 return new SubSet(true, from, false, (byte)0); 373 } 374 375 378 public ByteSortedSet subSet(byte from, byte to) { 379 return new SubSet(true, from, true, to); 380 } 381 382 private class SubSet extends AbstractByteSet implements ByteSortedSet, java.io.Serializable { 383 384 private boolean hasLowerBound; 385 private boolean hasUpperBound; 386 private byte lowerBound; 387 private byte upperBound; 388 389 SubSet(boolean hasLowerBound, byte lowerBound, boolean hasUpperBound, byte upperBound) { 390 if (hasLowerBound) { 391 if (lowerBound < 0) 392 Exceptions.negativeArgument("lower bound", String.valueOf(lowerBound)); 393 if (hasUpperBound) 394 if (upperBound < lowerBound) 395 Exceptions.invalidSetBounds(String.valueOf(lowerBound), String.valueOf(upperBound)); 396 } 397 this.hasLowerBound = hasLowerBound; 398 this.lowerBound = lowerBound; 399 this.hasUpperBound = hasUpperBound; 400 this.upperBound = upperBound; 401 } 402 403 public boolean add(byte v) { 404 if (!inSubRange(v)) 405 Exceptions.valueNotInSubRange(String.valueOf(v)); 406 return ByteRangeSet.this.add(v); 407 } 408 409 public boolean remove(byte v) { 410 if (!inSubRange(v)) 411 Exceptions.valueNotInSubRange(String.valueOf(v)); 412 return ByteRangeSet.this.remove(v); 413 } 414 415 public boolean contains(byte v) { 416 return inSubRange(v) && ByteRangeSet.this.contains(v); 417 } 418 419 class EmptySubSetIterator implements ByteIterator { 420 public boolean hasNext() 421 { return false; } 422 423 public byte next() 424 { Exceptions.endOfIterator(); throw new RuntimeException (); } 425 426 public void remove() 427 { Exceptions.noElementToRemove(); } 428 } 429 430 class SimpleSubSetIterator implements ByteIterator { 431 int nextIndex; 432 int size; 433 int lastIndex; 434 byte lastValue; 435 byte from; 436 byte to; 437 438 SimpleSubSetIterator(byte from, byte to) { 439 size = (int)(to-from+1); 440 nextIndex = 0; 441 lastIndex = -1; 442 this.from = from; 443 this.to = to; 444 } 445 446 public boolean hasNext() { 447 return nextIndex < size; 448 } 449 450 public byte next() { 451 if (!hasNext()) 452 Exceptions.endOfIterator(); 453 lastValue = (byte)(from + nextIndex); 454 lastIndex = nextIndex; 455 nextIndex++; 456 return lastValue; 457 } 458 459 public void remove() { 460 if (lastIndex == -1) 461 Exceptions.noElementToRemove(); 462 ByteRangeSet.this.remove(lastValue); 463 lastIndex = -1; 464 } 465 466 } 467 468 class NonEmptySubSetIterator implements ByteIterator { 469 byte first; 470 byte last; 471 int rangeIndexLow; 472 int rangeIndexHigh; 473 ByteRange rangeLow; 474 ByteRange rangeHigh; 475 byte previousValue; 476 ByteRange currRange; 477 int currRangeIndex; 478 int currOffset; 479 boolean valueAvailable; 480 int nextIndex; 481 482 NonEmptySubSetIterator(byte first, byte last, int rangeIndexLow, int rangeIndexHigh) { 483 if (rangeIndexLow == rangeIndexHigh) 484 throw new RuntimeException ("Internal error"); 485 this.first = first; 486 this.last = last; 487 this.rangeIndexLow = rangeIndexLow; 488 this.rangeIndexHigh = rangeIndexHigh; 489 rangeLow = new ByteRange(first, range(rangeIndexLow).last()); 490 rangeHigh = new ByteRange(range(rangeIndexHigh).first(), last); 491 currRangeIndex = rangeIndexLow; 492 currRange = rangeLow; 493 currOffset = 0; 494 previousValue = first; 495 valueAvailable = false; 496 nextIndex = 0; 497 } 498 499 private ByteRange getRange(int rangeIndex) { 500 if (rangeIndex == rangeIndexLow) 501 return rangeLow; 502 if (rangeIndex == rangeIndexHigh) 503 return rangeHigh; 504 return range(rangeIndex); 505 } 506 507 private void recalc() { 508 first = first(); 509 last = last(); 510 511 rangeIndexLow = getRangeIndexOf(first); 512 rangeIndexHigh = getRangeIndexOf(last); 513 if (rangeIndexLow == rangeIndexHigh) 514 rangeLow = rangeHigh = new ByteRange(first, last); 515 else { 516 rangeLow = new ByteRange(first, range(rangeIndexLow).last()); 517 rangeHigh = new ByteRange(range(rangeIndexHigh).first(), last); 518 } 519 currOffset = nextIndex; 520 currRangeIndex = rangeIndexLow; 521 currRange = rangeLow; 522 for (;;) { 523 int rs = currRange.length(); 524 if (currOffset < rs) 525 break; 526 currOffset -= rs; 527 currRange = getRange(++currRangeIndex); 528 } 529 } 530 531 public boolean hasNext() { 532 return previousValue < last; 533 } 534 535 public byte next() { 536 if (!hasNext()) 537 Exceptions.endOfIterator(); 538 previousValue = (byte)(currRange.first() + currOffset++); 539 if (currOffset == currRange.length() && previousValue < last) { 540 currOffset = 0; 541 currRange = getRange(++currRangeIndex); 542 } 543 nextIndex++; 544 valueAvailable = true; 545 return previousValue; 546 } 547 548 public void remove() { 549 if (!valueAvailable) 550 Exceptions.noElementToRemove(); 551 ByteRangeSet.this.remove(previousValue); 552 nextIndex--; 553 recalc(); 554 valueAvailable = false; 555 } 556 } 557 558 public ByteIterator iterator() { 559 byte first; 560 byte last; 561 int rangeIndexLow; 562 int rangeIndexHigh; 563 564 try { 565 first = first(); 566 } catch (NoSuchElementException e) { 567 return new EmptySubSetIterator(); 568 } 569 last = last(); 570 rangeIndexLow = getRangeIndexOf(first); 571 rangeIndexHigh = getRangeIndexOf(last); 572 if (rangeIndexLow == rangeIndexHigh) 573 return new SimpleSubSetIterator(first, last); 574 return new NonEmptySubSetIterator(first, last, rangeIndexLow, rangeIndexHigh); 575 } 576 577 public int size() { 578 if (ByteRangeSet.this.size() == 0) 579 return 0; 580 int size; 581 byte first; 582 int rangeIndexLow; 583 try { 584 first = first(); 585 rangeIndexLow = getRangeIndexOf(first); 586 } catch (NoSuchElementException e) { 587 return 0; 588 } 589 byte last = last(); 590 int rangeIndexHigh = getRangeIndexOf(last); 591 if (rangeIndexLow == rangeIndexHigh) { 592 size = (int)(last-first+1); 593 } else { 594 ByteRange rangeLow = range(rangeIndexLow); 595 ByteRange rangeHigh = range(rangeIndexHigh); 596 int sizeLow = (int)(rangeLow.last()-first+1); 597 int sizeHigh = (int)(last-rangeHigh.first()+1); 598 599 size = sizeLow + sizeHigh; 600 for (int i = rangeIndexLow+1; i < rangeIndexHigh; i++) 601 size += range(i).length(); 602 } 603 return size; 604 } 605 606 public byte first() { 607 byte first = firstFrom(hasLowerBound ? lowerBound : 0); 608 if (hasUpperBound && first >= upperBound) 609 Exceptions.setNoFirst(); 610 return first; 611 } 612 613 public byte last() { 614 byte last = lastFrom(hasUpperBound ? (byte)(upperBound-1) : ByteRangeSet.this.last()); 615 if (hasLowerBound && last < lowerBound) 616 Exceptions.setNoLast(); 617 return last; 618 } 619 620 public ByteSortedSet headSet(byte to) { 621 if (!inSubRange(to)) 622 Exceptions.invalidUpperBound(String.valueOf(to)); 623 return new SubSet(hasLowerBound, lowerBound, true, to); 624 } 625 626 public ByteSortedSet tailSet(byte from) { 627 if (!inSubRange(from)) 628 Exceptions.invalidLowerBound(String.valueOf(from)); 629 return new SubSet(true, from, hasUpperBound, upperBound); 630 } 631 632 public ByteSortedSet subSet(byte from, byte to) { 633 if (!inSubRange(from)) 634 Exceptions.invalidLowerBound(String.valueOf(from)); 635 if (!inSubRange(to)) 636 Exceptions.invalidUpperBound(String.valueOf(to)); 637 return new SubSet(true, from, true, to); 638 } 639 640 private boolean inSubRange(byte v) { 641 if (hasLowerBound && v < lowerBound) 642 return false; 643 if (hasUpperBound && v >= upperBound) 644 return false; 645 return true; 646 } 647 648 } 649 650 public String toString() { 651 StringBuffer s = new StringBuffer (); 652 s.append('['); 653 for (int i = 0, rsize = ranges.size(); i < rsize; i++) { 654 if (i > 0) 655 s.append(','); 656 s.append(range(i)); 657 } 658 s.append(']'); 659 return s.toString(); 660 } 661 662 public void trimToSize() { 663 } 665 666 673 public Object clone() { 674 try { 675 ByteRangeSet c = (ByteRangeSet)super.clone(); 676 c.ranges = (ArrayList )ranges.clone(); 677 return c; 678 } catch (CloneNotSupportedException e) { 679 Exceptions.cloning(); throw new RuntimeException (); 680 } 681 } 682 683 687 public void clear() { 688 ranges.clear(); 689 size = 0; 690 } 691 692 public boolean contains(byte v) 693 { return getRangeIndexOf(v) >= 0; } 694 695 public int hashCode() { 696 int h = 0; 697 for (int i = 0, index = 0, rsize = ranges.size(); i < rsize; i++) { 698 ByteRange r = range(i); 699 for (byte c = r.first(), last = r.last(); c <= last; c++) 700 h += c; 701 } 702 return h; 703 } 704 705 public boolean isEmpty() 706 { return size == 0; } 707 708 public int size() 709 { return size; } 710 711 public boolean remove(byte v) { 712 int index = getRangeIndexOf(v); 713 if (index < 0) 714 return false; 715 ByteRange r = range(index); 717 if (v == r.first()) { 718 if (r.length() == 1) 719 ranges.remove(index); 720 else 721 ranges.set(index, new ByteRange((byte)(r.first()+1), r.last())); 722 } else if (v == r.last()) { 723 ranges.set(index, new ByteRange(r.first(), (byte)(r.last()-1))); 725 } else { 726 ByteRange r1 = new ByteRange(r.first(), (byte)(v-1)); 728 ByteRange r2 = new ByteRange((byte)(v+1), r.last()); 729 ranges.set(index, r1); 730 ranges.add(index+1, r2); 731 } 732 size--; 733 return true; 734 } 735 736 public byte[] toArray(byte[] a) { 737 if (a == null || a.length < size) 738 a = new byte[size]; 739 for (int i = 0, index = 0, rsize = ranges.size(); i < rsize; i++) { 740 ByteRange r = range(i); 741 for (byte c = r.first(), last = r.last(); c <= last; c++) 742 a[index++] = c; 743 } 744 return a; 745 } 746 747 751 768 public boolean containsAll(ByteRange range) { 769 774 ByteRange r = getRangeOf(range.first()); 775 return r != null ? r.contains(range.last()) : false; 776 } 777 778 799 public boolean addAll(ByteRangeSet c) { 800 int oldSize = size; 801 for (int i = 0, rsize = c.ranges.size(); i < rsize; i++) 802 addAll(c.range(i)); 803 return size != oldSize; 804 } 805 806 825 public boolean addAll(ByteRange range) { 826 int oldSize = size; 827 int index = insertRange(range); 828 if (index != -1) { 829 int nindex = index; 830 if (nindex > 0) 831 nindex--; 832 size += range.length(); 833 normalize(nindex); 834 } 835 return size != oldSize; 836 } 837 838 855 public boolean addAll(byte first, byte last) { 856 return addAll(new ByteRange(first, last)); 857 } 858 859 874 public boolean addAll(byte[] a) { 875 if (a.length == 0) 876 return false; 877 878 887 int oldSize = size; 888 byte[] sa; 889 if (!isSorted(a)) { 890 sa = (byte[])a.clone(); 891 java.util.Arrays.sort(sa); 892 } else { 893 sa = a; 894 } 895 896 int index = 0; 898 byte c0, c1; 899 while (index < sa.length) { 900 c0 = sa[index]; 901 index = range(sa, index); 902 c1 = sa[index]; 903 ranges.add(new ByteRange(c0, c1)); 904 index++; 905 } 906 907 912 java.util.Collections.sort(ranges); 913 normalize(); 914 return size != oldSize; 915 } 916 917 930 private int range(byte[] a, int index) { 931 byte c0 = a[index++]; 932 while (index < a.length && a[index] == c0) 934 index++; 935 while (index < a.length && a[index] == (byte)(c0+1)) { 937 c0 = a[index++]; 938 while (index < a.length && a[index] == c0) 940 index++; 941 } 942 return index-1; 943 } 944 945 958 private boolean isSorted(byte[] a) { 959 for (int i = 1; i < a.length; i++) 960 if (a[i] < a[i-1]) 961 return false; 962 return true; 963 } 964 965 973 public ByteRange[] ranges() { 974 ByteRange[] a = new ByteRange[ranges.size()]; 975 ranges.toArray(a); 976 return a; 977 } 978 979 } 980 | Popular Tags |