Mercurial > projects > ldc

comparison tango/tango/core/BitArray.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
1 /**
2 * This module contains a packed bit array implementation in the style of D's
3 * built-in dynamic arrays.
4 *
5 * Copyright: Copyright (C) 2005-2006 Digital Mars, www.digitalmars.com.
6 * All rights reserved.
7 * License: BSD style: $(LICENSE)
8 * Authors: Walter Bright, Sean Kelly
9 */
10 module tango.core.BitArray;
11
12
13 private import tango.core.BitManip;
14
15
16 /**
17 * An array of bits.
18 */
19 struct BitArray
20 {
21 size_t len;
22 uint* ptr;
23
24
25 /**
26 *
27 */
28 static BitArray opCall( bool[] bits )
29 {
30 BitArray temp;
31
32 temp.length = bits.length;
33 foreach( pos, val; bits )
34 temp[pos] = val;
35 return temp;
36 }
37
38 /**
39 *
40 */
41 size_t length()
42 {
43 return len;
44 }
45
46
47 /**
48 *
49 */
50 void length(size_t newlen)
51 {
52 if (newlen != len)
53 {
54 size_t olddim = dim();
55 size_t newdim = (newlen + 31) / 32;
56
57 if (newdim != olddim)
58 {
59 // Create a fake array so we can use D's realloc machinery
60 uint[] b = ptr[0 .. olddim];
61
62 b.length = newdim; // realloc
63 ptr = b.ptr;
64 if (newdim & 31)
65 {
66 // Set any pad bits to 0
67 ptr[newdim - 1] &= ~(~0 << (newdim & 31));
68 }
69 }
70 len = newlen;
71 }
72 }
73
74
75 /**
76 *
77 */
78 size_t dim()
79 {
80 return (len + 31) / 32;
81 }
82
83
84 /**
85 * Support for array.dup property for BitArray.
86 */
87 BitArray dup()
88 {
89 BitArray ba;
90
91 uint[] b = ptr[0 .. dim].dup;
92 ba.len = len;
93 ba.ptr = b.ptr;
94 return ba;
95 }
96
97
98 debug( UnitTest )
99 {
100 unittest
101 {
102 BitArray a;
103 BitArray b;
104 int i;
105
106 a.length = 3;
107 a[0] = 1; a[1] = 0; a[2] = 1;
108 b = a.dup;
109 assert(b.length == 3);
110 for (i = 0; i < 3; i++)
111 {
112 //printf("b[%d] = %d\n", i, b[i]);
113 assert(b[i] == (((i ^ 1) & 1) ? true : false));
114 }
115 }
116 }
117
118
119 /**
120 * Set BitArray to contents of ba[]
121 */
122 void opAssign(bool[] ba)
123 {
124 length = ba.length;
125 foreach (i, b; ba)
126 {
127 (*this)[i] = b;
128 }
129 }
130
131
132 /**
133 * Map BitArray onto v[], with numbits being the number of bits
134 * in the array. Does not copy the data.
135 *
136 * This is the inverse of opCast.
137 */
138 void init(void[] v, size_t numbits)
139 in
140 {
141 assert(numbits <= v.length * 8);
142 assert((v.length & 3) == 0);
143 }
144 body
145 {
146 ptr = cast(uint*)v.ptr;
147 len = numbits;
148 }
149
150
151 debug( UnitTest )
152 {
153 unittest
154 {
155 BitArray a = [1,0,1,0,1];
156 BitArray b;
157 void[] v;
158
159 v = cast(void[])a;
160 b.init(v, a.length);
161
162 assert(b[0] == 1);
163 assert(b[1] == 0);
164 assert(b[2] == 1);
165 assert(b[3] == 0);
166 assert(b[4] == 1);
167
168 a[0] = 0;
169 assert(b[0] == 0);
170
171 assert(a == b);
172 }
173 }
174
175
176 /**
177 * Support for array.reverse property for BitArray.
178 */
179 BitArray reverse()
180 out (result)
181 {
182 assert(result == *this);
183 }
184 body
185 {
186 if (len >= 2)
187 {
188 bool t;
189 size_t lo, hi;
190
191 lo = 0;
192 hi = len - 1;
193 for (; lo < hi; lo++, hi--)
194 {
195 t = (*this)[lo];
196 (*this)[lo] = (*this)[hi];
197 (*this)[hi] = t;
198 }
199 }
200 return *this;
201 }
202
203
204 debug( UnitTest )
205 {
206 unittest
207 {
208 BitArray b;
209 static bool[5] data = [1,0,1,1,0];
210 int i;
211
212 b = data;
213 b.reverse;
214 for (i = 0; i < data.length; i++)
215 {
216 assert(b[i] == data[4 - i]);
217 }
218 }
219 }
220
221
222 /**
223 * Support for array.sort property for BitArray.
224 */
225 BitArray sort()
226 out (result)
227 {
228 assert(result == *this);
229 }
230 body
231 {
232 if (len >= 2)
233 {
234 size_t lo, hi;
235
236 lo = 0;
237 hi = len - 1;
238 while (1)
239 {
240 while (1)
241 {
242 if (lo >= hi)
243 goto Ldone;
244 if ((*this)[lo] == true)
245 break;
246 lo++;
247 }
248
249 while (1)
250 {
251 if (lo >= hi)
252 goto Ldone;
253 if ((*this)[hi] == false)
254 break;
255 hi--;
256 }
257
258 (*this)[lo] = false;
259 (*this)[hi] = true;
260
261 lo++;
262 hi--;
263 }
264 Ldone:
265 ;
266 }
267 return *this;
268 }
269
270
271 debug( UnitTest )
272 {
273 unittest
274 {
275 static uint x = 0b1100011000;
276 static BitArray ba = { 10, &x };
277
278 ba.sort;
279 for (size_t i = 0; i < 6; i++)
280 assert(ba[i] == false);
281 for (size_t i = 6; i < 10; i++)
282 assert(ba[i] == true);
283 }
284 }
285
286
287 /**
288 * Support for foreach loops for BitArray.
289 */
290 int opApply(int delegate(inout bool) dg)
291 {
292 int result;
293
294 for (size_t i = 0; i < len; i++)
295 {
296 bool b = opIndex(i);
297 result = dg(b);
298 opIndexAssign(b,i);
299 if (result)
300 break;
301 }
302 return result;
303 }
304
305 /** ditto */
306 int opApply(int delegate(inout size_t, inout bool) dg)
307 {
308 int result;
309
310 for (size_t i = 0; i < len; i++)
311 {
312 bool b = opIndex(i);
313 result = dg(i, b);
314 opIndexAssign(b,i);
315 if (result)
316 break;
317 }
318 return result;
319 }
320
321
322 debug( UnitTest )
323 {
324 unittest
325 {
326 BitArray a = [1,0,1];
327
328 int i;
329 foreach (b;a)
330 {
331 switch (i)
332 {
333 case 0: assert(b == true); break;
334 case 1: assert(b == false); break;
335 case 2: assert(b == true); break;
336 default: assert(0);
337 }
338 i++;
339 }
340
341 foreach (j,b;a)
342 {
343 switch (j)
344 {
345 case 0: assert(b == true); break;
346 case 1: assert(b == false); break;
347 case 2: assert(b == true); break;
348 default: assert(0);
349 }
350 }
351 }
352 }
353
354
355 /**
356 * Support for operators == and != for bit arrays.
357 */
358 int opEquals(BitArray a2)
359 {
360 int i;
361
362 if (this.length != a2.length)
363 return 0; // not equal
364 byte *p1 = cast(byte*)this.ptr;
365 byte *p2 = cast(byte*)a2.ptr;
366 uint n = this.length / 8;
367 for (i = 0; i < n; i++)
368 {
369 if (p1[i] != p2[i])
370 return 0; // not equal
371 }
372
373 ubyte mask;
374
375 n = this.length & 7;
376 mask = cast(ubyte)((1 << n) - 1);
377 //printf("i = %d, n = %d, mask = %x, %x, %x\n", i, n, mask, p1[i], p2[i]);
378 return (mask == 0) || (p1[i] & mask) == (p2[i] & mask);
379 }
380
381 debug( UnitTest )
382 {
383 unittest
384 {
385 BitArray a = [1,0,1,0,1];
386 BitArray b = [1,0,1];
387 BitArray c = [1,0,1,0,1,0,1];
388 BitArray d = [1,0,1,1,1];
389 BitArray e = [1,0,1,0,1];
390
391 assert(a != b);
392 assert(a != c);
393 assert(a != d);
394 assert(a == e);
395 }
396 }
397
398
399 /**
400 * Implement comparison operators.
401 */
402 int opCmp(BitArray a2)
403 {
404 uint len;
405 uint i;
406
407 len = this.length;
408 if (a2.length < len)
409 len = a2.length;
410 ubyte* p1 = cast(ubyte*)this.ptr;
411 ubyte* p2 = cast(ubyte*)a2.ptr;
412 uint n = len / 8;
413 for (i = 0; i < n; i++)
414 {
415 if (p1[i] != p2[i])
416 break; // not equal
417 }
418 for (uint j = i * 8; j < len; j++)
419 { ubyte mask = cast(ubyte)(1 << j);
420 int c;
421
422 c = cast(int)(p1[i] & mask) - cast(int)(p2[i] & mask);
423 if (c)
424 return c;
425 }
426 return cast(int)this.len - cast(int)a2.length;
427 }
428
429 debug( UnitTest )
430 {
431 unittest
432 {
433 BitArray a = [1,0,1,0,1];
434 BitArray b = [1,0,1];
435 BitArray c = [1,0,1,0,1,0,1];
436 BitArray d = [1,0,1,1,1];
437 BitArray e = [1,0,1,0,1];
438
439 assert(a > b);
440 assert(a >= b);
441 assert(a < c);
442 assert(a <= c);
443 assert(a < d);
444 assert(a <= d);
445 assert(a == e);
446 assert(a <= e);
447 assert(a >= e);
448 }
449 }
450
451
452 /**
453 * Convert to void[].
454 */
455 void[] opCast()
456 {
457 return cast(void[])ptr[0 .. dim];
458 }
459
460
461 debug( UnitTest )
462 {
463 unittest
464 {
465 BitArray a = [1,0,1,0,1];
466 void[] v = cast(void[])a;
467
468 assert(v.length == a.dim * uint.sizeof);
469 }
470 }
471
472
473 /**
474 * Support for [$(I index)] operation for BitArray.
475 */
476 bool opIndex(size_t i)
477 in
478 {
479 assert(i < len);
480 }
481 body
482 {
483 return cast(bool)bt(ptr, i);
484 }
485
486
487 /**
488 * Support for unary operator ~ for bit arrays.
489 */
490 BitArray opCom()
491 {
492 auto dim = this.dim();
493
494 BitArray result;
495
496 result.length = len;
497 for (size_t i = 0; i < dim; i++)
498 result.ptr[i] = ~this.ptr[i];
499 if (len & 31)
500 result.ptr[dim - 1] &= ~(~0 << (len & 31));
501 return result;
502 }
503
504
505 debug( UnitTest )
506 {
507 unittest
508 {
509 BitArray a = [1,0,1,0,1];
510 BitArray b = ~a;
511
512 assert(b[0] == 0);
513 assert(b[1] == 1);
514 assert(b[2] == 0);
515 assert(b[3] == 1);
516 assert(b[4] == 0);
517 }
518 }
519
520
521 /**
522 * Support for binary operator & for bit arrays.
523 */
524 BitArray opAnd(BitArray e2)
525 in
526 {
527 assert(len == e2.length);
528 }
529 body
530 {
531 auto dim = this.dim();
532
533 BitArray result;
534
535 result.length = len;
536 for (size_t i = 0; i < dim; i++)
537 result.ptr[i] = this.ptr[i] & e2.ptr[i];
538 return result;
539 }
540
541
542 debug( UnitTest )
543 {
544 unittest
545 {
546 BitArray a = [1,0,1,0,1];
547 BitArray b = [1,0,1,1,0];
548
549 BitArray c = a & b;
550
551 assert(c[0] == 1);
552 assert(c[1] == 0);
553 assert(c[2] == 1);
554 assert(c[3] == 0);
555 assert(c[4] == 0);
556 }
557 }
558
559
560 /**
561 * Support for binary operator | for bit arrays.
562 */
563 BitArray opOr(BitArray e2)
564 in
565 {
566 assert(len == e2.length);
567 }
568 body
569 {
570 auto dim = this.dim();
571
572 BitArray result;
573
574 result.length = len;
575 for (size_t i = 0; i < dim; i++)
576 result.ptr[i] = this.ptr[i] | e2.ptr[i];
577 return result;
578 }
579
580
581 debug( UnitTest )
582 {
583 unittest
584 {
585 BitArray a = [1,0,1,0,1];
586 BitArray b = [1,0,1,1,0];
587
588 BitArray c = a | b;
589
590 assert(c[0] == 1);
591 assert(c[1] == 0);
592 assert(c[2] == 1);
593 assert(c[3] == 1);
594 assert(c[4] == 1);
595 }
596 }
597
598
599 /**
600 * Support for binary operator ^ for bit arrays.
601 */
602 BitArray opXor(BitArray e2)
603 in
604 {
605 assert(len == e2.length);
606 }
607 body
608 {
609 auto dim = this.dim();
610
611 BitArray result;
612
613 result.length = len;
614 for (size_t i = 0; i < dim; i++)
615 result.ptr[i] = this.ptr[i] ^ e2.ptr[i];
616 return result;
617 }
618
619
620 debug( UnitTest )
621 {
622 unittest
623 {
624 BitArray a = [1,0,1,0,1];
625 BitArray b = [1,0,1,1,0];
626
627 BitArray c = a ^ b;
628
629 assert(c[0] == 0);
630 assert(c[1] == 0);
631 assert(c[2] == 0);
632 assert(c[3] == 1);
633 assert(c[4] == 1);
634 }
635 }
636
637
638 /**
639 * Support for binary operator - for bit arrays.
640 *
641 * $(I a - b) for BitArrays means the same thing as $(I a &amp; ~b).
642 */
643 BitArray opSub(BitArray e2)
644 in
645 {
646 assert(len == e2.length);
647 }
648 body
649 {
650 auto dim = this.dim();
651
652 BitArray result;
653
654 result.length = len;
655 for (size_t i = 0; i < dim; i++)
656 result.ptr[i] = this.ptr[i] & ~e2.ptr[i];
657 return result;
658 }
659
660
661 debug( UnitTest )
662 {
663 unittest
664 {
665 BitArray a = [1,0,1,0,1];
666 BitArray b = [1,0,1,1,0];
667
668 BitArray c = a - b;
669
670 assert(c[0] == 0);
671 assert(c[1] == 0);
672 assert(c[2] == 0);
673 assert(c[3] == 0);
674 assert(c[4] == 1);
675 }
676 }
677
678
679 /**
680 * Support for binary operator ~ for bit arrays.
681 */
682 BitArray opCat(bool b)
683 {
684 BitArray r;
685
686 r = this.dup;
687 r.length = len + 1;
688 r[len] = b;
689 return r;
690 }
691
692
693 /** ditto */
694 BitArray opCat_r(bool b)
695 {
696 BitArray r;
697
698 r.length = len + 1;
699 r[0] = b;
700 for (size_t i = 0; i < len; i++)
701 r[1 + i] = (*this)[i];
702 return r;
703 }
704
705
706 /** ditto */
707 BitArray opCat(BitArray b)
708 {
709 BitArray r;
710
711 r = this.dup();
712 r ~= b;
713 return r;
714 }
715
716
717 debug( UnitTest )
718 {
719 unittest
720 {
721 BitArray a = [1,0];
722 BitArray b = [0,1,0];
723 BitArray c;
724
725 c = (a ~ b);
726 assert(c.length == 5);
727 assert(c[0] == 1);
728 assert(c[1] == 0);
729 assert(c[2] == 0);
730 assert(c[3] == 1);
731 assert(c[4] == 0);
732
733 c = (a ~ true);
734 assert(c.length == 3);
735 assert(c[0] == 1);
736 assert(c[1] == 0);
737 assert(c[2] == 1);
738
739 c = (false ~ a);
740 assert(c.length == 3);
741 assert(c[0] == 0);
742 assert(c[1] == 1);
743 assert(c[2] == 0);
744 }
745 }
746
747
748 /**
749 * Support for [$(I index)] operation for BitArray.
750 */
751 bool opIndexAssign(bool b, size_t i)
752 in
753 {
754 assert(i < len);
755 }
756 body
757 {
758 if (b)
759 bts(ptr, i);
760 else
761 btr(ptr, i);
762 return b;
763 }
764
765
766 /**
767 * Support for operator &= bit arrays.
768 */
769 BitArray opAndAssign(BitArray e2)
770 in
771 {
772 assert(len == e2.length);
773 }
774 body
775 {
776 auto dim = this.dim();
777
778 for (size_t i = 0; i < dim; i++)
779 ptr[i] &= e2.ptr[i];
780 return *this;
781 }
782
783
784 debug( UnitTest )
785 {
786 unittest
787 {
788 BitArray a = [1,0,1,0,1];
789 BitArray b = [1,0,1,1,0];
790
791 a &= b;
792 assert(a[0] == 1);
793 assert(a[1] == 0);
794 assert(a[2] == 1);
795 assert(a[3] == 0);
796 assert(a[4] == 0);
797 }
798 }
799
800
801 /**
802 * Support for operator |= for bit arrays.
803 */
804 BitArray opOrAssign(BitArray e2)
805 in
806 {
807 assert(len == e2.length);
808 }
809 body
810 {
811 auto dim = this.dim();
812
813 for (size_t i = 0; i < dim; i++)
814 ptr[i] |= e2.ptr[i];
815 return *this;
816 }
817
818
819 debug( UnitTest )
820 {
821 unittest
822 {
823 BitArray a = [1,0,1,0,1];
824 BitArray b = [1,0,1,1,0];
825
826 a |= b;
827 assert(a[0] == 1);
828 assert(a[1] == 0);
829 assert(a[2] == 1);
830 assert(a[3] == 1);
831 assert(a[4] == 1);
832 }
833 }
834
835
836 /**
837 * Support for operator ^= for bit arrays.
838 */
839 BitArray opXorAssign(BitArray e2)
840 in
841 {
842 assert(len == e2.length);
843 }
844 body
845 {
846 auto dim = this.dim();
847
848 for (size_t i = 0; i < dim; i++)
849 ptr[i] ^= e2.ptr[i];
850 return *this;
851 }
852
853
854 debug( UnitTest )
855 {
856 unittest
857 {
858 BitArray a = [1,0,1,0,1];
859 BitArray b = [1,0,1,1,0];
860
861 a ^= b;
862 assert(a[0] == 0);
863 assert(a[1] == 0);
864 assert(a[2] == 0);
865 assert(a[3] == 1);
866 assert(a[4] == 1);
867 }
868 }
869
870
871 /**
872 * Support for operator -= for bit arrays.
873 *
874 * $(I a -= b) for BitArrays means the same thing as $(I a &amp;= ~b).
875 */
876 BitArray opSubAssign(BitArray e2)
877 in
878 {
879 assert(len == e2.length);
880 }
881 body
882 {
883 auto dim = this.dim();
884
885 for (size_t i = 0; i < dim; i++)
886 ptr[i] &= ~e2.ptr[i];
887 return *this;
888 }
889
890
891 debug( UnitTest )
892 {
893 unittest
894 {
895 BitArray a = [1,0,1,0,1];
896 BitArray b = [1,0,1,1,0];
897
898 a -= b;
899 assert(a[0] == 0);
900 assert(a[1] == 0);
901 assert(a[2] == 0);
902 assert(a[3] == 0);
903 assert(a[4] == 1);
904 }
905 }
906
907
908 /**
909 * Support for operator ~= for bit arrays.
910 */
911 BitArray opCatAssign(bool b)
912 {
913 length = len + 1;
914 (*this)[len - 1] = b;
915 return *this;
916 }
917
918
919 debug( UnitTest )
920 {
921 unittest
922 {
923 BitArray a = [1,0,1,0,1];
924 BitArray b;
925
926 b = (a ~= true);
927 assert(a[0] == 1);
928 assert(a[1] == 0);
929 assert(a[2] == 1);
930 assert(a[3] == 0);
931 assert(a[4] == 1);
932 assert(a[5] == 1);
933
934 assert(b == a);
935 }
936 }
937
938
939 /**
940 * ditto
941 */
942 BitArray opCatAssign(BitArray b)
943 {
944 auto istart = len;
945 length = len + b.length;
946 for (auto i = istart; i < len; i++)
947 (*this)[i] = b[i - istart];
948 return *this;
949 }
950
951
952 debug( UnitTest )
953 {
954 unittest
955 {
956 BitArray a = [1,0];
957 BitArray b = [0,1,0];
958 BitArray c;
959
960 c = (a ~= b);
961 assert(a.length == 5);
962 assert(a[0] == 1);
963 assert(a[1] == 0);
964 assert(a[2] == 0);
965 assert(a[3] == 1);
966 assert(a[4] == 0);
967
968 assert(c == a);
969 }
970 }
971 }