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