tagion.utils.BitMask source code

1 module tagion.utils.BitMask;
2 
3 enum WORD_SIZE = size_t(size_t.sizeof * 8);
4 
5 size_t bitsize(const size_t[] mask) pure nothrow @nogc @safe {
6     return mask.length * WORD_SIZE;
7 }
8 
9 size_t wordindex(const size_t i) pure nothrow @nogc @safe {
10     return i / WORD_SIZE;
11 }
12 
13 size_t word_bitindex(const size_t i) pure nothrow @nogc @safe {
14     return i % WORD_SIZE;
15 }
16 
17 @safe
18 struct BitMask {
19     import std.algorithm;
20     import std.format;
21     import std.range;
22     import std.traits;
23 
24     enum absolute_mask = 0x1000;
25     private size_t[] mask;
26 
27     void opAssign(const BitMask rhs) pure nothrow {
28         mask = rhs.mask.dup;
29     }
30 
31     /++
32      This set the mask as bit stream with LSB first
33      +/
34     this(T)(T bitstring) if (isSomeString!T) {
35         auto bitrange = bitstring.filter!((c) => (c == '0' || c == '1')).enumerate;
36         foreach (i, c; bitrange) {
37             if (c == '1') {
38                 this[i] = true;
39             }
40         }
41     }
42 
43     this(R)(scope R range) pure nothrow if ((isInputRange!R) && is(ElementType!R : bool)) {
44         this(range.enumerate
45                 .filter!(b => b.value)
46                 .map!(b => b.index));
47     }
48 
49     this(R)(scope R range) pure nothrow if ((isInputRange!R) && isIntegral!(ElementType!R) && !is(ElementType!R : bool)) {
50         range.each!((n) => this[n] = true);
51     }
52 
53     BitMask dup() const pure nothrow {
54         BitMask result;
55         result.mask = mask.dup;
56         return result;
57     }
58 
59     void clear() pure nothrow {
60         mask[] = 0;
61     }
62 
63     @nogc
64     bool opEquals(const BitMask rhs) const pure nothrow {
65         import std.algorithm;
66 
67         if (mask == rhs.mask) {
68             return true;
69         }
70         const min_length = min(mask.length, rhs.mask.length);
71         if (mask[0 .. min_length] == rhs.mask[0 .. min_length]) {
72             return mask.all!(q{a==0}) && rhs.mask.all!(q{a==0});
73 
74         }
75         return false;
76     }
77 
78     unittest {
79         BitMask bits_a, bits_b;
80         assert(bits_a == bits_b);
81         bits_b.mask.length = 1;
82         assert(bits_a == bits_b);
83         bits_a[17] = true;
84         assert(bits_a != bits_b);
85         bits_b[17] = true;
86         assert(bits_a == bits_b);
87         bits_b[100] = true;
88         assert(bits_a != bits_b);
89         bits_a[100] = true;
90         assert(bits_a == bits_b);
91         BitMask all_null_bits;
92         all_null_bits.mask.length = 3; // long sequency of bits of value
93         assert(all_null_bits == BitMask.init);
94         assert(BitMask.init == all_null_bits);
95     }
96 
97     Range opSlice() const pure nothrow {
98         return Range(mask);
99     }
100 
101     unittest {
102         BitMask bits;
103         assert(bits[].empty);
104         bits[17] = true;
105         assert(equal(bits[], [17]));
106         bits[0] = true;
107         assert(equal(bits[], [0, 17]));
108         enum first_bit_in_the_next_word = 8 * size_t.sizeof;
109         enum last_bit_in_a_word = first_bit_in_the_next_word - 1;
110         bits[last_bit_in_a_word] = true;
111         assert(equal(bits[], [0, 17, last_bit_in_a_word]));
112         bits[first_bit_in_the_next_word] = true;
113         assert(equal(bits[], [0, 17, last_bit_in_a_word, first_bit_in_the_next_word]));
114     }
115 
116     @nogc
117     struct Range {
118         private {
119             const(size_t[]) mask;
120             size_t index;
121             size_t bit_pos;
122         }
123 
124         private this(
125                 const(size_t[]) mask,
126         size_t index,
127         size_t bit_pos) pure nothrow {
128             this.mask = mask;
129             this.index = index;
130             this.bit_pos = bit_pos;
131         }
132 
133         this(const size_t[] mask) pure nothrow {
134             this.mask = mask;
135             if (mask.length && (mask[0] & 0x1) is 0) {
136                 popFront;
137             }
138         }
139 
140         static size_t pos(size_t BIT_SIZE = WORD_SIZE)(const size_t x, const size_t index = 0) pure nothrow {
141             static if (BIT_SIZE is 1) {
142                 return (x) ? index : WORD_SIZE;
143             }
144             else {
145                 enum HALF_SIZE = BIT_SIZE >> 1;
146                 enum MASK = (size_t(1) << HALF_SIZE) - size_t(1);
147                 if (x & MASK) {
148                     return pos!HALF_SIZE(x & MASK, index);
149                 }
150                 else {
151                     return pos!HALF_SIZE(x >> HALF_SIZE, index + HALF_SIZE);
152                 }
153             }
154         }
155 
156         static unittest {
157             assert(pos(0b1) is 0);
158             assert(pos(0b10) is 1);
159             assert(pos(0b1000_0000_0000) is 11);
160             assert(pos(0) is WORD_SIZE);
161             enum small_pos = (WORD_SIZE >> 1) + 5;
162             enum larger_pos = small_pos + 7;
163             enum small_val = size_t(1) << small_pos;
164             enum larger_val = size_t(1) << larger_pos;
165             assert(pos(small_val | larger_val) is small_pos);
166         }
167 
168         pure nothrow {
169             const {
170                 size_t rest() {
171                     return (bit_pos < WORD_SIZE - 1) ? (
172                             mask[index] & ~((size_t(1) << (bit_pos + 1)) - 1)) : 0;
173                 }
174 
175                 bool empty() {
176                     return index >= mask.length;
177                 }
178 
179                 size_t front() {
180                     return index * WORD_SIZE + bit_pos;
181                 }
182             }
183             void popFront() {
184                 if (!empty) {
185                     bit_pos = pos(rest);
186                     if (bit_pos >= WORD_SIZE) {
187                         bit_pos = 0;
188                         index++;
189                         if (index < mask.length && ((mask[index] & 0x1) is 0)) {
190                             popFront;
191                         }
192                     }
193                 }
194             }
195 
196             Range save() {
197                 return Range(mask, index, bit_pos);
198             }
199         }
200     }
201 
202     bool opIndex(size_t i) const pure nothrow @nogc
203     in {
204         assert(i < absolute_mask);
205     }
206     do {
207         if (i < mask.bitsize) {
208             return (mask[i.wordindex] & (size_t(1) << i.word_bitindex)) != 0;
209         }
210         return false;
211     }
212 
213     bool opIndexAssign(const bool b, const size_t i) pure nothrow
214     in {
215         assert(i < absolute_mask);
216     }
217     do {
218         if (i >= mask.bitsize) {
219             mask.length = i.wordindex + 1;
220         }
221         if (b) {
222             mask[i.wordindex] |= size_t(1) << i.word_bitindex;
223         }
224         else {
225             mask[i.wordindex] &= ~(size_t(1) << i.word_bitindex);
226         }
227         return b;
228     }
229 
230     unittest {
231         BitMask bits;
232         assert(!bits[100]);
233         bits[100] = true;
234         assert(bits[100]);
235         bits[100] = false;
236         assert(!bits[100]);
237     }
238 
239     BitMask opUnary(string op)() const pure nothrow
240     if (op == "~") {
241         BitMask result;
242         result.mask = new size_t[mask.length];
243         result.mask[] = ~mask[];
244         return result;
245     }
246 
247     @trusted
248     unittest {
249         BitMask bits;
250         assert(~bits == BitMask.init);
251         bits.mask.length = 1;
252         const all_bits = BitMask('1'.repeat(8 * size_t.sizeof).array);
253         assert(~bits == all_bits);
254         BitMask expected = all_bits.dup;
255         expected[7] = false;
256         assert(~bits != expected);
257         bits[7] = true;
258         assert(~bits == expected);
259 
260     }
261 
262     BitMask opBinary(string op)(scope const BitMask rhs) const pure nothrow
263     if (op == "-" || op == "&" || op == "|" || op == "^") {
264         import std.algorithm.comparison : max, min;
265 
266         BitMask result;
267         result.mask = mask.dup;
268         result.opOpAssign!op(rhs);
269         return result;
270     }
271 
272     version (unittest) {
273         import std.array;
274         import std.stdio;
275         import tagion.basic.Debug;
276 
277         /// Result table
278         /// 
279     }
280 
281     unittest { // opBinary and opOpAssign
282 
283         BitMask bits_a, bits_b;
284         enum op_list = ["|", "&", "^", "-"];
285         //enum righ
286         static struct Expected {
287             BitMask Y, A, B; /// y = a OP b
288         }
289 
290         const left_one_right_none = [
291             "|": Expected(BitMask("010101"), BitMask("010101"), BitMask.init),
292             "&": Expected(BitMask("000000"), BitMask("010101"), BitMask.init),
293             "^": Expected(BitMask("010101"), BitMask("010101"), BitMask.init),
294             "-": Expected(BitMask("010101"), BitMask("010101"), BitMask.init),
295         ];
296         const left_one_right_one = [
297             "|": Expected(BitMask("010111001"), BitMask("010101001"), BitMask("0101110")),
298             "&": Expected(BitMask("010001"), BitMask("010101"), BitMask("0100010")),
299             "^": Expected(BitMask("00110001"), BitMask("000101"), BitMask("00100101")),
300             "-": Expected(BitMask("0000101"), BitMask("000010111"), BitMask("01010101111")),
301         ];
302 
303         const left_more_right_more = [
304             "|": Expected(BitMask([1, 57, 100]), BitMask([57]), BitMask([100, 1])),
305             "&": Expected(BitMask([57, 101]), BitMask([1, 57, 101, 65]), BitMask([101, 57, 22])),
306             "^": Expected(BitMask([1, 2, 57, 100]), BitMask([2, 57, 100, 65]), BitMask([1, 65])),
307             "-": Expected(BitMask([2, 100]), BitMask([2, 57, 100, 65]), BitMask([67, 57, 65])),
308         ];
309 
310         static foreach (OP; op_list) {
311             assert(bits_a.opBinary!OP(bits_b) == BitMask.init);
312             {
313                 foreach (test; only(left_one_right_none, left_one_right_one, left_more_right_more)) {
314                     const expected = test[OP];
315                     with (expected) {
316                         const result = A.opBinary!OP(B);
317                         assert(result == Y,
318                                 __format("%.16s == %.16s %s %.16s result %.16s", Y, A, OP, B, result));
319                     }
320                     with (expected) {
321                         auto result = A.dup;
322                         result.opOpAssign!OP(B);
323 
324                         assert(result == Y,
325                                 __format("%.16s == (%.16s %s= %.16s) result %.16s", Y, A, OP, B, result));
326 
327                     }
328 
329                 }
330             }
331         }
332     }
333 
334     BitMask opOpAssign(string op)(scope const BitMask rhs) pure nothrow
335     if (op == "-" || op == "&" || op == "|" || op == "^") {
336         if (mask.length > rhs.mask.length) {
337             switch (op) {
338             case "&":
339                 mask[rhs.mask.length .. $] = 0;
340                 break;
341             default:
342             }
343         }
344         else if (mask.length < rhs.mask.length) {
345             mask.length = rhs.mask.length;
346         }
347 
348         static if (op == "-") {
349             mask[0 .. rhs.mask.length] &= ~rhs.mask[0 .. rhs.mask.length];
350         }
351         else {
352             enum code = format(q{mask[0..rhs.mask.length] %s= rhs.mask[0..rhs.mask.length];}, op);
353             mixin(code);
354         }
355         return this;
356     }
357 
358     BitMask opBinary(string op, Index)(const Index index) const pure nothrow
359     if ((op == "-" || op == "+") && isIntegral!Index) {
360         BitMask result = dup;
361         result[index] = (op == "+");
362         return result;
363     }
364 
365     unittest {
366         BitMask bits;
367         assert(bits + 17 == BitMask([17]));
368         bits = BitMask([42, 17]);
369         assert(bits + 100 == BitMask([17, 100, 42]));
370         assert(bits - 17 == BitMask([42]));
371     }
372 
373     void chunk(size_t bit_len) pure nothrow {
374         const new_size = bit_len.wordindex + 1;
375         if (new_size < mask.length) {
376             mask.length = new_size;
377         }
378         const chunk_mask = ((size_t(1) << (bit_len.word_bitindex)) - 1);
379         mask[$ - 1] &= chunk_mask;
380     }
381 
382     unittest {
383         BitMask bits = BitMask([17, 42, 99, 101]);
384         bits.chunk(100);
385         assert(equal(bits[], [17, 42, 99]));
386         bits.chunk(99);
387         assert(equal(bits[], [17, 42]));
388     }
389 
390     size_t count() const pure nothrow @nogc {
391         import core.bitop : popcnt;
392 
393         return mask.map!(m => m.popcnt).sum;
394     }
395 
396     unittest {
397         BitMask bits;
398         assert(bits.count == 0);
399         bits[17] = true;
400         assert(bits.count == 1);
401         bits = ~bits;
402         assert(bits.count == WORD_SIZE - 1);
403         bits[WORD_SIZE * 3 / 2] = true;
404         assert(bits.count == WORD_SIZE);
405         bits[WORD_SIZE / 2] = false;
406         bits = ~bits;
407         assert(bits.count == WORD_SIZE + 1);
408     }
409 
410     void toString(scope void delegate(scope const(char)[]) @safe sink,
411     const FormatSpec!char fmt) const {
412         enum separator = '_';
413         import std.stdio;
414 
415         @nogc @safe struct BitRange {
416             size_t index;
417             const size_t width;
418             const(size_t[]) mask;
419             this(const BitMask bitmask, const size_t width) {
420                 mask = bitmask.mask;
421                 this.width = (width is 0) ? mask.bitsize : width;
422             }
423 
424             pure nothrow {
425                 char front() const {
426                     const word_index = index.wordindex;
427                     if (word_index < mask.length) {
428                         return (mask[word_index] & (size_t(1) << (index.word_bitindex))) ? '1' : '0';
429                     }
430                     return '0';
431                 }
432 
433                 bool empty() const {
434                     return index >= width;
435                 }
436 
437                 void popFront() {
438                     index++;
439                 }
440             }
441         }
442 
443         switch (fmt.spec) {
444         case 's':
445             auto bit_range = BitRange(this, fmt.width);
446             scope char[] str;
447             auto max_size = bit_range.width + (bit_range.width) / fmt.precision + 1;
448             str.length = max_size;
449             size_t index;
450             size_t sep_count;
451             while (!bit_range.empty) {
452                 str[index++] = bit_range.front;
453                 bit_range.popFront;
454                 if (fmt.precision !is 0 && !bit_range.empty) {
455                     sep_count++;
456                     if ((sep_count % fmt.precision) is 0) {
457                         str[index++] = separator;
458                     }
459                 }
460             }
461             sink(str[0 .. index]);
462             break;
463         default:
464             assert(0, "Unknown format specifier: %" ~ fmt.spec);
465         }
466     }
467 
468     @trusted
469     unittest {
470         {
471             auto bits = BitMask("0101_1");
472             assert(format("%16.8s", bits) == "01011000_00000000");
473             assert(format("%16.4s", bits) == "0101_1000_0000_0000");
474             assert(format("%7.3s", bits) == "010_110_0");
475         }
476 
477         {
478             BitMask bits;
479             bits[64] = true;
480             assert(format("%.16s", bits) ==
481                     "0000000000000000_0000000000000000_0000000000000000_0000000000000000_1000000000000000_0000000000000000_0000000000000000_0000000000000000");
482             bits[17] = true;
483             bits[78] = true;
484             bits[64] = false;
485             assert(format("%.16s", bits) ==
486                     "0000000000000000_0100000000000000_0000000000000000_0000000000000000_0000000000000010_0000000000000000_0000000000000000_0000000000000000");
487         }
488 
489         {
490             const a = BitMask("1000_1100_1100");
491             const b = BitMask("0010_1001_0101");
492             { // bit or
493                 const y = a | b;
494                 assert(format("%16.4s", y) == "1010_1101_1101_0000");
495                 assert(y.count is 8);
496             }
497 
498             { // bit and
499                 const y = a & b;
500                 assert(format("%16.4s", y) == "0000_1000_0100_0000");
501                 assert(y.count is 2);
502             }
503 
504             { // bit xor
505                 const y = a ^ b;
506                 assert(format("%16.4s", y) == "1010_0101_1001_0000");
507                 assert(y.count is 6);
508             }
509 
510             { // bit and not
511                 const y = a - b;
512                 assert(format("%16.4s", y) == "1000_0100_1000_0000");
513                 assert(y.count is 3);
514             }
515 
516             version (BITMASK) {
517                 BitMask null_mask;
518                 const y = a - null_mask;
519                 assert(y == a);
520             }
521 
522             {
523                 auto y = a.dup;
524                 y |= b;
525                 assert(format("%16.4s", y) == "1010_1101_1101_0000");
526                 assert(y.count is 8);
527 
528             }
529 
530             { // bit and
531                 auto y = a.dup;
532                 y &= b;
533                 assert(format("%16.4s", y) == "0000_1000_0100_0000");
534                 assert(y.count is 2);
535 
536             }
537 
538             { // bit xor
539                 auto y = a.dup;
540                 y ^= b;
541                 assert(format("%16.4s", y) == "1010_0101_1001_0000");
542                 assert(y.count is 6);
543             }
544 
545             { // bit and not
546                 auto y = a.dup;
547                 y -= b;
548                 assert(format("%16.4s", y) == "1000_0100_1000_0000");
549                 assert(y.count is 3);
550             }
551 
552             { // Not and chunk
553                 auto y = ~a;
554                 assert(format("%32.4s", y) == "0111_0011_0011_1111_1111_1111_1111_1111");
555                 y.chunk(16);
556                 assert(format("%32.4s", y) == "0111_0011_0011_1111_0000_0000_0000_0000");
557                 assert(y.count is 11);
558             }
559         }
560 
561     }
562 
563     unittest {
564         import std.algorithm : equal;
565         import std.algorithm.iteration : fold, uniq;
566         import std.algorithm.sorting : merge, sort;
567         import std.stdio;
568 
569         { // Bit assign
570             BitMask a;
571             assert(!a[42]);
572             assert(!a[17]);
573             assert(!a[0]);
574             a[42] = true;
575             assert(a[42]);
576             assert(!a[17]);
577             assert(!a[0]);
578             a[0] = true;
579             assert(a[42]);
580             assert(!a[17]);
581             assert(a[0]);
582             a[17] = true;
583             assert(a[42]);
584             assert(a[17]);
585             assert(a[0]);
586 
587         }
588 
589         { // Range
590             const bit_list = [17, 52, 53, 54, 75, 28, 101];
591             { // Empty Range
592                 BitMask a;
593                 assert(a[].empty);
594                 size_t[] a_empty;
595                 assert(equal(a[], a_empty));
596             }
597 
598             { // First element
599                 BitMask a;
600                 a[0] = true;
601                 auto range = a[];
602                 assert(range.front is 0);
603                 assert(!range.empty);
604                 range.popFront;
605                 assert(range.empty);
606                 assert(equal(a[], [0]));
607             }
608 
609             { // One element
610                 BitMask a;
611                 a[2] = true;
612                 assert(equal(a[], [2]));
613             }
614 
615             { // One element at the end of a word
616                 BitMask a;
617                 a[63] = true;
618                 assert(equal(a[], [63]));
619             }
620 
621             { // One element at the begin of the next word
622                 BitMask a;
623                 a[64] = true;
624                 assert(equal(a[], [64]));
625             }
626 
627             { //  elements at the end and begin of a word
628                 BitMask a;
629                 a[63] = true;
630                 a[64] = true;
631                 assert(equal(a[], [63, 64]));
632             }
633 
634             { // Simple range test
635                 auto a = BitMask(bit_list);
636                 assert(equal(a[], bit_list.dup.sort));
637             }
638         }
639 
640         void and_filter(ref BitMask result, Range a, Range b) @safe {
641             if (a.front < b.front) {
642                 a.popFront;
643             }
644             else if (a.front > b.front) {
645                 b.popFront;
646             }
647             else {
648                 if (a.empty) {
649                     return;
650                 }
651                 result[b.front] = true;
652                 a.popFront;
653                 b.popFront;
654             }
655             and_filter(result, a, b);
656         }
657 
658         void xor_filter(ref BitMask result, Range a, Range b) @safe {
659             if (a.front < b.front) {
660                 result[a.front] = true;
661                 a.popFront;
662             }
663             else if (a.front > b.front) {
664                 result[b.front] = true;
665                 b.popFront;
666             }
667             else {
668                 if (a.empty) {
669                     return;
670                 }
671                 //result[b.front]=true;
672                 a.popFront;
673                 b.popFront;
674             }
675             and_filter(result, a, b);
676         }
677 
678         { // Check BitMask with mask.length > 1
679             const a_list = [17, 52, 53, 54, 75, 28, 101];
680             const a = BitMask(a_list);
681             const b_list = [17, 52, 54, 76, 28, 101, 102, 103];
682             const b = BitMask(b_list);
683 
684             { // Or
685                 const y = a | b;
686                 auto y_list = (a_list ~ b_list).dup.sort.uniq; //uniq;//.dup.sort;
687                 assert(equal(y[], y_list));
688                 assert(y.count is 10);
689             }
690 
691             { // And
692                 const y = a & b;
693                 BitMask result;
694                 and_filter(result, a[], b[]);
695                 assert(result == y);
696                 assert(y.count is 5);
697             }
698 
699             { // Xor
700                 const y = a ^ b;
701                 const result = ~a & b | a & ~b;
702                 assert(result == y);
703                 assert(y.count is 5);
704             }
705 
706             { // and not
707                 const y = a - b;
708                 const result = a & ~b;
709                 assert(result == y);
710                 assert(y.count is 2);
711             }
712 
713             { // Empty Or=
714                 BitMask y;
715                 y |= a;
716                 assert(y == a);
717                 assert(a.count is y.count);
718             }
719 
720             { // Or
721                 auto y = a.dup;
722                 y |= b;
723                 auto y_list = (a_list ~ b_list).dup.sort.uniq;
724                 assert(equal(y[], y_list));
725                 assert(y.count is 10);
726             }
727 
728             { // And
729                 auto y = a.dup;
730                 y &= b;
731                 BitMask result;
732                 and_filter(result, a[], b[]);
733                 assert(result == y);
734                 assert(y.count is 5);
735             }
736 
737             { // Xor
738                 auto y = a.dup;
739                 y ^= b;
740                 //const y= a ^ b;
741                 const result = ~a & b | a & ~b;
742                 assert(result == y);
743                 assert(y.count is 5);
744             }
745 
746             { // and not
747                 auto y = a.dup;
748                 y -= b;
749 
750                 //const y= a - b;
751                 const result = a & ~b;
752                 assert(result == y);
753                 assert(y.count is 2);
754             }
755         }
756 
757         { // Duplicate on assign
758             BitMask z;
759             auto y = z;
760             z[3] = true;
761             assert(equal(z[], [3]));
762             assert(y[].empty);
763             y = z;
764             z[5] = true;
765             assert(equal(z[], [3, 5]));
766             assert(equal(y[], [3]));
767         }
768 
769     }
770 }