BitSet.html

BitSet.cs

using System;
using System.IO;
using System.Text;
using System.Collections;

namespace Ilog.Language.Util
{

This is a C# translation of the java.util.BitSet class adapted from the SUN java sources of the jdk1.5.0. All original comments by original authors have been kept. Features not ported to the C# version have been commented out. This port was done by Hassan Aït-Kaci.

The logic, data representation, and interface of the original Java implementation was essentially adhered to albeit with the following modifications:

All method names have been capitalized to obey C#'s convention.
The length() method has been replaced with a read-only Width property (the term "width" being a more appropriate description).
The argumentless methods isEmpty(), size(), and cardinality() have been replaced with the read-only properties IsEmpty, Size, and Cardinality.
A read-only 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.
A boolean indexer has been added to ease the getting and the setting of bits with bracket indexing notation taking a Boolean value.
A GetEnumerator method implementing the IEnumerable interface has been added to allow foreach iteration over a BitSet's "on" bits' indices.
All the logical operations in java.util.BitSet that returned void now return BitSet. This allows composing them while being compatible with being used as statements.
Static versions which do not alter their operands for all logical operators were added.
Overloaded logical operators have been added to ease the writing of algebraic expressions involving BitSets. These are aliases of the added named static operators. They are:
- | (same as Or);
- & (same as And);
- - (same as AndNot);
- ^ (same as Xor).

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.

Since: JDK1.0

Author: Arthur van Hoff, Michael McCloskey

Version: 1.60, 02/19/04


  [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., 2⁶-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 2^{ADDRESS_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 2^{BITS_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 2^{BITS_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 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.

Throws: ArgumentOutOfRangeException if the specified initial size is negative.

Parameters:

nbits - the initial size of the bit set.


      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.

Parameters:

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.

Throws: ArgumentOutOfRangeException if the specified index is negative.

Parameters:

bitIndex - the index of the bit to flip.


      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.

Throws: ArgumentOutOfRangeException if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex.

Parameters:

fromIndex - index of the first bit to flip.

toIndex - index after the last bit to flip.


      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; i<endUnitIndex; i++)
	      units[i] ^= WORD_MASK;
	  
	  // Handle last word
	  bitMask = BitsRightOf(toIndex & BIT_INDEX_MASK);
	  units[endUnitIndex] ^= bitMask;

	  // Check to see if we reduced size
	  if (units[unitsInUse-1] == 0)
            RecalculateUnitsInUse();

	  return this;
	}

Returns a long that has all bits that are less significant than the specified index set to 1. All other bits are 0.


      private static ulong BitsRightOf (int x)
	{
	  return (x==0 ? 0 : WORD_MASK >> (64-x));
	}

Returns a long that has all the bits that are more significant than or equal to the specified index set to 1. All other bits are 0.


      private static ulong BitsLeftOf (int x)
	{
	  return WORD_MASK << x;
	}

Sets the bit at the specified index to true. Returns this modified bitset.

Throws: ArgumentOutOfRangeException if the specified index is negative.

Parameters:

bitIndex - a bit index.


      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.

Throws: ArgumentOutOfRangeException if the specified index is negative.

Parameters:

bitIndex - a bit index.

value - a boolean value to set.


      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.

Throws: ArgumentOutOfRangeException if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex.

Parameters:

fromIndex - index of the first bit to be set.

toIndex - index after the last bit to be set.


      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; i<endUnitIndex; i++)
	      units[i] |= WORD_MASK;
	  
	  // Handle last word
	  bitMask = BitsRightOf(toIndex & BIT_INDEX_MASK);
	  units[endUnitIndex] |= bitMask;

	  return this;
	}

Sets the bits from the specified fromIndex(inclusive) to the specified toIndex(exclusive) to the specified value. Returns this modified bitset.

Throws: ArgumentOutOfRangeException if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex.

Parameters:

fromIndex - index of the first bit to be set.

toIndex - index after the last bit to be set

value - value to set the selected bits to


      public BitSet Set (int fromIndex, int toIndex, bool value)
	{
	  if (value)
            Set(fromIndex, toIndex);
	  else
            Clear(fromIndex, toIndex);

	  return this;
	}

Sets the bit specified by the index to false. Returns this modified bitset.

Throws: ArgumentOutOfRangeException if the specified index is negative.

Parameters:

bitIndex - the index of the bit to be cleared.


      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.

Throws: ArgumentOutOfRangeException if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex.

Parameters:

fromIndex - index of the first bit to be cleared.

toIndex - index after the last bit to be cleared.


      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; i<endUnitIndex; i++)
	      if (i < unitsInUse)
		units[i] = 0;
	  
	  // Handle last word
	  if (endUnitIndex < unitsInUse)
	    {
	      bitMask = BitsRightOf(toIndex & BIT_INDEX_MASK);
	      units[endUnitIndex] &= ~bitMask;
	    }

	  if (units[unitsInUse-1] == 0)
            RecalculateUnitsInUse();

	  return this;
	}

Sets all of the bits in this BitSet to false.


      public BitSet Clear ()
	{
	  while (unitsInUse > 0)
            units[--unitsInUse] = 0;

	  return this;
	}

