DynamicDenseSetFilter

Store elements of type E in a set in the range 0 .. length.

Can be seen as a generalization of std.typecons.BitFlags to integer types.

Typically used to implement very fast membership checking. For instance in graph traversal algorithms, this filter is typically used as a temporary set node (integer) ids that checks if a node has been previously visisted or not.

struct DynamicDenseSetFilter (

Growable growable = Growable.yes

Copyable copyable = Copyable.no

) if (

isDynamicDenseSetFilterable!E

) {

import core.memory : malloc = pureMalloc, calloc = pureCalloc, realloc = pureRealloc;;

import core.bitop : bts, btr, btc, bt;;

void free(void* ptr) via import nxt.qcmeman : free;;

alias ElementType = E;

pure nothrow @safe @nogc

static if(growable == Growable.no)

enum elementMaxCount;

static if(growable == Growable.no)

static typeof(this) withInferredLength();

static if(!(copyable))

typeof(this) dup();

E insert [@property setter];

alias put = insert;

E remove [@property setter];

E complement [@property setter];

E contains [@property setter];

E opBinaryRight [@property setter];

typeof(this) opBinary [@property setter];

size_t capacity [@property getter];

}

Constructors

this this(size_t length): Construct set to store E-values in the range [0 .. length[.

Destructor

~this ~this(): Undocumented in source.

Postblit

this(this) this(this): Undocumented in source.

Members

Aliases

ElementType alias ElementType = E: Undocumented in source.
put alias put = insert: Undocumented in source.

Functions

clear void clear(): Clear contents.
dup typeof(this) dup()

Manifest constants

elementMaxCount enum elementMaxCount;: Maximum number of elements in filter.

Properties

capacity size_t capacity [@property getter]: Get current capacity in number of elements (bits). If growable is Growable.yes then capacity is variable, otherwise it's constant.
complement E complement [@property setter]: Insert element e if it's present otherwise remove it.
contains E contains [@property setter]: Check if element e is stored/contained.
insert E insert [@property setter]: Insert element e.
opBinary typeof(this) opBinary [@property setter]
opBinaryRight E opBinaryRight [@property setter]: Check if element e is stored/contained.
remove E remove [@property setter]: Remove element e.

Static functions

withInferredLength typeof(this) withInferredLength(): Construct from inferred capacity and length elementMaxCount.

Examples

alias E = uint;

import std.range.primitives : isOutputRange;
alias Set = DynamicDenseSetFilter!(E, Growable.no);
static assert(isOutputRange!(Set, E));

const set0 = Set();
assert(set0.capacity == 0);

const length = 2^^6;
auto set = DynamicDenseSetFilter!(E, Growable.no)(2*length);
const y = set.dup;
assert(y.capacity == 2*length);

foreach (const ix; 0 .. length)
{
	assert(!set.contains(ix));
	assert(ix !in set);

	assert(!set.insert(ix));
	assert(set.contains(ix));
	assert(ix in set);

	assert(set.complement(ix));
	assert(!set.contains(ix));
	assert(ix !in set);

	assert(!set.complement(ix));
	assert(set.contains(ix));
	assert(ix in set);

	assert(!set.contains(ix + 1));
}

auto z = set.dup;
foreach (const ix; 0 .. length)
{
	assert(z.contains(ix));
	assert(ix in z);
}

foreach (const ix; 0 .. length)
{
	assert(set.contains(ix));
	assert(ix in set);
}

foreach (const ix; 0 .. length)
{
	assert(set.contains(ix));
	set.remove(ix);
	assert(!set.contains(ix));
}

alias E = uint;

auto set = DynamicDenseSetFilter!(E, Growable.yes)();
assert(set._length == 0);

const length = 2^^16;
foreach (const ix; 0 .. length)
{
	assert(!set.contains(ix));
	assert(ix !in set);

	assert(!set.insert(ix));
	assert(set.contains(ix));
	assert(ix in set);

	assert(set.complement(ix));
	assert(!set.contains(ix));
	assert(ix !in set);

	assert(!set.complement(ix));
	assert(set.contains(ix));
	assert(ix in set);

	assert(!set.contains(ix + 1));
}

test RefCounted storage

import std.typecons : RefCounted;
alias E = uint;

RefCounted!(DynamicDenseSetFilter!(E, Growable.yes)) set;

assert(set._length == 0);
assert(set.capacity == 0);

assert(!set.insert(0));
assert(set._length == 1);
assert(set.capacity == 2);

const y = set;

foreach (const e; 1 .. 1000)
{
	assert(!set.insert(e));
	assert(set._length == e + 1);
	assert(y._length == e + 1);
}

const set1 = RefCounted!(DynamicDenseSetFilter!(E, Growable.yes))(42);
assert(set1._length == 42);
assert(set1.capacity == 64);

enum E : ubyte { a, b, c, d, dAlias = d }

auto set = DynamicDenseSetFilter!(E, Growable.yes)();

assert(set._length == 0);

import std.traits : EnumMembers;
foreach (const lang; [EnumMembers!E])
	assert(!set.contains(lang));
foreach (const lang; [EnumMembers!E])
{
	set.insert(lang);
	assert(set.contains(lang));
}

enum E : ubyte { a, b, c, d, dAlias = d }

auto set = DynamicDenseSetFilter!(E, Growable.no).withInferredLength(); /+ TODO: use instantiator function here +/
assert(set.capacity == typeof(set).elementMaxCount);

static assert(!__traits(compiles, { assert(set.contains(0)); }));
static assert(!__traits(compiles, { assert(set.insert(0)); }));
static assert(!__traits(compiles, { assert(0 in set); }));

import std.traits : EnumMembers;
foreach (const lang; [EnumMembers!E])
{
	assert(!set.contains(lang));
	assert(lang !in set);
}
foreach (const lang; [EnumMembers!E])
{
	set.insert(lang);
	assert(set.contains(lang));
	assert(lang in set);
}