1 23 package com.tc.jrexx.set; 24 25 import java.util.NoSuchElementException ; 26 27 public class CharSet implements ISet_char { 28 29 interface IAbstract extends java.io.Serializable { 30 abstract int size(); 31 abstract boolean isEmpty(); 32 abstract void complement(); 33 abstract boolean contains(char ch); 34 abstract boolean add(char ch); 35 abstract boolean remove(char ch); 36 abstract void addAll(IAbstract set); 37 abstract void removeAll(IAbstract set); 38 abstract void retainAll(IAbstract set); 39 abstract ISet_char.Iterator iterator(); 40 abstract void addAll(String chars,int offset,int length); 41 abstract void addAll(char[] chars,int offset,int length); 42 abstract boolean equals(Object obj); 43 } 44 45 395 396 398 static final class Wrapper implements java.io.Serializable { 399 final int offset; 400 long value; 401 402 Wrapper(int offset,long value) { 403 this.offset = offset; 404 this.value = value; 405 406 } 409 410 415 int size() { 416 int answer = 0; 417 for (long tmp=this.value; tmp!=0; tmp>>>=4) { 418 switch((int)(tmp & 15L)) { 419 case 0 : answer+= 0; break; 420 case 1 : answer+= 1; break; 421 case 2 : answer+= 1; break; 422 case 3 : answer+= 2; break; 423 case 4 : answer+= 1; break; 424 case 5 : answer+= 2; break; 425 case 6 : answer+= 2; break; 426 case 7 : answer+= 3; break; 427 case 8 : answer+= 1; break; 428 case 9 : answer+= 2; break; 429 case 10 : answer+= 2; break; 430 case 11 : answer+= 3; break; 431 case 12 : answer+= 2; break; 432 case 13 : answer+= 3; break; 433 case 14 : answer+= 3; break; 434 case 15 : answer+= 4; break; 435 default : throw new RuntimeException ("error: should never happen"); 436 } 437 } 438 return answer; 439 } 440 } 441 442 final static int[] PRIMENUMBERS = new int[]{ 443 3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97, 444 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191, 445 193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283, 446 293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401, 447 409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509, 448 521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631, 449 641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751, 450 757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877, 451 881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009, 452 1013,1019,1021,1024 453 }; 454 455 final static long[] VALUES = new long[64]; 456 static{ 457 VALUES[0] = 1L; 458 for (int t=0,i=1; i<VALUES.length; ++i,++t) VALUES[i] = VALUES[t]<<1; 459 } 460 461 final class LongMap implements IAbstract { 462 463 Wrapper[] sets = null; 464 int size = 0; 465 466 protected LongMap(LongMap set) { 467 this.sets = new Wrapper[set.sets.length]; 468 for (int i=0; i<set.sets.length; ++i) 469 if (set.sets[i]!=null) 470 this.sets[i] = new Wrapper(set.sets[i].offset,set.sets[i].value); 471 472 this.size = set.size; 473 } 474 475 LongMap() { 476 this.sets = new Wrapper[CharSet.PRIMENUMBERS[0]]; 477 } 478 479 LongMap(char ch1,char ch2) { 480 this.sets = new Wrapper[CharSet.PRIMENUMBERS[0]]; 481 this.add(ch1); 482 this.add(ch2); 483 } 484 485 public boolean isEmpty() {return this.size()==0;} 486 public int size() { 487 if (this.size>=0) return this.size; 488 int answer = 0; 489 for (int i=0; i<this.sets.length; ++i) { 490 if (this.sets[i]!=null) answer+= this.sets[i].size(); 491 } 492 this.size = answer; 493 return answer; 494 } 495 496 public boolean contains(char ch) { 497 final int offset = ch/64; 498 final int index = offset % this.sets.length; 499 if (this.sets[index]==null || this.sets[index].offset != offset) return false; 500 return (this.sets[index].value & (VALUES[ch%64]))!=0; 501 } 502 503 public void complement() { 504 this.size = -1; 505 final Wrapper[] tmp = this.sets; 506 this.sets = new Wrapper[CharSet.PRIMENUMBERS[0]]; 507 for (int offset=0; offset<CharSet.this.max; ++offset) { 508 int index = offset % tmp.length; 509 long value = -1L; 510 if (tmp[index]!=null && tmp[index].offset==offset) value^= tmp[index].value; 511 if (value!=0) this.addAll(offset,value); 512 } 513 } 514 515 public boolean add(char ch) { 516 if (ch>CharSet.this.maxChar) 517 throw new IllegalArgumentException ( 518 "ch > maxChar = " 519 +CharSet.this.maxChar 520 +"("+(int)CharSet.this.maxChar+")" 521 ); 522 523 final int offset = ch/64; 524 loop: do { 525 int index = offset % this.sets.length; 526 if (this.sets[index]==null) { 527 this.sets[index] = new Wrapper(offset,1L<<(ch%64)); 528 if (this.size>=0) ++this.size; 529 return true; 530 } 531 if (this.sets[index].offset==offset) { 532 long oldValue = this.sets[index].value; 533 this.sets[index].value|= VALUES[ch%64]; 534 long newValue = this.sets[index].value; 535 536 if (oldValue==newValue) return false; 537 538 if (this.size>=0) ++this.size; 539 return true; 540 } 541 542 this.expand(); 543 } while(true); 544 } 545 546 public void addAll(char[] chars,int offset,int length) { 547 for (; length>0; ++offset,--length) this.add(chars[offset]); 548 } 549 550 public void addAll(String chars,int offset,int length) { 551 for (; length>0; ++offset,--length) this.add(chars.charAt(offset)); 552 } 553 554 555 public void addAll(IAbstract set) { 556 this.addAll((LongMap)set); 557 } 558 559 void addAll(LongMap set) { 560 if (this.sets.length>=set.sets.length) { 561 for (int i=0; i<set.sets.length; ++i) { 562 if (set.sets[i]!=null) 563 this.addAll(set.sets[i].offset,set.sets[i].value); 564 } 565 } else { 566 final Wrapper[] tmp = this.sets; 567 this.sets = new Wrapper[set.sets.length]; 568 for (int i=0; i<set.sets.length; ++i) 569 this.sets[i] = (set.sets[i]==null) ? null : new Wrapper(set.sets[i].offset,set.sets[i].value); 570 this.size = set.size; 571 572 for (int i=0; i<tmp.length; ++i) { 573 if (tmp[i]!=null) this.addAll(tmp[i]); 574 } 575 } 576 } 577 578 private void addAll(int offset,long value) { 579 this.size = -1; 580 loop: do { 581 int index = offset % this.sets.length; 582 if (this.sets[index]==null) { 583 this.sets[index] = new Wrapper(offset,value); 584 return; 585 } 586 if (this.sets[index].offset==offset) { 587 this.sets[index].value|= value; 588 return; 589 } 590 591 this.expand(); 592 } while(true); 593 } 594 595 private void addAll(Wrapper w) { 596 this.size = -1; 597 loop: do { 598 int index = w.offset % this.sets.length; 599 if (this.sets[index]==null) { 600 this.sets[index] = w; 601 return; 602 } 603 if (this.sets[index].offset==w.offset) { 604 this.sets[index].value|= w.value; 605 return; 606 } 607 608 this.expand(); 609 } while(true); 610 } 611 612 613 public boolean remove(char ch) { 614 final int offset = ch/64; 615 final int index = offset % this.sets.length; 616 if (this.sets[index]==null) return false; 617 if (this.sets[index].offset!=offset) return false; 618 619 long oldValue = this.sets[index].value; 620 this.sets[index].value&= (-1L)^(VALUES[ch%64]); 621 long newValue = this.sets[index].value; 622 623 if (oldValue==newValue) return false; 624 625 if (this.size>0) --this.size; 626 if (newValue==0) this.sets[index] = null; 627 return true; 628 } 629 630 public void removeAll(IAbstract set) { 631 this.removeAll((LongMap)set); 632 } 633 634 void removeAll(LongMap set) { 635 for (int i=0; i<set.sets.length; ++i) { 636 if (set.sets[i]!=null) 637 this.removeAll(set.sets[i].offset,set.sets[i].value); 638 } 639 } 640 641 private void removeAll(int offset,long value) { 642 final int index = offset % this.sets.length; 643 if (this.sets[index]==null) return; 644 if (this.sets[index].offset!=offset) return; 645 646 this.size = -1; 647 this.sets[index].value&= (-1L)^value; 648 if (this.sets[index].value==0) this.sets[index] = null; 649 } 650 651 public void retainAll(IAbstract set) { 652 this.retainAll((LongMap)set); 653 } 654 655 void retainAll(LongMap set) { 656 this.size = -1; 657 for (int i=0; i<this.sets.length; ++i) { 658 if (this.sets[i]!=null) { 659 Wrapper w1 = this.sets[i]; 660 Wrapper w2 = set.sets[w1.offset % set.sets.length]; 661 if (w2==null) this.sets[i] = null; 662 else { 663 if (w1.offset!=w2.offset) this.sets[i] = null; 664 else { 665 w1.value&= w2.value; 666 if (this.sets[i].value==0) this.sets[i] = null; 667 } 668 } 669 } 670 } 671 } 672 673 private void expand() { 674 final Wrapper[] values = this.sets; 675 reInit: do { 676 this.sets = new Wrapper[this.nextPrimeNumber()]; 677 for (int i=0; i<values.length; ++i) { 678 if (values[i]!=null) { 679 int index = values[i].offset % this.sets.length; 680 if (this.sets[index]!=null) continue reInit; 681 this.sets[index] = values[i]; 682 } 683 } 684 return; 685 } while(true); 686 } 687 688 private int nextPrimeNumber() { 689 final int currentPrimeNumber = this.sets.length; 690 int i = 0; 691 while (CharSet.PRIMENUMBERS[i]!=currentPrimeNumber) ++i; 692 return CharSet.PRIMENUMBERS[++i]; 693 } 694 695 public ISet_char.Iterator iterator() { 696 return new LongMapIterator(CharSet.this, this); 697 } 698 699 public boolean equals(Object obj) { 700 if (this==obj) return true; 701 if (obj==null) return false; 702 if (this.getClass()!=obj.getClass()) return false; 703 704 LongMap set = (LongMap)obj; 705 if (this.size!=set.size) return false; 706 707 for (int i=0; i<this.sets.length; ++i) { 708 if (this.sets[i]!=null) { 709 if (this.sets[i].value==0) throw new Error ("this.sets[i].value==0"); 710 Wrapper w1 = this.sets[i]; 711 Wrapper w2 = set.sets[w1.offset % set.sets.length]; 712 if (w2==null) return false; 713 else { 714 if (w1.offset!=w2.offset) return false; 715 else { 716 if (w1.value!=w2.value) return false; 717 } 718 } 719 } 720 } 721 722 return true; 723 } 724 } 725 726 727 private static final class LongMapIterator implements ISet_char.Iterator { 728 int currentOffset = 0; 729 730 long currentValue = 1L; 731 732 char currentChar = '\u0000'; 733 734 final int setsLength; 736 private final LongMap longMap; 737 738 private final CharSet charSet; 739 740 public LongMapIterator(CharSet charSet, LongMap longMap) { 741 this.charSet = charSet; 742 this.longMap = longMap; 743 this.setsLength = longMap.sets.length; 744 } 745 746 public boolean hasNext() { 747 748 do { 749 if (longMap.contains(this.currentChar)) return true; 750 } while(++this.currentChar!='\u0000'); 751 return false; 752 753 772 } 773 774 public char next() { 775 do { 776 if (longMap.contains(this.currentChar)) return this.currentChar++; 777 } while(++this.currentChar!='\u0000'); 778 779 throw new NoSuchElementException (charSet.toString()); 780 781 803 } 804 } 805 806 807 810 static final int max = 4; 811 static final char maxChar = (char)(64*max-1); 812 813 protected CharSet.IAbstract set; 814 815 protected CharSet(IAbstract set) { 816 this.set = set; 817 } 818 819 public CharSet() { 820 this.set = new LongMap(); 821 } 822 823 public CharSet(char ch) { 824 this(); 825 this.set.add(ch); 826 } 827 828 public CharSet(String s) { 829 this(); 830 this.set.addAll(s,0,s.length()); 831 } 832 833 public void complement() { 834 this.set.complement(); 835 } 836 837 public boolean contains(char ch) { 838 return this.set.contains(ch); 839 } 840 841 public boolean isEmpty() { 842 return this.set.isEmpty(); 843 } 844 845 public int size() { 846 return this.set.size(); 847 } 848 849 public ISet_char.Iterator iterator() { 850 return this.set.iterator(); 851 } 852 853 public void clear() { 854 this.set = new LongMap(); 856 } 857 858 public boolean add(char ch) { 859 860 return this.set.add(ch); 861 } 862 863 public boolean remove(char ch) { 864 return this.set.remove(ch); 865 } 866 867 public void addAll(String chars) { 868 this.addAll(chars,0,chars.length()); 869 } 870 public void addAll(String chars,int offset) { 871 this.addAll(chars,offset,chars.length()-offset); 872 } 873 874 public void addAll(String chars,int offset,int length) { 875 if (length==0) return; 876 this.set.addAll(chars,offset,length); 877 } 878 879 public void addAll(char[] chars) { 880 this.addAll(chars,0,chars.length); 881 } 882 public void addAll(char[] chars,int offset) { 883 this.addAll(chars,offset,chars.length-offset); 884 } 885 886 public void addAll(char[] chars,int offset,int length) { 887 if (length==0) return; 888 this.set.addAll(chars,offset,length); 889 } 890 891 895 public void addAll(ISet_char set) { 896 if (set instanceof CharSet) this.set.addAll(((CharSet)set).set); 897 else { 898 final ISet_char.Iterator it = set.iterator(); 899 for (int i=set.size(); i>0; --i) this.set.add(it.next()); 900 } 901 } 902 903 907 public void removeAll(ISet_char set) { 908 if (set instanceof CharSet) this.set.removeAll(((CharSet)set).set); 909 else { 910 final ISet_char.Iterator it = set.iterator(); 911 for (int i=set.size(); i>0; --i) this.set.remove(it.next()); 912 } 913 } 914 915 public void retainAll(ISet_char set) { 916 if (set instanceof CharSet) this.set.retainAll(((CharSet)set).set); 917 else { 918 final CharSet charSet = new CharSet(); 919 final ISet_char.Iterator it = set.iterator(); 920 for (int i=set.size(); i>0; --i) charSet.add(it.next()); 921 this.set.retainAll(charSet.set); 922 } 923 } 924 925 public boolean equals(Object obj) { 926 if (this==obj) return true; 927 if (obj==null) return false; 928 if (this.getClass()!=obj.getClass()) return false; 929 return this.set.equals(((CharSet)obj).set); 930 } 931 932 public int hashCode() { 933 return this.set.size(); 934 } 935 936 protected IAbstract cloneAbstract(IAbstract set) { 937 if (set instanceof LongMap) return new LongMap((LongMap)set); 938 throw new Error (""); 939 } 940 941 public Object clone() { 942 try { 943 CharSet clone = (CharSet)super.clone(); 944 clone.set = clone.cloneAbstract(set); 945 return clone; 946 } catch(CloneNotSupportedException e) { 947 throw new Error ("CloneNotSupportedException:\n"+e); 948 } 949 } 950 951 public String toString() { 952 StringBuffer answer = new StringBuffer (); 953 954 int from = -1; 955 char ch = '\u0000'; 956 do { 957 if (this.contains(ch)) { 958 if (from==-1) from = ch; 959 } else { 960 if (from!=-1) { 961 char to = ch; --to; 962 if (from==to) { 963 if (to=='[' || to==']' || to=='\\' || to=='-') answer.append('\\'); 964 answer.append(to); 965 } else { 966 char char_from = (char)from; 967 if (char_from=='[' || char_from==']' || char_from=='\\' || char_from=='-') answer.append('\\'); 968 answer.append((char)from); 969 if (to!=++from) answer.append("-"); 970 if (to=='[' || to==']' || to=='\\' || to=='-') answer.append('\\'); 971 answer.append(to); 972 } 973 974 from = -1; 975 } 976 } 977 } while (++ch!='\u0000'); 978 979 if (from!=-1) { 980 char char_from = (char)from; 981 if (char_from=='[' || char_from==']' || char_from=='\\' || char_from=='-') answer.append('\\'); 982 answer.append((char)from); 983 if (from!='\ufffe') answer.append('-'); 984 answer.append('\uffff'); 985 } 986 987 for (int i=answer.length()-1; i>=0; --i) { 988 if (answer.charAt(i)>'\u00ff') answer.setCharAt(i,'.'); 989 } 990 991 return answer.toString(); 992 } 993 994 } | Popular Tags |