0001: /*
0002: * 01/07/2003 - 15:19:32
0003: *
0004: * CharSet.java -
0005: * Copyright (C) 2003 Buero fuer Softwarearchitektur GbR
0006: * ralf.meyer@karneim.com
0007: * http://jrexx.sf.net
0008: *
0009: * This program is free software; you can redistribute it and/or
0010: * modify it under the terms of the GNU Lesser General Public License
0011: * as published by the Free Software Foundation; either version 2
0012: * of the License, or (at your option) any later version.
0013: *
0014: * This program is distributed in the hope that it will be useful,
0015: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0016: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0017: * GNU Lesser General Public License for more details.
0018: *
0019: * You should have received a copy of the GNU Lesser General Public License
0020: * along with this program; if not, write to the Free Software
0021: * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
0022: */
0023: package com.tc.jrexx.set;
0024:
0025: import java.util.NoSuchElementException;
0026:
0027: public class CharSet implements ISet_char {
0028:
0029: interface IAbstract extends java.io.Serializable {
0030: abstract int size();
0031:
0032: abstract boolean isEmpty();
0033:
0034: abstract void complement();
0035:
0036: abstract boolean contains(char ch);
0037:
0038: abstract boolean add(char ch);
0039:
0040: abstract boolean remove(char ch);
0041:
0042: abstract void addAll(IAbstract set);
0043:
0044: abstract void removeAll(IAbstract set);
0045:
0046: abstract void retainAll(IAbstract set);
0047:
0048: abstract ISet_char.Iterator iterator();
0049:
0050: abstract void addAll(String chars, int offset, int length);
0051:
0052: abstract void addAll(char[] chars, int offset, int length);
0053:
0054: abstract boolean equals(Object obj);
0055: }
0056:
0057: /*
0058: final class Empty extends Abstract {
0059: int size() {return 0;}
0060: boolean isEmpty() {return true;}
0061: void complement() {CharSet.this.set = new CharSet.Full();}
0062: boolean contains(char ch) {return false;}
0063: boolean add(char ch) {
0064: CharSet.this.set = new CharSet.Char(ch);
0065: CharSet.this.modifiedFlag = true;
0066: return true;
0067: }
0068: int addAll(char[] chars,int offset,int length) {
0069: CharSet.this.set = new CharSet.Char(chars[offset]);
0070: CharSet.this.modifiedFlag = true;
0071:
0072: return 1+CharSet.this.set.addAll(chars,++offset,--length);
0073: }
0074: int addAll(String chars,int offset,int length) {
0075: CharSet.this.set = new CharSet.Char(chars.charAt(offset));
0076: CharSet.this.modifiedFlag = true;
0077:
0078: return 1+CharSet.this.set.addAll(chars,++offset,--length);
0079: }
0080:
0081: int addAll(Abstract set) {
0082: if (set instanceof Char) CharSet.this.set = new Char( (Char)set );
0083: else
0084: if (set instanceof LongMap) CharSet.this.set = new LongMap( (LongMap)set );
0085: else
0086: if (set instanceof CharComplement) CharSet.this.set = new CharComplement( (CharComplement)set );
0087: else
0088: if (set instanceof LongMapComplement) CharSet.this.set = new LongMapComplement( (LongMapComplement)set );
0089: else
0090: if (set instanceof Full) CharSet.this.set = new Full();
0091:
0092: return set.size();
0093: }
0094:
0095: boolean remove(char ch) {return false;}
0096: int removeAll(Abstract set) {return 0;}
0097:
0098: boolean retain(char ch) {return false;}
0099: int retainAll(Abstract set) {return 0;}
0100:
0101: ISet_char.Iterator iterator() {
0102: return new ISet_char.Iterator() {
0103: public boolean hasNext() {
0104: if (CharSet.this.modifiedFlag) throw new ConcurrentModificationException();
0105: return false;
0106: }
0107: public char next() {
0108: throw new NoSuchElementException();
0109: }
0110: };
0111: }
0112: }
0113:
0114: final class Full extends Abstract {
0115: int size() {return 65535;}
0116: boolean isEmpty() {return false;}
0117: void complement() {CharSet.this.set = new CharSet.Empty();}
0118: boolean contains(char ch) {return true;}
0119: boolean add(char ch) {return false;}
0120: int addAll(String chars,int offset,int length) {return 0;}
0121: int addAll(char[] chars,int offset,int length) {return 0;}
0122: int addAll(Abstract set) {return 0;}
0123: boolean remove(char ch) {
0124: CharSet.this.set = new CharSet.CharComplement(ch);
0125: CharSet.this.modifiedFlag = true;
0126: return true;
0127: }
0128: int removeAll(Abstract set) {
0129: if (set instanceof Char) CharSet.this.set = new CharComplement( (Char)set );
0130: else
0131: if (set instanceof LongMap) CharSet.this.set = new LongMapComplement( (LongMap)set );
0132: else
0133: if (set instanceof CharComplement) CharSet.this.set = new Char( (CharComplement)set );
0134: else
0135: if (set instanceof LongMapComplement) CharSet.this.set = new LongMap( (LongMapComplement)set );
0136: else
0137: if (set instanceof Full) CharSet.this.set = new Empty();
0138:
0139: return set.size();
0140: }
0141: boolean retain(char ch) {
0142: CharSet.this.set = new CharSet.Char(ch);
0143: return true;
0144: }
0145: int retainAll(Abstract set) {
0146: if (set instanceof Char) CharSet.this.set = new Char( (Char)set );
0147: else
0148: if (set instanceof LongMap) CharSet.this.set = new LongMap( (LongMap)set );
0149: else
0150: if (set instanceof CharComplement) CharSet.this.set = new CharComplement( (CharComplement)set );
0151: else
0152: if (set instanceof LongMapComplement) CharSet.this.set = new LongMapComplement( (LongMapComplement)set );
0153: else
0154: if (set instanceof Empty) CharSet.this.set = new Empty();
0155:
0156: return set.size();
0157: }
0158: ISet_char.Iterator iterator() {
0159: return new ISet_char.Iterator() {
0160: int index = 0;
0161: public boolean hasNext() {
0162: if (CharSet.this.modifiedFlag) throw new ConcurrentModificationException();
0163: return this.index!=65536;
0164: }
0165: public char next() {
0166: if (this.index==65536) throw new NoSuchElementException();
0167: if (CharSet.this.modifiedFlag) throw new ConcurrentModificationException();
0168: final char result = (char)this.index;
0169: ++this.index;
0170: return result;
0171: }
0172: };
0173: }
0174: };
0175:
0176: final class Char extends Abstract {
0177: final char ch;
0178: Char(char ch) {this.ch = ch;}
0179: int size() {return 1;}
0180: boolean isEmpty() {return false;}
0181: boolean contains(char ch) {return this.ch==ch;}
0182: void complement() {
0183: CharSet.this.set = new CharSet.CharComplement(this.ch);
0184: }
0185: boolean add(char ch) {
0186: if (ch==this.ch) return false;
0187: CharSet.this.set = new CharSet.LongMap(this.ch,ch);
0188: return true;
0189: }
0190: int addAll(String chars,int offset,int length) {
0191: loop: {
0192: for (; length>0; ++offset,--length)
0193: if (chars.charAt(offset)!=this.ch) break loop;
0194: return 0;
0195: }
0196:
0197: CharSet.this.set = new CharSet.LongMap(this.ch,chars.charAt(offset));
0198: return 1+CharSet.this.set.addAll(chars,++offset,--length);
0199: }
0200:
0201: int addAll(char[] chars,int offset,int length) {
0202: loop: {
0203: for (; length>0; ++offset,--length)
0204: if (chars[offset]!=this.ch) break loop;
0205: return 0;
0206: }
0207:
0208: CharSet.this.set = new CharSet.LongMap(this.ch,chars[offset]);
0209: return 1+CharSet.this.set.addAll(chars,++offset,--length);
0210: }
0211:
0212: int addAll(Abstract set) {
0213: if (set instanceof Char) {
0214: if (this.ch!=((Char)set).ch) CharSet.this.set = new LongMap( this,(Char)set );
0215: else {
0216: return 0;
0217: }
0218: } else
0219: if (set instanceof LongMap) {
0220: if (set.contains(this.ch)==false) CharSet.this.set = new LongMap( this,(LongMap)set );
0221: else {
0222: CharSet.this.set = new LongMap( (LongMap)set );
0223: return set.size()-1;
0224: }
0225: } else
0226: if (set instanceof CharComplement) {
0227: if ( ((CharComplement)set).ch==this.ch ) CharSet.this.set = new Full();
0228: else {
0229: CharSet.this.set = new LongMapComplement( (CharComplement)set );
0230: return 65534;
0231: }
0232: } else
0233: if (set instanceof LongMapComplement) {
0234: if (set.contains(this.ch)==false) CharSet.this.set = new LongMapComplement( this,(LongMapComplement)set );
0235: else {
0236: CharSet.this.set = new LongMapComplement( (LongMapComplement)set );
0237: return set.size()-1;
0238: }
0239: }
0240:
0241: return set.size();
0242: }
0243:
0244: boolean remove(char ch) {
0245: if (this.ch==ch) return false;
0246: CharSet.this.set = new CharSet.Empty();
0247: CharSet.this.modifiedFlag = true;
0248: return true;
0249: }
0250:
0251: int removeAll(Abstract set) {
0252: if (set.contains(this.ch)==false) return 0;
0253: CharSet.this.set = new Empty();
0254: return 1;
0255: }
0256:
0257: boolean retain(char ch) {
0258: if (this.ch==ch) return true;
0259: CharSet.this.set = new Empty();
0260: return false;
0261: }
0262:
0263: int retainAll(Abstract set) {
0264: if (set.contains(this.ch)) return 1;
0265: CharSet.this.set = new Empty();
0266: return false;
0267: }
0268:
0269:
0270: ISet_char.Iterator iterator() {
0271: return new ISet_char.Iterator() {
0272: boolean hasNext = true;
0273: public boolean hasNext() {
0274: if (CharSet.this.modifiedFlag) throw new ConcurrentModificationException();
0275: return this.hasNext;
0276: }
0277: public char next() {
0278: if (this.hasNext==false) throw new NoSuchElementException();
0279: if (CharSet.this.modifiedFlag) throw new ConcurrentModificationException();
0280: this.hasNext = false;
0281: return CharSet.Char.this.ch;
0282: }
0283: };
0284: }
0285: }
0286:
0287: final class CharComplement extends Abstract {
0288: final char ch;
0289: CharComplement(char ch) {this.ch = ch;}
0290: int size() {return 65534;}
0291: boolean isEmpty() {return false;}
0292: void complement() {CharSet.this.set = new CharSet.Char(this.ch);}
0293: boolean contains(char ch) {return this.ch!=ch;}
0294: boolean add(char ch) {
0295: if (ch!=this.ch) return false;
0296: CharSet.this.set = new CharSet.Full();
0297: return true;
0298: }
0299: int addAll(String chars,int offset,int length) {
0300: for (; length>0; ++offset,--length) {
0301: if (chars.charAt(offset)==this.ch) {
0302: CharSet.this.set = new CharSet.Full();
0303: return 1;
0304: }
0305: }
0306: return 0;
0307: }
0308: int addAll(char[] chars,int offset,int length) {
0309: for (; length>0; ++offset,--length) {
0310: if (chars[offset]==this.ch) {
0311: CharSet.this.set = new CharSet.Full();
0312: return 1;
0313: }
0314: }
0315: return 0;
0316: }
0317: int addAll(Abstract set) {
0318: if (set.contains(this.ch)==false) return 0;
0319: else {
0320: CharSet.this.set = new Full();
0321: return 1;
0322: }
0323: }
0324:
0325: boolean remove(char ch) {
0326: if (ch==this.ch) return false;
0327: CharSet.this.set = new LongMapComplement(this.ch,ch);
0328: CharSet.this.modifiedFlag = true;
0329: return true;
0330: }
0331:
0332: int removeAll(Abstract set) {
0333: if (set instanceof Char) {
0334: if ( set.contains(this.ch) ) return 0;
0335: else {
0336: CharSet.this.set = new LongMapComplement(this.ch,((Char)set).ch);
0337: return 1; // set.size();
0338: }
0339: } else
0340: if (set instanceof LongMap) {
0341: if ( set.contains(this.ch) ) {
0342: CharSet.this.set = new LongMapComplement((LongMap)map);
0343: return set.size()-1;
0344: } else {
0345: LongMap tmp = new LongMapComplement(this.ch,(LongMap)map);
0346: return set.size();
0347: }
0348: } else
0349: if (set instanceof CharComplement) {
0350: if ( set.contains(this.ch) ) {
0351: CharSet.this.set = new Char(this.ch);
0352: return 65534; // set.size()-1
0353: } else {
0354: CharSet.this.set = new Empty();
0355: return 65535;
0356: }
0357: } else
0358: if (set instanceof LongMapComplement) {
0359: if (set.contains(this.ch)) {
0360: CharSet.this.set = new LongMap(((LongMapComplement)set).);
0361: return set.size()-1;
0362: }
0363: }
0364:
0365: }
0366:
0367: boolean retain(char ch) {
0368: if (this.ch==ch) {
0369: CharSet.this.set = new Empty();
0370: return false;
0371: } else {
0372: CharSet.this.set = new Char(ch);
0373: return true;
0374: }
0375: }
0376:
0377: int retain(Abstract set) {
0378: if (set.contains(this.ch)) {
0379: CharSet.this.set = new Empty();
0380: return 0;
0381: } else {
0382: CharSet.this.set = Char((Char)set);
0383: }
0384:
0385: return set.size();
0386: }
0387:
0388: ISet_char.Iterator iterator() {
0389: return new ISet_char.Iterator() {
0390: int index = 0;
0391: public boolean hasNext() {
0392: if (this.index==(int)CharSet.CharComplement.this.ch) ++this.index;
0393: return this.index!=65536;
0394: }
0395: public char next() {
0396: if (this.index==(int)CharSet.CharComplement.this.ch) ++this.index;
0397: if (this.index==65536) throw new NoSuchElementException();
0398: if (CharSet.this.modifiedFlag) throw new ConcurrentModificationException();
0399: final char result = (char)this.index;
0400: ++this.index;
0401: return result;
0402: }
0403: };
0404: }
0405: }
0406: */
0407:
0408: // static int wrapperCount = 0;
0409: static final class Wrapper implements java.io.Serializable {
0410: final int offset;
0411: long value;
0412:
0413: Wrapper(int offset, long value) {
0414: this .offset = offset;
0415: this .value = value;
0416:
0417: // ++wrapperCount;
0418: // if (wrapperCount>1060000) System.out.println("+"+wrapperCount);
0419: }
0420:
0421: // protected void finalize() throws Throwable {
0422: // --wrapperCount;
0423: // if (wrapperCount>99900 && wrapperCount<100000) System.out.println("-"+wrapperCount);
0424: // }
0425:
0426: int size() {
0427: int answer = 0;
0428: for (long tmp = this .value; tmp != 0; tmp >>>= 4) {
0429: switch ((int) (tmp & 15L)) {
0430: case 0:
0431: answer += 0;
0432: break;
0433: case 1:
0434: answer += 1;
0435: break;
0436: case 2:
0437: answer += 1;
0438: break;
0439: case 3:
0440: answer += 2;
0441: break;
0442: case 4:
0443: answer += 1;
0444: break;
0445: case 5:
0446: answer += 2;
0447: break;
0448: case 6:
0449: answer += 2;
0450: break;
0451: case 7:
0452: answer += 3;
0453: break;
0454: case 8:
0455: answer += 1;
0456: break;
0457: case 9:
0458: answer += 2;
0459: break;
0460: case 10:
0461: answer += 2;
0462: break;
0463: case 11:
0464: answer += 3;
0465: break;
0466: case 12:
0467: answer += 2;
0468: break;
0469: case 13:
0470: answer += 3;
0471: break;
0472: case 14:
0473: answer += 3;
0474: break;
0475: case 15:
0476: answer += 4;
0477: break;
0478: default:
0479: throw new RuntimeException(
0480: "error: should never happen");
0481: }
0482: }
0483: return answer;
0484: }
0485: }
0486:
0487: final static int[] PRIMENUMBERS = new int[] { 3, 5, 7, 11, 13, 17,
0488: 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
0489: 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
0490: 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
0491: 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271,
0492: 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
0493: 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421,
0494: 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
0495: 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
0496: 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647,
0497: 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
0498: 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821,
0499: 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
0500: 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
0501: 991, 997, 1009, 1013, 1019, 1021, 1024 };
0502:
0503: final static long[] VALUES = new long[64];
0504: static {
0505: VALUES[0] = 1L;
0506: for (int t = 0, i = 1; i < VALUES.length; ++i, ++t)
0507: VALUES[i] = VALUES[t] << 1;
0508: }
0509:
0510: final class LongMap implements IAbstract {
0511:
0512: Wrapper[] sets = null;
0513: int size = 0;
0514:
0515: protected LongMap(LongMap set) {
0516: this .sets = new Wrapper[set.sets.length];
0517: for (int i = 0; i < set.sets.length; ++i)
0518: if (set.sets[i] != null)
0519: this .sets[i] = new Wrapper(set.sets[i].offset,
0520: set.sets[i].value);
0521:
0522: this .size = set.size;
0523: }
0524:
0525: LongMap() {
0526: this .sets = new Wrapper[CharSet.PRIMENUMBERS[0]];
0527: }
0528:
0529: LongMap(char ch1, char ch2) {
0530: this .sets = new Wrapper[CharSet.PRIMENUMBERS[0]];
0531: this .add(ch1);
0532: this .add(ch2);
0533: }
0534:
0535: public boolean isEmpty() {
0536: return this .size() == 0;
0537: }
0538:
0539: public int size() {
0540: if (this .size >= 0)
0541: return this .size;
0542: int answer = 0;
0543: for (int i = 0; i < this .sets.length; ++i) {
0544: if (this .sets[i] != null)
0545: answer += this .sets[i].size();
0546: }
0547: this .size = answer;
0548: return answer;
0549: }
0550:
0551: public boolean contains(char ch) {
0552: final int offset = ch / 64;
0553: final int index = offset % this .sets.length;
0554: if (this .sets[index] == null
0555: || this .sets[index].offset != offset)
0556: return false;
0557: return (this .sets[index].value & (VALUES[ch % 64])) != 0;
0558: }
0559:
0560: public void complement() {
0561: this .size = -1;
0562: final Wrapper[] tmp = this .sets;
0563: this .sets = new Wrapper[CharSet.PRIMENUMBERS[0]];
0564: for (int offset = 0; offset < CharSet.this .max; ++offset) {
0565: int index = offset % tmp.length;
0566: long value = -1L;
0567: if (tmp[index] != null && tmp[index].offset == offset)
0568: value ^= tmp[index].value;
0569: if (value != 0)
0570: this .addAll(offset, value);
0571: }
0572: }
0573:
0574: public boolean add(char ch) {
0575: if (ch > CharSet.this .maxChar)
0576: throw new IllegalArgumentException("ch > maxChar = "
0577: + CharSet.this .maxChar + "("
0578: + (int) CharSet.this .maxChar + ")");
0579:
0580: final int offset = ch / 64;
0581: loop: do {
0582: int index = offset % this .sets.length;
0583: if (this .sets[index] == null) {
0584: this .sets[index] = new Wrapper(offset,
0585: 1L << (ch % 64));
0586: if (this .size >= 0)
0587: ++this .size;
0588: return true;
0589: }
0590: if (this .sets[index].offset == offset) {
0591: long oldValue = this .sets[index].value;
0592: this .sets[index].value |= VALUES[ch % 64];
0593: long newValue = this .sets[index].value;
0594:
0595: if (oldValue == newValue)
0596: return false;
0597:
0598: if (this .size >= 0)
0599: ++this .size;
0600: return true;
0601: }
0602:
0603: this .expand();
0604: } while (true);
0605: }
0606:
0607: public void addAll(char[] chars, int offset, int length) {
0608: for (; length > 0; ++offset, --length)
0609: this .add(chars[offset]);
0610: }
0611:
0612: public void addAll(String chars, int offset, int length) {
0613: for (; length > 0; ++offset, --length)
0614: this .add(chars.charAt(offset));
0615: }
0616:
0617: public void addAll(IAbstract set) {
0618: this .addAll((LongMap) set);
0619: }
0620:
0621: void addAll(LongMap set) {
0622: if (this .sets.length >= set.sets.length) {
0623: for (int i = 0; i < set.sets.length; ++i) {
0624: if (set.sets[i] != null)
0625: this .addAll(set.sets[i].offset,
0626: set.sets[i].value);
0627: }
0628: } else {
0629: final Wrapper[] tmp = this .sets;
0630: this .sets = new Wrapper[set.sets.length];
0631: for (int i = 0; i < set.sets.length; ++i)
0632: this .sets[i] = (set.sets[i] == null) ? null
0633: : new Wrapper(set.sets[i].offset,
0634: set.sets[i].value);
0635: this .size = set.size;
0636:
0637: for (int i = 0; i < tmp.length; ++i) {
0638: if (tmp[i] != null)
0639: this .addAll(tmp[i]);
0640: }
0641: }
0642: }
0643:
0644: private void addAll(int offset, long value) {
0645: this .size = -1;
0646: loop: do {
0647: int index = offset % this .sets.length;
0648: if (this .sets[index] == null) {
0649: this .sets[index] = new Wrapper(offset, value);
0650: return;
0651: }
0652: if (this .sets[index].offset == offset) {
0653: this .sets[index].value |= value;
0654: return;
0655: }
0656:
0657: this .expand();
0658: } while (true);
0659: }
0660:
0661: private void addAll(Wrapper w) {
0662: this .size = -1;
0663: loop: do {
0664: int index = w.offset % this .sets.length;
0665: if (this .sets[index] == null) {
0666: this .sets[index] = w;
0667: return;
0668: }
0669: if (this .sets[index].offset == w.offset) {
0670: this .sets[index].value |= w.value;
0671: return;
0672: }
0673:
0674: this .expand();
0675: } while (true);
0676: }
0677:
0678: public boolean remove(char ch) {
0679: final int offset = ch / 64;
0680: final int index = offset % this .sets.length;
0681: if (this .sets[index] == null)
0682: return false;
0683: if (this .sets[index].offset != offset)
0684: return false;
0685:
0686: long oldValue = this .sets[index].value;
0687: this .sets[index].value &= (-1L) ^ (VALUES[ch % 64]);
0688: long newValue = this .sets[index].value;
0689:
0690: if (oldValue == newValue)
0691: return false;
0692:
0693: if (this .size > 0)
0694: --this .size;
0695: if (newValue == 0)
0696: this .sets[index] = null;
0697: return true;
0698: }
0699:
0700: public void removeAll(IAbstract set) {
0701: this .removeAll((LongMap) set);
0702: }
0703:
0704: void removeAll(LongMap set) {
0705: for (int i = 0; i < set.sets.length; ++i) {
0706: if (set.sets[i] != null)
0707: this .removeAll(set.sets[i].offset,
0708: set.sets[i].value);
0709: }
0710: }
0711:
0712: private void removeAll(int offset, long value) {
0713: final int index = offset % this .sets.length;
0714: if (this .sets[index] == null)
0715: return;
0716: if (this .sets[index].offset != offset)
0717: return;
0718:
0719: this .size = -1;
0720: this .sets[index].value &= (-1L) ^ value;
0721: if (this .sets[index].value == 0)
0722: this .sets[index] = null;
0723: }
0724:
0725: public void retainAll(IAbstract set) {
0726: this .retainAll((LongMap) set);
0727: }
0728:
0729: void retainAll(LongMap set) {
0730: this .size = -1;
0731: for (int i = 0; i < this .sets.length; ++i) {
0732: if (this .sets[i] != null) {
0733: Wrapper w1 = this .sets[i];
0734: Wrapper w2 = set.sets[w1.offset % set.sets.length];
0735: if (w2 == null)
0736: this .sets[i] = null;
0737: else {
0738: if (w1.offset != w2.offset)
0739: this .sets[i] = null;
0740: else {
0741: w1.value &= w2.value;
0742: if (this .sets[i].value == 0)
0743: this .sets[i] = null;
0744: }
0745: }
0746: }
0747: }
0748: }
0749:
0750: private void expand() {
0751: final Wrapper[] values = this .sets;
0752: reInit: do {
0753: this .sets = new Wrapper[this .nextPrimeNumber()];
0754: for (int i = 0; i < values.length; ++i) {
0755: if (values[i] != null) {
0756: int index = values[i].offset % this .sets.length;
0757: if (this .sets[index] != null)
0758: continue reInit;
0759: this .sets[index] = values[i];
0760: }
0761: }
0762: return;
0763: } while (true);
0764: }
0765:
0766: private int nextPrimeNumber() {
0767: final int currentPrimeNumber = this .sets.length;
0768: int i = 0;
0769: while (CharSet.PRIMENUMBERS[i] != currentPrimeNumber)
0770: ++i;
0771: return CharSet.PRIMENUMBERS[++i];
0772: }
0773:
0774: public ISet_char.Iterator iterator() {
0775: return new LongMapIterator(CharSet.this , this );
0776: }
0777:
0778: public boolean equals(Object obj) {
0779: if (this == obj)
0780: return true;
0781: if (obj == null)
0782: return false;
0783: if (this .getClass() != obj.getClass())
0784: return false;
0785:
0786: LongMap set = (LongMap) obj;
0787: if (this .size != set.size)
0788: return false;
0789:
0790: for (int i = 0; i < this .sets.length; ++i) {
0791: if (this .sets[i] != null) {
0792: if (this .sets[i].value == 0)
0793: throw new Error("this.sets[i].value==0");
0794: Wrapper w1 = this .sets[i];
0795: Wrapper w2 = set.sets[w1.offset % set.sets.length];
0796: if (w2 == null)
0797: return false;
0798: else {
0799: if (w1.offset != w2.offset)
0800: return false;
0801: else {
0802: if (w1.value != w2.value)
0803: return false;
0804: }
0805: }
0806: }
0807: }
0808:
0809: return true;
0810: }
0811: }
0812:
0813: private static final class LongMapIterator implements
0814: ISet_char.Iterator {
0815: int currentOffset = 0;
0816:
0817: long currentValue = 1L;
0818:
0819: char currentChar = '\u0000';
0820:
0821: final int setsLength; // = CharSet.LongMap.this.sets.length;
0822:
0823: private final LongMap longMap;
0824:
0825: private final CharSet charSet;
0826:
0827: public LongMapIterator(CharSet charSet, LongMap longMap) {
0828: this .charSet = charSet;
0829: this .longMap = longMap;
0830: this .setsLength = longMap.sets.length;
0831: }
0832:
0833: public boolean hasNext() {
0834:
0835: do {
0836: if (longMap.contains(this .currentChar))
0837: return true;
0838: } while (++this .currentChar != '\u0000');
0839: return false;
0840:
0841: /*
0842: // if (CharSet.this.modifiedFlag) throw new ConcurrentModificationException();
0843:
0844: for (; this.currentOffset<=1024; ++this.currentOffset) {
0845: Wrapper w = CharSet.LongMap.this.sets[this.currentOffset%setsLength];
0846: if (w==null) this.currentChar+= 64;
0847: else {
0848: if (w.offset==this.currentOffset) {
0849: for (; this.currentValue!=0; this.currentValue<<=1, ++this.currentChar) {
0850: if ((w.value & this.currentValue)!=0) {
0851: return true;
0852: }
0853: }
0854: this.currentValue = 1L;
0855: }
0856: }
0857: }
0858: return false;
0859: */
0860: }
0861:
0862: public char next() {
0863: do {
0864: if (longMap.contains(this .currentChar))
0865: return this .currentChar++;
0866: } while (++this .currentChar != '\u0000');
0867:
0868: throw new NoSuchElementException(charSet.toString());
0869:
0870: /*
0871: // if (CharSet.this.modifiedFlag) throw new ConcurrentModificationException();
0872:
0873: for (; this.currentOffset<=1024; ++this.currentOffset) {
0874: Wrapper w = CharSet.LongMap.this.sets[this.currentOffset%setsLength];
0875: if (w==null) this.currentChar+= 64;
0876: else {
0877: if (w.offset==this.currentOffset) {
0878: for (; this.currentValue!=0; this.currentValue<<=1, ++this.currentChar) {
0879: if ((w.value & this.currentValue)!=0) {
0880: final char result = this.currentChar;
0881: this.currentValue<<=1;
0882: if (this.currentValue!=0) ++this.currentChar;
0883: return result;
0884: }
0885: }
0886: this.currentValue = 1L;
0887: }
0888: }
0889: }
0890: throw new NoSuchElementException(this.currentChar+" \""+CharSet.this.toString()+"\" "+CharSet.this.size());
0891: */
0892: }
0893: }
0894:
0895: // CharSet.Abstract set = new Empty();
0896: // transient boolean modifiedFlag = false;
0897:
0898: static final int max = 4;
0899: static final char maxChar = (char) (64 * max - 1);
0900:
0901: protected CharSet.IAbstract set;
0902:
0903: protected CharSet(IAbstract set) {
0904: this .set = set;
0905: }
0906:
0907: public CharSet() {
0908: this .set = new LongMap();
0909: }
0910:
0911: public CharSet(char ch) {
0912: this ();
0913: this .set.add(ch);
0914: }
0915:
0916: public CharSet(String s) {
0917: this ();
0918: this .set.addAll(s, 0, s.length());
0919: }
0920:
0921: public void complement() {
0922: this .set.complement();
0923: }
0924:
0925: public boolean contains(char ch) {
0926: return this .set.contains(ch);
0927: }
0928:
0929: public boolean isEmpty() {
0930: return this .set.isEmpty();
0931: }
0932:
0933: public int size() {
0934: return this .set.size();
0935: }
0936:
0937: public ISet_char.Iterator iterator() {
0938: return this .set.iterator();
0939: }
0940:
0941: public void clear() {
0942: // this.set = new CharSet.Empty();
0943: this .set = new LongMap();
0944: }
0945:
0946: public boolean add(char ch) {
0947:
0948: return this .set.add(ch);
0949: }
0950:
0951: public boolean remove(char ch) {
0952: return this .set.remove(ch);
0953: }
0954:
0955: public void addAll(String chars) {
0956: this .addAll(chars, 0, chars.length());
0957: }
0958:
0959: public void addAll(String chars, int offset) {
0960: this .addAll(chars, offset, chars.length() - offset);
0961: }
0962:
0963: public void addAll(String chars, int offset, int length) {
0964: if (length == 0)
0965: return;
0966: this .set.addAll(chars, offset, length);
0967: }
0968:
0969: public void addAll(char[] chars) {
0970: this .addAll(chars, 0, chars.length);
0971: }
0972:
0973: public void addAll(char[] chars, int offset) {
0974: this .addAll(chars, offset, chars.length - offset);
0975: }
0976:
0977: public void addAll(char[] chars, int offset, int length) {
0978: if (length == 0)
0979: return;
0980: this .set.addAll(chars, offset, length);
0981: }
0982:
0983: /**
0984: * adds all chars from set to this ISet_char without adding doublicates.
0985: * returns the number of chars added to this ISet_char.
0986: */
0987: public void addAll(ISet_char set) {
0988: if (set instanceof CharSet)
0989: this .set.addAll(((CharSet) set).set);
0990: else {
0991: final ISet_char.Iterator it = set.iterator();
0992: for (int i = set.size(); i > 0; --i)
0993: this .set.add(it.next());
0994: }
0995: }
0996:
0997: /**
0998: * Removes from this set all of its elements that are contained in the specified set (optional operation).
0999: * returns the number of chars that were removed.
1000: */
1001: public void removeAll(ISet_char set) {
1002: if (set instanceof CharSet)
1003: this .set.removeAll(((CharSet) set).set);
1004: else {
1005: final ISet_char.Iterator it = set.iterator();
1006: for (int i = set.size(); i > 0; --i)
1007: this .set.remove(it.next());
1008: }
1009: }
1010:
1011: public void retainAll(ISet_char set) {
1012: if (set instanceof CharSet)
1013: this .set.retainAll(((CharSet) set).set);
1014: else {
1015: final CharSet charSet = new CharSet();
1016: final ISet_char.Iterator it = set.iterator();
1017: for (int i = set.size(); i > 0; --i)
1018: charSet.add(it.next());
1019: this .set.retainAll(charSet.set);
1020: }
1021: }
1022:
1023: public boolean equals(Object obj) {
1024: if (this == obj)
1025: return true;
1026: if (obj == null)
1027: return false;
1028: if (this .getClass() != obj.getClass())
1029: return false;
1030: return this .set.equals(((CharSet) obj).set);
1031: }
1032:
1033: public int hashCode() {
1034: return this .set.size();
1035: }
1036:
1037: protected IAbstract cloneAbstract(IAbstract set) {
1038: if (set instanceof LongMap)
1039: return new LongMap((LongMap) set);
1040: throw new Error("");
1041: }
1042:
1043: public Object clone() {
1044: try {
1045: CharSet clone = (CharSet) super .clone();
1046: clone.set = clone.cloneAbstract(set);
1047: return clone;
1048: } catch (CloneNotSupportedException e) {
1049: throw new Error("CloneNotSupportedException:\n" + e);
1050: }
1051: }
1052:
1053: public String toString() {
1054: StringBuffer answer = new StringBuffer();
1055:
1056: int from = -1;
1057: char ch = '\u0000';
1058: do {
1059: if (this .contains(ch)) {
1060: if (from == -1)
1061: from = ch;
1062: } else {
1063: if (from != -1) {
1064: char to = ch;
1065: --to;
1066: if (from == to) {
1067: if (to == '[' || to == ']' || to == '\\'
1068: || to == '-')
1069: answer.append('\\');
1070: answer.append(to);
1071: } else {
1072: char char_from = (char) from;
1073: if (char_from == '[' || char_from == ']'
1074: || char_from == '\\'
1075: || char_from == '-')
1076: answer.append('\\');
1077: answer.append((char) from);
1078: if (to != ++from)
1079: answer.append("-");
1080: if (to == '[' || to == ']' || to == '\\'
1081: || to == '-')
1082: answer.append('\\');
1083: answer.append(to);
1084: }
1085:
1086: from = -1;
1087: }
1088: }
1089: } while (++ch != '\u0000');
1090:
1091: if (from != -1) {
1092: char char_from = (char) from;
1093: if (char_from == '[' || char_from == ']'
1094: || char_from == '\\' || char_from == '-')
1095: answer.append('\\');
1096: answer.append((char) from);
1097: if (from != '\ufffe')
1098: answer.append('-');
1099: answer.append('\uffff');
1100: }
1101:
1102: for (int i = answer.length() - 1; i >= 0; --i) {
1103: if (answer.charAt(i) > '\u00ff')
1104: answer.setCharAt(i, '.');
1105: }
1106:
1107: return answer.toString();
1108: }
1109:
1110: }
|