source: other-projects/rsyntax-textarea/devel-packages/jflex-1.4.3/src/JFlex/StateSet.java@ 25584

Last change on this file since 25584 was 25584, checked in by davidb, 12 years ago

Initial cut an a text edit area for GLI that supports color syntax highlighting
File size: 8.1 KB
Line 
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 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
20package 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 */
30final 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}
Note: See TracBrowser for help on using the repository browser.