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         {
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.

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)();