BitArray

allOne bool allOne(): Check if this has only ones.
allZero bool allZero(): Check if this has only zeros.
capacity size_t capacity(): Get capacity in number of bits.
countOnes size_t countOnes(): Get number of bits set (to one).
countZeros size_t countZeros(): Get number of bits cleared (to zero).
dup typeof(this) dup(): Explicit copying (duplicate).
empty bool empty(): Check if empty.
indexOfFirstOne size_t indexOfFirstOne(): Find index of first set (one) bit or length if no bit set.
indexOfFirstZero size_t indexOfFirstZero(): Find index of first cleared (zero) bit or length if no bit cleared.
length size_t length(): Get length.
opEquals bool opEquals(typeof(this) rhs): Equality, operators == and !=.
opIndex bool opIndex(size_t i): Get the i'th bit.
opIndexAssign bool opIndexAssign(bool value, size_t i): Set the i'th bit to value.
opSliceAssign typeof(this) opSliceAssign(bool value): Set all bits to value via slice assignment syntax.
reset void reset(): Empty.

Static functions

withLength typeof(this) withLength(size_t length): Construct with length number of zero bits.

Examples

Test _blockCount and _fullBlocks.length.

1 static void test(bool blockAlignedLength)()
2 {
3     alias BA = BitArray!(blockAlignedLength);
4 
5     assert(BA.withLength(0)._blockCount == 0);
6     assert(BA.withLength(1)._blockCount == 1);
7 
8     {
9         auto a = BA.withLength(1*BA.bitsPerBlock - 1);
10         assert(a._blockCount == 1);
11         assert(a._fullBlocks.length == 0);
12     }
13 
14     {
15         auto a = BA.withLength(1*BA.bitsPerBlock + 0);
16         assert(a._blockCount == 1);
17         assert(a._fullBlocks.length == 1);
18     }
19 
20     {
21         auto a = BA.withLength(1*BA.bitsPerBlock + 1);
22         assert(a._blockCount == 2);
23         assert(a._fullBlocks.length == 1);
24     }
25 
26     {
27         auto a = BA.withLength(2*BA.bitsPerBlock - 1);
28         assert(a._blockCount == 2);
29         assert(a._fullBlocks.length == 1);
30     }
31 
32     {
33         auto a = BA.withLength(2*BA.bitsPerBlock + 0);
34         assert(a._blockCount == 2);
35         assert(a._fullBlocks.length == 2);
36     }
37 
38     {
39         auto a = BA.withLength(2*BA.bitsPerBlock + 1);
40         assert(a._blockCount == 3);
41         assert(a._fullBlocks.length == 2);
42     }
43 }
44 test!(false)();

Test indexing and element assignment.

1 static void test(bool blockAlignedLength)(size_t length)
2 {
3     alias BA = BitArray!(blockAlignedLength);
4 
5     auto a = BA.withLength(length);
6 
7     assert(a.length == length);
8     foreach (const i; 0 .. length)
9     {
10         assert(!a[i]);
11     }
12 
13     a[0] = true;
14     assert(a[0]);
15     foreach (const i; 1 .. length)
16     {
17         assert(!a[i]);
18     }
19 
20     assert(!a[1]);
21     a[1] = true;
22     assert(a[1]);
23     a[1] = false;
24     assert(!a[1]);
25 }
26 test!(false)(100);
27 test!(true)(64);

Test countOnes and countZeros.

1 static void test(bool blockAlignedLength)()
2 {
3     alias BA = BitArray!(blockAlignedLength);
4 
5     foreach (const n; 1 .. 5*BA.bitsPerBlock)
6     {
7         static if (blockAlignedLength)
8         {
9             if (n % BA.bitsPerBlock != 0) // if block aligned length
10             {
11                 continue;
12             }
13         }
14 
15         auto a = BA.withLength(n);
16 
17         // set bits forwards
18         foreach (const i; 0 .. n)
19         {
20             assert(a.countOnes == i);
21             assert(a.countZeros == n - i);
22             a[i] = true;
23             assert(a.countOnes == i + 1);
24             assert(a.countZeros == n - (i + 1));
25         }
26 
27         assert(a.countOnes == n);
28         assert(a.countZeros == 0);
29 
30         auto b = a.dup;
31         assert(b.countOnes == n);
32         assert(b.countZeros == 0);
33 
34         assert(a == b);
35 
36         // clear `a` bits forwards
37         foreach (const i; 0 .. n)
38         {
39             assert(a.countOnes == n - i);
40             assert(a.countZeros == i);
41             a[i] = false;
42             assert(a.countOnes == n - (i + 1));
43             assert(a.countZeros == i + 1);
44         }
45 
46         b[] = false;
47         assert(a == b);
48 
49         // set bits backwards
50         foreach (const i; 0 .. n)
51         {
52             assert(a.countOnes == i);
53             a[n-1 - i] = true;
54             assert(a.countOnes == i + 1);
55         }
56 
57         b[] = true;
58         assert(a == b);
59     }
60 }
61 test!(false)();
62 test!(true)();

Test emptying (resetting) via .clear and explicit copying with .dup.

1 static void test(bool blockAlignedLength)()
2 {
3     alias BA = BitArray!(blockAlignedLength);
4 
5     static if (blockAlignedLength)
6     {
7         const n = 5 * BA.bitsPerBlock;
8     }
9     else
10     {
11         const n = 5 * BA.bitsPerBlock + 1;
12     }
13     auto a = BA.withLength(n);
14 
15     assert(a.length == n);
16 
17     a.reset();
18     assert(a.length == 0);
19 
20     a = BA.withLength(n);
21     assert(a.length == n);
22 
23     auto b = a.dup;
24     assert(b.length == n);
25 
26     a.reset();
27     assert(a.length == 0);
28 }
29 test!(false)();
30 test!(true)();

