1 19 package bak.pcj.set; 20 21 import bak.pcj.CharIterator; 22 import bak.pcj.CharCollection; 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 CharRangeSet extends AbstractCharSet implements CharSortedSet, Cloneable , Serializable { 45 46 50 private ArrayList ranges; 51 52 56 private int size; 57 58 61 public CharRangeSet() { 62 ranges = new ArrayList (); 63 size = 0; 64 } 65 66 75 public CharRangeSet(char[] a) { 76 this(); 77 addAll(a); 78 } 79 80 91 public CharRangeSet(CharCollection c) { 92 this(); 93 addAll(c); 94 } 95 96 100 110 private CharRange range(int index) { 111 return (CharRange)ranges.get(index); 112 } 113 114 124 private CharRange getRangeOf(char v) { 125 int index = getRangeIndexOf(v); 126 return index >= 0 ? range(index) : null; 127 } 128 129 139 private int getRangeIndexOf(char v) { 140 if (size == 0) 141 return -1; 142 CharRange 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 = (CharRange)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(CharRange range) { 171 CharRange 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 CharRange r1 = range(index); 204 CharRange r2 = range(index+1); 205 CharRange 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 CharRange 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(char v) { 246 int index = getRangeIndexOf(v); 247 if (index >= 0) 248 return false; 249 int insertionIndex = -index-1; 250 ranges.add(insertionIndex, new CharRange(v, v)); 251 if (insertionIndex > 0) 252 insertionIndex--; 253 size++; 254 normalize(insertionIndex); 255 return true; 256 } 257 258 public CharIterator iterator() { 259 return new CharIterator() { 260 int nextIndex = 0; 261 int lastIndex = -1; 262 int currRange = 0; 263 int currOffset = 0; 264 char lastValue; 265 266 public boolean hasNext() { 267 return nextIndex < size; 268 } 269 270 public char 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 CharRangeSet.this.remove(lastValue); 291 nextIndex--; 292 if (nextIndex < size) 293 recalc(); 294 lastIndex = -1; 295 } 296 297 private char curr() { 298 return (char)(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 char first() { 320 if (size == 0) 321 Exceptions.setNoFirst(); 322 return range(0).first(); 323 } 324 325 private char firstFrom(char 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 char last() { 342 if (size == 0) 343 Exceptions.setNoLast(); 344 return range(ranges.size()-1).last(); 345 } 346 347 private char lastFrom(char 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 CharSortedSet headSet(char to) { 365 return new SubSet(false, (char)0, true, to); 366 } 367 368 371 public CharSortedSet tailSet(char from) { 372 return new SubSet(true, from, false, (char)0); 373 } 374 375 378 public CharSortedSet subSet(char from, char to) { 379 return new SubSet(true, from, true, to); 380 } 381 382 private class SubSet extends AbstractCharSet implements CharSortedSet, java.io.Serializable { 383 384 private boolean hasLowerBound; 385 private boolean hasUpperBound; 386 private char lowerBound; 387 private char upperBound; 388 389 SubSet(boolean hasLowerBound, char lowerBound, boolean hasUpperBound, char 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(char v) { 404 if (!inSubRange(v)) 405 Exceptions.valueNotInSubRange(String.valueOf(v)); 406 return CharRangeSet.this.add(v); 407 } 408 409 public boolean remove(char v) { 410 if (!inSubRange(v)) 411 Exceptions.valueNotInSubRange(String.valueOf(v)); 412 return CharRangeSet.this.remove(v); 413 } 414 415 public boolean contains(char v) { 416 return inSubRange(v) && CharRangeSet.this.contains(v); 417 } 418 419 class EmptySubSetIterator implements CharIterator { 420 public boolean hasNext() 421 { return false; } 422 423 public char next() 424 { Exceptions.endOfIterator(); throw new RuntimeException (); } 425 426 public void remove() 427 { Exceptions.noElementToRemove(); } 428 } 429 430 class SimpleSubSetIterator implements CharIterator { 431 int nextIndex; 432 int size; 433 int lastIndex; 434 char lastValue; 435 char from; 436 char to; 437 438 SimpleSubSetIterator(char from, char 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 char next() { 451 if (!hasNext()) 452 Exceptions.endOfIterator(); 453 lastValue = (char)(from + nextIndex); 454 lastIndex = nextIndex; 455 nextIndex++; 456 return lastValue; 457 } 458 459 public void remove() { 460 if (lastIndex == -1) 461 Exceptions.noElementToRemove(); 462 CharRangeSet.this.remove(lastValue); 463 lastIndex = -1; 464 } 465 466 } 467 468 class NonEmptySubSetIterator implements CharIterator { 469 char first; 470 char last; 471 int rangeIndexLow; 472 int rangeIndexHigh; 473 CharRange rangeLow; 474 CharRange rangeHigh; 475 char previousValue; 476 CharRange currRange; 477 int currRangeIndex; 478 int currOffset; 479 boolean valueAvailable; 480 int nextIndex; 481 482 NonEmptySubSetIterator(char first, char 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 CharRange(first, range(rangeIndexLow).last()); 490 rangeHigh = new CharRange(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 CharRange 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 CharRange(first, last); 515 else { 516 rangeLow = new CharRange(first, range(rangeIndexLow).last()); 517 rangeHigh = new CharRange(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 char next() { 536 if (!hasNext()) 537 Exceptions.endOfIterator(); 538 previousValue = (char)(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 CharRangeSet.this.remove(previousValue); 552 nextIndex--; 553 recalc(); 554 valueAvailable = false; 555 } 556 } 557 558 public CharIterator iterator() { 559 char first; 560 char 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 (CharRangeSet.this.size() == 0) 579 return 0; 580 int size; 581 char first; 582 int rangeIndexLow; 583 try { 584 first = first(); 585 rangeIndexLow = getRangeIndexOf(first); 586 } catch (NoSuchElementException e) { 587 return 0; 588 } 589 char last = last(); 590 int rangeIndexHigh = getRangeIndexOf(last); 591 if (rangeIndexLow == rangeIndexHigh) { 592 size = (int)(last-first+1); 593 } else { 594 CharRange rangeLow = range(rangeIndexLow); 595 CharRange 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 char first() { 607 char first = firstFrom(hasLowerBound ? lowerBound : 0); 608 if (hasUpperBound && first >= upperBound) 609 Exceptions.setNoFirst(); 610 return first; 611 } 612 613 public char last() { 614 char last = lastFrom(hasUpperBound ? (char)(upperBound-1) : CharRangeSet.this.last()); 615 if (hasLowerBound && last < lowerBound) 616 Exceptions.setNoLast(); 617 return last; 618 } 619 620 public CharSortedSet headSet(char to) { 621 if (!inSubRange(to)) 622 Exceptions.invalidUpperBound(String.valueOf(to)); 623 return new SubSet(hasLowerBound, lowerBound, true, to); 624 } 625 626 public CharSortedSet tailSet(char from) { 627 if (!inSubRange(from)) 628 Exceptions.invalidLowerBound(String.valueOf(from)); 629 return new SubSet(true, from, hasUpperBound, upperBound); 630 } 631 632 public CharSortedSet subSet(char from, char 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(char 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 CharRangeSet c = (CharRangeSet)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(char 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 CharRange r = range(i); 699 for (char 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(char v) { 712 int index = getRangeIndexOf(v); 713 if (index < 0) 714 return false; 715 CharRange r = range(index); 717 if (v == r.first()) { 718 if (r.length() == 1) 719 ranges.remove(index); 720 else 721 ranges.set(index, new CharRange((char)(r.first()+1), r.last())); 722 } else if (v == r.last()) { 723 ranges.set(index, new CharRange(r.first(), (char)(r.last()-1))); 725 } else { 726 CharRange r1 = new CharRange(r.first(), (char)(v-1)); 728 CharRange r2 = new CharRange((char)(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 char[] toArray(char[] a) { 737 if (a == null || a.length < size) 738 a = new char[size]; 739 for (int i = 0, index = 0, rsize = ranges.size(); i < rsize; i++) { 740 CharRange r = range(i); 741 for (char 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(CharRange range) { 769 774 CharRange r = getRangeOf(range.first()); 775 return r != null ? r.contains(range.last()) : false; 776 } 777 778 799 public boolean addAll(CharRangeSet 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(CharRange 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(char first, char last) { 856 return addAll(new CharRange(first, last)); 857 } 858 859 874 public boolean addAll(char[] a) { 875 if (a.length == 0) 876 return false; 877 878 887 int oldSize = size; 888 char[] sa; 889 if (!isSorted(a)) { 890 sa = (char[])a.clone(); 891 java.util.Arrays.sort(sa); 892 } else { 893 sa = a; 894 } 895 896 int index = 0; 898 char c0, c1; 899 while (index < sa.length) { 900 c0 = sa[index]; 901 index = range(sa, index); 902 c1 = sa[index]; 903 ranges.add(new CharRange(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(char[] a, int index) { 931 char c0 = a[index++]; 932 while (index < a.length && a[index] == c0) 934 index++; 935 while (index < a.length && a[index] == (char)(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(char[] 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 CharRange[] ranges() { 974 CharRange[] a = new CharRange[ranges.size()]; 975 ranges.toArray(a); 976 return a; 977 } 978 979 } 980 | Popular Tags |