20
20
// With many thanks to Eric V. Smith from the ANTLR list.
23
/*A BitSet to replace java.util.BitSet.
24
* Primary differences are that most set operators return new sets
25
* as opposed to oring and anding "in place". Further, a number of
26
* operations were added. I cannot contain a BitSet because there
27
* is no way to access the internal bits (which I need for speed)
28
* and, because it is final, I cannot subclass to add functionality.
29
* Consider defining set degree. Without access to the bits, I must
30
* call a method n times to test the ith bit...ack!
32
* Also seems like or() from util is wrong when size of incoming set is bigger
33
* than this.bits.length.
35
* @author Terence Parr
36
* @author <br><a href="mailto:pete@yamuna.demon.co.uk">Pete Wells</a>
39
public class BitSet : ICloneable
41
protected internal const int BITS = 64; // number of bits / long
42
protected internal const int NIBBLE = 4;
43
protected internal const int LOG_BITS = 6; // 2^6 == 64
45
/*We will often need to do a mod operator (i mod nbits). Its
46
* turns out that, for powers of two, this mod operation is
47
* same as (i & (nbits-1)). Since mod is slow, we use a
48
* precomputed mod mask to do the mod instead.
50
protected internal static readonly int MOD_MASK = BITS - 1;
52
/*The actual data bits */
53
protected internal long[] dataBits;
55
/*Construct a bitset of size one word (64 bits) */
56
public BitSet() : this(BITS)
60
/*Construction from a static array of longs */
61
public BitSet(long[] bits_)
66
/*Construct a bitset given the size
67
* @param nbits The size of the bitset in bits
69
public BitSet(int nbits)
71
dataBits = new long[((nbits - 1) >> LOG_BITS) + 1];
74
/*or this element into this set (grow as necessary to accommodate) */
75
public virtual void add(int el)
77
int n = wordNumber(el);
78
if (n >= dataBits.Length)
82
dataBits[n] |= bitMask(el);
85
public virtual BitSet and(BitSet a)
87
BitSet s = (BitSet) this.Clone();
92
public virtual void andInPlace(BitSet a)
94
int min = (int) (Math.Min(dataBits.Length, a.dataBits.Length));
95
for (int i = min - 1; i >= 0; i--)
97
dataBits[i] &= a.dataBits[i];
99
// clear all bits in this not present in a (if this bigger than a).
100
for (int i = min; i < dataBits.Length; i++)
106
private static long bitMask(int bitNumber)
108
int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
109
return 1L << bitPosition;
112
public virtual void clear()
114
for (int i = dataBits.Length - 1; i >= 0; i--)
120
public virtual void clear(int el)
122
int n = wordNumber(el);
123
if (n >= dataBits.Length)
125
// grow as necessary to accommodate
128
dataBits[n] &= ~ bitMask(el);
131
public virtual object Clone()
137
s.dataBits = new long[dataBits.Length];
138
Array.Copy(dataBits, 0, s.dataBits, 0, dataBits.Length);
140
catch //(System.Exception e)
142
throw new System.ApplicationException();
147
public virtual int degree()
150
for (int i = dataBits.Length - 1; i >= 0; i--)
152
long word = dataBits[i];
155
for (int bit = BITS - 1; bit >= 0; bit--)
157
if ((word & (1L << bit)) != 0)
167
override public int GetHashCode()
169
return dataBits.GetHashCode();
172
/*code "inherited" from java.util.BitSet */
173
override public bool Equals(object obj)
175
if ((obj != null) && (obj is BitSet))
177
BitSet bset = (BitSet) obj;
179
int n = (int) (System.Math.Min(dataBits.Length, bset.dataBits.Length));
180
for (int i = n; i-- > 0; )
182
if (dataBits[i] != bset.dataBits[i])
187
if (dataBits.Length > n)
189
for (int i = (int) (dataBits.Length); i-- > n; )
191
if (dataBits[i] != 0)
197
else if (bset.dataBits.Length > n)
199
for (int i = (int) (bset.dataBits.Length); i-- > n; )
201
if (bset.dataBits[i] != 0)
213
* Grows the set to a larger number of bits.
214
* @param bit element that must fit in set
216
public virtual void growToInclude(int bit)
218
int newSize = (int) (System.Math.Max(dataBits.Length << 1, numWordsToHold(bit)));
219
long[] newbits = new long[newSize];
220
Array.Copy(dataBits, 0, newbits, 0, dataBits.Length);
224
public virtual bool member(int el)
226
int n = wordNumber(el);
227
if (n >= dataBits.Length)
229
return (dataBits[n] & bitMask(el)) != 0;
232
public virtual bool nil()
234
for (int i = dataBits.Length - 1; i >= 0; i--)
236
if (dataBits[i] != 0)
242
public virtual BitSet not()
244
BitSet s = (BitSet) this.Clone();
249
public virtual void notInPlace()
251
for (int i = dataBits.Length - 1; i >= 0; i--)
253
dataBits[i] = ~ dataBits[i];
257
/*complement bits in the range 0..maxBit. */
258
public virtual void notInPlace(int maxBit)
260
notInPlace(0, maxBit);
263
/*complement bits in the range minBit..maxBit.*/
264
public virtual void notInPlace(int minBit, int maxBit)
266
// make sure that we have room for maxBit
267
growToInclude(maxBit);
268
for (int i = minBit; i <= maxBit; i++)
270
int n = wordNumber(i);
271
dataBits[n] ^= bitMask(i);
275
private int numWordsToHold(int el)
277
return (el >> LOG_BITS) + 1;
280
public static BitSet of(int el)
282
BitSet s = new BitSet(el + 1);
287
/*return this | a in a new set */
288
public virtual BitSet or(BitSet a)
290
BitSet s = (BitSet) this.Clone();
295
public virtual void orInPlace(BitSet a)
297
// If this is smaller than a, grow this first
298
if (a.dataBits.Length > dataBits.Length)
300
setSize((int) (a.dataBits.Length));
302
int min = (int) (System.Math.Min(dataBits.Length, a.dataBits.Length));
303
for (int i = min - 1; i >= 0; i--)
305
dataBits[i] |= a.dataBits[i];
309
// remove this element from this set
310
public virtual void remove(int el)
312
int n = wordNumber(el);
313
if (n >= dataBits.Length)
317
dataBits[n] &= ~ bitMask(el);
321
* Sets the size of a set.
322
* @param nwords how many words the new set should be
324
private void setSize(int nwords)
326
long[] newbits = new long[nwords];
327
int n = (int) (System.Math.Min(nwords, dataBits.Length));
328
Array.Copy(dataBits, 0, newbits, 0, n);
332
public virtual int size()
334
return dataBits.Length << LOG_BITS; // num words * bits per word
337
/*return how much space is being used by the dataBits array not
338
* how many actually have member bits on.
340
public virtual int lengthInLongWords()
342
return dataBits.Length;
345
/*Is this contained within a? */
346
public virtual bool subset(BitSet a)
348
if (a == null) //(a == null || !(a is BitSet))
350
return this.and(a).Equals(this);
353
/*Subtract the elements of 'a' from 'this' in-place.
354
* Basically, just turn off all bits of 'this' that are in 'a'.
356
public virtual void subtractInPlace(BitSet a)
360
// for all words of 'a', turn off corresponding bits of 'this'
361
for (int i = 0; i < dataBits.Length && i < a.dataBits.Length; i++)
363
dataBits[i] &= ~ a.dataBits[i];
367
public virtual int[] toArray()
369
int[] elems = new int[degree()];
371
for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
381
public virtual long[] toPackedArray()
386
override public string ToString()
388
return ToString(",");
391
/*Transform a bit set into a string by formatting each element as an integer
392
* @separator The string to put in between elements
393
* @return A commma-separated list of values
395
public virtual string ToString(string separator)
398
for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
412
/*Create a string representation where instead of integer elements, the
413
* ith element of vocabulary is displayed instead. Vocabulary is a Vector
415
* @separator The string to put in between elements
416
* @return A commma-separated list of character constants.
418
public virtual string ToString(string separator, ArrayList vocabulary)
420
if (vocabulary == null)
422
return ToString(separator);
425
for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
433
if (i >= vocabulary.Count)
435
str += "<bad element " + i + ">";
437
else if (vocabulary[i] == null)
439
str += "<" + i + ">";
443
str += (string) vocabulary[i];
451
* Dump a comma-separated list of the words making up the bit set.
452
* Split each 64 bit number into two more manageable 32 bit numbers.
453
* This generates a comma-separated list of C++-like unsigned long constants.
455
public virtual string toStringOfHalfWords()
457
string s = new string("".ToCharArray());
458
for (int i = 0; i < dataBits.Length; i++)
462
long tmp = dataBits[i];
466
tmp = SupportClass.URShift(dataBits[i], 32);
474
* Dump a comma-separated list of the words making up the bit set.
475
* This generates a comma-separated list of Java-like long int constants.
477
public virtual string toStringOfWords()
479
string s = new string("".ToCharArray());
480
for (int i = 0; i < dataBits.Length; i++)
484
s += (dataBits[i] + "L");
489
/*Print out the bit set but collapse char ranges. */
490
/* public virtual string toStringWithRanges(string separator, CharFormatter formatter)
493
int[] elems = this.toArray();
494
if (elems.Length == 0)
500
while (i < elems.Length)
504
for (int j = i + 1; j < elems.Length; j++)
506
if (elems[j] != elems[j - 1] + 1)
517
if (lastInRange - i >= 2)
519
str += formatter.literalChar(elems[i]);
521
str += formatter.literalChar(elems[lastInRange]);
522
i = lastInRange; // skip past end of range for next range
526
// no range, just print current char and move on
527
str += formatter.literalChar(elems[i]);
534
private static int wordNumber(int bit)
536
return bit >> LOG_BITS; // bit / BITS
23
/*A BitSet to replace java.util.BitSet.
24
* Primary differences are that most set operators return new sets
25
* as opposed to oring and anding "in place". Further, a number of
26
* operations were added. I cannot contain a BitSet because there
27
* is no way to access the internal bits (which I need for speed)
28
* and, because it is final, I cannot subclass to add functionality.
29
* Consider defining set degree. Without access to the bits, I must
30
* call a method n times to test the ith bit...ack!
32
* Also seems like or() from util is wrong when size of incoming set is bigger
33
* than this.bits.length.
35
* @author Terence Parr
36
* @author <br><a href="mailto:pete@yamuna.demon.co.uk">Pete Wells</a>
39
public class BitSet : ICloneable
41
protected internal const int BITS = 64; // number of bits / long
42
protected internal const int NIBBLE = 4;
43
protected internal const int LOG_BITS = 6; // 2^6 == 64
45
/*We will often need to do a mod operator (i mod nbits). Its
46
* turns out that, for powers of two, this mod operation is
47
* same as (i & (nbits-1)). Since mod is slow, we use a
48
* precomputed mod mask to do the mod instead.
50
protected internal static readonly int MOD_MASK = BITS - 1;
52
/*The actual data bits */
53
protected internal long[] dataBits;
55
/*Construct a bitset of size one word (64 bits) */
56
public BitSet() : this(BITS)
60
/*Construction from a static array of longs */
61
public BitSet(long[] bits_)
66
/*Construct a bitset given the size
67
* @param nbits The size of the bitset in bits
69
public BitSet(int nbits)
71
dataBits = new long[((nbits - 1) >> LOG_BITS) + 1];
74
/*or this element into this set (grow as necessary to accommodate) */
75
public virtual void add(int el)
77
int n = wordNumber(el);
78
if (n >= dataBits.Length)
82
dataBits[n] |= bitMask(el);
85
public virtual BitSet and(BitSet a)
87
BitSet s = (BitSet) this.Clone();
92
public virtual void andInPlace(BitSet a)
94
int min = (int) (Math.Min(dataBits.Length, a.dataBits.Length));
95
for (int i = min - 1; i >= 0; i--)
97
dataBits[i] &= a.dataBits[i];
99
// clear all bits in this not present in a (if this bigger than a).
100
for (int i = min; i < dataBits.Length; i++)
106
private static long bitMask(int bitNumber)
108
int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
109
return 1L << bitPosition;
112
public virtual void clear()
114
for (int i = dataBits.Length - 1; i >= 0; i--)
120
public virtual void clear(int el)
122
int n = wordNumber(el);
123
if (n >= dataBits.Length)
125
// grow as necessary to accommodate
128
dataBits[n] &= ~ bitMask(el);
131
public virtual object Clone()
137
s.dataBits = new long[dataBits.Length];
138
Array.Copy(dataBits, 0, s.dataBits, 0, dataBits.Length);
140
catch //(System.Exception e)
142
throw new System.ApplicationException();
147
public virtual int degree()
150
for (int i = dataBits.Length - 1; i >= 0; i--)
152
long word = dataBits[i];
155
for (int bit = BITS - 1; bit >= 0; bit--)
157
if ((word & (1L << bit)) != 0)
167
override public int GetHashCode()
169
return dataBits.GetHashCode();
172
/*code "inherited" from java.util.BitSet */
173
override public bool Equals(object obj)
175
if ((obj != null) && (obj is BitSet))
177
BitSet bset = (BitSet) obj;
179
int n = (int) (System.Math.Min(dataBits.Length, bset.dataBits.Length));
180
for (int i = n; i-- > 0; )
182
if (dataBits[i] != bset.dataBits[i])
187
if (dataBits.Length > n)
189
for (int i = (int) (dataBits.Length); i-- > n; )
191
if (dataBits[i] != 0)
197
else if (bset.dataBits.Length > n)
199
for (int i = (int) (bset.dataBits.Length); i-- > n; )
201
if (bset.dataBits[i] != 0)
213
* Grows the set to a larger number of bits.
214
* @param bit element that must fit in set
216
public virtual void growToInclude(int bit)
218
int newSize = (int) (System.Math.Max(dataBits.Length << 1, numWordsToHold(bit)));
219
long[] newbits = new long[newSize];
220
Array.Copy(dataBits, 0, newbits, 0, dataBits.Length);
224
public virtual bool member(int el)
226
int n = wordNumber(el);
227
if (n >= dataBits.Length)
229
return (dataBits[n] & bitMask(el)) != 0;
232
public virtual bool nil()
234
for (int i = dataBits.Length - 1; i >= 0; i--)
236
if (dataBits[i] != 0)
242
public virtual BitSet not()
244
BitSet s = (BitSet) this.Clone();
249
public virtual void notInPlace()
251
for (int i = dataBits.Length - 1; i >= 0; i--)
253
dataBits[i] = ~ dataBits[i];
257
/*complement bits in the range 0..maxBit. */
258
public virtual void notInPlace(int maxBit)
260
notInPlace(0, maxBit);
263
/*complement bits in the range minBit..maxBit.*/
264
public virtual void notInPlace(int minBit, int maxBit)
266
// make sure that we have room for maxBit
267
growToInclude(maxBit);
268
for (int i = minBit; i <= maxBit; i++)
270
int n = wordNumber(i);
271
dataBits[n] ^= bitMask(i);
275
private int numWordsToHold(int el)
277
return (el >> LOG_BITS) + 1;
280
public static BitSet of(int el)
282
BitSet s = new BitSet(el + 1);
287
/*return this | a in a new set */
288
public virtual BitSet or(BitSet a)
290
BitSet s = (BitSet) this.Clone();
295
public virtual void orInPlace(BitSet a)
297
// If this is smaller than a, grow this first
298
if (a.dataBits.Length > dataBits.Length)
300
setSize((int) (a.dataBits.Length));
302
int min = (int) (System.Math.Min(dataBits.Length, a.dataBits.Length));
303
for (int i = min - 1; i >= 0; i--)
305
dataBits[i] |= a.dataBits[i];
309
// remove this element from this set
310
public virtual void remove(int el)
312
int n = wordNumber(el);
313
if (n >= dataBits.Length)
317
dataBits[n] &= ~ bitMask(el);
321
* Sets the size of a set.
322
* @param nwords how many words the new set should be
324
private void setSize(int nwords)
326
long[] newbits = new long[nwords];
327
int n = (int) (System.Math.Min(nwords, dataBits.Length));
328
Array.Copy(dataBits, 0, newbits, 0, n);
332
public virtual int size()
334
return dataBits.Length << LOG_BITS; // num words * bits per word
337
/*return how much space is being used by the dataBits array not
338
* how many actually have member bits on.
340
public virtual int lengthInLongWords()
342
return dataBits.Length;
345
/*Is this contained within a? */
346
public virtual bool subset(BitSet a)
348
if (a == null) //(a == null || !(a is BitSet))
350
return this.and(a).Equals(this);
353
/*Subtract the elements of 'a' from 'this' in-place.
354
* Basically, just turn off all bits of 'this' that are in 'a'.
356
public virtual void subtractInPlace(BitSet a)
360
// for all words of 'a', turn off corresponding bits of 'this'
361
for (int i = 0; i < dataBits.Length && i < a.dataBits.Length; i++)
363
dataBits[i] &= ~ a.dataBits[i];
367
public virtual int[] toArray()
369
int[] elems = new int[degree()];
371
for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
381
public virtual long[] toPackedArray()
386
override public string ToString()
388
return ToString(",");
391
/*Transform a bit set into a string by formatting each element as an integer
392
* @separator The string to put in between elements
393
* @return A commma-separated list of values
395
public virtual string ToString(string separator)
398
for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
412
/*Create a string representation where instead of integer elements, the
413
* ith element of vocabulary is displayed instead. Vocabulary is a Vector
415
* @separator The string to put in between elements
416
* @return A commma-separated list of character constants.
418
public virtual string ToString(string separator, ArrayList vocabulary)
420
if (vocabulary == null)
422
return ToString(separator);
425
for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
433
if (i >= vocabulary.Count)
435
str += "<bad element " + i + ">";
437
else if (vocabulary[i] == null)
439
str += "<" + i + ">";
443
str += (string) vocabulary[i];
451
* Dump a comma-separated list of the words making up the bit set.
452
* Split each 64 bit number into two more manageable 32 bit numbers.
453
* This generates a comma-separated list of C++-like unsigned long constants.
455
public virtual string toStringOfHalfWords()
457
string s = new string("".ToCharArray());
458
for (int i = 0; i < dataBits.Length; i++)
462
long tmp = dataBits[i];
466
tmp = SupportClass.URShift(dataBits[i], 32);
474
* Dump a comma-separated list of the words making up the bit set.
475
* This generates a comma-separated list of Java-like long int constants.
477
public virtual string toStringOfWords()
479
string s = new string("".ToCharArray());
480
for (int i = 0; i < dataBits.Length; i++)
484
s += (dataBits[i] + "L");
489
/*Print out the bit set but collapse char ranges. */
490
/* public virtual string toStringWithRanges(string separator, CharFormatter formatter)
493
int[] elems = this.toArray();
494
if (elems.Length == 0)
500
while (i < elems.Length)
504
for (int j = i + 1; j < elems.Length; j++)
506
if (elems[j] != elems[j - 1] + 1)
517
if (lastInRange - i >= 2)
519
str += formatter.literalChar(elems[i]);
521
str += formatter.literalChar(elems[lastInRange]);
522
i = lastInRange; // skip past end of range for next range
526
// no range, just print current char and move on
527
str += formatter.literalChar(elems[i]);
534
private static int wordNumber(int bit)
536
return bit >> LOG_BITS; // bit / BITS
b'\\ No newline at end of file'
added
removed
lib/csharp/src/antlr.collections.impl/BitSet.cs
