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