?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
* Filters/FilterPackage.cs, Filters/FilterRPM.cs,
[beagle.git] / Util / BetterBitArray.cs
blobea1211b5fc85c4c0c54572521c80b33a725a249c
1 //
2 // Bit Array.cs
3 //
4 // Authors:
5 // Ben Maurer (bmaurer@users.sourceforge.net)
6 // Modified by Jon Trowbridge (trow@novell.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.Collections;
36
37 namespace Beagle.Util {
38 [Serializable]
39 public class BetterBitArray : ICollection, ICloneable {
40 int [] _array;
41 int _length;
42 int _version = 0;
43
44 #region Constructors
45 public BetterBitArray (BetterBitArray bits)
46 {
47 if (bits == null)
48 throw new ArgumentNullException ("bits");
49
50 _length = bits._length;
51 _array = new int [(_length + 31) / 32];
52
53 Array.Copy(bits._array, _array, _array.Length);
54 }
55
56 public BetterBitArray (bool [] values)
57 {
58 if (values == null)
59 throw new ArgumentNullException ("values");
60
61 _length = values.Length;
62 _array = new int [(_length + 31) / 32];
63
64 for (int i = 0; i < values.Length; i++)
65 this [i] = values [i];
66 }
67
68 public BetterBitArray (byte [] bytes)
69 {
70 if (bytes == null)
71 throw new ArgumentNullException ("bytes");
72
73 _length = bytes.Length * 8;
74 _array = new int [(_length + 31) / 32];
75
76 for (int i = 0; i < bytes.Length; i++)
77 setByte (i, bytes [i]);
78 }
79
80 public BetterBitArray (int [] values)
81 {
82 if (values == null)
83 throw new ArgumentNullException ("values");
84
85 int arrlen = values.Length;
86 _length = arrlen*32;
87 _array = new int [arrlen];
88 Array.Copy (values, _array, arrlen);
89 }
90
91 public BetterBitArray (int length)
92 {
93 if (length < 0)
94 throw new ArgumentOutOfRangeException ("length");
95
96 _length = length;
97 _array = new int [(_length + 31) / 32];
98 _contains_true = ContainsTrueState.No; // better
99 _cached_true_count = 0; // better
100 }
101
102 public BetterBitArray (int length, bool defaultValue) : this (length)
103 {
104 if (defaultValue) {
105 for (int i = 0; i < _array.Length; i++)
106 _array[i] = ~0;
107 _contains_true = ContainsTrueState.Yes; // better
108 _cached_true_count = length; // better
109 } else {
110 _contains_true = ContainsTrueState.No;
111 _cached_true_count = 0;
112 }
113 }
114
115 private BetterBitArray (int [] array, int length)
116 {
117 _array = array;
118 _length = length;
119 }
120 #endregion
121 #region Utility Methods
122
123 byte getByte (int byteIndex)
124 {
125 int index = byteIndex / 4;
126 int shift = (byteIndex % 4) * 8;
127
128 int theByte = _array [index] & (0xff << shift);
129
130 return (byte)((theByte >> shift) & 0xff);
131 }
132
133 void setByte (int byteIndex, byte value)
134 {
135 int index = byteIndex / 4;
136 int shift = (byteIndex % 4) * 8;
137
138 // clear the byte
139 _array [index] &= ~(0xff << shift);
140 // or in the new byte
141 _array [index] |= value << shift;
142
143 _version++;
144 }
145
146 void checkOperand (BetterBitArray operand)
147 {
148 if (operand == null)
149 throw new ArgumentNullException ();
150 if (operand._length != _length)
151 throw new ArgumentException ();
152 }
153 #endregion
154
155 public int Count {
156 get { return _length; }
157 }
158
159 public bool IsReadOnly {
160 get { return false; }
161 }
162
163 public bool IsSynchronized {
164 get { return false; }
165 }
166
167 public bool this [int index] {
168 get { return Get (index); }
169 set { Set (index, value); }
170 }
171
172 public int Length {
173 get { return _length; }
174 set {
175 if (value < 0)
176 throw new ArgumentOutOfRangeException ();
177
178 int newLen = value;
179 if (_length != newLen) {
180 int numints = (newLen + 31) / 32;
181 int [] newArr = new int [numints];
182 int copylen = (numints > _array.Length) ? _array.Length : numints;
183 Array.Copy (_array, newArr, copylen);
184
185 // set the internal state
186 _array = newArr;
187 _length = newLen;
188 _version++;
189 }
190 }
191 }
192
193 public object SyncRoot {
194 get { return this; }
195 }
196
197 public object Clone ()
198 {
199 // LAMESPEC: docs say shallow, MS makes deep.
200 return new BetterBitArray (this);
201 }
202
203 public void CopyTo (Array array, int index)
204 {
205 if (array == null)
206 throw new ArgumentNullException ("array");
207 if (index < 0)
208 throw new ArgumentOutOfRangeException ("index");
209
210 if (array.Rank != 1)
211 throw new ArgumentException ("array", "Array rank must be 1");
212
213 if (index >= array.Length)
214 throw new ArgumentException ("index", "index is greater than array.Length");
215
216 // in each case, check to make sure enough space in array
217
218 if (array is bool []) {
219 if (array.Length - index < _length)
220 throw new ArgumentException ();
221
222 bool [] barray = (bool []) array;
223
224 // Copy the bits into the array
225 for (int i = 0; i < _length; i++)
226 barray[index + i] = this [i];
227
228 } else if (array is byte []) {
229 int numbytes = (_length + 7) / 8;
230
231 if ((array.Length - index) < numbytes)
232 throw new ArgumentException ();
233
234 byte [] barray = (byte []) array;
235 // Copy the bytes into the array
236 for (int i = 0; i < numbytes; i++)
237 barray [index + i] = getByte (i);
238
239 } else if (array is int []) {
240
241 Array.Copy (_array, 0, array, index, (_length + 31) / 32);
242
243 } else {
244 throw new ArgumentException ("array", "Unsupported type");
245 }
246 }
247
248 public BetterBitArray Not ()
249 {
250 int ints = (_length + 31) / 32;
251 for (int i = 0; i < ints; i++)
252 _array [i] = ~_array [i];
253
254 _version++;
255 _contains_true = ContainsTrueState.Maybe; // better
256 _cached_true_count = -1; // better
257 return this;
258 }
259
260 public BetterBitArray And (BetterBitArray value)
261 {
262 checkOperand (value);
263
264 int ints = (_length + 31) / 32;
265 for (int i = 0; i < ints; i++)
266 _array [i] &= value._array [i];
267
268 _version++;
269 _contains_true = ContainsTrueState.Maybe; // better
270 _cached_true_count = -1; // better
271 return this;
272 }
273
274 public BetterBitArray AndNot (BetterBitArray value)
275 {
276 checkOperand (value);
277
278 int ints = (_length + 31) / 32;
279 for (int i = 0; i < ints; i++)
280 _array [i] &= ~value._array [i];
281
282 _version++;
283 _contains_true = ContainsTrueState.Maybe; // better
284 _cached_true_count = -1; // better
285 return this;
286 }
287
288 public BetterBitArray Or (BetterBitArray value)
289 {
290 checkOperand (value);
291
292 int ints = (_length + 31) / 32;
293 for (int i = 0; i < ints; i++)
294 _array [i] |= value._array [i];
295
296 _version++;
297 if (_contains_true == ContainsTrueState.Yes
298 || value._contains_true == ContainsTrueState.Yes)
299 _contains_true = ContainsTrueState.Yes;
300 else
301 _contains_true = ContainsTrueState.Maybe; // better
302 _cached_true_count = -1; // better
303 return this;
304 }
305
306 public BetterBitArray Xor (BetterBitArray value)
307 {
308 checkOperand (value);
309
310 int ints = (_length + 31) / 32;
311 for (int i = 0; i < ints; i++)
312 _array [i] ^= value._array [i];
313
314 _version++;
315 _contains_true = ContainsTrueState.Maybe; // better
316 _cached_true_count = -1; // better
317 return this;
318 }
319
320 public bool Get (int index)
321 {
322 if (index < 0 || index >= _length)
323 throw new ArgumentOutOfRangeException ();
324
325 // better
326 bool rv;
327 rv = (_array [index / 32] & (1 << (index % 32))) != 0;
328 if (rv)
329 _contains_true = ContainsTrueState.Yes;
330 return rv;
331 }
332
333 public void Set (int index, bool value)
334 {
335 if (index < 0 || index >= _length)
336 throw new ArgumentOutOfRangeException ();
337
338 // better
339 if (_cached_true_count != -1) {
340 bool old;
341 old = (_array [index / 32] & (1 << (index % 32))) != 0;
342 if (old)
343 --_cached_true_count;
344 if (value)
345 ++_cached_true_count;
346 }
347
348 if (value) {
349 _array [index / 32] |= (1 << (index % 32));
350 _contains_true = ContainsTrueState.Yes; // better
351 } else {
352 _array [index / 32] &= ~(1 << (index % 32));
353 if (_contains_true == ContainsTrueState.Yes) // better
354 _contains_true = ContainsTrueState.Maybe;
355 }
356
357 _version++;
358 }
359
360 public void SetAll (bool value)
361 {
362 if (value) {
363 for (int i = 0; i < _array.Length; i++)
364 _array[i] = ~0;
365 _contains_true = ContainsTrueState.Yes; // better
366 _cached_true_count = _length;
367 }
368 else {
369 Array.Clear (_array, 0, _array.Length);
370 _contains_true = ContainsTrueState.No; // better
371 _cached_true_count = 0; // better
372 }
373
374 _version++;
375 }
376
377 public IEnumerator GetEnumerator ()
378 {
379 return new BetterBitArrayEnumerator (this);
380 }
381
382 [Serializable]
383 class BetterBitArrayEnumerator : IEnumerator, ICloneable {
384
385 BetterBitArray _bitArray;
386 bool _current;
387 int _index, _version;
388
389 public object Clone () {
390 return MemberwiseClone ();
391 }
392
393 public BetterBitArrayEnumerator (BetterBitArray ba)
394 {
395 _index = -1;
396 _bitArray = ba;
397 _version = ba._version;
398 }
399
400 public object Current {
401 get {
402 if (_index == -1)
403 throw new InvalidOperationException ("Enum not started");
404 if (_index >= _bitArray.Count)
405 throw new InvalidOperationException ("Enum Ended");
406
407 return _current;
408 }
409 }
410
411 public bool MoveNext ()
412 {
413 checkVersion ();
414
415 if (_index < (_bitArray.Count - 1)) {
416 _current = _bitArray [++_index];
417 return true;
418 }
419 else
420 _index = _bitArray.Count;
421
422 return false;
423 }
424
425 public void Reset ()
426 {
427 checkVersion ();
428 _index = -1;
429 }
430
431 void checkVersion ()
432 {
433 if (_version != _bitArray._version)
434 throw new InvalidOperationException ();
435 }
436 }
437
438 ////////////////////////////////////////////////////////////////////////////
439
440 //
441 // The "Better" parts are below
442 //
443
444 static private int [] true_count = new int [256];
445
446 static BetterBitArray ()
447 {
448 for (int i = 0; i < 256; ++i) {
449 int x = i;
450 int count = 0;
451 while (x != 0) {
452 if ((x & 1) == 1)
453 ++count;
454 x >>= 1;
455 }
456 true_count [i] = count;
457 }
458 }
459
460 private enum ContainsTrueState {
461 Yes,
462 No,
463 Maybe
464 }
465
466 // Just in case, start in an ambiguous state.
467 private ContainsTrueState _contains_true = ContainsTrueState.Maybe;
468 private int _cached_true_count = -1;
469
470 // Returns the number of array elements that are set to true.
471 public int TrueCount {
472 get {
473 if (_cached_true_count < 0) {
474 _cached_true_count = 0;
475
476 for (int i = 0; i < _array.Length; ++i) {
477 int x = _array [i];
478 byte b1 = (byte) (x & 0xff);
479 byte b2 = (byte) ((x & (0xff << 8)) >> 8);
480 byte b3 = (byte) ((x & (0xff << 16)) >> 16);
481 byte b4 = (byte) ((x & (0xff << 24)) >> 24);
482 _cached_true_count += true_count [b1];
483 _cached_true_count += true_count [b2];
484 _cached_true_count += true_count [b3];
485 _cached_true_count += true_count [b4];
486 }
487
488
489 if (_cached_true_count == 0)
490 _contains_true = ContainsTrueState.No;
491 else
492 _contains_true = ContainsTrueState.Yes;
493 }
494
495 int paranoid_check = 0;
496 for (int i = 0; i < Count; ++i)
497 if (Get (i))
498 ++paranoid_check;
499 if (paranoid_check != _cached_true_count)
500 Logger.Log.Error ("TrueCount mismatch: {0} vs {1}", _cached_true_count, paranoid_check);
501
502 return _cached_true_count;
503 }
504 }
505
506 // Returns the index of the next 'true' value greater than or equal to
507 // start. If there is no such value, we return an index greater than
508 // or equal to array.Count.
509 // FIXME: It would be slightly nicer to provide some sort of enumerator
510 // that returned the indexes of the bits that are set.
511 public int GetNextTrueIndex (int start)
512 {
513 if (start >= _length || _contains_true == ContainsTrueState.No)
514 return _length;
515 else if (start < 0)
516 start = 0;
517
518 int i, offset;
519 i = start / 32;
520 offset = start % 32;
521
522 while (i < _array.Length) {
523
524 int array_value;
525 array_value = _array [i];
526
527 if (array_value != 0) {
528 if (offset > 0)
529 array_value = array_value >> offset;
530 while (offset < 32) {
531 if ((array_value & 1) != 0) {
532 if (i * 32 + offset < _length)
533 _contains_true = ContainsTrueState.Yes;
534 else if (start == 0)
535 _contains_true = ContainsTrueState.No;
536 return i * 32 + offset;
537 }
538 ++offset;
539 array_value = array_value >> 1;
540 }
541 }
542
543 ++i;
544 offset = 0;
545 }
546
547 if (start == 0)
548 _contains_true = ContainsTrueState.No;
549
550 // Failed
551 return _length;
552 }
553
554 // A version of GetNextTrueIndex for walking
555 // backwards across the array.
556 public int GetPreviousTrueIndex (int start)
557 {
558 if (start < 0 || _contains_true == ContainsTrueState.No)
559 return -1;
560 else if (start >= _length)
561 start = _length-1;
562
563 int i, offset;
564 i = start / 32;
565 offset = start % 32;
566
567 while (i >= 0) {
568
569 int array_value;
570 array_value = _array [i];
571
572 if (array_value != 0) {
573 int mask;
574 mask = 1 << offset;
575 while (offset >= 0) {
576 if ((array_value & mask) != 0)
577 return i * 32 + offset;
578 --offset;
579 mask >>= 1;
580 }
581 }
582
583 --i;
584 offset = 31;
585 }
586
587 // failed
588 return -1;
589 }
590
591 public bool ContainsTrue ()
592 {
593 if (_contains_true == ContainsTrueState.Maybe) {
594 if (GetNextTrueIndex (0) < _length)
595 _contains_true = ContainsTrueState.Yes;
596 else
597 _contains_true = ContainsTrueState.No;
598 }
599
600 return _contains_true == ContainsTrueState.Yes;
601 }
602
603 #if false
604 static void Main ()
605 {
606 Random rng = new Random ();
607
608 for (int trial = 0; trial < 10000; ++trial) {
609
610 bool failed = false;
611
612 BetterBitArray ba = new BetterBitArray (rng.Next (100000) + 1);
613
614 Hashtable true_hash = new Hashtable ();
615 int N = 1 + rng.Next (10000);
616 for (int k = 0; k < N; ++k) {
617 int j = rng.Next (ba.Count);
618 ba [j] = true;
619 true_hash [j] = true;
620 }
621
622 int i = 0;
623 while (i < ba.Count) {
624 i = ba.GetNextTrueIndex (i);
625 if (i < ba.Count) {
626 if (true_hash.Contains (i)) {
627 true_hash.Remove (i);
628 } else {
629 Console.WriteLine ("Spurious true at {0}", i);
630 failed = true;
631 }
632 }
633
634 ++i;
635 }
636
637 if (true_hash.Count > 0) {
638 Console.WriteLine ("Missed some trues:");
639 foreach (int k in true_hash.Values)
640 Console.WriteLine (" {0}", k);
641 failed = true;
642 }
643
644 Console.WriteLine ("Trial #{0}: {1}", trial+1,
645 failed ? "FAILED" : "ok");
646 }
647 }
648 #endif
649
650 }
651 }
A Beagle Git Repo