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

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