1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
|
---|
2 | * JFlex 1.4.3 *
|
---|
3 | * Copyright (C) 1998-2009 Gerwin Klein <[email protected]> *
|
---|
4 | * All rights reserved. *
|
---|
5 | * *
|
---|
6 | * This program is free software; you can redistribute it and/or modify *
|
---|
7 | * it under the terms of the GNU General Public License. See the file *
|
---|
8 | * COPYRIGHT for more information. *
|
---|
9 | * *
|
---|
10 | * This program is distributed in the hope that it will be useful, *
|
---|
11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of *
|
---|
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
|
---|
13 | * GNU General Public License for more details. *
|
---|
14 | * *
|
---|
15 | * You should have received a copy of the GNU General Public License along *
|
---|
16 | * with this program; if not, write to the Free Software Foundation, Inc., *
|
---|
17 | * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *
|
---|
18 | * *
|
---|
19 | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
|
---|
20 | package JFlex;
|
---|
21 |
|
---|
22 | /**
|
---|
23 | * A set of NFA states (= integers).
|
---|
24 | *
|
---|
25 | * Very similar to java.util.BitSet, but is faster and doesn't crash
|
---|
26 | *
|
---|
27 | * @author Gerwin Klein
|
---|
28 | * @version JFlex 1.4.3, $Revision: 433 $, $Date: 2009-01-31 19:52:34 +1100 (Sat, 31 Jan 2009) $
|
---|
29 | */
|
---|
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"); //$NON-NLS-1$ //$NON-NLS-2$
|
---|
65 | Out.dump("Set is : "+this); //$NON-NLS-1$
|
---|
66 | }
|
---|
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"); //$NON-NLS-1$ //$NON-NLS-2$
|
---|
74 | Out.dump("Set is : "+this); //$NON-NLS-1$
|
---|
75 | }
|
---|
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 | // if (needed < bits.length) return;
|
---|
88 |
|
---|
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 | /**
|
---|
108 | * Returns one element of the set and removes it.
|
---|
109 | *
|
---|
110 | * Precondition: the set is not empty.
|
---|
111 | */
|
---|
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 | /**
|
---|
136 | * Returns the set of elements that contained are in the specified set
|
---|
137 | * but are not contained in this set.
|
---|
138 | */
|
---|
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); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
|
---|
159 |
|
---|
160 | return result;
|
---|
161 | }
|
---|
162 |
|
---|
163 | public void add(StateSet set) {
|
---|
164 |
|
---|
165 | if (DEBUG) Out.dump("StateSet.add("+set+") start"); //$NON-NLS-1$ //$NON-NLS-2$
|
---|
166 |
|
---|
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"); //$NON-NLS-1$ //$NON-NLS-2$
|
---|
189 | Out.dump("Set is : "+this); //$NON-NLS-1$
|
---|
190 | }
|
---|
191 | }
|
---|
192 |
|
---|
193 |
|
---|
194 |
|
---|
195 | public boolean containsSet(StateSet set) {
|
---|
196 |
|
---|
197 | if (DEBUG)
|
---|
198 | Out.dump("StateSet.containsSet("+set+"), this="+this); //$NON-NLS-1$ //$NON-NLS-2$
|
---|
199 |
|
---|
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 | /**
|
---|
215 | * @throws ClassCastException if b is not a StateSet
|
---|
216 | * @throws NullPointerException if b is null
|
---|
217 | */
|
---|
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); //$NON-NLS-1$ //$NON-NLS-2$
|
---|
225 |
|
---|
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 | // ignore zero high bits
|
---|
257 | 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 | /**
|
---|
288 | * Copy specified StateSet into this.
|
---|
289 | *
|
---|
290 | * @param set the state set to copy.
|
---|
291 | */
|
---|
292 | public void copy(StateSet set) {
|
---|
293 |
|
---|
294 | if (DEBUG)
|
---|
295 | Out.dump("StateSet.copy("+set+") start"); //$NON-NLS-1$ //$NON-NLS-2$
|
---|
296 |
|
---|
297 | if (set == null) {
|
---|
298 | for (int i = 0; i < bits.length; i++) bits[i] = 0;
|
---|
299 | return;
|
---|
300 | }
|
---|
301 |
|
---|
302 | if (bits.length < set.bits.length) {
|
---|
303 | bits = new long[set.bits.length];
|
---|
304 | }
|
---|
305 | else {
|
---|
306 | for (int i = set.bits.length; i < bits.length; i++) bits[i] = 0;
|
---|
307 | }
|
---|
308 |
|
---|
309 | System.arraycopy(set.bits, 0, bits, 0, bits.length);
|
---|
310 |
|
---|
311 | if (DEBUG) {
|
---|
312 | Out.dump("StateSet.copy("+set+") end"); //$NON-NLS-1$ //$NON-NLS-2$
|
---|
313 | Out.dump("Set is : "+this); //$NON-NLS-1$
|
---|
314 | }
|
---|
315 | }
|
---|
316 |
|
---|
317 |
|
---|
318 | public String toString() {
|
---|
319 | StateSetEnumerator set = states();
|
---|
320 |
|
---|
321 | StringBuffer result = new StringBuffer("{"); //$NON-NLS-1$
|
---|
322 |
|
---|
323 | if ( set.hasMoreElements() ) result.append(""+set.nextElement()); //$NON-NLS-1$
|
---|
324 |
|
---|
325 | while ( set.hasMoreElements() ) {
|
---|
326 | int i = set.nextElement();
|
---|
327 | result.append( ", "+i); //$NON-NLS-1$
|
---|
328 | }
|
---|
329 |
|
---|
330 | result.append("}"); //$NON-NLS-1$
|
---|
331 |
|
---|
332 | return result.toString();
|
---|
333 | }
|
---|
334 | }
|
---|