BitArray

Array of bits.

Like std.bitmanip.BitArray but @safe pure nothrow @nogc.

Set blockAlignedLength to true if this.length is always a multiple of Block.size.

TODO: use Flag instead, or wrap in BlockAlignedBitArray where this class is made private BitArray and alias BitArray = BitArray!(true).

TODO: support append bit via pushBack(bool).

Destructor

~this ~this(): Destroy.

Postblit

this(this) this(this): Only explicit copying via .dup for now.

Members

Aliases

clear alias clear = reset: Undocumented in source.
opDollar alias opDollar = length: Undocumented in source.

Functions

allOne bool allOne(): Check if this has only ones.
allZero bool allZero(): Check if this has only zeros.
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.
opCast bool opCast(): Undocumented in source. Be warned that the author may not have intended to support it.
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.

Properties

capacity size_t capacity [@property getter]: Get capacity in number of bits.
length size_t length [@property getter]: Get length.

Static functions

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

Examples

Test _blockCount and _fullBlocks.length.

static void test(bool blockAlignedLength)()
{
    alias BA = BitArray!(blockAlignedLength);

    assert(BA.withLength(0)._blockCount == 0);
    assert(BA.withLength(1)._blockCount == 1);

    {
        auto a = BA.withLength(1*BA.bitsPerBlock - 1);
        assert(a._blockCount == 1);
        assert(a._fullBlocks.length == 0);
    }

    {
        auto a = BA.withLength(1*BA.bitsPerBlock + 0);
        assert(a._blockCount == 1);
        assert(a._fullBlocks.length == 1);
    }

    {
        auto a = BA.withLength(1*BA.bitsPerBlock + 1);
        assert(a._blockCount == 2);
        assert(a._fullBlocks.length == 1);
    }

    {
        auto a = BA.withLength(2*BA.bitsPerBlock - 1);
        assert(a._blockCount == 2);
        assert(a._fullBlocks.length == 1);
    }

    {
        auto a = BA.withLength(2*BA.bitsPerBlock + 0);
        assert(a._blockCount == 2);
        assert(a._fullBlocks.length == 2);
    }

    {
        auto a = BA.withLength(2*BA.bitsPerBlock + 1);
        assert(a._blockCount == 3);
        assert(a._fullBlocks.length == 2);
    }
}
test!(false)();

Test indexing and element assignment.

static void test(bool blockAlignedLength)(size_t length)
{
    alias BA = BitArray!(blockAlignedLength);

    auto a = BA.withLength(length);

    assert(a.length == length);
    foreach (const i; 0 .. length)
        assert(!a[i]);

    a[0] = true;
    assert(a[0]);
    foreach (const i; 1 .. length)
        assert(!a[i]);

    assert(!a[1]);
    a[1] = true;
    assert(a[1]);
    a[1] = false;
    assert(!a[1]);
}
test!(false)(100);
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             if (n % BA.bitsPerBlock != 0) // if block aligned length
9                 continue;
10 
11         auto a = BA.withLength(n);
12 
13         // set bits forwards
14         foreach (const i; 0 .. n)
15         {
16             assert(a.countOnes == i);
17             assert(a.countZeros == n - i);
18             a[i] = true;
19             assert(a.countOnes == i + 1);
20             assert(a.countZeros == n - (i + 1));
21         }
22 
23         assert(a.countOnes == n);
24         assert(a.countZeros == 0);
25 
26         auto b = a.dup;
27         assert(b.countOnes == n);
28         assert(b.countZeros == 0);
29 
30         assert(a == b);
31 
32         // clear `a` bits forwards
33         foreach (const i; 0 .. n)
34         {
35             assert(a.countOnes == n - i);
36             assert(a.countZeros == i);
37             a[i] = false;
38             assert(a.countOnes == n - (i + 1));
39             assert(a.countZeros == i + 1);
40         }
41 
42         b[] = false;
43         assert(a == b);
44 
45         // set bits backwards
46         foreach (const i; 0 .. n)
47         {
48             assert(a.countOnes == i);
49             a[n-1 - i] = true;
50             assert(a.countOnes == i + 1);
51         }
52 
53         b[] = true;
54         assert(a == b);
55     }
56 }
57 test!(false)();
58 test!(true)();

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

