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.
canFindIndexOf bool canFindIndexOf(bool value, UInt currIx, UInt nextIx): Undocumented in source. Be warned that the author may not have intended to support it.
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.
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 bool opCast(): Undocumented in source. Be warned that the author may not have intended to support it.
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, Index2 i): Undocumented in source.
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.
opSlice inout(Range!()) opSlice(): Undocumented in source. Be warned that the author may not have intended to support it.
opSlice inout(Range!()) opSlice(size_t i, size_t j): Undocumented in source. Be warned that the author may not have intended to support it.
opSliceAssign typeof(this) opSliceAssign(bool value): Set all bits to value via slice assignment syntax.
put typeof(this) put(size_t i, bool b): Puts the i'th bit to b.
reset void reset(): Reset all bits (to zero).
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.

Properties

dim uint dim [@property getter]: Gets the amount of native words backing this.
dup typeof(this) dup [@property getter]: Duplicate.
ptr inout(Block*) ptr [@property getter]: Get pointer to data blocks.
reverse typeof(this) reverse [@property getter]: Reverses the bits of the StaticBitArray in place.
reverseBlock Block reverseBlock [@property setter]: Reverse block Block.
sort typeof(this) sort [@property getter]: Sorts the StaticBitArray's elements.

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

import std.algorithm : equal;
import nxt.rational : Rational;

alias Q = Rational!ulong;
enum m = 256;

StaticBitArray!m b0;

import nxt.modulo : Mod;
static assert(is(typeof(b0.oneIndexes.front()) == Mod!m));

b0[1] = 1;
b0[2] = 1;

b0[m/2 - 11] = 1;
b0[m/2 - 1] = 1;
b0[m/2] = 1;
b0[m/2 + 1] = 1;
b0[m/2 + 11] = 1;

b0[m - 3] = 1;
b0[m - 2] = 1;

assert(b0.oneIndexes.equal([1, 2,
                            m/2 - 11, m/2 - 1, m/2, m/2 + 1, m/2 + 11,
                            m - 3,
                            m - 2].s[]));
assert(b0.countOnes == 9);

run-time

import std.algorithm : equal;
import nxt.rational : Rational;

alias Q = Rational!ulong;
enum m = 256;

StaticBitArray!m b0;

import nxt.modulo : Mod;
static assert(is(typeof(b0.oneIndexes.front()) == Mod!m));

b0[0] = 1;
b0[1] = 1;
b0[m/2 - 11] = 1;
b0[m/2 - 1] = 1;
b0[m/2] = 1;
b0[m/2 + 1] = 1;
b0[m/2 + 11] = 1;
b0[m - 2] = 1;
b0[m - 1] = 1;

assert(b0.oneIndexes.equal([0, 1,
                            m/2 - 11, m/2 - 1, m/2, m/2 + 1, m/2 + 11,
                            m - 2,
                            m - 1].s[]));
assert(b0.countOnes == 9);

ditto

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

test ubyte access

auto b8 = StaticBitArray!(8, ubyte)();
b8[0] = 1;
b8[1] = 1;
b8[3] = 1;
b8[6] = 1;

assert(b8.ubytes == [64 + 8 + 2 + 1].s[]);

alias Ix = b8.Index;
Ix nextIx;

assert(b8.canFindIndexOf(true, Ix(0), nextIx));
assert(nextIx == 0);

assert(b8.canFindIndexOf(true, Ix(1), nextIx));
assert(nextIx == 1);

assert(b8.canFindIndexOf(true, Ix(2), nextIx));
assert(nextIx == 3);

assert(b8.canFindIndexOf(true, Ix(3), nextIx));
assert(nextIx == 3);

assert(b8.canFindIndexOf(true, Ix(4), nextIx));
assert(nextIx == 6);

assert(!b8.canFindIndexOf(true, Ix(7), nextIx));

test all zero and all one predicates

