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