4.9. BitVectorx: Extension through Composition

The BitArray class is provided within the System.Collections name-space. It manages an array of Boolean objects as if it were a bit vector. A true value indicates that the bit is turned on; false, that it is off. Count returns the number of elements in the array. It is a property of the ICollection interface, from which BitArray is derived.

We can turn a bit on or off either by subscripting into the array:

bat1[ 2 ] = bat2[ 4 ] = true;

or by explicitly setting the element:

lbat.Set(ix, bat[ ix ] );

A function called SetAll() sets all the bits in the array to either true or false. The value of an element can be read either through subscripting or by the Get() method:

// both return the value of the first element
bool b1 = bat1[ 0 ];
bool b2 = bat1.Get( 0 );

To reverse the values of the BitArray object, we use the Not() method:

bat1.Not(); // bits are now reversed

Six constructors support the creation of a BitArray object. The following code segment illustrates their use.

const int  elemSize  = 6;
const bool elemValue = true;

// create a BitArray of size elemSize;
// each element is initialized to false
BitArray bits0 = new BitArray( elemSize );

// create a BitArray of size elemSize;
// each element is initialized to elemValue
BitArray bits1 = new BitArray( elemSize, elemValue );

// create a BitArray copied from another BitArray
BitArray bits2 = new BitArray( bits1 );

// create a BitArray with the number and value
// of elements from a bool array
bool [] bvals  = { false, true, false, true, false, true };
BitArray bits3 = new BitArray( bvals );

// create a BitArray initialized to an array of bytes
// in which each byte represents 8 consecutive bits
byte [] byteValues = { 255, 0 };

// evaluates to 1111111100000000
BitArray bits5 = new BitArray( byteValues );

// create a BitArray initialized to an array of ints
// in which each int represents 32 consecutive bits
int [] intValues = { -7 };

// evaluates to 10011111111111111111111111111111
BitArray bits6 = new BitArray( intValues );

In addition, we can perform a bitwise AND operation between two BitArray objects using the And() method:

BitArray andResult = bat1.And( bat2 );

andResult holds true for each element that is set for both bat1 and bat2; each other element is set to false.

There is also support for bitwise OR using the Or() method (an element is evaluated as true if it is set in either bat1 or bat2), and for bitwise XOR using the Xor() method. (The bitwise exclusive OR operation returns true if exactly one operand is set, and returns false if both operands have the same Boolean value.)

One small disappointment in the BitArray class is the absence of a provision for displaying the collection of bits. The inherited ToString() method prints out only the class type:

System.Collections.BitArray

rather than displaying the elements as a string, such as

00000101

In the documentation, an example of displaying a BitArray object has the user iterating across the elements, printing out the literal true or false values:

False False False False False True False True

This approach really doesn't scale to BitArray objects with many elements.

Another minor complaint is that there is no support for converting the container of bits into a numeric value. For example, given a BitArray object with an eight-element configuration of 00000101, it would be useful to retrieve an unsigned numeric representation—in this case, a return value of 5.

While at DreamWorks Animation, I was technical lead on a pencil test animation system released to the studio as ToonShooter. Animators use the system to transfer their drawings to the computer through a GUI-driven digital video camera. The sequences of drawings animating a scene are entered as levels. Each level represents an element in the scene. Each character, for example, is drawn as a separate level. There may be a background level, and levels for foreground images, shadows, vehicles, cute animals, and so on.

One use of the tool is to allow the animator to check the smoothness of the animation. A second use is to check the correctness of the lip movements of the characters with the soundtrack. A third use is to play back scenes with or without audio for director approval. The user can turn levels on or off prior to and during playback.

Playback has to occur at a minimum of 24 frames per second if the animation is to appear smooth. Before an image is displayed, it may require compositing. That is, if more than one level is active, the active levels, each of which represents an image, must be combined to form one composite image. Levels are combined pixel by pixel across the set of active levels. Compositing is done on the fly as it delivers frames to the playback engine. If compositing takes too long to deliver a frame, the tool can no longer play at speed without either dropping frames or breaking up the audio. Needless to say, both conditions are extremely annoying to the user.

One way to speed up compositing is to cache the composited images. Before we invoke the compositor, we check that the resulting image is not already available in the cache. Failing an exact match, we look for a best match—perhaps two, three, or four required levels have already been composited, so we composite only the missing level(s). To look up and retrieve images quickly, we need to be able to uniquely tag the different composited images efficiently. A unique signature for each image consists of its frame number and the set of its active levels.