Test indexOfFirstOne for single set ones.

1 static void test(bool blockAlignedLength)()
2 {
3     alias BA = BitArray!(blockAlignedLength);
4 
5     static if (blockAlignedLength)
6     {
7         const n = 2 * BA.bitsPerBlock;
8     }
9     else
10     {
11         const n = 2 * BA.bitsPerBlock + 1;
12     }
13     auto a = BA.withLength(n);
14 
15     assert(a.length == n);
16     assert(a.indexOfFirstOne == n); // miss
17 
18     a[0] = true;
19     assert(a.indexOfFirstOne == 0);
20     a[] = false;
21 
22     a[2] = true;
23     assert(a.indexOfFirstOne == 2);
24     a[] = false;
25 
26     a[n/2-1] = true;
27     assert(a.indexOfFirstOne == n/2-1);
28     a[] = false;
29 
30     a[n/2] = true;
31     assert(a.indexOfFirstOne == n/2);
32     a[] = false;
33 
34     a[n/2+1] = true;
35     assert(a.indexOfFirstOne == n/2+1);
36     a[] = false;
37 
38     a[n-1] = true;
39     assert(a.indexOfFirstOne == n-1);
40     a[] = false;
41 
42     assert(a.indexOfFirstOne == n); // miss
43 }
44 test!(false)();
45 test!(true)();

Test indexOfFirstOne for multi set ones.

1 static void test(bool blockAlignedLength)()
2 {
3     alias BA = BitArray!(blockAlignedLength);
4 
5     static if (blockAlignedLength)
6     {
7         const n = 2 * BA.bitsPerBlock;
8     }
9     else
10     {
11         const n = 2 * BA.bitsPerBlock + 1;
12     }
13     auto a = BA.withLength(n);
14 
15     a[0] = true;
16     a[BA.bitsPerBlock/2] = true;
17     a[BA.bitsPerBlock - 1] = true;
18     assert(a.indexOfFirstOne == 0);
19 }
20 test!(false)();
21 test!(true)();

Test indexOfFirstZero for single set zeros.

1 static void test(bool blockAlignedLength)()
2 {
3     alias BA = BitArray!(blockAlignedLength);
4 
5     static if (blockAlignedLength)
6     {
7         const n = 2 * BA.bitsPerBlock;
8     }
9     else
10     {
11         const n = 2 * BA.bitsPerBlock + 1;
12     }
13     auto a = BA.withLength(n);
14 
15     a[] = true;
16 
17     assert(a.length == n);
18     assert(a.indexOfFirstZero == n); // miss
19 
20     a[0] = false;
21     assert(a.indexOfFirstZero == 0);
22     a[0] = true;
23 
24     a[2] = false;
25     assert(a.indexOfFirstZero == 2);
26     a[2] = true;
27 
28     a[n/2-1] = false;
29     assert(a.indexOfFirstZero == n/2-1);
30     a[n/2-1] = true;
31 
32     a[n/2] = false;
33     assert(a.indexOfFirstZero == n/2);
34     a[n/2] = true;
35 
36     a[n/2+1] = false;
37     assert(a.indexOfFirstZero == n/2+1);
38     a[n/2+1] = true;
39 
40     a[n-1] = false;
41     assert(a.indexOfFirstZero == n-1);
42     a[n-1] = true;
43 
44     assert(a.indexOfFirstZero == n); // miss
45 }
46 test!(false)();
47 test!(true)();

Test indexOfFirstZero for multi set zeros.

1 static void test(bool blockAlignedLength)()
2 {
3     alias BA = BitArray!(blockAlignedLength);
4 
5     static if (blockAlignedLength)
6     {
7         const n = 2 * BA.bitsPerBlock;
8     }
9     else
10     {
11         const n = 2 * BA.bitsPerBlock + 1;
12     }
13     auto a = BA.withLength(n);
14 
15     a[] = true;
16 
17     a[0] = false;
18     a[BA.bitsPerBlock/2] = false;
19     a[BA.bitsPerBlock - 1] = false;
20     assert(a.indexOfFirstZero == 0);
21 }
22 test!(false)();
23 test!(true)();

Test indexOfFirstOne for multi set ones.

1 static void test(bool blockAlignedLength)()
2 {
3     alias BA = BitArray!(blockAlignedLength);
4 
5     static if (blockAlignedLength)
6     {
7         const n = 2 * BA.bitsPerBlock;
8     }
9     else
10     {
11         const n = 2 * BA.bitsPerBlock + 1;
12     }
13     auto a = BA.withLength(n);
14 
15     a[] = false;
16 
17     a[0] = true;
18     a[BA.bitsPerBlock/2] = true;
19     a[BA.bitsPerBlock - 1] = true;
20     assert(a.indexOfFirstOne == 0);
21 }
22 test!(false)();
23 test!(true)();

Test casting to bool.

1 static void test(bool blockAlignedLength)()
2 {
3     alias BA = BitArray!(blockAlignedLength);
4 
5     static if (blockAlignedLength)
6     {
7         const n = 2 * BA.bitsPerBlock;
8     }
9     else
10     {
11         const n = 2 * BA.bitsPerBlock + 1;
12     }
13     auto a = BA.withLength(n);
14 
15     assert(a.allZero);
16 
17     a[0] = true;
18     assert(!a.allZero);
19     a[0] = false;
20     assert(a.allZero);
21 }
22 test!(false)();

import std.exception: assertThrown;
import core.exception : AssertError;
assertThrown!AssertError(BitArray!(true).withLength(1));

BitArray

Destructor

Postblit

Members

Functions

Static functions

Examples

Meta

Source