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