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 //
  11 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  12 //
  13 // Permission is hereby granted, free of charge, to any person obtaining
  14 // a copy of this software and associated documentation files (the
  15 // "Software"), to deal in the Software without restriction, including
  16 // without limitation the rights to use, copy, modify, merge, publish,
  17 // distribute, sublicense, and/or sell copies of the Software, and to
  18 // permit persons to whom the Software is furnished to do so, subject to
  19 // the following conditions:
  20 //
  21 // The above copyright notice and this permission notice shall be
  22 // included in all copies or substantial portions of the Software.
  23 //
  24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  31 //
  32
  33 using System;
  34
  35 namespace System.Collections {
  36         [Serializable]
  37         public sealed class BitArray : ICollection, ICloneable {
  38                 int [] _array;
  39                 int _length;
  40                 int _version = 0;
  41
  42 #region Constructors
  43                 public BitArray (BitArray bits)
  44                 {
  45                         if (bits == null)
  46                                 throw new ArgumentNullException ("bits");
  47
  48                         _length = bits._length;
  49                         _array = new int [(_length + 31) / 32];
  50
  51                         Array.Copy(bits._array, _array, _array.Length);
  52                 }
  53
  54                 public BitArray (bool [] values)
  55                 {
  56                         if (values == null)
  57                                 throw new ArgumentNullException ("values");
  58
  59                         _length = values.Length;
  60                         _array = new int [(_length + 31) / 32];
  61
  62                         for (int i = 0; i < values.Length; i++)
  63                                 this [i] = values [i];
  64                 }
  65
  66                 public BitArray (byte [] bytes)
  67                 {
  68                         if (bytes == null)
  69                                 throw new ArgumentNullException ("bytes");
  70
  71                         _length = bytes.Length * 8;
  72                         _array = new int [(_length + 31) / 32];
  73
  74                         for (int i = 0; i < bytes.Length; i++)
  75                                 setByte (i, bytes [i]);
  76                 }
  77
  78                 public BitArray (int [] values)
  79                 {
  80                         if (values == null)
  81                                 throw new ArgumentNullException ("values");
  82
  83                         int arrlen = values.Length;
  84                         _length = arrlen*32;
  85                         _array = new int [arrlen];
  86                         Array.Copy (values, _array, arrlen);
  87                 }
  88
  89                 public BitArray (int length)
  90                 {
  91                         if (length < 0)
  92                                 throw new ArgumentOutOfRangeException ("length");
  93
  94                         _length = length;
  95                         _array = new int [(_length + 31) / 32];
  96                 }
  97
  98                 public BitArray (int length, bool defaultValue) : this (length)
  99                 {
 100                         if (defaultValue) {
 101                                 for (int i = 0; i < _array.Length; i++)
 102                                 _array[i] = ~0;
 103                         }
 104                 }
 105
 106                 private BitArray (int [] array, int length)
 107                 {
 108                         _array = array;
 109                         _length = length;
 110                 }
 111 #endregion
 112 #region Utility Methods
 113
 114                 byte getByte (int byteIndex)
 115                 {
 116                         int index = byteIndex / 4;
 117                         int shift = (byteIndex % 4) * 8;
 118
 119                         int theByte = _array [index] & (0xff << shift);
 120
 121                         return (byte)((theByte >> shift) & 0xff);
 122                 }
 123
 124                 void setByte (int byteIndex, byte value)
 125                 {
 126                         int index = byteIndex / 4;
 127                         int shift = (byteIndex % 4) * 8;
 128
 129                         // clear the byte
 130                         _array [index] &= ~(0xff << shift);
 131                         // or in the new byte
 132                         _array [index] |= value << shift;
 133
 134                         _version++;
 135                 }
 136
 137                 void checkOperand (BitArray operand)
 138                 {
 139                         if (operand == null)
 140                                 throw new ArgumentNullException ();
 141                         if (operand._length != _length)
 142                                 throw new ArgumentException ();
 143                 }
 144 #endregion
 145
 146                 public int Count {
 147                         get { return _length; }
 148                 }
 149
 150                 public bool IsReadOnly {
 151                         get { return false; }
 152                 }
 153
 154                 public bool IsSynchronized {
 155                         get { return false; }
 156                 }
 157
 158                 public bool this [int index] {
 159                         get { return Get (index); }
 160                         set { Set (index, value); }
 161                 }
 162
 163                 public int Length {
 164                         get { return _length; }
 165                         set {
 166                                 if (value < 0)
 167                                         throw new ArgumentOutOfRangeException ();
 168
 169                                 int newLen = value;
 170                                 if (_length != newLen) {
 171                                         int numints = (newLen + 31) / 32;
 172                                         int [] newArr = new int [numints];
 173                                         int copylen = (numints > _array.Length) ? _array.Length : numints;
 174                                         Array.Copy (_array, newArr, copylen);
 175
 176                                         // set the internal state
 177                                         _array = newArr;
 178                                         _length = newLen;
 179                                         _version++;
 180                                 }
 181                         }
 182                 }
 183
 184                 public object SyncRoot {
 185                         get { return this; }
 186                 }
 187
 188                 public object Clone ()
 189                 {
 190                         // LAMESPEC: docs say shallow, MS makes deep.
 191                         return new BitArray (this);
 192                 }
 193
 194                 public void CopyTo (Array array, int index)
 195                 {
 196                         if (array == null)
 197                                 throw new ArgumentNullException ("array");
 198                         if (index < 0)
 199                                 throw new ArgumentOutOfRangeException ("index");
 200
 201                         if (array.Rank != 1)
 202                                 throw new ArgumentException ("array", "Array rank must be 1");
 203
 204                         if (index >= array.Length)
 205                                 throw new ArgumentException ("index", "index is greater than array.Length");
 206
 207                         // in each case, check to make sure enough space in array
 208
 209                         if (array is bool []) {
 210                                 if (array.Length - index < _length)
 211                                          throw new ArgumentException ();
 212
 213                                 bool [] barray = (bool []) array;
 214
 215                                 // Copy the bits into the array
 216                                 for (int i = 0; i < _length; i++)
 217                                         barray[index + i] = this [i];
 218
 219                         } else if (array is byte []) {
 220                                 int numbytes = (_length + 7) / 8;
 221
 222                                 if ((array.Length - index) < numbytes)
 223                                          throw new ArgumentException ();
 224
 225                                 byte [] barray = (byte []) array;
 226                                 // Copy the bytes into the array
 227                                 for (int i = 0; i < numbytes; i++)
 228                                         barray [index + i] = getByte (i);
 229
 230                         } else if (array is int []) {
 231
 232                                 Array.Copy (_array, 0, array, index, (_length + 31) / 32);
 233
 234                         } else {
 235                                 throw new ArgumentException ("array", "Unsupported type");
 236                         }
 237                 }
 238
 239                 public BitArray Not ()
 240                 {
 241                         int ints = (_length + 31) / 32;
 242                         for (int i = 0; i < ints; i++)
 243                                 _array [i] = ~_array [i];
 244
 245                         _version++;
 246                         return this;
 247                 }
 248
 249                 public BitArray And (BitArray value)
 250                 {
 251                         checkOperand (value);
 252
 253                         int ints = (_length + 31) / 32;
 254                         for (int i = 0; i < ints; i++)
 255                                 _array [i] &= value._array [i];
 256
 257                         _version++;
 258                         return this;
 259                 }
 260
 261                 public BitArray Or (BitArray value)
 262                 {
 263                         checkOperand (value);
 264
 265                         int ints = (_length + 31) / 32;
 266                         for (int i = 0; i < ints; i++)
 267                                 _array [i] |= value._array [i];
 268
 269                         _version++;
 270                         return this;
 271                 }
 272
 273                 public BitArray Xor (BitArray value)
 274                 {
 275                         checkOperand (value);
 276
 277                         int ints = (_length + 31) / 32;
 278                         for (int i = 0; i < ints; i++)
 279                                 _array [i] ^= value._array [i];
 280
 281                         _version++;
 282                         return this;
 283                 }
 284
 285                 public bool Get (int index)
 286                 {
 287                         if (index < 0 || index >= _length)
 288                                 throw new ArgumentOutOfRangeException ();
 289
 290                         return (_array [index / 32] & (1 << (index % 32))) != 0;
 291                 }
 292
 293                 public void Set (int index, bool value)
 294                 {
 295                         if (index < 0 || index >= _length)
 296                                 throw new ArgumentOutOfRangeException ();
 297
 298                         if (value)
 299                                 _array [index / 32] |=  (1 << (index % 32));
 300                         else
 301                                 _array [index / 32] &= ~(1 << (index % 32));
 302
 303                         _version++;
 304                 }
 305
 306                 public void SetAll (bool value)
 307                 {
 308                         if (value) {
 309                                 for (int i = 0; i < _array.Length; i++)
 310                                         _array[i] = ~0;
 311                         }
 312                         else
 313                                 Array.Clear (_array, 0, _array.Length);
 314
 315                         _version++;
 316                 }
 317
 318                 public IEnumerator GetEnumerator ()
 319                 {
 320                         return new BitArrayEnumerator (this);
 321                 }
 322
 323                 [Serializable]
 324                 class BitArrayEnumerator : IEnumerator, ICloneable {
 325                         BitArray _bitArray;
 326                         bool _current;
 327                         int _index, _max, _version;
 328
 329                         public object Clone () {
 330                                 return MemberwiseClone ();
 331                         }
 332
 333                         public BitArrayEnumerator (BitArray ba)
 334                         {
 335                                 _index = -1;
 336                                 _bitArray = ba;
 337                                 _max = ba._length;
 338                                 _version = ba._version;
 339                         }
 340
 341                         public object Current {
 342                                 get {
 343                                         if (_index == -1)
 344                                                 throw new InvalidOperationException ("Enum not started");
 345                                         if (_index >= _bitArray.Count)
 346                                                 throw new InvalidOperationException ("Enum Ended");
 347
 348                                         return _current;
 349                                 }
 350                         }
 351
 352                         public bool MoveNext ()
 353                         {
 354                                 checkVersion ();
 355
 356                                 if (_index < (_bitArray.Count - 1)) {
 357                                         _current = _bitArray [++_index];
 358                                         return true;
 359                                 }
 360                                 else
 361                                         _index = _bitArray.Count;
 362
 363                                 return false;
 364                         }
 365
 366                         public void Reset ()
 367                         {
 368                                 checkVersion ();
 369                                 _index = -1;
 370                         }
 371
 372                         void checkVersion ()
 373                         {
 374                                 if (_version != _bitArray._version)
 375                                         throw new InvalidOperationException ();
 376                         }
 377                 }
 378         }
 379 }