StaticBitArray

A statically sized std.bitmanip.BitArray.

TODO Infer Block from len as is done for Bound and Mod.

TODO Optimize allOne, allZero using intrinsic?

@safe
struct StaticBitArray (
uint capacity
Block = DefaultBlock
) if (
isUnsigned!DefaultBlock
) {}

Constructors

this
this(bool[] ba)

Set this to the contents of ba.

this
this(bool[capacity] ba)

Set this to the contents of ba.

Members

Aliases

Index
alias Index = Mod!capacity
Undocumented in source.
bitsSet
alias bitsSet = oneIndexes
clear
alias clear = reset
Undocumented in source.

Functions

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

Meta