phobos-next ~master (2024-03-19T05:49:32Z)

BitArray

nxt container bitarray

Array of bits.

Like std.bitmanip.BitArray but pure nothrow @safe @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).

@safe
struct BitArray (
bool blockAlignedLength = false
alias Allocator = null
) {
import core.bitop : bt, bts, btr;;
import core.bitop : bt, bts, btr;;
import core.bitop : bt, bts, btr;;
import nxt.bitarray_algorithm;;
~this();
typeof(this) dup();
void clear();
size_t length [@property setter];
size_t length [@property getter];
alias opDollar = length;
size_t capacity [@property getter];
bool opIndex(size_t i);
bool opIndexAssign(bool value, size_t i);
typeof(this) opSliceAssign(bool value);
version(none)
bool opCast();
bool allZero();
bool allOne();
size_t countOnes();
size_t countZeros();
size_t indexOfFirstOne();
size_t indexOfFirstZero();
bool opEquals(typeof(this) rhs);
this(this);
}

Destructor

~this
~this()

Destroy.

Postblit

this(this)
this(this)

Only explicit copying via .dup for now.

Members

Aliases

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.

clear
void clear()

Empty.

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

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.

Properties

capacity
size_t capacity [@property getter]

Get capacity in number of bits.

length
size_t length [@property setter]

Set length.

length
size_t length [@property getter]

Get length.

Examples

Test _blockCount and _fullBlocks.length.

static void test(bool blockAlignedLength)() {
	import nxt.construction : makeOfLength;
	alias BA = BitArray!(blockAlignedLength);

	assert(makeOfLength!BA(0)._blockCount == 0);
	assert(makeOfLength!BA(1)._blockCount == 1);

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

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

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

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

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

	{
		auto a = makeOfLength!BA(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 = makeOfLength!BA(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.

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

	foreach (const n; 1 .. 5*BA.bitsPerBlock) {
		static if (blockAlignedLength)
			if (n % BA.bitsPerBlock != 0) // if block aligned length
				continue;

		auto a = makeOfLength!BA(n);

		// set bits forwards
		foreach (const i; 0 .. n) {
			assert(a.countOnes == i);
			assert(a.countZeros == n - i);
			a[i] = true;
			assert(a.countOnes == i + 1);
			assert(a.countZeros == n - (i + 1));
		}

		assert(a.countOnes == n);
		assert(a.countZeros == 0);

		auto b = a.dup;
		assert(b.countOnes == n);
		assert(b.countZeros == 0);

		assert(a == b);

		// clear `a` bits forwards
		foreach (const i; 0 .. n) {
			assert(a.countOnes == n - i);
			assert(a.countZeros == i);
			a[i] = false;
			assert(a.countOnes == n - (i + 1));
			assert(a.countZeros == i + 1);
		}

		b[] = false;
		assert(a == b);

		// set bits backwards
		foreach (const i; 0 .. n) {
			assert(a.countOnes == i);
			a[n-1 - i] = true;
			assert(a.countOnes == i + 1);
		}

		b[] = true;
		assert(a == b);
	}
}
test!(false)();
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 = makeOfLength!BA(n);

	assert(a.length == n);

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

	a = makeOfLength!BA(n);
	assert(a.length == n);

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

	a.clear();
	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 = makeOfLength!BA(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 = makeOfLength!BA(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 = makeOfLength!BA(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 = makeOfLength!BA(n);

	a[] = true;

	a[0] = false;
	a[BA.bitsPerBlock/2] = false;
	a[BA.bitsPerBlock - 1] = false;
	assert(a.indexOfFirstZero == 0);
}
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 = makeOfLength!BA(n);

	a[] = false;

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

Test casting to bool.

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 = makeOfLength!BA(n);

	assert(a.allZero);

	a[0] = true;
	assert(!a.allZero);
	a[0] = false;
	assert(a.allZero);
}
test!(false)();
import std.exception: assertThrown;
import core.exception : AssertError;
alias BA = BitArray!(true);
assertThrown!AssertError(makeOfLength!BA(1));

Meta

Source

See Implementation

nxt container bitarray structs

Page generated by adrdox