Returns the value of the bit with the specified index. The value is true if the bit with the index bitIndex is currently set in this BitSet; otherwise, the result is false. Returns this modified bitset.

Throws: ArgumentOutOfRangeException if the specified index is negative.

Returns: the value of the bit with the specified index.

Parameters:

bitIndex - the bit index.


      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).

Throws: ArgumentOutOfRangeException if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex.

Returns: a new BitSet from a range of this BitSet.

Parameters:

fromIndex - index of the first bit to include.

toIndex - index after the last bit to include.


      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
          }

Throws: ArgumentOutOfRangeException if the specified index is negative.

Returns: the index of the next set bit.

Parameters:

fromIndex - the index to start checking from (inclusive).


      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.

Throws: ArgumentOutOfRangeException if the specified index is negative.

Returns: the index of the next clear bit.

Parameters:

fromIndex - the index to start checking from (inclusive).


      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.

Returns: 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.

Returns: 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. the specified BitSet.

Returns: boolean indicating whether this BitSet intersects

Parameters:

set - BitSet to intersect with


      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. BitSet.

Returns: the number of bits set to true in this


      public int Cardinality
	{
	  get
	    {
	      int sum = 0;
	      for (int i=0; i<unitsInUse; i++)
		sum += BitCount(units[i]);
	      return sum;
	    }
	}

Returns the number of bits set in val. For a derivation of this algorithm, see "Algorithms and data structures with applications to graphics and geometry", by Jurg Nievergelt and Klaus Hinrichs, Prentice Hall, 1993.


      private int BitCount (long val)
	{
	  val -= (val & unchecked((long)0xaaaaaaaaaaaaaaaaL)) >> 1;
	  val  = (val & unchecked((long)0x3333333333333333L))
	       + ((val >> 2) & unchecked((long)0x3333333333333333L));
	  val  = (val + (val >> 4)) & unchecked((long)0x0f0f0f0f0f0f0f0fL);
	  val += val >> 8;
	  val += val >> 16;
	  return ((int)(val) + (int)(val >> 32)) & 0xff;
	}

Performs a logical AND of this target bit set with the argument bit set. This bit set is modified so that each bit in it has the value true 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.

Parameters:

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; i<unitsInUse; i++)
	    units[i] &= set.units[i];

	  // Clear out units no longer used
	  for ( ; i < oldUnitsInUse; i++)
	    units[i] = 0;

	  // Recalculate units in use if necessary
	  if (unitsInUse > 0 && units[unitsInUse - 1] == 0)
            RecalculateUnitsInUse();

	  return this;
	}

Performs a logical OR of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value true 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.

Parameters:

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; i<unitsInCommon; i++)
	    units[i] |= set.units[i];

	  // Copy any remaining bits
	  for (; i<set.unitsInUse; i++)
	    units[i] = set.units[i];

	  if (unitsInUse < set.unitsInUse)
            unitsInUse = set.unitsInUse;

	  return this;
	}

Performs a logical XOR of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value true if and only if one of the following statements holds:

The bit initially has the value true, and the corresponding bit in the argument has the value false.
The bit initially has the value false, and the corresponding bit in the argument has the value true.

Returns this modified bitset.

Parameters:

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; i<unitsInCommon; i++)
	    units[i] ^= set.units[i];

	  // Copy any remaining bits
	  for ( ; i<set.unitsInUse; i++)
            units[i] = set.units[i];

	  RecalculateUnitsInUse();

	  return this;
	}

Clears all of the bits in this BitSet whose corresponding bit is set in the specified BitSet. Returns this modified bitset. BitSet.

Parameters:

set - the BitSet with which to mask this


      public BitSet AndNot (BitSet set)
	{
	  int unitsInCommon = Math.Min(unitsInUse, set.unitsInUse);

	  // Perform logical (a & !b) on bits in common
	  for (int i=0; i<unitsInCommon; i++)
	    {
	      units[i] &= ~set.units[i];
	    }

	  RecalculateUnitsInUse();

	  return this;
	}

Returns a hash code value for this bit set. The has code depends only on which bits have been set within this BitSet. The algorithm used to compute it may be described as follows.

Suppose the bits in the BitSet 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.

Overrides the hashCode method of Object.

Returns: 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.

Returns: 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.

Overrides the equals method of Object. false otherwise.

Returns: true if the objects are the same;

Parameters:

obj - the object to compare with.


      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; i<unitsInUse; i++)
		if (units[i] != 0)
		  return false;
	    }
	  else
	    {
	      for (int i = minUnitsInUse; i<set.unitsInUse; i++)
		if (set.units[i] != 0)
		  return false;
	    }

	  return true;
	}

Cloning this BitSet produces a new BitSet 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.

Returns: 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.

Overrides the toString method of Object.

Example:

        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}".

Returns: 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;
	}
    }
}

This file was generated on Fri Jun 24 13:12:15 CEST 2005 from file BitSet.cs
by the ilog.language.tools.Hilite Java tool written by Hassan Aït-Kaci