static void test(size_t restBitCount)()
{
    enum n = 8*size_t.sizeof + restBitCount;

    auto bs = StaticBitArray!(n, size_t)();

    assert(bs.allZero);
    assert(!bs.allOne);

    foreach (immutable i; 0 .. n - 1)
    {
        bs[i] = true;
        assert(!bs.allZero);
        assert(!bs.allOne);
    }
    bs[n - 1] = true;

    assert(bs.allOne);
}
test!0;
test!1;
test!2;
test!37;
test!62;
test!63;

ditto

import std.format : format;

const b0_ = StaticBitArray!0([]);
const b0 = b0_;
assert(format("%s", b0) == "[]");
assert(format("%b", b0) is null);

const b1_ = StaticBitArray!1([1]);
const b1 = b1_;
assert(format("%s", b1) == "[1]");
assert(format("%b", b1) == "1");

const b4 = StaticBitArray!4([0, 0, 0, 0]);
assert(format("%b", b4) == "0000");

const b8 = StaticBitArray!8([0, 0, 0, 0, 1, 1, 1, 1]);
assert(format("%s", b8) == "[0, 0, 0, 0, 1, 1, 1, 1]");
assert(format("%b", b8) == "00001111");

const b16 = StaticBitArray!16([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]);
assert(format("%s", b16) == "[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]");
assert(format("%b", b16) == "00001111_00001111");

const b9 = StaticBitArray!9([1, 0, 0, 0, 0, 1, 1, 1, 1]);
assert(format("%b", b9) == "1_00001111");

const b17 = StaticBitArray!17([1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]);
assert(format("%b", b17) == "1_00001111_00001111");

test range

static testRange(Block)()
{
    StaticBitArray!(6, Block) bs = [false, 1, 0, 0, true, 0];
    bs.put(3, true);

    import std.algorithm : equal;

    assert(bs[0] == false);
    assert(bs[1] == true);
    assert(bs[2] == false);
    assert(bs[3] == true);
    assert(bs[4] == true);
    assert(bs[5] == false);

    assert(bs.at!0 == false);
    assert(bs.at!1 == true);
    assert(bs.at!2 == false);
    assert(bs.at!3 == true);
    assert(bs.at!4 == true);
    assert(bs.at!5 == false);

    // test slicing
    assert(bs[].equal([0, 1, 0, 1, 1, 0].s[]));
    assert(bs[1 .. 4].equal([1, 0, 1].s[]));

    auto rs = bs[1 .. 6 - 1]; // TODO Use opDollar
    assert(rs.length == 4);
    assert(rs.front == 1);
    assert(rs.back == 1);

    rs.popFront();
    assert(rs.front == 0);
    assert(rs.back == 1);

    rs.popBack();
    assert(rs.front == 1);
    assert(rs.back == 1);

    rs.popFront();
    rs.popBack();

    assert(rs.length == 0);
    assert(rs.empty);
}

import std.meta : AliasSeq;
foreach (Block; AliasSeq!(ubyte, ushort, uint, ulong, size_t))
{
    testRange!Block;
}

alias Block = size_t;
enum blockCount = 2;
enum n = blockCount * 8*Block.sizeof - 1;
StaticBitArray!(n) x;
static assert(x.blockCount == blockCount);

assert(x.indexOfFirstOne == n);
x[n - 1] = true;
assert(x.indexOfFirstOne == x.length - 1);
x[n - 2] = true;
assert(x.indexOfFirstOne == x.length - 2);

x[n/2 + 1] = true;
assert(x.indexOfFirstOne == x.length/2 + 1);
x[n/2] = true;
assert(x.indexOfFirstOne == x.length/2);
x[n/2 - 1] = true;
assert(x.indexOfFirstOne == x.length/2 - 1);

x[0] = true;
assert(x.indexOfFirstOne == 0);
assert(x[0]);
assert(!x[1]);

x[1] = true;
assert(x[1]);

x[1] = false;
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

Properties

Structs

Examples

Meta

Source