?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
2010-04-07 Jb Evain <jbevain@novell.com>
[mcs.git] / class / corlib / System.Collections / BitArray.cs
blob684295d07e4745785f2d134c3b2d32352e1ba7cd
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 private BitArray (int [] array, int length)
117 {
118 m_array = array;
119 m_length = length;
120 }
121 #endregion
122 #region Utility Methods
123
124 byte getByte (int byteIndex)
125 {
126 int index = byteIndex / 4;
127 int shift = (byteIndex % 4) * 8;
128
129 int theByte = m_array [index] & (0xff << shift);
130
131 return (byte)((theByte >> shift) & 0xff);
132 }
133
134 void setByte (int byteIndex, byte value)
135 {
136 int index = byteIndex / 4;
137 int shift = (byteIndex % 4) * 8;
138
139 // clear the byte
140 m_array [index] &= ~(0xff << shift);
141 // or in the new byte
142 m_array [index] |= value << shift;
143
144 _version++;
145 }
146
147 void checkOperand (BitArray operand)
148 {
149 if (operand == null)
150 throw new ArgumentNullException ();
151 if (operand.m_length != m_length)
152 throw new ArgumentException ();
153 }
154 #endregion
155
156 public int Count {
157 get { return m_length; }
158 }
159
160 public bool IsReadOnly {
161 get { return false; }
162 }
163
164 public bool IsSynchronized {
165 get { return false; }
166 }
167
168 public bool this [int index] {
169 get { return Get (index); }
170 set { Set (index, value); }
171 }
172
173 public int Length {
174 get { return m_length; }
175 set {
176 if (m_length == value)
177 return;
178
179 if (value < 0)
180 throw new ArgumentOutOfRangeException ();
181
182 // Currently we never shrink the array
183 if (value > m_length) {
184 int numints = (value + 31) / 32;
185 int old_numints = (m_length + 31) / 32;
186 if (numints > m_array.Length) {
187 int [] newArr = new int [numints];
188 Array.Copy (m_array, newArr, m_array.Length);
189 m_array = newArr;
190 } else {
191 Array.Clear(m_array, old_numints, numints - old_numints);
192 }
193
194 int mask = m_length % 32;
195 if (mask > 0)
196 m_array [old_numints - 1] &= (1 << mask) - 1;
197 }
198
199 // set the internal state
200 m_length = value;
201 _version++;
202 }
203 }
204
205 public object SyncRoot {
206 get { return this; }
207 }
208
209 public object Clone ()
210 {
211 // LAMESPEC: docs say shallow, MS makes deep.
212 return new BitArray (this);
213 }
214
215 public void CopyTo (Array array, int index)
216 {
217 if (array == null)
218 throw new ArgumentNullException ("array");
219 if (index < 0)
220 throw new ArgumentOutOfRangeException ("index");
221
222 if (array.Rank != 1)
223 throw new ArgumentException ("array", "Array rank must be 1");
224
225 if (index >= array.Length && m_length > 0)
226 throw new ArgumentException ("index", "index is greater than array.Length");
227
228 // in each case, check to make sure enough space in array
229
230 if (array is bool []) {
231 if (array.Length - index < m_length)
232 throw new ArgumentException ();
233
234 bool [] barray = (bool []) array;
235
236 // Copy the bits into the array
237 for (int i = 0; i < m_length; i++)
238 barray[index + i] = this [i];
239
240 } else if (array is byte []) {
241 int numbytes = (m_length + 7) / 8;
242
243 if ((array.Length - index) < numbytes)
244 throw new ArgumentException ();
245
246 byte [] barray = (byte []) array;
247 // Copy the bytes into the array
248 for (int i = 0; i < numbytes; i++)
249 barray [index + i] = getByte (i);
250
251 } else if (array is int []) {
252
253 Array.Copy (m_array, 0, array, index, (m_length + 31) / 32);
254
255 } else {
256 throw new ArgumentException ("array", "Unsupported type");
257 }
258 }
259
260 public BitArray Not ()
261 {
262 int ints = (m_length + 31) / 32;
263 for (int i = 0; i < ints; i++)
264 m_array [i] = ~m_array [i];
265
266 _version++;
267 return this;
268 }
269
270 public BitArray And (BitArray value)
271 {
272 checkOperand (value);
273
274 int ints = (m_length + 31) / 32;
275 for (int i = 0; i < ints; i++)
276 m_array [i] &= value.m_array [i];
277
278 _version++;
279 return this;
280 }
281
282 public BitArray Or (BitArray value)
283 {
284 checkOperand (value);
285
286 int ints = (m_length + 31) / 32;
287 for (int i = 0; i < ints; i++)
288 m_array [i] |= value.m_array [i];
289
290 _version++;
291 return this;
292 }
293
294 public BitArray Xor (BitArray value)
295 {
296 checkOperand (value);
297
298 int ints = (m_length + 31) / 32;
299 for (int i = 0; i < ints; i++)
300 m_array [i] ^= value.m_array [i];
301
302 _version++;
303 return this;
304 }
305
306 public bool Get (int index)
307 {
308 if (index < 0 || index >= m_length)
309 throw new ArgumentOutOfRangeException ();
310
311 return (m_array [index >> 5] & (1 << (index & 31))) != 0;
312 }
313
314 public void Set (int index, bool value)
315 {
316 if (index < 0 || index >= m_length)
317 throw new ArgumentOutOfRangeException ();
318
319 if (value)
320 m_array [index >> 5] |= (1 << (index & 31));
321 else
322 m_array [index >> 5] &= ~(1 << (index & 31));
323
324 _version++;
325 }
326
327 public void SetAll (bool value)
328 {
329 if (value) {
330 for (int i = 0; i < m_array.Length; i++)
331 m_array[i] = ~0;
332 }
333 else
334 Array.Clear (m_array, 0, m_array.Length);
335
336 _version++;
337 }
338
339 public IEnumerator GetEnumerator ()
340 {
341 return new BitArrayEnumerator (this);
342 }
343
344 [Serializable]
345 class BitArrayEnumerator : IEnumerator, ICloneable {
346 BitArray _bitArray;
347 bool _current;
348 int _index, _version;
349
350 public object Clone () {
351 return MemberwiseClone ();
352 }
353
354 public BitArrayEnumerator (BitArray ba)
355 {
356 _index = -1;
357 _bitArray = ba;
358 _version = ba._version;
359 }
360
361 public object Current {
362 get {
363 if (_index == -1)
364 throw new InvalidOperationException ("Enum not started");
365 if (_index >= _bitArray.Count)
366 throw new InvalidOperationException ("Enum Ended");
367
368 return _current;
369 }
370 }
371
372 public bool MoveNext ()
373 {
374 checkVersion ();
375
376 if (_index < (_bitArray.Count - 1)) {
377 _current = _bitArray [++_index];
378 return true;
379 }
380
381 _index = _bitArray.Count;
382 return false;
383 }
384
385 public void Reset ()
386 {
387 checkVersion ();
388 _index = -1;
389 }
390
391 void checkVersion ()
392 {
393 if (_version != _bitArray._version)
394 throw new InvalidOperationException ();
395 }
396 }
397 }
398 }
git-svn mirror of mcs