DenseSetFilter

Store presence of 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 DenseSetFilter (

Growable growable = Growable.yes

Copyable copyable = Copyable.no

) if (

isDenseSetFilterable!E

) {

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

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

alias ElementType = E;

@safe pure nothrow @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 at most length number of bits.

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 = DenseSetFilter!(E, Growable.no);
static assert(isOutputRange!(Set, E));

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

const length = 2^^6;
auto set = DenseSetFilter!(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 = DenseSetFilter!(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 = int;

RefCounted!(DenseSetFilter!(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!(DenseSetFilter!(E, Growable.yes))(42);
assert(set1._length == 42);
assert(set1.capacity == 64);

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

auto set = DenseSetFilter!(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 = DenseSetFilter!(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);
}