Mercurial > projects > ldc

comparison lphobos/std/bitarray.d @ 473:373489eeaf90

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Applied downs' lphobos update
author Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
date Mon, 04 Aug 2008 19:28:49 +0200
parents
children
comparison
equal deleted inserted replaced
472:15c804b6ce77 473:373489eeaf90
1 /***********************
2 * Macros:
3 * WIKI = StdBitarray
4 */
5
6 module std.bitarray;
7
8 //debug = bitarray; // uncomment to turn on debugging printf's
9
10 private import std.intrinsic;
11
12 /**
13 * An array of bits.
14 */
15
16 struct BitArray
17 {
18 size_t len;
19 uint* ptr;
20
21 size_t dim()
22 {
23 return (len + 31) / 32;
24 }
25
26 size_t length()
27 {
28 return len;
29 }
30
31 void length(size_t newlen)
32 {
33 if (newlen != len)
34 {
35 size_t olddim = dim();
36 size_t newdim = (newlen + 31) / 32;
37
38 if (newdim != olddim)
39 {
40 // Create a fake array so we can use D's realloc machinery
41 uint[] b = ptr[0 .. olddim];
42 b.length = newdim; // realloc
43 ptr = b.ptr;
44 if (newdim & 31)
45 { // Set any pad bits to 0
46 ptr[newdim - 1] &= ~(~0 << (newdim & 31));
47 }
48 }
49
50 len = newlen;
51 }
52 }
53
54 /**********************************************
55 * Support for [$(I index)] operation for BitArray.
56 */
57 bool opIndex(size_t i)
58 in
59 {
60 assert(i < len);
61 }
62 body
63 {
64 return cast(bool)bt(ptr, i);
65 }
66
67 /** ditto */
68 bool opIndexAssign(bool b, size_t i)
69 in
70 {
71 assert(i < len);
72 }
73 body
74 {
75 if (b)
76 bts(ptr, i);
77 else
78 btr(ptr, i);
79 return b;
80 }
81
82 /**********************************************
83 * Support for array.dup property for BitArray.
84 */
85 BitArray dup()
86 {
87 BitArray ba;
88
89 uint[] b = ptr[0 .. dim].dup;
90 ba.len = len;
91 ba.ptr = b.ptr;
92 return ba;
93 }
94
95 unittest
96 {
97 BitArray a;
98 BitArray b;
99 int i;
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 (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(inout 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(inout size_t, inout 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 body
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 body
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 static uint x = 0b1100011000;
276 static 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 int opEquals(BitArray a2)
290 { size_t i;
291
292 if (this.length != a2.length)
293 return 0; // not equal
294 uint *p1 = cast(uint*)this.ptr;
295 uint *p2 = cast(uint*)a2.ptr;
296 size_t n = this.length / (8 * uint.sizeof);
297 for (i = 0; i < n; i++)
298 {
299 if (p1[i] != p2[i])
300 return 0; // not equal
301 }
302
303 uint mask;
304
305 n = this.length & ((8 * uint.sizeof) - 1);
306 mask = (1 << n) - 1;
307 //printf("i = %d, n = %d, mask = %x, %x, %x\n", i, n, mask, p1[i], p2[i]);
308 return (mask == 0) || (p1[i] & mask) == (p2[i] & mask);
309 }
310
311 unittest
312 {
313 debug(bitarray) printf("BitArray.opEquals unittest\n");
314
315 static bool[] ba = [1,0,1,0,1];
316 static bool[] bb = [1,0,1];
317 static bool[] bc = [1,0,1,0,1,0,1];
318 static bool[] bd = [1,0,1,1,1];
319 static bool[] be = [1,0,1,0,1];
320
321 BitArray a; a.init(ba);
322 BitArray b; b.init(bb);
323 BitArray c; c.init(bc);
324 BitArray d; d.init(bd);
325 BitArray e; e.init(be);
326
327 assert(a != b);
328 assert(a != c);
329 assert(a != d);
330 assert(a == e);
331 }
332
333 /***************************************
334 * Implement comparison operators.
335 */
336
337 int opCmp(BitArray a2)
338 {
339 size_t len;
340 size_t i;
341
342 len = this.length;
343 if (a2.length < len)
344 len = a2.length;
345 uint* p1 = cast(uint*)this.ptr;
346 uint* p2 = cast(uint*)a2.ptr;
347 size_t n = len / (8 * uint.sizeof);
348 for (i = 0; i < n; i++)
349 {
350 if (p1[i] != p2[i])
351 break; // not equal
352 }
353 /*
354 for (uint j = i * 8; j < len; j++)
355 { ubyte mask = cast(ubyte)(1 << j);
356 int c;
357
358 c = cast(int)(p1[i] & mask) - cast(int)(p2[i] & mask);
359 if (c)
360 return c;
361 }
362 */
363 uint mask = 1;
364 for (size_t j = i * (8 * uint.sizeof); j < len; j++)
365 { int c;
366
367 c = cast(int)(p1[i] & mask) - cast(int)(p2[i] & mask);
368 if (c)
369 return c;
370 mask <<= 1;
371 }
372 ptrdiff_t c = cast(ptrdiff_t)this.len - cast(ptrdiff_t)a2.length;
373 if (c < 0)
374 return -1;
375 else if (c > 0)
376 return 1;
377 return 0;
378 }
379
380 unittest
381 {
382 debug(bitarray) printf("BitArray.opCmp unittest\n");
383
384 static bool[] ba = [1,0,1,0,1];
385 static bool[] bb = [1,0,1];
386 static bool[] bc = [1,0,1,0,1,0,1];
387 static bool[] bd = [1,0,1,1,1];
388 static bool[] be = [1,0,1,0,1];
389
390 BitArray a; a.init(ba);
391 BitArray b; b.init(bb);
392 BitArray c; c.init(bc);
393 BitArray d; d.init(bd);
394 BitArray e; e.init(be);
395
396 assert(a > b);
397 assert(a >= b);
398 assert(a < c);
399 assert(a <= c);
400 assert(a < d);
401 assert(a <= d);
402 assert(a == e);
403 assert(a <= e);
404 assert(a >= e);
405 }
406
407 /***************************************
408 * Set BitArray to contents of ba[]
409 */
410
411 void init(bool[] ba)
412 {
413 length = ba.length;
414 foreach (i, b; ba)
415 {
416 (*this)[i] = b;
417 }
418 }
419
420
421 /***************************************
422 * Map BitArray onto v[], with numbits being the number of bits
423 * in the array. Does not copy the data.
424 *
425 * This is the inverse of opCast.
426 */
427 void init(void[] v, size_t numbits)
428 in
429 {
430 assert(numbits <= v.length * 8);
431 assert((v.length & 3) == 0);
432 }
433 body
434 {
435 ptr = cast(uint*)v.ptr;
436 len = numbits;
437 }
438
439 unittest
440 {
441 debug(bitarray) printf("BitArray.init unittest\n");
442
443 static bool[] ba = [1,0,1,0,1];
444
445 BitArray a; a.init(ba);
446 BitArray b;
447 void[] v;
448
449 v = cast(void[])a;
450 b.init(v, a.length);
451
452 assert(b[0] == 1);
453 assert(b[1] == 0);
454 assert(b[2] == 1);
455 assert(b[3] == 0);
456 assert(b[4] == 1);
457
458 a[0] = 0;
459 assert(b[0] == 0);
460
461 assert(a == b);
462 }
463
464 /***************************************
465 * Convert to void[].
466 */
467 void[] opCast()
468 {
469 return cast(void[])ptr[0 .. dim];
470 }
471
472 unittest
473 {
474 debug(bitarray) printf("BitArray.opCast unittest\n");
475
476 static bool[] ba = [1,0,1,0,1];
477
478 BitArray a; a.init(ba);
479 void[] v = cast(void[])a;
480
481 assert(v.length == a.dim * uint.sizeof);
482 }
483
484 /***************************************
485 * Support for unary operator ~ for bit arrays.
486 */
487 BitArray opCom()
488 {
489 auto dim = this.dim();
490
491 BitArray result;
492
493 result.length = len;
494 for (size_t i = 0; i < dim; i++)
495 result.ptr[i] = ~this.ptr[i];
496 if (len & 31)
497 result.ptr[dim - 1] &= ~(~0 << (len & 31));
498 return result;
499 }
500
501 unittest
502 {
503 debug(bitarray) printf("BitArray.opCom unittest\n");
504
505 static bool[] ba = [1,0,1,0,1];
506
507 BitArray a; a.init(ba);
508 BitArray b = ~a;
509
510 assert(b[0] == 0);
511 assert(b[1] == 1);
512 assert(b[2] == 0);
513 assert(b[3] == 1);
514 assert(b[4] == 0);
515 }
516
517
518 /***************************************
519 * Support for binary operator & for bit arrays.
520 */
521 BitArray opAnd(BitArray e2)
522 in
523 {
524 assert(len == e2.length);
525 }
526 body
527 {
528 auto dim = this.dim();
529
530 BitArray result;
531
532 result.length = len;
533 for (size_t i = 0; i < dim; i++)
534 result.ptr[i] = this.ptr[i] & e2.ptr[i];
535 return result;
536 }
537
538 unittest
539 {
540 debug(bitarray) printf("BitArray.opAnd unittest\n");
541
542 static bool[] ba = [1,0,1,0,1];
543 static bool[] bb = [1,0,1,1,0];
544
545 BitArray a; a.init(ba);
546 BitArray b; b.init(bb);
547
548 BitArray c = a & b;
549
550 assert(c[0] == 1);
551 assert(c[1] == 0);
552 assert(c[2] == 1);
553 assert(c[3] == 0);
554 assert(c[4] == 0);
555 }
556
557
558 /***************************************
559 * Support for binary operator | for bit arrays.
560 */
561 BitArray opOr(BitArray e2)
562 in
563 {
564 assert(len == e2.length);
565 }
566 body
567 {
568 auto dim = this.dim();
569
570 BitArray result;
571
572 result.length = len;
573 for (size_t i = 0; i < dim; i++)
574 result.ptr[i] = this.ptr[i] | e2.ptr[i];
575 return result;
576 }
577
578 unittest
579 {
580 debug(bitarray) printf("BitArray.opOr unittest\n");
581
582 static bool[] ba = [1,0,1,0,1];
583 static bool[] bb = [1,0,1,1,0];
584
585 BitArray a; a.init(ba);
586 BitArray b; b.init(bb);
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 * Support for binary operator ^ for bit arrays.
600 */
601 BitArray opXor(BitArray e2)
602 in
603 {
604 assert(len == e2.length);
605 }
606 body
607 {
608 auto dim = this.dim();
609
610 BitArray result;
611
612 result.length = len;
613 for (size_t i = 0; i < dim; i++)
614 result.ptr[i] = this.ptr[i] ^ e2.ptr[i];
615 return result;
616 }
617
618 unittest
619 {
620 debug(bitarray) printf("BitArray.opXor unittest\n");
621
622 static bool[] ba = [1,0,1,0,1];
623 static bool[] bb = [1,0,1,1,0];
624
625 BitArray a; a.init(ba);
626 BitArray b; b.init(bb);
627
628 BitArray c = a ^ b;
629
630 assert(c[0] == 0);
631 assert(c[1] == 0);
632 assert(c[2] == 0);
633 assert(c[3] == 1);
634 assert(c[4] == 1);
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 unittest
661 {
662 debug(bitarray) printf("BitArray.opSub unittest\n");
663
664 static bool[] ba = [1,0,1,0,1];
665 static bool[] bb = [1,0,1,1,0];
666
667 BitArray a; a.init(ba);
668 BitArray b; b.init(bb);
669
670 BitArray c = a - b;
671
672 assert(c[0] == 0);
673 assert(c[1] == 0);
674 assert(c[2] == 0);
675 assert(c[3] == 0);
676 assert(c[4] == 1);
677 }
678
679
680 /***************************************
681 * Support for operator &= bit arrays.
682 */
683 BitArray opAndAssign(BitArray e2)
684 in
685 {
686 assert(len == e2.length);
687 }
688 body
689 {
690 auto dim = this.dim();
691
692 for (size_t i = 0; i < dim; i++)
693 ptr[i] &= e2.ptr[i];
694 return *this;
695 }
696
697 unittest
698 {
699 debug(bitarray) printf("BitArray.opAndAssign unittest\n");
700
701 static bool[] ba = [1,0,1,0,1];
702 static bool[] bb = [1,0,1,1,0];
703
704 BitArray a; a.init(ba);
705 BitArray b; b.init(bb);
706
707 a &= b;
708 assert(a[0] == 1);
709 assert(a[1] == 0);
710 assert(a[2] == 1);
711 assert(a[3] == 0);
712 assert(a[4] == 0);
713 }
714
715
716 /***************************************
717 * Support for operator |= for bit arrays.
718 */
719 BitArray opOrAssign(BitArray e2)
720 in
721 {
722 assert(len == e2.length);
723 }
724 body
725 {
726 auto dim = this.dim();
727
728 for (size_t i = 0; i < dim; i++)
729 ptr[i] |= e2.ptr[i];
730 return *this;
731 }
732
733 unittest
734 {
735 debug(bitarray) printf("BitArray.opOrAssign unittest\n");
736
737 static bool[] ba = [1,0,1,0,1];
738 static bool[] bb = [1,0,1,1,0];
739
740 BitArray a; a.init(ba);
741 BitArray b; b.init(bb);
742
743 a |= b;
744 assert(a[0] == 1);
745 assert(a[1] == 0);
746 assert(a[2] == 1);
747 assert(a[3] == 1);
748 assert(a[4] == 1);
749 }
750
751 /***************************************
752 * Support for operator ^= for bit arrays.
753 */
754 BitArray opXorAssign(BitArray e2)
755 in
756 {
757 assert(len == e2.length);
758 }
759 body
760 {
761 auto dim = this.dim();
762
763 for (size_t i = 0; i < dim; i++)
764 ptr[i] ^= e2.ptr[i];
765 return *this;
766 }
767
768 unittest
769 {
770 debug(bitarray) printf("BitArray.opXorAssign unittest\n");
771
772 static bool[] ba = [1,0,1,0,1];
773 static bool[] bb = [1,0,1,1,0];
774
775 BitArray a; a.init(ba);
776 BitArray b; b.init(bb);
777
778 a ^= b;
779 assert(a[0] == 0);
780 assert(a[1] == 0);
781 assert(a[2] == 0);
782 assert(a[3] == 1);
783 assert(a[4] == 1);
784 }
785
786 /***************************************
787 * Support for operator -= for bit arrays.
788 *
789 * $(I a -= b) for BitArrays means the same thing as $(I a &amp;= ~b).
790 */
791 BitArray opSubAssign(BitArray e2)
792 in
793 {
794 assert(len == e2.length);
795 }
796 body
797 {
798 auto dim = this.dim();
799
800 for (size_t i = 0; i < dim; i++)
801 ptr[i] &= ~e2.ptr[i];
802 return *this;
803 }
804
805 unittest
806 {
807 debug(bitarray) printf("BitArray.opSubAssign unittest\n");
808
809 static bool[] ba = [1,0,1,0,1];
810 static bool[] bb = [1,0,1,1,0];
811
812 BitArray a; a.init(ba);
813 BitArray b; b.init(bb);
814
815 a -= b;
816 assert(a[0] == 0);
817 assert(a[1] == 0);
818 assert(a[2] == 0);
819 assert(a[3] == 0);
820 assert(a[4] == 1);
821 }
822
823 /***************************************
824 * Support for operator ~= for bit arrays.
825 */
826
827 BitArray opCatAssign(bool b)
828 {
829 length = len + 1;
830 (*this)[len - 1] = b;
831 return *this;
832 }
833
834 unittest
835 {
836 debug(bitarray) printf("BitArray.opCatAssign unittest\n");
837
838 static bool[] ba = [1,0,1,0,1];
839
840 BitArray a; a.init(ba);
841 BitArray b;
842
843 b = (a ~= true);
844 assert(a[0] == 1);
845 assert(a[1] == 0);
846 assert(a[2] == 1);
847 assert(a[3] == 0);
848 assert(a[4] == 1);
849 assert(a[5] == 1);
850
851 assert(b == a);
852 }
853
854 /***************************************
855 * ditto
856 */
857
858 BitArray opCatAssign(BitArray b)
859 {
860 auto istart = len;
861 length = len + b.length;
862 for (auto i = istart; i < len; i++)
863 (*this)[i] = b[i - istart];
864 return *this;
865 }
866
867 unittest
868 {
869 debug(bitarray) printf("BitArray.opCatAssign unittest\n");
870
871 static bool[] ba = [1,0];
872 static bool[] bb = [0,1,0];
873
874 BitArray a; a.init(ba);
875 BitArray b; b.init(bb);
876 BitArray c;
877
878 c = (a ~= b);
879 assert(a.length == 5);
880 assert(a[0] == 1);
881 assert(a[1] == 0);
882 assert(a[2] == 0);
883 assert(a[3] == 1);
884 assert(a[4] == 0);
885
886 assert(c == a);
887 }
888
889 /***************************************
890 * Support for binary operator ~ for bit arrays.
891 */
892 BitArray opCat(bool b)
893 {
894 BitArray r;
895
896 r = this.dup;
897 r.length = len + 1;
898 r[len] = b;
899 return r;
900 }
901
902 /** ditto */
903 BitArray opCat_r(bool b)
904 {
905 BitArray r;
906
907 r.length = len + 1;
908 r[0] = b;
909 for (size_t i = 0; i < len; i++)
910 r[1 + i] = (*this)[i];
911 return r;
912 }
913
914 /** ditto */
915 BitArray opCat(BitArray b)
916 {
917 BitArray r;
918
919 r = this.dup();
920 r ~= b;
921 return r;
922 }
923
924 unittest
925 {
926 debug(bitarray) printf("BitArray.opCat unittest\n");
927
928 static bool[] ba = [1,0];
929 static bool[] bb = [0,1,0];
930
931 BitArray a; a.init(ba);
932 BitArray b; b.init(bb);
933 BitArray c;
934
935 c = (a ~ b);
936 assert(c.length == 5);
937 assert(c[0] == 1);
938 assert(c[1] == 0);
939 assert(c[2] == 0);
940 assert(c[3] == 1);
941 assert(c[4] == 0);
942
943 c = (a ~ true);
944 assert(c.length == 3);
945 assert(c[0] == 1);
946 assert(c[1] == 0);
947 assert(c[2] == 1);
948
949 c = (false ~ a);
950 assert(c.length == 3);
951 assert(c[0] == 0);
952 assert(c[1] == 1);
953 assert(c[2] == 0);
954 }
955 }