StaticBitArray

allOne bool allOne(): Check if this has only ones.
allZero bool allZero(): Check if this has only zeros (is empty).
at bool at(): Get the i'th bit.
canFindIndexOf bool canFindIndexOf(bool value, Mod!(capacity, ModUInt) currIx, Mod!(capacity, ModUInt) nextIx): Find index (starting at currIx) of first bit that equals value.
countOnes Mod!(capacity + 1) countOnes(): Get number of bits set.
countZeros size_t countZeros(): Get number of (zero) bits unset.
denseness auto denseness(int depth): Get number of bits set divided by length.
dup typeof(this) dup(): Duplicate.
indexOfFirstOne size_t indexOfFirstOne(): Find index of first set (one) bit or typeof(return).max if no bit set.
indexOfFirstZero size_t indexOfFirstZero(): Find index of first cleared (zero) bit or typeof(return).max if no bit set.
oneIndexes auto oneIndexes()
opApply int opApply(int delegate(ref bool) dg)
int opApply(int delegate(bool) dg)
int opApply(int delegate(const ref size_t, ref bool) dg)
int opApply(int delegate(size_t, bool) dg): Support for foreach loops for StaticBitArray.
opBinary typeof(this) opBinary(typeof(this) e2): Support for binary operator & for StaticBitArray.
opBinary typeof(this) opBinary(typeof(this) e2): Support for binary operator | for StaticBitArray.
opBinary typeof(this) opBinary(typeof(this) e2): Support for binary operator ^ for StaticBitArray.
opBinary typeof(this) opBinary(typeof(this) e2): Support for binary operator - for StaticBitArray.
opCast void[] opCast(): Convert to void[].
opCast size_t[] opCast(): Convert to size_t[].
opCmp int opCmp(StaticBitArray!(capacity, Block2) a2): Supports comparison operators for StaticBitArray.
opCom typeof(this) opCom(): Complement operator.
opEquals bool opEquals(StaticBitArray!(capacity, Block2) a2): Support for operators == and != for StaticBitArray.
opIndex bool opIndex(size_t i): Gets the i'th bit.
opIndex bool opIndex(Mod!(capacity, ModUInt) i): Get the i'th bit.
opIndexAssign bool opIndexAssign(bool b, Mod!(capacity, ModUInt) i): Sets the i'th bit. No range checking needed.
opOpAssign typeof(this) opOpAssign(typeof(this) e2): Support for operator &= for StaticBitArray.
opOpAssign typeof(this) opOpAssign(typeof(this) e2): Support for operator |= for StaticBitArray.
opOpAssign typeof(this) opOpAssign(typeof(this) e2): Support for operator ^= for StaticBitArray.
opOpAssign typeof(this) opOpAssign(typeof(this) e2): Support for operator -= for StaticBitArray.
opSliceAssign typeof(this) opSliceAssign(bool value): Set all bits to value via slice assignment syntax.
ptr inout(Block*) ptr(): Get pointer to data blocks.
put typeof(this) put(size_t i, bool b): Puts the i'th bit to b.
reset void reset(): Reset all bits (to zero).
reverse typeof(this) reverse(): Reverses the bits of the StaticBitArray in place.
sort typeof(this) sort(): Sorts the StaticBitArray's elements.
sparseness auto sparseness(int depth): Get number of bits unset divided by length.
toHash hash_t toHash(): Support for hashing for StaticBitArray.
toString void toString(void delegate(scope const(char)[]) sink, FormatSpec!char fmt): Return a string representation of this StaticBitArray.
ubytes inout(ubyte)[] ubytes(): Data as an array of unsigned bytes.

Manifest constants

bitsPerBlock enum bitsPerBlock;: Number of bits per Block.
blockCount enum blockCount;: Number of Blocks.
length enum length;: Number of bits.

Static functions

dim uint dim(): Gets the amount of native words backing this.
reverseBlock Block reverseBlock(Block block): Reverse block Block.

Structs

OneIndexes struct OneIndexes(Store): Lazy range of the indices of set bits.
Range struct Range(): Bidirectional range into BitArray. * * TODO Provide opSliceAssign for interopability with range algorithms via * private static struct member Range. * * TODO Look at how std.container.array implements this. * * See_Also: https://dlang.org/phobos/std_bitmanip.html#bitsSet

