* * The logic, data representation, and interface of the original Java * implementation was essentially adhered to albeit with the following * modifications: *
*
*
length() method has been replaced with a
* read-only Width property (the term "width" being
* a more appropriate description).
* *
*
Count property has been added to
* denote the cardinality of the bit set; this is to be compatible
* with what is available in the C# System.Collections classes.
* *
*
*
*
*
* Last modified on Fri Jun 24 13:12:02 2005 by hak *
* ***************************************************************** * The following are the original java.util.BitSet comments. * ***************************************************************** *
* This class implements a vector of bits that grows as needed. Each
* component of the bit set has a boolean value. The
* bits of a BitSet are indexed by nonnegative integers.
* Individual indexed bits can be examined, set, or cleared. One
* BitSet may be used to modify the contents of another
* BitSet through logical AND, logical inclusive OR, and
* logical exclusive OR operations.
*
* By default, all bits in the set initially have the value
* false.
*
* Every bit set has a current size, which is the number of bits * of space currently in use by the bit set. Note that the size is * related to the implementation of a bit set, so it may change with * implementation. The length of a bit set relates to logical length * of a bit set and is defined independently of implementation. *
* Unless otherwise noted, passing a null parameter to any of the
* methods in a BitSet will result in a
* NullPointerException.
*
* A BitSet is not safe for multithreaded use without
* external synchronization.
*
* @author Arthur van Hoff
* @author Michael McCloskey
* @version 1.60, 02/19/04
* @since JDK1.0
*/
[Serializable]
public class BitSet : ICloneable, IEnumerable // implements Cloneable, java.io.Serializable
{
/**
* BitSets are packed into arrays of "units." Currently a unit is a long,
* which consists of 64 bits, requiring 6 address bits. The choice of unit
* is determined purely by performance concerns.
*/
/**
* This is how many bits are required to encode a unit
* address. Since in our representation, a unit can store from
* 0 to 63 (i.e.,
* 26-1) bits, the required width is
* 6.
*/
private const int ADDRESS_BITS_PER_UNIT = 6;
/**
* This denotes the number of bits that can be set per unit. It
* is equal to 2ADDRESS_BITS_PER_UNIT;
* i.e., 64.
*/
private const int BITS_PER_UNIT = 1 << ADDRESS_BITS_PER_UNIT;
/**
* This denotes the mask with which to isolate the index of a
* given bit in a unit; i.e., the value of an integer from
* 0 to 63 encoded as the six rightmost bits of
* a word. Thus, this mask has its ADDRESS_BITS_PER_UNIT
* rightmost bits set to 1, and all else set to
* 0.
*/
private const int BIT_INDEX_MASK = BITS_PER_UNIT - 1;
/** Used to shift left or right for a partial word mask. */
// private const long WORD_MASK = unchecked((long)0xffffffffffffffffL);
private const ulong WORD_MASK = 0xffffffffffffffffL;
/**
* The bit units in this BitSet. The i-th bit is stored
* in units[i/64] at bit position i % 64
* (where bit position 0 refers to the least significant
* bit and 63 refers to the most significant bit).
*
INVARIANT:
* The words in bits above unitsInUse-1 are zero.
*/
private ulong[] units;
/**
* The number of units in the logical size of this BitSet.
*
INVARIANT: unitsInUse is nonnegative.
*
INVARIANT: units[unitsInUse-1] is nonzero unless
* unitsInUse is zero.
*/
[NonSerialized]
private int unitsInUse = 0;
/**
* Given a bit index, returns the unit index containing it.
* Namely, this returns the result of dividing the specified bit
* index by 2BITS_PER_UNIT (viz., 64),
* or equivalently, shifting the specified index to the right by
* ADDRESS_BITS_PER_UNIT (viz., 6) positions.
*/
private static int UnitIndex (int bitIndex)
{
return bitIndex >> ADDRESS_BITS_PER_UNIT;
}
/**
* Given a bit index, returns a unit that masks that bit in its
* unit. In other words, isolate in the index the rightmost
* ADDRESS_BITS_PER_UNIT (viz., 6) bits by using
* BIT_INDEX_MASK; this gives the remainder of the
* division of the index by 2BITS_PER_UNIT
* (viz., 64). Then, shifting a single bit so many
* positions to the left as given by the masked address takes
* us to the wanted bit.
*/
private static ulong Bit (int bitIndex)
{
return 1L << (bitIndex & BIT_INDEX_MASK);
}
/**
* Set the field unitsInUse with the logical size in
* units of the bit set.
WARNING: This function assumes that
* the number of units actually in use is less than or equal to
* the current value of
* Suppose the bits in the Overrides the Overrides the
* Overrides the Example:
*
*
* unitsInUse!
*/
private void RecalculateUnitsInUse ()
{
// Traverse the bitset until a used unit is found
int i;
for (i = unitsInUse-1; i >= 0; i--)
if (units[i] != 0)
break;
unitsInUse = i+1; // The new logical size
}
/**
* Creates a new bit set. All bits are initially false.
*/
public BitSet ()
: this(BITS_PER_UNIT)
{
}
/**
* Creates a bit set whose initial size is large enough to explicitly
* represent bits with indices in the range 0 through
* nbits-1. All bits are initially false.
*
* @param nbits the initial size of the bit set.
* @throws ArgumentOutOfRangeException if the specified initial size is negative.
*/
public BitSet (int nbits)
{
// nbits can't be negative; size 0 is OK
if (nbits < 0)
throw new ArgumentOutOfRangeException("nbits < 0: " + nbits);
units = new ulong[UnitIndex(nbits-1) + 1];
}
/**
* Ensures that the BitSet can hold enough units.
* @param unitsRequired the minimum acceptable number of units.
*/
private void EnsureCapacity (int unitsRequired)
{
if (units.Length < unitsRequired)
{
// Allocate larger of doubled size or required size
int request = Math.Max(2 * units.Length, unitsRequired);
long[] newUnits = new long[request];
Array.Copy(units, 0, newUnits, 0, unitsInUse);
units = newUnits;
}
}
/**
* Sets the bit at the specified index to the complement of its
* current value. Returns this modified bitset.
*
* @param bitIndex the index of the bit to flip.
* @throws ArgumentOutOfRangeException if the specified index is negative.
*/
public BitSet Flip (int bitIndex)
{
if (bitIndex < 0)
throw new ArgumentOutOfRangeException("bitIndex < 0: " + bitIndex);
int index = UnitIndex(bitIndex);
int unitsRequired = index+1;
if (unitsInUse < unitsRequired)
{
EnsureCapacity(unitsRequired);
units[index] ^= Bit(bitIndex);
unitsInUse = unitsRequired;
}
else
{
units[index] ^= Bit(bitIndex);
if (units[unitsInUse-1] == 0)
RecalculateUnitsInUse();
}
return this;
}
/**
* Sets each bit from the specified fromIndex(inclusive) to the
* specified toIndex(exclusive) to the complement of its current
* value. Returns this modified bitset.
*
* @param fromIndex index of the first bit to flip.
* @param toIndex index after the last bit to flip.
* @throws ArgumentOutOfRangeException if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex.
*/
public BitSet Flip (int fromIndex, int toIndex)
{
if (fromIndex < 0)
throw new ArgumentOutOfRangeException("fromIndex < 0: " + fromIndex);
if (toIndex < 0)
throw new ArgumentOutOfRangeException("toIndex < 0: " + toIndex);
if (fromIndex > toIndex)
throw new ArgumentOutOfRangeException("fromIndex: " + fromIndex +
" > toIndex: " + toIndex);
// Increase capacity if necessary
int endUnitIndex = UnitIndex(toIndex);
int unitsRequired = endUnitIndex + 1;
if (unitsInUse < unitsRequired)
{
EnsureCapacity(unitsRequired);
unitsInUse = unitsRequired;
}
int startUnitIndex = UnitIndex(fromIndex);
ulong bitMask = 0;
if (startUnitIndex == endUnitIndex)
{
// Case 1: One word
bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -
(1L << (fromIndex & BIT_INDEX_MASK));
units[startUnitIndex] ^= bitMask;
if (units[unitsInUse-1] == 0)
RecalculateUnitsInUse();
return this;
}
// Case 2: Multiple words
// Handle first word
bitMask = BitsLeftOf(fromIndex & BIT_INDEX_MASK);
units[startUnitIndex] ^= bitMask;
// Handle intermediate words, if any
if (endUnitIndex - startUnitIndex > 1)
for (int i=startUnitIndex+1; itrue. Returns
* this modified bitset.
*
* @param bitIndex a bit index.
* @throws ArgumentOutOfRangeException if the specified index is negative.
*/
public BitSet Set (int bitIndex)
{
if (bitIndex < 0)
throw new ArgumentOutOfRangeException("bitIndex < 0: " + bitIndex);
int index = UnitIndex(bitIndex);
int unitsRequired = index + 1;
if (unitsInUse < unitsRequired)
{
EnsureCapacity(unitsRequired);
units[index] |= Bit(bitIndex);
unitsInUse = unitsRequired;
}
else
units[index] |= Bit(bitIndex);
return this;
}
/**
* Sets the bit at the specified index to the specified value.
* Returns this modified bitset.
*
* @param bitIndex a bit index.
* @param value a boolean value to set.
* @throws ArgumentOutOfRangeException if the specified index is negative.
*/
public BitSet Set (int bitIndex, bool value)
{
if (value)
Set(bitIndex);
else
Clear(bitIndex);
return this;
}
/**
* Sets the bits from the specified fromIndex(inclusive) to the
* specified toIndex(exclusive) to true.
* Returns this modified bitset.
*
* @param fromIndex index of the first bit to be set.
* @param toIndex index after the last bit to be set.
* @throws ArgumentOutOfRangeException if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex.
*/
public BitSet Set (int fromIndex, int toIndex)
{
if (fromIndex < 0)
throw new ArgumentOutOfRangeException("fromIndex < 0: " + fromIndex);
if (toIndex < 0)
throw new ArgumentOutOfRangeException("toIndex < 0: " + toIndex);
if (fromIndex > toIndex)
throw new ArgumentOutOfRangeException("fromIndex: " + fromIndex +
" > toIndex: " + toIndex);
// Increase capacity if necessary
int endUnitIndex = UnitIndex(toIndex);
int unitsRequired = endUnitIndex + 1;
if (unitsInUse < unitsRequired)
{
EnsureCapacity(unitsRequired);
unitsInUse = unitsRequired;
}
int startUnitIndex = UnitIndex(fromIndex);
ulong bitMask = 0;
if (startUnitIndex == endUnitIndex)
{
// Case 1: One word
bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -
(1L << (fromIndex & BIT_INDEX_MASK));
units[startUnitIndex] |= bitMask;
return this;
}
// Case 2: Multiple words
// Handle first word
bitMask = BitsLeftOf(fromIndex & BIT_INDEX_MASK);
units[startUnitIndex] |= bitMask;
// Handle intermediate words, if any
if (endUnitIndex - startUnitIndex > 1)
for (int i=startUnitIndex+1; ifalse.
* Returns this modified bitset.
*
* @param bitIndex the index of the bit to be cleared.
* @throws ArgumentOutOfRangeException if the specified index is negative.
*/
public BitSet Clear (int bitIndex)
{
if (bitIndex < 0)
throw new ArgumentOutOfRangeException("bitIndex < 0: " + bitIndex);
int index = UnitIndex(bitIndex);
if (index >= unitsInUse)
return this;
units[index] &= ~Bit(bitIndex);
if (units[unitsInUse-1] == 0)
RecalculateUnitsInUse();
return this;
}
/**
* Sets the bits from the specified fromIndex(inclusive) to the
* specified toIndex(exclusive) to false.
* Returns this modified bitset.
*
* @param fromIndex index of the first bit to be cleared.
* @param toIndex index after the last bit to be cleared.
* @throws ArgumentOutOfRangeException if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex.
*/
public BitSet Clear (int fromIndex, int toIndex)
{
if (fromIndex < 0)
throw new ArgumentOutOfRangeException("fromIndex < 0: " + fromIndex);
if (toIndex < 0)
throw new ArgumentOutOfRangeException("toIndex < 0: " + toIndex);
if (fromIndex > toIndex)
throw new ArgumentOutOfRangeException("fromIndex: " + fromIndex +
" > toIndex: " + toIndex);
int startUnitIndex = UnitIndex(fromIndex);
if (startUnitIndex >= unitsInUse)
return this;
int endUnitIndex = UnitIndex(toIndex);
ulong bitMask = 0;
if (startUnitIndex == endUnitIndex)
{
// Case 1: One word
bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -
(1L << (fromIndex & BIT_INDEX_MASK));
units[startUnitIndex] &= ~bitMask;
if (units[unitsInUse-1] == 0)
RecalculateUnitsInUse();
return this;
}
// Case 2: Multiple words
// Handle first word
bitMask = BitsLeftOf(fromIndex & BIT_INDEX_MASK);
units[startUnitIndex] &= ~bitMask;
// Handle intermediate words, if any
if (endUnitIndex - startUnitIndex > 1)
for (int i=startUnitIndex+1; itrue if the bit with the index bitIndex
* is currently set in this BitSet; otherwise, the result
* is false.
* Returns this modified bitset.
*
* @param bitIndex the bit index.
* @return the value of the bit with the specified index.
* @throws ArgumentOutOfRangeException if the specified index is negative.
*/
public bool Get (int bitIndex)
{
if (bitIndex < 0)
throw new ArgumentOutOfRangeException("bitIndex < 0: " + bitIndex);
bool result = false;
int index = UnitIndex(bitIndex);
if (index < unitsInUse)
result = ((units[index] & Bit(bitIndex)) != 0);
return result;
}
/**
* Returns a new BitSet composed of bits from this BitSet
* from fromIndex(inclusive) to toIndex(exclusive).
*
* @param fromIndex index of the first bit to include.
* @param toIndex index after the last bit to include.
* @return a new BitSet from a range of this BitSet.
* @throws ArgumentOutOfRangeException if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex.
*/
public BitSet Get (int fromIndex, int toIndex)
{
if (fromIndex < 0)
throw new ArgumentOutOfRangeException("fromIndex < 0: " + fromIndex);
if (toIndex < 0)
throw new ArgumentOutOfRangeException("toIndex < 0: " + toIndex);
if (fromIndex > toIndex)
throw new ArgumentOutOfRangeException("fromIndex: " + fromIndex +
" > toIndex: " + toIndex);
// If no set bits in range return empty bitset
if (Width <= fromIndex || fromIndex == toIndex)
return new BitSet(0);
// An optimization
if (Width < toIndex)
toIndex = Width;
BitSet result = new BitSet(toIndex - fromIndex);
int startBitIndex = fromIndex & BIT_INDEX_MASK;
int endBitIndex = toIndex & BIT_INDEX_MASK;
int targetWords = (toIndex - fromIndex + 63)/64;
int sourceWords = UnitIndex(toIndex) - UnitIndex(fromIndex) + 1;
int inverseIndex = 64 - startBitIndex;
int targetIndex = 0;
int sourceIndex = UnitIndex(fromIndex);
// Process all words but the last word
while (targetIndex < targetWords - 1)
result.units[targetIndex++] =
(units[sourceIndex++] >> startBitIndex)
| ((inverseIndex==64) ? 0 : units[sourceIndex] << inverseIndex);
// Process the last word
result.units[targetIndex] = (sourceWords == targetWords ?
(units[sourceIndex]
& BitsRightOf(endBitIndex)) >> startBitIndex :
(units[sourceIndex++] >> startBitIndex)
| ((inverseIndex==64) ? 0 :
(GetUnit(sourceIndex)
& BitsRightOf(endBitIndex)) << inverseIndex));
// Set unitsInUse correctly
result.unitsInUse = targetWords;
result.RecalculateUnitsInUse();
return result;
}
/**
* Returns the unit of this bitset at index j as if this bitset had an
* infinite amount of storage.
*/
private long GetUnit(int j)
{
return (j < unitsInUse) ? units[j] : 0;
}
/**
* Returns the index of the first bit that is set to true
* that occurs on or after the specified starting index. If no such
* bit exists then -1 is returned.
*
* To iterate over the true bits in a BitSet,
* use the following loop:
*
* for (int i=bs.NextSetBit(0); i>=0; i=bs.NextSetBit(i+1))
* {
* // operate on index i here
* }
*
* @param fromIndex the index to start checking from (inclusive).
* @return the index of the next set bit.
* @throws ArgumentOutOfRangeException if the specified index is negative.
*/
public int NextSetBit (int fromIndex)
{
if (fromIndex < 0)
throw new ArgumentOutOfRangeException("fromIndex < 0: " + fromIndex);
int u = UnitIndex(fromIndex);
if (u >= unitsInUse)
return -1;
int testIndex = (fromIndex & BIT_INDEX_MASK);
long unit = units[u] >> testIndex;
if (unit == 0)
testIndex = 0;
while((unit==0) && (u < unitsInUse-1))
unit = units[++u];
if (unit == 0)
return -1;
testIndex += TrailingZeroCnt(unit);
return ((u * BITS_PER_UNIT) + testIndex);
}
private static int TrailingZeroCnt (long val)
{
// Loop unrolled for performance
int byteVal = (int)val & 0xff;
if (byteVal != 0)
return trailingZeroTable[byteVal];
byteVal = (int)(val >> 8) & 0xff;
if (byteVal != 0)
return trailingZeroTable[byteVal] + 8;
byteVal = (int)(val >> 16) & 0xff;
if (byteVal != 0)
return trailingZeroTable[byteVal] + 16;
byteVal = (int)(val >> 24) & 0xff;
if (byteVal != 0)
return trailingZeroTable[byteVal] + 24;
byteVal = (int)(val >> 32) & 0xff;
if (byteVal != 0)
return trailingZeroTable[byteVal] + 32;
byteVal = (int)(val >> 40) & 0xff;
if (byteVal != 0)
return trailingZeroTable[byteVal] + 40;
byteVal = (int)(val >> 48) & 0xff;
if (byteVal != 0)
return trailingZeroTable[byteVal] + 48;
byteVal = (int)(val >> 56) & 0xff;
return trailingZeroTable[byteVal] + 56;
}
/*
* trailingZeroTable[i] is the number of trailing zero bits in the binary
* representation of i.
*/
private static byte[] trailingZeroTable = new byte[]
{
// -25, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
// What the hell is this -25? Shouldn't that be 8? -hak
8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
/**
* Returns the index of the first bit that is set to false
* that occurs on or after the specified starting index.
*
* @param fromIndex the index to start checking from (inclusive).
* @return the index of the next clear bit.
* @throws ArgumentOutOfRangeException if the specified index is negative.
*/
public int NextClearBit (int fromIndex)
{
if (fromIndex < 0)
throw new ArgumentOutOfRangeException("fromIndex < 0: " + fromIndex);
int u = UnitIndex(fromIndex);
if (u >= unitsInUse)
return fromIndex;
int testIndex = (fromIndex & BIT_INDEX_MASK);
long unit = units[u] >> testIndex;
if (unit == (WORD_MASK >> testIndex))
testIndex = 0;
while ((unit == WORD_MASK) && (u < unitsInUse-1))
unit = units[++u];
if (unit == WORD_MASK)
return Width;
if (unit == 0)
return u * BITS_PER_UNIT + testIndex;
testIndex += TrailingZeroCnt(~unit);
return ((u * BITS_PER_UNIT) + testIndex);
}
/**
* Returns the "logical size" of this BitSet: the index of
* the highest set bit in the BitSet plus one. Returns zero
* if the BitSet contains no set bits.
*
* @return the logical size of this BitSet.
*/
private int LogicalWidth ()
{
if (unitsInUse == 0)
return 0;
long highestUnit = units[unitsInUse - 1];
int highPart = (int)(highestUnit >> 32);
return 64 * (unitsInUse - 1) +
(highPart == 0 ? BitLength((int)highestUnit)
: 32 + BitLength((int)highPart));
}
/**
* BitLength(val) is the number of bits in val.
*/
private static int BitLength (int w)
{
// Binary search - decision tree (5 tests, rarely 6)
return
(w < 1<<15 ?
(w < 1<<7 ?
(w < 1<<3 ?
(w < 1<<1 ? (w < 1<<0 ? (w<0 ? 32 : 0) : 1) : (w < 1<<2 ? 2 : 3)) :
(w < 1<<5 ? (w < 1<<4 ? 4 : 5) : (w < 1<<6 ? 6 : 7))) :
(w < 1<<11 ?
(w < 1<<9 ? (w < 1<<8 ? 8 : 9) : (w < 1<<10 ? 10 : 11)) :
(w < 1<<13 ? (w < 1<<12 ? 12 : 13) : (w < 1<<14 ? 14 : 15)))) :
(w < 1<<23 ?
(w < 1<<19 ?
(w < 1<<17 ? (w < 1<<16 ? 16 : 17) : (w < 1<<18 ? 18 : 19)) :
(w < 1<<21 ? (w < 1<<20 ? 20 : 21) : (w < 1<<22 ? 22 : 23))) :
(w < 1<<27 ?
(w < 1<<25 ? (w < 1<<24 ? 24 : 25) : (w < 1<<26 ? 26 : 27)) :
(w < 1<<29 ? (w < 1<<28 ? 28 : 29) : (w < 1<<30 ? 30 : 31)))));
}
/**
* This is true if this BitSet contains no bits that are set
* to true.
*
* @return boolean indicating whether this BitSet is empty.
*/
public bool IsEmpty
{
get { return (unitsInUse == 0); }
}
/**
* Returns true if the specified BitSet has any bits set to
* true that are also set to true in this
* BitSet.
*
* @param set BitSet to intersect with
* @return boolean indicating whether this BitSet intersects
* the specified BitSet.
*/
public bool Intersects (BitSet set)
{
for (int i = Math.Min(unitsInUse, set.unitsInUse)-1; i>=0; i--)
if ((units[i] & set.units[i]) != 0)
return true;
return false;
}
/**
* Returns the number of bits set to true in this
* BitSet.
*
* @return the number of bits set to true in this
* BitSet.
*/
public int Cardinality
{
get
{
int sum = 0;
for (int i=0; itrue if and only if it both initially
* had the value true and the corresponding bit in the
* bit set argument also had the value true.
* Returns this modified bitset.
*
* @param set a bit set.
*/
public BitSet And (BitSet set)
{
if (this == set)
return this;
// Perform logical AND on bits in common
int oldUnitsInUse = unitsInUse;
unitsInUse = Math.Min(unitsInUse, set.unitsInUse);
int i;
for (i=0; itrue if and only if it either already had the
* value true or the corresponding bit in the bit set
* argument has the value true.
* Returns this modified bitset.
*
* @param set a bit set.
*/
public BitSet Or (BitSet set)
{
if (this == set)
return this;
EnsureCapacity(set.unitsInUse);
// Perform logical OR on bits in common
int unitsInCommon = Math.Min(unitsInUse, set.unitsInUse);
int i;
for (i=0; itrue if and only if one of the following
* statements holds:
*
*
* Returns this modified bitset.
*
* @param set a bit set.
*/
public BitSet Xor (BitSet set)
{
int unitsInCommon;
if (unitsInUse >= set.unitsInUse)
{
unitsInCommon = set.unitsInUse;
}
else
{
unitsInCommon = unitsInUse;
int newUnitsInUse = set.unitsInUse;
EnsureCapacity(newUnitsInUse);
unitsInUse = newUnitsInUse;
}
// Perform logical XOR on bits in common
int i;
for (i=0; itrue, and the
* corresponding bit in the argument has the value false.
* false, and the
* corresponding bit in the argument has the value true.
* BitSet.
* Returns this modified bitset.
*
* @param set the BitSet with which to mask this
* BitSet.
*/
public BitSet AndNot (BitSet set)
{
int unitsInCommon = Math.Min(unitsInUse, set.unitsInUse);
// Perform logical (a & !b) on bits in common
for (int i=0; iBitSet were to be stored
* in an array of long integers called, say,
* units, in such a manner that bit k is
* set in the BitSet (for nonnegative values of
* k) if and only if the expression
*
* ((k>>6) < units.Length)
* && ((units[k>>6] & (1L << (bit & 0x3F))) != 0)
*
* is true. Then the following definition of the GetHashCode()
* method would be a correct implementation of the actual algorithm:
*
* public override int GetHashCode ()
* {
* long h = 1234;
* for (int i = units.Length; --i >= 0; )
* {
* h ^= units[i] * (i + 1);
* }
* return (int)((h >> 32) ^ h);
* }
*
* Note that the hash code values change if the set of bits is altered.
* hashCode method of Object.
*
* @return a hash code value for this bit set.
*/
public override int GetHashCode ()
{
long h = 1234;
for (int i = units.Length; --i >= 0; )
h ^= units[i] * (i + 1);
return (int)((h >> 32) ^ h);
}
/**
* This is the number of bits of space actually in use by this
* BitSet to represent bit values. The maximum
* element in the set is the size - 1st element.
*
* @return the number of bits currently in this bit set.
*/
public int Size
{
get { return units.Length << ADDRESS_BITS_PER_UNIT; }
}
/**
* Compares this object against the specified object. The result
* is true if and only if the argument is not
* null and is a Bitset object that has
* exactly the same set of bits set to true as this
* bit set. That is, for every nonnegative int index
* k,
*
* ((BitSet)obj).Get(k) == this.Get(k)
*
* must be true. The current sizes of the two bit sets are not
* compared. equals method of
* Object.
*
* @param obj the object to compare with.
* @return true if the objects are the same;
* false otherwise.
*/
public override bool Equals (Object obj)
{
if (this == obj)
return true;
if (!(obj is BitSet))
return false;
BitSet set = (BitSet) obj;
int minUnitsInUse = Math.Min(unitsInUse, set.unitsInUse);
// Check units in use by both BitSets
for (int i = 0; i < minUnitsInUse; i++)
if (units[i] != set.units[i])
return false;
// Check any units in use by only one BitSet (must be 0 in other)
if (unitsInUse > minUnitsInUse)
{
for (int i = minUnitsInUse; iBitSet
* that is equal to it.
* The clone of the bit set is another bit set that has exactly the
* same bits set to true as this bit set and the same
* current size.
*
* @return a clone of this bit set.
*/
public Object Clone ()
{
BitSet newset = (BitSet)MemberwiseClone();
newset.units = new long[units.Length];
Array.Copy(units, 0, newset.units, 0, unitsInUse);
return newset;
}
/**
* This override of readObject makes sure unitsInUse is set properly
* when deserializing a bitset
*
*/
// private void readObject(java.io.ObjectInputStream in)
// // throws IOException, ClassNotFoundException
// {
// in.defaultReadObject();
// // Assume maximum length then find real length
// // because RecalculateUnitsInUse assumes maintenance
// // or reduction in logical size
// unitsInUse = units.Length;
// RecalculateUnitsInUse();
// }
/**
* Returns a string representation of this bit set. For every index
* for which this BitSet contains a bit in the set
* state, the decimal representation of that index is included in
* the result. Such indices are listed in order from lowest to
* highest, separated by ", " (a comma and a space) and
* surrounded by braces, resulting in the usual mathematical
* notation for a set of integers.toString method of Object.
*
* BitSet drPepper = new BitSet();
* Now drPepper.toString() returns "{}".
* drPepper.Set(2);
* Now drPepper.toString() returns "{2}".
* drPepper.Set(4);
* drPepper.Set(10);
* Now drPepper.toString() returns "{2, 4, 10}".
*
* @return a string representation of this bit set.
*/
public override String ToString ()
{
int numBits = unitsInUse << ADDRESS_BITS_PER_UNIT;
StringBuilder buffer = new StringBuilder(8*numBits + 2);
String separator = "";
buffer.Append('{');
for (int i = 0; i < numBits; i++)
{
if (Get(i))
{
buffer.Append(separator);
separator = ", ";
buffer.Append(i);
}
}
return buffer.Append('}').ToString();
}
/* *******************************************************************
* The following do not belong to the java interface and are only
* specific to this C# implementation.
* *******************************************************************
*/
/**
* Creates a new bitset equal to the specified one.
* This constructor is specific to the C# version.
*/
public BitSet (BitSet other)
{
units = new long[other.units.Length];
Array.Copy(other.units, 0, units, 0, other.unitsInUse);
unitsInUse = other.unitsInUse;
}
/**
* Returns the number of "on" bits in this bit set.
*/
public int Count
{
get
{
return Cardinality;
}
}
/**
* Returns the "logical size" of this BitSet: the index of
* the highest set bit in the BitSet plus one. Returns zero
* if the BitSet contains no set bits.
*/
public int Width
{
get
{
return LogicalWidth();
}
}
/**
* Using this BitSet indexed by an integer, one can test the bit at the
* specified index, as this will return false or true depending on whether
* the corresponding bit is 0 or 1. Accordingly, assigning false or true to
* this BitSet indexed by an integer will set the corresponding bit to 0 or 1.
*/
public bool this [int index]
{
get
{
return Get(index);
}
set
{
if (value)
Set(index);
else
Clear(index);
}
}
/**
* Returns true iff all the bits that are "on" in this bitset are
* also "on" in the specified bitset. As sets of indices, this
* corresponds to this being a subset of the given set. This method
* is specific to the C# version.
*/
public bool IsSubsetOf (BitSet set)
{
if (IsEmpty)
return true;
if (set.IsEmpty)
return false;
for (int i = 0; i < Math.Min(unitsInUse, set.unitsInUse); i++)
if (units[i] != (units[i] & set.units[i]))
return false;
return true;
}
/**
* Returns true iff all the bits that are "on" in this bitset are
* also "on" in the specified bitset, with some "on" bits in the
* second set being "off" in this bitset. As sets of indices, this
* corresponds to this being a strict subset of the given set. This
* method is specific to the C# version.
*/
public bool IsStrictSubsetOf (BitSet set)
{
return IsSubsetOf(set) && Cardinality != set.Cardinality;
}
/**
* Returns true iff all the bits that are "on" in bitset one are
* also "on" in bitset two. As sets of indices, this corresponds
* to bitset one being a subset of bitset two. This method is
* specific to the C# version.
*/
public static bool operator <= (BitSet one, BitSet two)
{
return one.IsSubsetOf(two);
}
/**
* Returns true iff all the bits that are "on" in bitset two are
* also "on" in bitset one. As sets of indices, this corresponds
* to bitset one being a superset of bitset two. This method is
* specific to the C# version.
*/
public static bool operator >= (BitSet one, BitSet two)
{
return two.IsSubsetOf(one);
}
/**
* Returns true iff all the bits that are "on" in bitset one are
* also "on" in bitset two, with some "on" bits in bitset two being
* "off" in bitset one. As sets of indices, this corresponds to bitset
* one being a strict subset of bitset two. This method is specific to
* the C# version.
*/
public static bool operator < (BitSet one, BitSet two)
{
return one.IsStrictSubsetOf(two);
}
/**
* Returns true iff all the bits that are "on" in bitset two are
* also "on" in bitset one, with some "on" bits in bitset one being
* "off" in bitset two. As sets of indices, this corresponds to bitset
* one being a strict superset of bitset two. This method is specific
* to the C# version.
*/
public static bool operator > (BitSet one, BitSet two)
{
return two.IsStrictSubsetOf(one);
}
/**
* Returns a new bitset which is the bitwise logical or of the
* two specified ones. This method is specific to the C# version.
*/
public static BitSet Or (BitSet one, BitSet two)
{
return new BitSet(one).Or(two);
}
/**
* Returns a new bitset which is the bitwise logical or of the
* two specified ones. This method is specific to the C# version.
*/
public static BitSet operator | (BitSet one, BitSet two)
{
return new BitSet(one).Or(two);
}
/**
* Returns a new bitset which is the bitwise logical and of the
* two specified ones. This method is specific to the C# version.
*/
public static BitSet And (BitSet one, BitSet two)
{
return new BitSet(one).And(two);
}
/**
* Returns a new bitset which is the bitwise logical and of the
* two specified ones. This method is specific to the C# version.
*/
public static BitSet operator & (BitSet one, BitSet two)
{
return new BitSet(one).And(two);
}
/**
* Returns a new bitset which is the bitwise logical xor of the
* two specified ones. This method is specific to the C# version.
*/
public static BitSet Xor (BitSet one, BitSet two)
{
return new BitSet(one).Xor(two);
}
/**
* Returns a new bitset which is the bitwise logical xor of the
* two specified ones. This method is specific to the C# version.
*/
public static BitSet operator ^ (BitSet one, BitSet two)
{
return new BitSet(one).Xor(two);
}
/**
* Returns a new bitset which is the bitwise logical AndNot of the
* two specified ones. This method is specific to the C# version.
*/
public static BitSet AndNot (BitSet one, BitSet two)
{
return new BitSet(one).AndNot(two);
}
/**
* Returns a new bitset which is the bitwise logical AndNot of the
* two specified ones. This method is specific to the C# version.
*/
public static BitSet operator - (BitSet one, BitSet two)
{
return new BitSet(one).AndNot(two);
}
/**
* Returns an enumerator for this Bitset listing the indices for
* which this BitSet contains a bit in the "on" set
* state. Such indices are listed in order from lowest to highest.
*/
public IEnumerator GetEnumerator ()
{
for (int i = 0; i < unitsInUse << ADDRESS_BITS_PER_UNIT; i++)
if (Get(i))
yield return i;
}
}
}