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

) {

@safe pure nothrow @nogc

enum elementMaxCount;

static typeof(this) withInferredLength();

this(size_t length);

void clear();

typeof(this) dup();

bool insert(E e);

bool remove(E e);

bool complement(E e);

bool contains(E e);

bool opBinaryRight(E e);

typeof(this) opBinary(typeof(this) e);

size_t capacity();

}

Constructors

this this(size_t length): Construct set to store at most length number of bits.

Destructor

A destructor is present on this object, but not explicitly documented in the source.

Postblit

A postblit is present on this object, but not explicitly documented in the source.

Members

Functions

capacity size_t capacity(): Get current capacity in number of elements (bits). If growable is Growable.yes then capacity is variable, otherwise it's constant.
clear void clear(): Clear contents.
complement bool complement(E e): Insert element e if it's present otherwise remove it.
contains bool contains(E e): Check if element e is stored/contained.
dup typeof(this) dup()
insert bool insert(E e): Insert element e.
opBinary typeof(this) opBinary(typeof(this) e)
opBinaryRight bool opBinaryRight(E e): Check if element e is stored/contained.
remove bool remove(E e): Remove element e.

Manifest constants

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

Static functions

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

Examples

1 alias E = uint;
2 
3 import std.range.primitives : isOutputRange;
4 alias Set = DenseSetFilter!(E, Growable.no);
5 static assert(isOutputRange!(Set, E));
6 
7 const set0 = Set();
8 assert(set0.capacity == 0);
9 
10 const length = 2^^6;
11 auto set = DenseSetFilter!(E, Growable.no)(2*length);
12 const y = set.dup;
13 assert(y.capacity == 2*length);
14 
15 foreach (const ix; 0 .. length)
16 {
17     assert(!set.contains(ix));
18     assert(ix !in set);
19 
20     assert(!set.insert(ix));
21     assert(set.contains(ix));
22     assert(ix in set);
23 
24     assert(set.complement(ix));
25     assert(!set.contains(ix));
26     assert(ix !in set);
27 
28     assert(!set.complement(ix));
29     assert(set.contains(ix));
30     assert(ix in set);
31 
32     assert(!set.contains(ix + 1));
33 }
34 
35 auto z = set.dup;
36 foreach (const ix; 0 .. length)
37 {
38     assert(z.contains(ix));
39     assert(ix in z);
40 }
41 
42 foreach (const ix; 0 .. length)
43 {
44     assert(set.contains(ix));
45     assert(ix in set);
46 }
47 
48 foreach (const ix; 0 .. length)
49 {
50     assert(set.contains(ix));
51     set.remove(ix);
52     assert(!set.contains(ix));
53 }

1 alias E = uint;
2 
3 auto set = DenseSetFilter!(E, Growable.yes)();
4 assert(set._length == 0);
5 
6 const length = 2^^16;
7 foreach (const ix; 0 .. length)
8 {
9     assert(!set.contains(ix));
10     assert(ix !in set);
11 
12     assert(!set.insert(ix));
13     assert(set.contains(ix));
14     assert(ix in set);
15 
16     assert(set.complement(ix));
17     assert(!set.contains(ix));
18     assert(ix !in set);
19 
20     assert(!set.complement(ix));
21     assert(set.contains(ix));
22     assert(ix in set);
23 
24     assert(!set.contains(ix + 1));
25 }

test RefCounted storage

1 import std.typecons : RefCounted;
2 alias E = int;
3 
4 RefCounted!(DenseSetFilter!(E, Growable.yes)) set;
5 
6 assert(set._length == 0);
7 assert(set.capacity == 0);
8 
9 assert(!set.insert(0));
10 assert(set._length == 1);
11 assert(set.capacity == 2);
12 
13 const y = set;
14 
15 foreach (const e; 1 .. 1000)
16 {
17     assert(!set.insert(e));
18     assert(set._length == e + 1);
19     assert(y._length == e + 1);
20 }
21 
22 const set1 = RefCounted!(DenseSetFilter!(E, Growable.yes))(42);
23 assert(set1._length == 42);
24 assert(set1.capacity == 64);

1 enum E : ubyte { a, b, c, d, dAlias = d }
2 
3 auto set = DenseSetFilter!(E, Growable.yes)();
4 
5 assert(set._length == 0);
6 
7 import std.traits : EnumMembers;
8 foreach (const lang; [EnumMembers!E])
9 {
10     assert(!set.contains(lang));
11 }
12 foreach (const lang; [EnumMembers!E])
13 {
14     set.insert(lang);
15     assert(set.contains(lang));
16 }

1 enum E : ubyte { a, b, c, d, dAlias = d }
2 
3 auto set = DenseSetFilter!(E, Growable.no).withInferredLength(); // TODO use instantiator function here
4 assert(set.capacity == typeof(set).elementMaxCount);
5 
6 static assert(!__traits(compiles, { assert(set.contains(0)); }));
7 static assert(!__traits(compiles, { assert(set.insert(0)); }));
8 static assert(!__traits(compiles, { assert(0 in set); }));
9 
10 import std.traits : EnumMembers;
11 foreach (const lang; [EnumMembers!E])
12 {
13     assert(!set.contains(lang));
14     assert(lang !in set);
15 }
16 foreach (const lang; [EnumMembers!E])
17 {
18     set.insert(lang);
19     assert(set.contains(lang));
20     assert(lang in set);
21 }