Examples

run-time

1 import std.algorithm : equal;
2 import nxt.rational : Rational;
3 
4 alias Q = Rational!ulong;
5 enum m = 256;
6 
7 StaticBitArray!m b0;
8 
9 import nxt.modulo : Mod;
10 static assert(is(typeof(b0.oneIndexes.front()) == Mod!m));
11 
12 b0[1] = 1;
13 b0[2] = 1;
14 
15 b0[m/2 - 11] = 1;
16 b0[m/2 - 1] = 1;
17 b0[m/2] = 1;
18 b0[m/2 + 1] = 1;
19 b0[m/2 + 11] = 1;
20 
21 b0[m - 3] = 1;
22 b0[m - 2] = 1;
23 
24 assert(b0.oneIndexes.equal([1, 2,
25                             m/2 - 11, m/2 - 1, m/2, m/2 + 1, m/2 + 11,
26                             m - 3,
27                             m - 2].s[]));
28 assert(b0.countOnes == 9);

run-time

1 import std.algorithm : equal;
2 import nxt.rational : Rational;
3 
4 alias Q = Rational!ulong;
5 enum m = 256;
6 
7 StaticBitArray!m b0;
8 
9 import nxt.modulo : Mod;
10 static assert(is(typeof(b0.oneIndexes.front()) == Mod!m));
11 
12 b0[0] = 1;
13 b0[1] = 1;
14 b0[m/2 - 11] = 1;
15 b0[m/2 - 1] = 1;
16 b0[m/2] = 1;
17 b0[m/2 + 1] = 1;
18 b0[m/2 + 11] = 1;
19 b0[m - 2] = 1;
20 b0[m - 1] = 1;
21 
22 assert(b0.oneIndexes.equal([0, 1,
23                             m/2 - 11, m/2 - 1, m/2, m/2 + 1, m/2 + 11,
24                             m - 2,
25                             m - 1].s[]));
26 assert(b0.countOnes == 9);

ditto

import std.traits : isIterable;
static assert(isIterable!(StaticBitArray!256));

test ubyte access

1 auto b8 = StaticBitArray!(8, ubyte)();
2 b8[0] = 1;
3 b8[1] = 1;
4 b8[3] = 1;
5 b8[6] = 1;
6 
7 assert(b8.ubytes == [64 + 8 + 2 + 1].s[]);
8 
9 alias Ix = b8.Index;
10 Ix nextIx;
11 
12 assert(b8.canFindIndexOf(true, Ix(0), nextIx));
13 assert(nextIx == 0);
14 
15 assert(b8.canFindIndexOf(true, Ix(1), nextIx));
16 assert(nextIx == 1);
17 
18 assert(b8.canFindIndexOf(true, Ix(2), nextIx));
19 assert(nextIx == 3);
20 
21 assert(b8.canFindIndexOf(true, Ix(3), nextIx));
22 assert(nextIx == 3);
23 
24 assert(b8.canFindIndexOf(true, Ix(4), nextIx));
25 assert(nextIx == 6);
26 
27 assert(!b8.canFindIndexOf(true, Ix(7), nextIx));

test all zero and all one predicates

1 static void test(size_t restBitCount)()
2 {
3     enum n = 8*size_t.sizeof + restBitCount;
4 
5     auto bs = StaticBitArray!(n, size_t)();
6 
7     assert(bs.allZero);
8     assert(!bs.allOne);
9 
10     foreach (immutable i; 0 .. n - 1)
11     {
12         bs[i] = true;
13         assert(!bs.allZero);
14         assert(!bs.allOne);
15     }
16     bs[n - 1] = true;
17 
18     assert(bs.allOne);
19 }
20 test!0;
21 test!1;
22 test!2;
23 test!37;
24 test!62;
25 test!63;

ditto

