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

   1 //
   2 // Bit Array.cs
   3 //
   4 // Authors:
   5 // Ben Maurer (bmaurer@users.sourceforge.net)
   6 //
   7 // (C) 2003 Ben Maurer
   8 //
   9
  10 using System;
  11
  12 namespace System.Collections {
  13         [Serializable]
  14         public sealed class BitArray : ICollection, ICloneable {
  15                 int [] _array;
  16                 int _length;
  17                 int _version = 0;
  18
  19 #region Constructors
  20                 public BitArray (BitArray orig)
  21                 {
  22                         if (orig == null)
  23                                 throw new ArgumentNullException ("orig");
  24
  25                         _length = orig._length;
  26                         _array = new int [(_length + 31) / 32];
  27
  28                         Array.Copy(orig._array, _array, _array.Length);
  29                 }
  30
  31                 public BitArray (bool [] bits)
  32                 {
  33                         if (bits == null)
  34                                 throw new ArgumentNullException ("bits");
  35
  36                         _length = bits.Length;
  37                         _array = new int [(_length + 31) / 32];
  38
  39                         for (int i = 0; i < bits.Length; i++)
  40                                 this [i] = bits [i];
  41                 }
  42
  43                 public BitArray (byte [] bytes)
  44                 {
  45                         if (bytes == null)
  46                                 throw new ArgumentNullException ("bytes");
  47
  48                         _length = bytes.Length * 8;
  49                         _array = new int [(_length + 31) / 32];
  50
  51                         for (int i = 0; i < bytes.Length; i++)
  52                                 setByte (i, bytes [i]);
  53                 }
  54
  55                 public BitArray (int [] words)
  56                 {
  57                         if (words == null)
  58                                 throw new ArgumentNullException ("words");
  59
  60                         int arrlen = words.Length;
  61                         _length = arrlen*32;
  62                         _array = new int [arrlen];
  63                         Array.Copy (words, _array, arrlen);
  64                 }
  65
  66                 public BitArray (int capacity)
  67                 {
  68                         if (capacity < 0)
  69                                 throw new ArgumentOutOfRangeException ("capacity");
  70
  71                         _length = capacity;
  72                         _array = new int [(_length + 31) / 32];
  73                 }
  74
  75                 public BitArray (int capacity, bool value) : this (capacity)
  76                 {
  77                         if (value) {
  78                                 for (int i = 0; i < _array.Length; i++)
  79                                 _array[i] = ~0;
  80                         }
  81                 }
  82
  83                 private BitArray (int [] array, int length)
  84                 {
  85                         _array = array;
  86                         _length = length;
  87                 }
  88 #endregion
  89 #region Utility Methods
  90
  91                 byte getByte (int byteIndex)
  92                 {
  93                         int index = byteIndex / 4;
  94                         int shift = (byteIndex % 4) * 8;
  95
  96                         int theByte = _array [index] & (0xff << shift);
  97
  98                         return (byte)((theByte >> shift) & 0xff);
  99                 }
 100
 101                 void setByte (int byteIndex, byte value)
 102                 {
 103                         int index = byteIndex / 4;
 104                         int shift = (byteIndex % 4) * 8;
 105
 106                         // clear the byte
 107                         _array [index] &= ~(0xff << shift);
 108                         // or in the new byte
 109                         _array [index] |= value << shift;
 110
 111                         _version++;
 112                 }
 113
 114                 void checkOperand (BitArray operand)
 115                 {
 116                         if (operand == null)
 117                                 throw new ArgumentNullException ();
 118                         if (operand._length != _length)
 119                                 throw new ArgumentException ();
 120                 }
 121 #endregion
 122
 123                 public int Count {
 124                         get { return _length; }
 125                 }
 126
 127                 public bool IsReadOnly {
 128                         get { return false; }
 129                 }
 130
 131                 public bool IsSynchronized {
 132                         get { return false; }
 133                 }
 134
 135                 public bool this [int index] {
 136                         get { return Get (index); }
 137                         set { Set (index, value); }
 138                 }
 139
 140                 public int Length {
 141                         get { return _length; }
 142                         set {
 143                                 if (value < 0)
 144                                         throw new ArgumentOutOfRangeException ();
 145
 146                                 int newLen = value;
 147                                 if (_length != newLen) {
 148                                         int numints = (newLen + 31) / 32;
 149                                         int [] newArr = new int [numints];
 150                                         int copylen = (numints > _array.Length) ? _array.Length : numints;
 151                                         Array.Copy (_array, newArr, copylen);
 152
 153                                         // set the internal state
 154                                         _array = newArr;
 155                                         _length = newLen;
 156                                         _version++;
 157                                 }
 158                         }
 159                 }
 160
 161                 public object SyncRoot {
 162                         get { return this; }
 163                 }
 164
 165                 public object Clone ()
 166                 {
 167                         // LAMESPEC: docs say shallow, MS makes deep.
 168                         return new BitArray (this);
 169                 }
 170
 171                 public void CopyTo (Array array, int index)
 172                 {
 173                         if (array == null)
 174                                 throw new ArgumentNullException ("array");
 175                         if (index < 0)
 176                                 throw new ArgumentOutOfRangeException ("index");
 177
 178                         if (array.Rank != 1)
 179                                 throw new ArgumentException ("array", "Array rank must be 1");
 180
 181                         if (index >= array.Length)
 182                                 throw new ArgumentException ("index", "index is greater than array.Length");
 183
 184                         // in each case, check to make sure enough space in array
 185
 186                         if (array is bool []) {
 187                                 if (array.Length - index < _length)
 188                                          throw new ArgumentException ();
 189
 190                                 bool [] barray = (bool []) array;
 191
 192                                 // Copy the bits into the array
 193                                 for (int i = 0; i < _length; i++)
 194                                         barray[index + i] = this [i];
 195
 196                         } else if (array is byte []) {
 197                                 int numbytes = (_length + 7) / 8;
 198
 199                                 if ((array.Length - index) < numbytes)
 200                                          throw new ArgumentException ();
 201
 202                                 byte [] barray = (byte []) array;
 203                                 // Copy the bytes into the array
 204                                 for (int i = 0; i < numbytes; i++)
 205                                         barray [index + i] = getByte (i);
 206
 207                         } else if (array is int []) {
 208
 209                                 Array.Copy (_array, 0, array, index, (_length + 31) / 32);
 210
 211                         } else {
 212                                 throw new ArgumentException ("array", "Unsupported type");
 213                         }
 214                 }
 215
 216                 public BitArray Not ()
 217                 {
 218                         int ints = (_length + 31) / 32;
 219                         for (int i = 0; i < ints; i++)
 220                                 _array [i] = ~_array [i];
 221
 222                         _version++;
 223                         return this;
 224                 }
 225
 226                 public BitArray And (BitArray operand)
 227                 {
 228                         checkOperand (operand);
 229
 230                         int ints = (_length + 31) / 32;
 231                         for (int i = 0; i < ints; i++)
 232                                 _array [i] &= operand._array [i];
 233
 234                         _version++;
 235                         return this;
 236                 }
 237
 238                 public BitArray Or (BitArray operand)
 239                 {
 240                         checkOperand (operand);
 241
 242                         int ints = (_length + 31) / 32;
 243                         for (int i = 0; i < ints; i++)
 244                                 _array [i] |= operand._array [i];
 245
 246                         _version++;
 247                         return this;
 248                 }
 249
 250                 public BitArray Xor (BitArray operand)
 251                 {
 252                         checkOperand (operand);
 253
 254                         int ints = (_length + 31) / 32;
 255                         for (int i = 0; i < ints; i++)
 256                                 _array [i] ^= operand._array [i];
 257
 258                         _version++;
 259                         return this;
 260                 }
 261
 262                 public bool Get (int index)
 263                 {
 264                         if (index < 0 || index >= _length)
 265                                 throw new ArgumentOutOfRangeException ();
 266
 267                         return (_array [index / 32] & (1 << (index % 32))) != 0;
 268                 }
 269
 270                 public void Set (int index, bool value)
 271                 {
 272                         if (index < 0 || index >= _length)
 273                                 throw new ArgumentOutOfRangeException ();
 274
 275                         if (value)
 276                                 _array [index / 32] |=  (1 << (index % 32));
 277                         else
 278                                 _array [index / 32] &= ~(1 << (index % 32));
 279
 280                         _version++;
 281                 }
 282
 283                 public void SetAll (bool value)
 284                 {
 285                         if (value) {
 286                                 for (int i = 0; i < _array.Length; i++)
 287                                         _array[i] = ~0;
 288                         }
 289                         else
 290                                 Array.Clear (_array, 0, _array.Length);
 291
 292                         _version++;
 293                 }
 294
 295                 public IEnumerator GetEnumerator ()
 296                 {
 297                         return new BitArrayEnumerator (this);
 298                 }
 299
 300                 [Serializable]
 301                 class BitArrayEnumerator : IEnumerator, ICloneable {
 302                         BitArray _bitArray;
 303                         bool _current;
 304                         int _index, _max, _version;
 305
 306                         public object Clone () {
 307                                 return MemberwiseClone ();
 308                         }
 309
 310                         public BitArrayEnumerator (BitArray ba)
 311                         {
 312                                 _index = -1;
 313                                 _bitArray = ba;
 314                                 _max = ba._length;
 315                                 _version = ba._version;
 316                         }
 317
 318                         public object Current {
 319                                 get {
 320                                         if (_index == -1)
 321                                                 throw new InvalidOperationException ("Enum not started");
 322                                         if (_index >= _bitArray.Count)
 323                                                 throw new InvalidOperationException ("Enum Ended");
 324
 325                                         return _current;
 326                                 }
 327                         }
 328
 329                         public bool MoveNext ()
 330                         {
 331                                 checkVersion ();
 332
 333                                 if (_index < (_bitArray.Count - 1)) {
 334                                         _current = _bitArray [++_index];
 335                                         return true;
 336                                 }
 337                                 else
 338                                         _index = _bitArray.Count;
 339
 340                                 return false;
 341                         }
 342
 343                         public void Reset ()
 344                         {
 345                                 checkVersion ();
 346                                 _index = -1;
 347                         }
 348
 349                         void checkVersion ()
 350                         {
 351                                 if (_version != _bitArray._version)
 352                                         throw new InvalidOperationException ();
 353                         }
 354                 }
 355         }
 356 }