mcs/class/corlib/System.Collections/BitArray.cs

   1 using System;
   2
   3 namespace System.Collections
   4 {
   5   // do we really need to specify IEnumerable since ICollection extends it?
   6   public class BitArray : ICollection, IEnumerable, ICloneable
   7   {
   8     private Int32[] m_array;
   9     private int m_length;
  10     private int m_modCount = 0;
  11
  12     private int bitsToInts(int bits)
  13     {
  14       int retval = bits/32;
  15       if (bits % 32 != 0)
  16         retval++;
  17
  18       return retval;
  19     }
  20
  21     private int bitsToBytes(int bits)
  22     {
  23       int retval = bits/8;
  24       if (bits % 8 != 0)
  25         retval++;
  26
  27       return retval;
  28     }
  29
  30
  31     private void setBit(int bitIndex, bool value)
  32     {
  33       int index = bitIndex/32;
  34       int shift = bitIndex%32;
  35
  36       Int32 theBit = 1 << shift;
  37
  38       if(value)
  39         m_array[index] |= theBit;
  40       else
  41         m_array[index] &= ~theBit;
  42
  43       m_modCount++;
  44     }
  45
  46     private bool getBit(int bitIndex)
  47     {
  48       int index = bitIndex/32;
  49       int shift = bitIndex%32;
  50
  51       Int32 theBit = m_array[index] & (1 << shift);
  52
  53       return (theBit == 0) ? false : true;
  54     }
  55
  56     private byte getByte(int byteIndex)
  57     {
  58       int index = byteIndex/4;
  59       int shift = (byteIndex%4)*8;
  60
  61       Int32 theByte = m_array[index] & (0xff << shift);
  62
  63       return (byte)((theByte >> shift)&0xff);
  64     }
  65
  66     private void setByte(int byteIndex, byte value)
  67     {
  68       int index = byteIndex/4;
  69       int shift = (byteIndex%4)*8;
  70
  71       Int32 orig = m_array[index];
  72
  73       // clear the byte
  74       orig &= ~(0xff << shift);
  75       // or in the new byte
  76       orig |= value << shift;
  77
  78       m_array[index] = orig;
  79
  80       m_modCount++;
  81     }
  82
  83     /* --- Constructors --- */
  84     public BitArray(BitArray orig)
  85     {
  86       m_length = orig.m_length;
  87
  88       int numInts = bitsToInts(m_length);
  89       m_array = new Int32[numInts];
  90       Array.Copy(orig.m_array, m_array, numInts);
  91     }
  92
  93     public BitArray(bool[] bits)
  94     {
  95       m_length = bits.Length;
  96
  97       int numInts = bitsToInts(m_length);
  98       m_array = new Int32[numInts];
  99       for (int i=0; i < bits.Length; i++)
 100         setBit(i, bits[i]);
 101     }
 102
 103     public BitArray(byte[] bytes)
 104     {
 105       m_length = bytes.Length * 8;
 106
 107       m_array = new Int32[bytes.Length/4];
 108       for (int i=0; i < bytes.Length; i++)
 109         setByte(i, bytes[i]);
 110     }
 111
 112     public BitArray(int capacity)
 113     {
 114       m_length = capacity;
 115       m_array = new Int32[bitsToInts(m_length)];
 116     }
 117
 118     public BitArray(int[] words)
 119     {
 120       int arrlen = words.Length;
 121       m_length = arrlen*32;
 122       m_array = new Int32[arrlen];
 123       Array.Copy(words, m_array, arrlen);
 124     }
 125
 126     public BitArray(int capacity, bool value) : this(capacity)
 127     {
 128       if (value)
 129       {
 130         // FIXME:  Maybe you can create an array pre filled?
 131         for (int i = 0; i < m_array.Length; i++)
 132           m_array[i] = ~0;
 133       }
 134     }
 135
 136     private BitArray(Int32 [] array, int length)
 137     {
 138       m_array = array;
 139       m_length = length;
 140     }
 141
 142
 143     /* --- Public properties --- */
 144     public virtual int Count
 145     {
 146       get
 147       {
 148         return m_length;
 149       }
 150     }
 151
 152     public virtual bool IsReadOnly
 153     {
 154       get
 155       {
 156         return false;
 157       }
 158     }
 159
 160     public virtual bool IsSynchronized
 161     {
 162       get
 163       {
 164         return false;
 165       }
 166     }
 167
 168     public virtual bool this[int index]
 169     {
 170       get
 171       {
 172         return Get(index);
 173       }
 174       set
 175       {
 176         Set(index, value);
 177       }
 178
 179     }
 180
 181     public virtual int Length
 182     {
 183       get
 184       {
 185         return m_length;
 186       }
 187       set
 188       {
 189         if (value < 0)
 190           throw new ArgumentOutOfRangeException();
 191
 192         int newLen = value;
 193         if (m_length != newLen)
 194         {
 195           int numints = bitsToInts(newLen);
 196           Int32 [] newArr = new Int32[numints];
 197           Array.Copy(m_array, newArr, numints);
 198
 199           // clear out the junk bits at the end:
 200           int numjunkbits = 32 - (newLen%32);
 201           UInt32 mask = (~0U >> numjunkbits);
 202           newArr[numints - 1] &= (int)mask;
 203
 204           // set the internal state
 205           m_array = newArr;
 206           m_length = newLen;
 207           m_modCount++;
 208         }
 209       }
 210     }
 211
 212     public virtual object SyncRoot
 213     {
 214       get
 215       {
 216         return this;
 217       }
 218     }
 219
 220     /* --- Public methods --- */
 221     public BitArray And(BitArray operand)
 222     {
 223       if (operand == null)
 224         throw new ArgumentNullException();
 225       if (operand.m_length != m_length)
 226         throw new ArgumentException();
 227
 228       Int32 [] newarr = new Int32[m_array.Length];
 229       for (int i=0; i < m_array.Length; i++)
 230         newarr[i] = m_array[i] & operand.m_array[i];
 231
 232       return new BitArray(newarr, m_length);
 233     }
 234
 235     public object Clone()
 236     {
 237       // FIXME: according to the doc, this should be a shallow copy.
 238       // But the MS implementation seems to do a deep copy.
 239       return new BitArray((Int32 [])m_array.Clone(), m_length);
 240     }
 241
 242     public void CopyTo(Array array, int index)
 243     {
 244       if (array == null)
 245         throw new ArgumentNullException();
 246       if (index < 0)
 247         throw new ArgumentOutOfRangeException();
 248
 249       // FIXME: Throw ArgumentException if array is multidimensional
 250       if (index >= array.Length)
 251         throw new ArgumentException();
 252
 253       // in each case, check to make sure enough space in array
 254
 255       if (array is bool[])
 256       {
 257         if (index + m_length >= array.Length)
 258           throw new ArgumentException();
 259
 260         bool [] barray = (bool []) array;
 261
 262         // Copy the bits into the array
 263         for (int i = 0; i < m_length; i++)
 264           barray[index + i] = getBit(i);
 265       }
 266       else if (array is byte[])
 267       {
 268         int numbytes = bitsToBytes(m_length);
 269         if (index + numbytes >= array.Length)
 270           throw new ArgumentException();
 271
 272         byte [] barray = (byte []) array;
 273         // Copy the bytes into the array
 274         for (int i = 0; i < numbytes; i++)
 275           barray[index + i] = getByte(i);
 276       }
 277       else if (array is int[])
 278       {
 279         int numints = bitsToInts(m_length);
 280         if (index + numints >= array.Length)
 281           throw new ArgumentException();
 282
 283         Array.Copy(m_array, array, numints);
 284       }
 285       else
 286       {
 287         throw new InvalidCastException();
 288       }
 289     }
 290
 291
 292     /*
 293      * All this code for nothing... Apparently, The MS BitArray doesn't
 294      * override Equals!
 295      *public override bool Equals(object obj)
 296     {
 297       // If it's not a BitArray, then it can't be equal to us.
 298       if (!(obj is BitArray))
 299         return false;
 300
 301       // If the references are equal, then clearly the instances are equal
 302       if (this == obj)
 303         return true;
 304
 305       // If its length is different, than it can't be equal.
 306       BitArray b = (BitArray) obj;
 307       if (m_length != b.m_length)
 308         return false;
 309
 310
 311       // Now compare the bits.
 312       // This is a little tricky, because if length doesn't divide 32,
 313       // then we shouldn't compare the unused bits in the last element
 314       // of m_array.
 315
 316       // Compare all full ints.  If any differ, then we are not equal.
 317       int numints = m_length/32;
 318       for (int i = 0; i < numints; i++)
 319       {
 320         if (b.m_array[i] != m_array[i])
 321           return false;
 322       }
 323
 324       // Compare the left over bits (if any)
 325       int extrabits = m_length%32;
 326       if (extrabits != 0)
 327       {
 328         // our mask is the "extrabits" least significant bits set to 1.
 329         UInt32 comparemask = ~0U >> (32 - extrabits);
 330
 331         // numints is rounded down, so it's safe to use as an index here,
 332         // as long as extrabits > 0.
 333         if ((b.m_array[numints] & comparemask)
 334             != (m_array[numints] & comparemask))
 335           return false;
 336       }
 337
 338       // We passed through all the above, so we are equal.
 339       return true;
 340
 341     }
 342     *  End comment out of Equals()
 343     */
 344
 345     public bool Get(int index)
 346     {
 347       if (index < 0 || index >= m_length)
 348         throw new ArgumentOutOfRangeException();
 349       return getBit(index);
 350     }
 351
 352     public IEnumerator GetEnumerator()
 353     {
 354
 355       return new BitArrayEnumerator(this);
 356     }
 357
 358     /*
 359      *  Since MS doesn't appear to override Equals/GetHashCode, we don't.
 360      *public override int GetHashCode()
 361     {
 362       // We could make this a constant time function
 363       // by just picking a constant number of bits, spread out
 364       // evenly across the entire array.  For now, this will suffice.
 365
 366       int retval = m_length;
 367
 368       // Add in each array element, except for the leftover bits.
 369       int numints = m_length/32;
 370       for (int i = 0; i < numints; i++)
 371         retval += (int)m_array[i];
 372
 373       // That's enough.  Adding in the leftover bits is tiring.
 374
 375       return retval;
 376     }
 377     * End comment out of GetHashCode()
 378     */
 379
 380     public BitArray Not()
 381     {
 382       Int32 [] newarr = new Int32[m_array.Length];
 383       for (int i=0; i < m_array.Length; i++)
 384         newarr[i] = ~m_array[i];
 385
 386       return new BitArray(newarr, m_length);
 387     }
 388
 389     public BitArray Or(BitArray operand)
 390     {
 391       if (operand == null)
 392         throw new ArgumentNullException();
 393       if (operand.m_length != m_length)
 394         throw new ArgumentException();
 395
 396       Int32 [] newarr = new Int32[m_array.Length];
 397       for (int i=0; i < m_array.Length; i++)
 398         newarr[i] = m_array[i] | operand.m_array[i];
 399
 400       return new BitArray(newarr, m_length);
 401     }
 402
 403     public void Set(int index, bool value)
 404     {
 405       if (index < 0 || index >= m_length)
 406         throw new ArgumentOutOfRangeException();
 407       setBit(index, value);
 408     }
 409
 410     public void SetAll(bool value)
 411     {
 412       if (value)
 413       {
 414         for (int i = 0; i < m_array.Length; i++)
 415           m_array[i] = ~0;
 416       }
 417       else
 418         Array.Clear(m_array, 0, m_array.Length);
 419       m_modCount++;
 420     }
 421
 422     public BitArray Xor(BitArray operand)
 423     {
 424       if (operand == null)
 425         throw new ArgumentNullException();
 426       if (operand.m_length != m_length)
 427         throw new ArgumentException();
 428
 429       Int32 [] newarr = new Int32[m_array.Length];
 430       for (int i=0; i < m_array.Length; i++)
 431         newarr[i] = m_array[i] ^ operand.m_array[i];
 432
 433       return new BitArray(newarr, m_length);
 434     }
 435
 436     ~BitArray()
 437     {
 438     }
 439
 440     class BitArrayEnumerator : IEnumerator
 441     {
 442       BitArray m_bitArray;
 443       private bool m_current;
 444       private int m_index;
 445       private int m_max;
 446       private int m_modCount;
 447
 448       public BitArrayEnumerator(BitArray ba)
 449       {
 450         m_index = -1;
 451         m_bitArray = ba;
 452         m_max = ba.m_length;
 453         m_modCount = ba.m_modCount;
 454       }
 455
 456       public object Current
 457       {
 458         get
 459         {
 460           if (m_index < 0 || m_index >= m_max)
 461             throw new InvalidOperationException();
 462           return m_current;
 463         }
 464       }
 465
 466       public bool MoveNext()
 467       {
 468         if (m_modCount != m_bitArray.m_modCount)
 469           throw new InvalidOperationException();
 470
 471         if (m_index + 1 >= m_max)
 472           return false;
 473
 474         m_index++;
 475         m_current = m_bitArray[m_index];
 476         return true;
 477       }
 478
 479       public void Reset()
 480       {
 481         if (m_modCount != m_bitArray.m_modCount)
 482           throw new InvalidOperationException();
 483         m_index = -1;
 484       }
 485     }
 486   }
 487 }
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498