1 import std.format : format;
2 
3 const b0_ = StaticBitArray!0([]);
4 const b0 = b0_;
5 assert(format("%s", b0) == "[]");
6 assert(format("%b", b0) is null);
7 
8 const b1_ = StaticBitArray!1([1]);
9 const b1 = b1_;
10 assert(format("%s", b1) == "[1]");
11 assert(format("%b", b1) == "1");
12 
13 const b4 = StaticBitArray!4([0, 0, 0, 0]);
14 assert(format("%b", b4) == "0000");
15 
16 const b8 = StaticBitArray!8([0, 0, 0, 0, 1, 1, 1, 1]);
17 assert(format("%s", b8) == "[0, 0, 0, 0, 1, 1, 1, 1]");
18 assert(format("%b", b8) == "00001111");
19 
20 const b16 = StaticBitArray!16([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]);
21 assert(format("%s", b16) == "[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]");
22 assert(format("%b", b16) == "00001111_00001111");
23 
24 const b9 = StaticBitArray!9([1, 0, 0, 0, 0, 1, 1, 1, 1]);
25 assert(format("%b", b9) == "1_00001111");
26 
27 const b17 = StaticBitArray!17([1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]);
28 assert(format("%b", b17) == "1_00001111_00001111");

test range

1 static testRange(Block)()
2 {
3     StaticBitArray!(6, Block) bs = [false, 1, 0, 0, true, 0];
4     bs.put(3, true);
5 
6     import std.algorithm : equal;
7 
8     assert(bs[0] == false);
9     assert(bs[1] == true);
10     assert(bs[2] == false);
11     assert(bs[3] == true);
12     assert(bs[4] == true);
13     assert(bs[5] == false);
14 
15     assert(bs.at!0 == false);
16     assert(bs.at!1 == true);
17     assert(bs.at!2 == false);
18     assert(bs.at!3 == true);
19     assert(bs.at!4 == true);
20     assert(bs.at!5 == false);
21 
22     // test slicing
23     assert(bs[].equal([0, 1, 0, 1, 1, 0].s[]));
24     assert(bs[1 .. 4].equal([1, 0, 1].s[]));
25 
26     auto rs = bs[1 .. 6 - 1]; // TODO Use opDollar
27     assert(rs.length == 4);
28     assert(rs.front == 1);
29     assert(rs.back == 1);
30 
31     rs.popFront();
32     assert(rs.front == 0);
33     assert(rs.back == 1);
34 
35     rs.popBack();
36     assert(rs.front == 1);
37     assert(rs.back == 1);
38 
39     rs.popFront();
40     rs.popBack();
41 
42     assert(rs.length == 0);
43     assert(rs.empty);
44 }
45 
46 import std.meta : AliasSeq;
47 foreach (Block; AliasSeq!(ubyte, ushort, uint, ulong, size_t))
48 {
49     testRange!Block;
50 }

1 alias Block = size_t;
2 enum blockCount = 2;
3 enum n = blockCount * 8*Block.sizeof - 1;
4 StaticBitArray!(n) x;
5 static assert(x.blockCount == blockCount);
6 
7 assert(x.indexOfFirstOne == n);
8 x[n - 1] = true;
9 assert(x.indexOfFirstOne == x.length - 1);
10 x[n - 2] = true;
11 assert(x.indexOfFirstOne == x.length - 2);
12 
13 x[n/2 + 1] = true;
14 assert(x.indexOfFirstOne == x.length/2 + 1);
15 x[n/2] = true;
16 assert(x.indexOfFirstOne == x.length/2);
17 x[n/2 - 1] = true;
18 assert(x.indexOfFirstOne == x.length/2 - 1);
19 
20 x[0] = true;
21 assert(x.indexOfFirstOne == 0);
22 assert(x[0]);
23 assert(!x[1]);
24 
25 x[1] = true;
26 assert(x[1]);
27 
28 x[1] = false;
29 assert(!x[1]);

Test opSliceAssign.

alias Block = size_t;
enum blockCount = 2;
enum n = blockCount * 8*Block.sizeof - 1;

StaticBitArray!(n) x;
assert(x.countOnes == 0);

x[] = true;
assert(x.countOnes == n);

x[] = false;
assert(x.countOnes == 0);

StaticBitArray

Constructors

Members

Aliases

Functions

Manifest constants

Static functions

Structs

Examples

Meta

Source