static void test(bool blockAlignedLength)()
{
    alias BA = BitArray!(blockAlignedLength);

    static if (blockAlignedLength)
        const n = 5 * BA.bitsPerBlock;
    else
        const n = 5 * BA.bitsPerBlock + 1;
    auto a = BA.withLength(n);

    assert(a.length == n);

    a.reset();
    assert(a.length == 0);

    a = BA.withLength(n);
    assert(a.length == n);

    auto b = a.dup;
    assert(b.length == n);

    a.reset();
    assert(a.length == 0);
}
test!(false)();
test!(true)();

Test indexOfFirstOne for single set ones.

static void test(bool blockAlignedLength)()
{
    alias BA = BitArray!(blockAlignedLength);

    static if (blockAlignedLength)
        const n = 2 * BA.bitsPerBlock;
    else
        const n = 2 * BA.bitsPerBlock + 1;
    auto a = BA.withLength(n);

    assert(a.length == n);
    assert(a.indexOfFirstOne == n); // miss

    a[0] = true;
    assert(a.indexOfFirstOne == 0);
    a[] = false;

    a[2] = true;
    assert(a.indexOfFirstOne == 2);
    a[] = false;

    a[n/2-1] = true;
    assert(a.indexOfFirstOne == n/2-1);
    a[] = false;

    a[n/2] = true;
    assert(a.indexOfFirstOne == n/2);
    a[] = false;

    a[n/2+1] = true;
    assert(a.indexOfFirstOne == n/2+1);
    a[] = false;

    a[n-1] = true;
    assert(a.indexOfFirstOne == n-1);
    a[] = false;

    assert(a.indexOfFirstOne == n); // miss
}
test!(false)();
test!(true)();

Test indexOfFirstOne for multi set ones.

static void test(bool blockAlignedLength)()
{
    alias BA = BitArray!(blockAlignedLength);

    static if (blockAlignedLength)
        const n = 2 * BA.bitsPerBlock;
    else
        const n = 2 * BA.bitsPerBlock + 1;
    auto a = BA.withLength(n);

    a[0] = true;
    a[BA.bitsPerBlock/2] = true;
    a[BA.bitsPerBlock - 1] = true;
    assert(a.indexOfFirstOne == 0);
}
test!(false)();
test!(true)();

Test indexOfFirstZero for single set zeros.

static void test(bool blockAlignedLength)()
{
    alias BA = BitArray!(blockAlignedLength);

    static if (blockAlignedLength)
        const n = 2 * BA.bitsPerBlock;
    else
        const n = 2 * BA.bitsPerBlock + 1;
    auto a = BA.withLength(n);

    a[] = true;

    assert(a.length == n);
    assert(a.indexOfFirstZero == n); // miss

    a[0] = false;
    assert(a.indexOfFirstZero == 0);
    a[0] = true;

    a[2] = false;
    assert(a.indexOfFirstZero == 2);
    a[2] = true;

    a[n/2-1] = false;
    assert(a.indexOfFirstZero == n/2-1);
    a[n/2-1] = true;

    a[n/2] = false;
    assert(a.indexOfFirstZero == n/2);
    a[n/2] = true;

    a[n/2+1] = false;
    assert(a.indexOfFirstZero == n/2+1);
    a[n/2+1] = true;

    a[n-1] = false;
    assert(a.indexOfFirstZero == n-1);
    a[n-1] = true;

    assert(a.indexOfFirstZero == n); // miss
}
test!(false)();
test!(true)();

Test indexOfFirstZero for multi set zeros.

static void test(bool blockAlignedLength)()
{
    alias BA = BitArray!(blockAlignedLength);

    static if (blockAlignedLength)
        const n = 2 * BA.bitsPerBlock;
    else
        const n = 2 * BA.bitsPerBlock + 1;
    auto a = BA.withLength(n);

    a[] = true;

    a[0] = false;
    a[BA.bitsPerBlock/2] = false;
    a[BA.bitsPerBlock - 1] = false;
    assert(a.indexOfFirstZero == 0);
}
test!(false)();
test!(true)();