|
1
20 package JFlex;
21
22
30 final public class StateSet {
31
32 private final boolean DEBUG = false;
33
34 public final static StateSet EMPTY = new StateSet();
35
36
37 final static int BITS = 6;
38 final static int MASK = (1<<BITS)-1;
39
40 long bits[];
41
42
43 public StateSet() {
44 this(256);
45 }
46
47 public StateSet(int size) {
48 bits = new long[size2nbits(size)];
49 }
50
51 public StateSet(int size, int state) {
52 this(size);
53 addState(state);
54 }
55
56 public StateSet(StateSet set) {
57 bits = new long[set.bits.length];
58 System.arraycopy(set.bits, 0, bits, 0, set.bits.length);
59 }
60
61
62 public void addState(int state) {
63 if (DEBUG) {
64 Out.dump("StateSet.addState("+state+") start"); Out.dump("Set is : "+this); }
67
68 int index = state >> BITS;
69 if (index >= bits.length) resize(state);
70 bits[index] |= (1L << (state & MASK));
71
72 if (DEBUG) {
73 Out.dump("StateSet.addState("+state+") end"); Out.dump("Set is : "+this); }
76 }
77
78
79 private int size2nbits (int size) {
80 return ((size >> BITS) + 1);
81 }
82
83
84 private void resize(int size) {
85 int needed = size2nbits(size);
86
87
89 long newbits[] = new long[Math.max(bits.length*4,needed)];
90 System.arraycopy(bits, 0, newbits, 0, bits.length);
91
92 bits = newbits;
93 }
94
95
96 public void clear() {
97 int l = bits.length;
98 for (int i = 0; i < l; i++) bits[i] = 0;
99 }
100
101 public boolean isElement(int state) {
102 int index = state >> BITS;
103 if (index >= bits.length) return false;
104 return (bits[index] & (1L << (state & MASK))) != 0;
105 }
106
107
112 public int getAndRemoveElement() {
113 int i = 0;
114 int o = 0;
115 long m = 1;
116
117 while (bits[i] == 0) i++;
118
119 while ( (bits[i] & m) == 0 ) {
120 m<<= 1;
121 o++;
122 }
123
124 bits[i]&= ~m;
125
126 return (i << BITS) + o;
127 }
128
129 public void remove(int state) {
130 int index = state >> BITS;
131 if (index >= bits.length) return;
132 bits[index] &= ~(1L << (state & MASK));
133 }
134
135
139 public StateSet complement(StateSet set) {
140
141 if (set == null) return null;
142
143 StateSet result = new StateSet();
144
145 result.bits = new long[set.bits.length];
146
147 int i;
148 int m = Math.min(bits.length, set.bits.length);
149
150 for (i = 0; i < m; i++) {
151 result.bits[i] = ~bits[i] & set.bits[i];
152 }
153
154 if (bits.length < set.bits.length)
155 System.arraycopy(set.bits, m, result.bits, m, result.bits.length-m);
156
157 if (DEBUG)
158 Out.dump("Complement of "+this+Out.NL+"and "+set+Out.NL+" is :"+result);
160 return result;
161 }
162
163 public void add(StateSet set) {
164
165 if (DEBUG) Out.dump("StateSet.add("+set+") start");
167 if (set == null) return;
168
169 long tbits[];
170 long sbits[] = set.bits;
171 int sbitsl = sbits.length;
172
173 if (bits.length < sbitsl) {
174 tbits = new long[sbitsl];
175 System.arraycopy(bits, 0, tbits, 0, bits.length);
176 }
177 else {
178 tbits = this.bits;
179 }
180
181 for (int i = 0; i < sbitsl; i++) {
182 tbits[i] |= sbits[i];
183 }
184
185 this.bits = tbits;
186
187 if (DEBUG) {
188 Out.dump("StateSet.add("+set+") end"); Out.dump("Set is : "+this); }
191 }
192
193
194
195 public boolean containsSet(StateSet set) {
196
197 if (DEBUG)
198 Out.dump("StateSet.containsSet("+set+"), this="+this);
200 int i;
201 int min = Math.min(bits.length, set.bits.length);
202
203 for (i = 0; i < min; i++)
204 if ( (bits[i] & set.bits[i]) != set.bits[i] ) return false;
205
206 for (i = min; i < set.bits.length; i++)
207 if ( set.bits[i] != 0 ) return false;
208
209 return true;
210 }
211
212
213
214
218 public boolean equals(Object  b) {
219
220 int i = 0;
221 int l1,l2;
222 StateSet set = (StateSet) b;
223
224 if (DEBUG) Out.dump("StateSet.equals("+set+"), this="+this);
226 l1 = bits.length;
227 l2 = set.bits.length;
228
229 if (l1 <= l2) {
230 while (i < l1) {
231 if (bits[i] != set.bits[i]) return false;
232 i++;
233 }
234
235 while (i < l2)
236 if (set.bits[i++] != 0) return false;
237 }
238 else {
239 while (i < l2) {
240 if (bits[i] != set.bits[i]) return false;
241 i++;
242 }
243
244 while (i < l1)
245 if (bits[i++] != 0) return false;
246 }
247
248 return true;
249 }
250
251 public int hashCode() {
252 long h = 1234;
253 long [] _bits = bits;
254 int i = bits.length-1;
255
256 while (i >= 0 && _bits[i] == 0) i--;
258
259 while (i >= 0)
260 h ^= _bits[i--] * i;
261
262 return (int)((h >> 32) ^ h);
263 }
264
265
266 public StateSetEnumerator states() {
267 return new StateSetEnumerator(this);
268 }
269
270
271 public boolean containsElements() {
272 for (int i = 0; i < bits.length; i++)
273 if (bits[i] != 0) return true;
274
275 return false;
276 }
277
278
279 public StateSet copy() {
280 StateSet set = new StateSet();
281 set.bits = new long[bits.length];
282 System.arraycopy(bits, 0, set.bits, 0, bits.length);
283 return set;
284 }
285
286
287 public void copy(StateSet set) {
288
289 if (DEBUG)
290 Out.dump("StateSet.copy("+set+") start");
292 if (set == null) {
293 for (int i = 0; i < bits.length; i++) bits[i] = 0;
294 return;
295 }
296
297 if (bits.length < set.bits.length) {
298 bits = new long[set.bits.length];
299 }
300 else {
301 for (int i = set.bits.length; i < bits.length; i++) bits[i] = 0;
302 }
303
304 System.arraycopy(set.bits, 0, bits, 0, bits.length);
305
306 if (DEBUG) {
307 Out.dump("StateSet.copy("+set+") end"); Out.dump("Set is : "+this); }
310 }
311
312
313 public String toString() {
314 StateSetEnumerator set = states();
315
316 StringBuffer result = new StringBuffer ("{");
318 if ( set.hasMoreElements() ) result.append(""+set.nextElement());
320 while ( set.hasMoreElements() ) {
321 int i = set.nextElement();
322 result.append( ", "+i); }
324
325 result.append("}");
327 return result.toString();
328 }
329 }
330 |
Popular Tags |
Java API By Example, From Geeks To Geeks.