An array of BitArray objects captures this information perfectly. Each element of the array represents the frame. The BitArray object represents the levels turned on for that frame. So for a six-level scene with a bit configuration of 00000101, levels 6 and 8 are turned on, and the unique tag retrieval code is 5.

Let's implement a BitVector class that provides the additional functionality absent from BitArray. My first idea is to derive the BitVector class from BitArray. In this way BitVector inherits all of the BitArray infrastructure, and we simply need to program what is different. Unfortunately, the BitArray class is sealed, so we cannot inherit:

public sealed class BitArray :
       ICollection, IEnumerable, ICloneable

An alternative design choice to inheritance is composition, in which we wrap our BitVector class around an internal BitArray member:

public sealed class BitVector :
       ICollection, IEnumerable, ICloneable
{
    private BitArray m_array;
    // ...
}

Although we do not inherit the BitArray members, we duplicate their functionality through small dispatch methods. For example,

// ICollection
public int Count { get { return m_array.Count; }}
public bool IsReadOnly { get { return m_array.IsReadOnly; }}
public object SyncRoot { get { return m_array.SyncRoot;   }}
public bool IsSynchronized
     { get{ return m_array.IsSynchronized; }}

public void CopyTo( Array array, int index )
     { m_array.CopyTo( array, index ); }

// IEnumerable
public IEnumerator GetEnumerator()
{
   return m_array.GetEnumerator();
}
// ICloneable
public object Clone()
{
      BitVector bv = new BitVector( m_array.Count );
      bv.m_array = (BitArray)m_array.Clone();
      return bv;
}

The next example shows the ToString() implementation. It iterates over the BitArray member, building up the string representation by appending either '1' or '0', depending on whether the bit is turned on. Because this algorithm modifies the string representation with each element, building up the representation by using a string object is not efficient.

The string class is immutable. If we append a character to a string object after examining a BitArray of 132 elements, we will have created 133 different string objects. One string object is actually sufficient. This is why we use a StringBuilder object instead.

The ToString() method is identified with the override keyword because it replaces the inherited virtual method defined within the object class:

override public string ToString()
{
    StringBuilder sb = new StringBuilder( m_array.Count );
    for ( int ix = m_array.Count-1; ix >= 0; --ix )
          sb.Append( m_array[ ix ] ? '1' : '0' );

    return sb.ToString();
}

The StringBuilder class is within the System.Text namespace. Its only purpose is to allow string modifications, such as removing, replacing, or inserting a character, without creating a new string with each modification. For example, to replace an ies ending of a word with y, using one of the overloaded StringBuilder Replace() methods, we write

if ( word.EndsWith( "ies" ))
     theWord.Replace( "ies", "y", theWord.Length-3, 3 );

We retrieve the string representation within the StringBuilder object through its ToString() method once our modifications are complete.

Here is an implementation of ToUlong() that turns our underlying bit vector into an unsigned long numeric value:

public ulong ToUlong()
{
      ulong bv = 0ul;
      for ( int ix = 0; ix < m_array.Count; ++ix )
      {
           if ( m_array[ix] )
           {
                 ulong bv2 = 1;
                 bv2 <<= ix;
                 bv += bv2;
           }

           Console.WriteLine( "{0} :: {1}", ix, bv );
      }

      return bv;
}

<<= is the bitwise compound left-shift assignment operator. When we assign bv2 a value of 1, internally this value is represented as the first bit in the underlying representation being turned on. A left shift moves the bits ix positions. For example, when ix is set to 1, each bit is shifted by one position. Shifting the 1-bit to the second position equals the value 2, shifting the 1-bit to the third position equals 4, and so on.

For example, the following is the ToString() and ToUlong() output of a small sequence of BitArray 24-element configurations:

000000000000000000000010 :: 2
000000000000000000001010 :: 10
000000000000000000101010 :: 42
000000000000000010101010 :: 170
000000000000001010101010 :: 682

To allow a BitVector to be used in any situation in which a BitArray can be used, we provide an implicit conversion from BitVector to BitArray:

public static implicit operator BitArray( BitVector bv )
       { return bv.m_array; }

By returning the private array member by reference, we are allowing multiple handles to this internal object. This means that it can be changed from outside the class. An alternative implementation returns a copy of the member by invoking the associated Clone() function:

return (BitArray)m_array.Clone();