nxt.filters source code

1 module nxt.filters;
2 
3 /// Growable flag.
4 enum Growable { no, yes }
5 
6 /// Copyable flag.
7 enum Copyable { no, yes }
8 
9 enum isDynamicDenseSetFilterable(E) = (__traits(isUnsigned, E)
10                                        /* && cast(size_t)E.max <= uint.max */ );      // and small enough
11 
12 /** Store elements of type `E` in a set in the range `0 .. length`.
13  *
14  * Can be seen as a generalization of `std.typecons.BitFlags` to integer types.
15  *
16  * Typically used to implement very fast membership checking. For instance in
17  * graph traversal algorithms, this filter is typically used as a temporary set
18  * node (integer) ids that checks if a node has been previously visisted or not.
19  */
20 struct DynamicDenseSetFilter(E,
21                              // TODO: make these use the Flags template
22                              Growable growable = Growable.yes,
23                              Copyable copyable = Copyable.no)
24 if (isDynamicDenseSetFilterable!E)
25 {
26     import core.memory : malloc = pureMalloc, calloc = pureCalloc, realloc = pureRealloc;
27     import core.bitop : bts, btr, btc, bt;
28 	import nxt.qcmeman : free;
29 
30     alias ElementType = E;
31 
32     @safe pure nothrow @nogc:
33 
34     static if (growable == Growable.no)
35     {
36         /// Maximum number of elements in filter.
37         enum elementMaxCount = cast(size_t)E.max + 1;
38 
39         /// Construct from inferred capacity and length `elementMaxCount`.
40         static typeof(this) withInferredLength()
41 		{
42 			version(LDC) pragma(inline, true);
43 			return typeof(return)(elementMaxCount);
44 		}
45     }
46 
47     /// Construct set to store E-values in the range `[0 .. length[`.
48     this(in size_t length) @trusted
49     {
50         _blocksPtr = null;
51         static if (growable == Growable.yes)
52         {
53             _length = length;
54             _capacity = 0;
55             assureCapacity(length);
56         }
57         else
58         {
59             _capacity = length;
60             _blocksPtr = cast(Block*)calloc(blockCount, Block.sizeof);
61         }
62     }
63 
64 	pragma(inline, true)
65     ~this() nothrow @nogc => release();
66 
67     /// Free storage.
68 	pragma(inline, true)
69     private void release() @trusted @nogc => free(_blocksPtr);
70 
71     /// Clear contents.
72     void clear()() @nogc
73     {
74         version(D_Coverage) {} else pragma(inline, true);
75         release();
76         _blocksPtr = null;
77         static if (growable == Growable.yes)
78             _length = 0;
79         _capacity = 0;
80     }
81 
82     static if (copyable)
83     {
84         this(this) @trusted
85         {
86             Block* srcBlocksPtr = _blocksPtr;
87             _blocksPtr = cast(Block*)malloc(blockCount * Block.sizeof);
88             _blocksPtr[0 .. blockCount] = srcBlocksPtr[0 .. blockCount];
89         }
90     }
91     else
92     {
93         @disable this(this);
94 
95         /// Returns: shallow (and deep) duplicate of `this`.
96         typeof(this) dup()() @trusted /* template-lazy */
97         {
98             typeof(return) copy;
99             static if (growable == Growable.yes)
100                 copy._length = this._length;
101             copy._capacity = this._capacity;
102             copy._blocksPtr = cast(Block*)malloc(blockCount * Block.sizeof);
103             copy._blocksPtr[0 .. blockCount] = this._blocksPtr[0 .. blockCount];
104             return copy;
105         }
106     }
107 
108     @property:
109 
110     static if (growable == Growable.yes)
111     {
112         /// Assure capacity is at least `newLength`.
113         private void assureCapacity()(in size_t newCapacity) @trusted /* template-lazy */
114         {
115             if (_capacity < newCapacity)
116             {
117                 const oldBlockCount = blockCount;
118                 static if (__VERSION__ >= 2098) import std.math.algebraic : nextPow2; else import std.math : nextPow2;
119                 _capacity = newCapacity.nextPow2;
120                 _blocksPtr = cast(Block*)realloc(_blocksPtr,
121                                                  blockCount * Block.sizeof);
122                 _blocksPtr[oldBlockCount .. blockCount] = 0;
123             }
124         }
125 
126         /// Assure length (and capacity) is at least `newLength`.
127         private void assureLength(size_t newLength) @trusted /* template-lazy */
128         {
129             assureCapacity(newLength);
130             if (_length < newLength)
131                 _length = newLength;
132         }
133     }
134 
135     /** Insert element `e`.
136      *
137      * Returns: precense status of element before insertion.
138      */
139     bool insert()(in E e) @trusted /* template-lazy */
140     {
141         version(D_Coverage) {} else pragma(inline, true);
142         const ix = cast(size_t)e;
143         static if (growable == Growable.yes)
144             assureLength(ix + 1);
145         else
146             assert(ix < _capacity);
147         return bts(_blocksPtr, ix) != 0;
148     }
149     alias put = insert;         // OutputRange compatibility
150 
151     /** Remove element `e`.
152      *
153      * Returns: precense status of element before removal.
154      */
155     bool remove()(in E e) @trusted /* template-lazy */
156     {
157         version(D_Coverage) {} else pragma(inline, true);
158         const ix = cast(size_t)e;
159         static if (growable == Growable.yes)
160             assureLength(ix + 1);
161         else
162             assert(ix < _capacity);
163         return btr(_blocksPtr, ix) != 0;
164     }
165 
166     /** Insert element `e` if it's present otherwise remove it.
167      *
168      * Returns: `true` if elements was zeroed, `false` otherwise.
169      */
170     bool complement()(in E e) @trusted // template-laze
171     {
172         version(D_Coverage) {} else pragma(inline, true);
173         const ix = cast(size_t)e;
174         static if (growable == Growable.yes)
175             assureLength(ix + 1);
176         else
177             assert(ix < _capacity);
178         return btc(_blocksPtr, ix) != 0;
179     }
180 
181     /// Check if element `e` is stored/contained.
182     bool contains()(in E e) @trusted const /* template-lazy */
183     {
184         version(D_Coverage) {} else pragma(inline, true);
185         const ix = cast(size_t)e;
186         static if (growable == Growable.yes)
187             return ix < _length && bt(_blocksPtr, ix) != 0;
188         else
189             return ix < _capacity && bt(_blocksPtr, ix) != 0;
190     }
191     /// ditto
192 	pragma(inline, true)
193     bool opBinaryRight(string op)(in E e) const if (op == "in")
194 		=> contains(e);
195 
196     /// ditto
197     typeof(this) opBinary(string op)(in typeof(this) e) const
198     if (op == "|" || op == "&" || op == "^")
199     {
200         typeof(return) result;
201         mixin(`result._blocks[] = _blocks[] ` ~ op ~ ` e._blocks[];`);
202         return result;
203     }
204 
205     /** Get current capacity in number of elements (bits).
206         If `growable` is `Growable.yes` then capacity is variable, otherwise it's constant.
207     */
208 	pragma(inline, true)
209     @property size_t capacity() const
210     	=> _capacity;
211 
212 private:
213 	pragma(inline, true)
214     @property size_t blockCount() const
215 		=> _capacity / Block.sizeof + (_capacity % Block.sizeof ? 1 : 0);
216 
217     alias Block = size_t;       /// Allocated block type.
218     Block* _blocksPtr;          /// Pointer to blocks of bits.
219     static if (growable == Growable.yes)
220         size_t _length;         /// Offset + 1 of highest set bit.
221     size_t _capacity;       /// Number of bits allocated.
222 }
223 
224 ///
225 @safe pure nothrow @nogc unittest
226 {
227     alias E = uint;
228 
229     import std.range.primitives : isOutputRange;
230     alias Set = DynamicDenseSetFilter!(E, Growable.no);
231     static assert(isOutputRange!(Set, E));
232 
233     const set0 = Set();
234     assert(set0.capacity == 0);
235 
236     const length = 2^^6;
237     auto set = DynamicDenseSetFilter!(E, Growable.no)(2*length);
238     const y = set.dup;
239     assert(y.capacity == 2*length);
240 
241     foreach (const ix; 0 .. length)
242     {
243         assert(!set.contains(ix));
244         assert(ix !in set);
245 
246         assert(!set.insert(ix));
247         assert(set.contains(ix));
248         assert(ix in set);
249 
250         assert(set.complement(ix));
251         assert(!set.contains(ix));
252         assert(ix !in set);
253 
254         assert(!set.complement(ix));
255         assert(set.contains(ix));
256         assert(ix in set);
257 
258         assert(!set.contains(ix + 1));
259     }
260 
261     auto z = set.dup;
262     foreach (const ix; 0 .. length)
263     {
264         assert(z.contains(ix));
265         assert(ix in z);
266     }
267 
268     foreach (const ix; 0 .. length)
269     {
270         assert(set.contains(ix));
271         assert(ix in set);
272     }
273 
274     foreach (const ix; 0 .. length)
275     {
276         assert(set.contains(ix));
277         set.remove(ix);
278         assert(!set.contains(ix));
279     }
280 }
281 
282 ///
283 @safe pure nothrow @nogc unittest
284 {
285     alias E = uint;
286 
287     auto set = DynamicDenseSetFilter!(E, Growable.yes)();
288     assert(set._length == 0);
289 
290     const length = 2^^16;
291     foreach (const ix; 0 .. length)
292     {
293         assert(!set.contains(ix));
294         assert(ix !in set);
295 
296         assert(!set.insert(ix));
297         assert(set.contains(ix));
298         assert(ix in set);
299 
300         assert(set.complement(ix));
301         assert(!set.contains(ix));
302         assert(ix !in set);
303 
304         assert(!set.complement(ix));
305         assert(set.contains(ix));
306         assert(ix in set);
307 
308         assert(!set.contains(ix + 1));
309     }
310 }
311 
312 /// test `RefCounted` storage
313 nothrow @nogc unittest          // TODO: pure when https://github.com/dlang/phobos/pull/4692/files has been merged
314 {
315     import std.typecons : RefCounted;
316     alias E = uint;
317 
318     RefCounted!(DynamicDenseSetFilter!(E, Growable.yes)) set;
319 
320     assert(set._length == 0);
321     assert(set.capacity == 0);
322 
323     assert(!set.insert(0));
324     assert(set._length == 1);
325     assert(set.capacity == 2);
326 
327     const y = set;
328 
329     foreach (const e; 1 .. 1000)
330     {
331         assert(!set.insert(e));
332         assert(set._length == e + 1);
333         assert(y._length == e + 1);
334     }
335 
336     const set1 = RefCounted!(DynamicDenseSetFilter!(E, Growable.yes))(42);
337     assert(set1._length == 42);
338     assert(set1.capacity == 64);
339 }
340 
341 ///
342 @safe pure nothrow @nogc unittest
343 {
344     enum E : ubyte { a, b, c, d, dAlias = d }
345 
346     auto set = DynamicDenseSetFilter!(E, Growable.yes)();
347 
348     assert(set._length == 0);
349 
350     import std.traits : EnumMembers;
351     foreach (const lang; [EnumMembers!E])
352         assert(!set.contains(lang));
353     foreach (const lang; [EnumMembers!E])
354     {
355         set.insert(lang);
356         assert(set.contains(lang));
357     }
358 
359 }
360 
361 ///
362 @safe pure nothrow @nogc unittest
363 {
364     enum E : ubyte { a, b, c, d, dAlias = d }
365 
366     auto set = DynamicDenseSetFilter!(E, Growable.no).withInferredLength(); // TODO: use instantiator function here
367     assert(set.capacity == typeof(set).elementMaxCount);
368 
369     static assert(!__traits(compiles, { assert(set.contains(0)); }));
370     static assert(!__traits(compiles, { assert(set.insert(0)); }));
371     static assert(!__traits(compiles, { assert(0 in set); }));
372 
373     import std.traits : EnumMembers;
374     foreach (const lang; [EnumMembers!E])
375     {
376         assert(!set.contains(lang));
377         assert(lang !in set);
378     }
379     foreach (const lang; [EnumMembers!E])
380     {
381         set.insert(lang);
382         assert(set.contains(lang));
383         assert(lang in set);
384     }
385 
386 }
387 
388 /** Check if `E` is filterable in `StaticDenseSetFilter`, that is castable to
389     `uint` and castable from unsigned int zero.
390 */
391 template isStaticDenseFilterableType(E)
392 {
393     static if (is(E == enum))
394         enum isStaticDenseFilterableType = true;
395     else
396     {
397         import std.traits : hasIndirections, isUnsigned, isSomeChar;
398         static if (isUnsigned!E ||
399                    isSomeChar!E)
400             enum isStaticDenseFilterableType = true;
401         else static if (is(typeof(E.init.toUnsigned)))
402         {
403             alias UnsignedType = typeof(E.init.toUnsigned());
404             enum isStaticDenseFilterableType = (isUnsigned!UnsignedType &&
405                                                 is(typeof(E.fromUnsigned(UnsignedType.init))) &&
406                                                 !hasIndirections!E);
407         }
408         else
409             enum isStaticDenseFilterableType = false;
410     }
411 }
412 
413 @safe pure nothrow @nogc unittest
414 {
415     static assert(isStaticDenseFilterableType!uint);
416     static assert(!isStaticDenseFilterableType!string);
417     static assert(isStaticDenseFilterableType!char);
418     static assert(!isStaticDenseFilterableType!(char*));
419 
420     enum E { a, b }
421     static assert(isStaticDenseFilterableType!E);
422 }
423 
424 /** Store presence of elements of type `E` in a set in the range `0 .. length`.
425  *
426  * Can be seen as a generalization of `std.typecons.BitFlags` to integer types.
427  *
428  * Typically used to implement very fast membership checking in sets of
429  * enumerators.
430  *
431  * TODO: Add operators for bitwise `and` and `or` operations similar to
432  * https://dlang.org/library/std/typecons/bit_flags.html
433  */
434 struct StaticDenseSetFilter(E, bool requestPacked = true)
435 if (isStaticDenseFilterableType!E)
436 {
437     import std.range.primitives : ElementType;
438     import std.traits : isIterable, isAssignable, isUnsigned;
439     import core.bitop : bts, btr, btc, bt;
440 
441     alias ElementType = E;
442     alias This = typeof(this);
443 
444     @safe pure:
445 
446     string toString() const @property @trusted
447     {
448         import std.array : Appender;
449         import std.conv : to;
450 
451         Appender!(typeof(return)) str = This.stringof ~ "([";
452         bool other = false;
453 
454         void putElement(in E e)
455         {
456             version(LDC) pragma(inline, true);
457             if (contains(e))
458             {
459                 if (other)
460                     str.put(", ");
461                 else
462                     other = true;
463                 str.put(e.to!string);
464             }
465         }
466 
467         static if (is(E == enum))
468         {
469             import std.traits : EnumMembers;
470             foreach (const e; [EnumMembers!E])
471                 putElement(e);
472         }
473         else
474         {
475             foreach (const i; E.unsignedMin .. E.unsignedMax + 1)
476                 putElement(E.fromUnsigned(i));
477         }
478 
479         str.put("])");
480         return str.data;
481     }
482 
483     nothrow @nogc:
484 
485     /** Construct from elements `r`.
486      */
487     private this(R)(R r)
488         if (isIterable!R &&
489             isAssignable!(E, ElementType!R))
490     {
491         foreach (const ref e; r)
492             insert(e);
493     }
494 
495     /** Construct from `r` if `r` is non-empty, otherwise construct a full set.
496      */
497     static typeof(this) withValuesOrFull(R)(R r)
498         if (isIterable!R &&
499             isAssignable!(E, ElementType!R))
500     {
501         import std.range.primitives : empty;
502         if (r.empty)
503             return asFull();
504         return typeof(return)(r);
505     }
506 
507     pragma(inline, true):
508 
509     /// Construct a full set .
510     static typeof(this) asFull()() /* template-lazy */
511     {
512         typeof(return) that = void;
513         that._blocks[] = Block.max;
514         return that;
515     }
516 
517     /** Insert element `e`.
518      */
519     void insert()(in E e) @trusted /* template-lazy */
520     {
521         import nxt.bitop_ex : setBit;
522         static if (isPackedInScalar)
523             _blocks[0].setBit(cast(size_t)e);
524         else
525             bts(_blocksPtr, cast(size_t)e);
526     }
527     alias put = insert;         // OutputRange compatibility
528 
529     /** Remove element `e`.
530      */
531     void remove()(in E e) @trusted /* template-lazy */
532     {
533         import nxt.bitop_ex : resetBit;
534         static if (isPackedInScalar)
535             _blocks[0].resetBit(cast(size_t)e);
536         else
537             btr(_blocksPtr, cast(size_t)e);
538     }
539 
540     @property:
541 
542     /** Check if element `e` is present/stored/contained.
543      */
544     bool contains()(in E e) @trusted const /* template-lazy */
545     {
546         import nxt.bitop_ex : testBit;
547         static if (isPackedInScalar)
548             return _blocks[0].testBit(cast(size_t)e);
549         else
550             return bt(_blocksPtr, cast(size_t)e) != 0;
551     }
552 
553     /// ditto
554     bool opBinaryRight(string op)(in E e) const if (op == "in")
555 		=> contains(e);
556 
557     /// ditto
558     typeof(this) opBinary(string op)(in typeof(this) e) const
559     if (op == "|" || op == "&" || op == "^")
560     {
561         typeof(return) result;
562         mixin(`result._blocks[] = _blocks[] ` ~ op ~ ` e._blocks[];`);
563         return result;
564     }
565 
566     /// ditto
567     typeof(this) opOpAssign(string op)(in typeof(this) e)
568     if (op == "|" || op == "&" || op == "^")
569     {
570         version(DigitalMars) pragma(inline, false);
571         mixin(`_blocks[] ` ~ op ~ `= e._blocks[];`);
572         return this;
573     }
574 
575 private:
576     static if (is(E == enum) || isUnsigned!E) // has normal
577     {
578         /// Maximum number of elements in filter.
579         enum elementMaxCount = E.max - E.min + 1;
580     }
581     else
582     {
583         /// Maximum number of elements in filter.
584         enum elementMaxCount = E.unsignedMax - E.unsignedMin + 1;
585     }
586 
587     static if (requestPacked)
588     {
589         static      if (elementMaxCount <= 8*ubyte.sizeof)
590         {
591             enum isPackedInScalar = true;
592             alias Block = ubyte;
593         }
594         else static if (elementMaxCount <= 8*ushort.sizeof)
595         {
596             enum isPackedInScalar = true;
597             alias Block = ushort;
598         }
599         else static if (elementMaxCount <= 8*uint.sizeof)
600         {
601             enum isPackedInScalar = true;
602             alias Block = uint;
603         }
604         else
605         {
606             enum isPackedInScalar = false;
607             alias Block = size_t;
608         }
609     }
610     else
611     {
612         enum isPackedInScalar = false;
613         alias Block = size_t;
614     }
615 
616     /** Number of bits per `Block`. */
617     enum bitsPerBlock = 8*Block.sizeof;
618 
619     /** Number of `Block`s. */
620     enum blockCount = (elementMaxCount + (bitsPerBlock-1)) / bitsPerBlock;
621 
622     Block[blockCount] _blocks;          /// Pointer to blocks of bits.
623     inout(Block)* _blocksPtr() @trusted inout
624 		=> _blocks.ptr;
625 }
626 
627 version(unittest)
628 {
629     import std.traits : EnumMembers;
630 }
631 
632 ///
633 @safe pure nothrow @nogc unittest
634 {
635     enum E : ubyte { a, b, c, d, dAlias = d }
636 
637     auto set = StaticDenseSetFilter!(E)();
638     static assert(set.sizeof == 1);
639 
640     static assert(!__traits(compiles, { assert(set.contains(0)); }));
641     static assert(!__traits(compiles, { assert(set.insert(0)); }));
642     static assert(!__traits(compiles, { assert(0 in set); }));
643 
644     // initially empty
645     foreach (const lang; [EnumMembers!E])
646     {
647         assert(!set.contains(lang));
648         assert(lang !in set);
649     }
650 
651     // insert
652     foreach (const lang; [EnumMembers!E])
653     {
654         set.insert(lang);
655         assert(set.contains(lang));
656         assert(lang in set);
657     }
658 
659     // remove
660     foreach (const lang; [EnumMembers!E])
661     {
662         set.remove(lang);
663         assert(!set.contains(lang));
664         assert(lang !in set);
665     }
666 }
667 
668 /// assignment from range
669 @safe pure nothrow @nogc unittest
670 {
671     enum E : ubyte { a, b, c, d, dAlias = d }
672 
673     const E[2] es = [E.a, E.c];
674     auto set = StaticDenseSetFilter!(E)(es[]);
675     static assert(set.sizeof == 1);
676 
677     foreach (const ref e; es)
678     {
679         assert(set.contains(e));
680     }
681 }
682 
683 /// assignment from range
684 @safe pure nothrow @nogc unittest
685 {
686     enum E : ubyte { a, b, c, d }
687 
688     const E[] es = [];
689     auto set = StaticDenseSetFilter!(E).withValuesOrFull(es[]);
690     static assert(set.sizeof == 1);
691 
692     foreach (const e; [EnumMembers!E])
693     {
694         assert(set.contains(e));
695         assert(e in set);
696         set.remove(e);
697         assert(!set.contains(e));
698         assert(e !in set);
699     }
700 }
701 
702 /// assignment from range
703 @safe pure nothrow @nogc unittest
704 {
705     enum E : ubyte { a, b, c, d }
706 
707     const E[2] es = [E.a, E.c];
708     auto set = StaticDenseSetFilter!(E).withValuesOrFull(es[]);
709     static assert(set.sizeof == 1);
710 
711     foreach (const ref e; es)
712     {
713         assert(set.contains(e));
714         set.remove(e);
715         assert(!set.contains(e));
716     }
717 }
718 
719 /// assignment from range
720 @safe pure nothrow @nogc unittest
721 {
722     enum E : ubyte { a, b, c, d }
723 
724     auto set = StaticDenseSetFilter!(E).asFull;
725     static assert(set.sizeof == 1);
726 
727     foreach (const e; [EnumMembers!E])
728     {
729         assert(set.contains(e));
730         set.remove(e);
731         assert(!set.contains(e));
732     }
733 }
734 
735 /// assignment from range
736 @safe pure nothrow @nogc unittest
737 {
738     enum E : ubyte
739     {
740         a, b, c, d, e, f, g, h,
741     }
742 
743     auto set = StaticDenseSetFilter!(E).asFull;
744     static assert(set.sizeof == 1);
745     static assert(set.isPackedInScalar);
746 
747     foreach (const e; [EnumMembers!E])
748     {
749         assert(set.contains(e));
750         set.remove(e);
751         assert(!set.contains(e));
752     }
753 }
754 
755 /// assignment from range
756 @safe pure nothrow @nogc unittest
757 {
758     enum E : ubyte
759     {
760         a, b, c, d, e, f, g, h,
761         i,
762     }
763 
764     auto set = StaticDenseSetFilter!(E).asFull;
765     static assert(set.sizeof == 2);
766     static assert(set.isPackedInScalar);
767 
768     foreach (const e; [EnumMembers!E])
769     {
770         assert(set.contains(e));
771         set.remove(e);
772         assert(!set.contains(e));
773     }
774 }
775 
776 /// assignment from range
777 @safe pure nothrow @nogc unittest
778 {
779     enum E : ubyte
780     {
781         a, b, c, d, e, f, g, h,
782         i, j, k, l, m, n, o, p,
783     }
784 
785     auto set = StaticDenseSetFilter!(E).asFull;
786     static assert(set.sizeof == 2);
787     static assert(set.isPackedInScalar);
788 
789     foreach (const e; [EnumMembers!E])
790     {
791         assert(set.contains(e));
792         set.remove(e);
793         assert(!set.contains(e));
794     }
795 }
796 
797 /// assignment from range
798 @safe pure nothrow @nogc unittest
799 {
800     enum E : ubyte
801     {
802         a, b, c, d, e, f, g, h,
803         i, j, k, l, m, n, o, p,
804         r,
805     }
806 
807     auto set = StaticDenseSetFilter!(E).asFull;
808     static assert(set.sizeof == 4);
809     static assert(set.isPackedInScalar);
810 
811     foreach (const e; [EnumMembers!E])
812     {
813         assert(set.contains(e));
814         set.remove(e);
815         assert(!set.contains(e));
816     }
817 }
818 
819 /// assignment from range
820 @safe pure nothrow @nogc unittest
821 {
822     enum E : ubyte
823     {
824         a, b, c, d, e, f, g, h,
825         i, j, k, l, m, n, o, p,
826         r, s, t, u, v, w, x, y,
827         z, a1, a2, a3, a4, a5, a6, a7,
828         a8
829     }
830 
831     auto set = StaticDenseSetFilter!(E).asFull;
832     static assert(set.sizeof == 8);
833     static assert(!set.isPackedInScalar);
834 
835     foreach (const e; [EnumMembers!E])
836     {
837         assert(set.contains(e));
838         set.remove(e);
839         assert(!set.contains(e));
840     }
841 }
842 
843 version(unittest)
844 {
845     enum Rel : ubyte { unknown, subClassOf, instanceOf, memberOf }
846     import nxt.bit_traits : packedBitSizeOf;
847     static assert(packedBitSizeOf!Rel == 2);
848 
849     struct Role
850     {
851         Rel rel;
852         bool reversion;
853 
854         enum unsignedMin = 0;
855         enum unsignedMax = 2^^(1 +  // reversion
856                                packedBitSizeOf!Rel // relation
857             ) - 1;
858 
859         alias UnsignedType = ushort;
860         static assert(typeof(this).sizeof == UnsignedType.sizeof);
861         static assert(Role.sizeof == 2);
862 
863         pragma(inline, true)
864         @safe pure nothrow @nogc:
865 
866         /// Create from `UnsignedType` `u`.
867         static typeof(this) fromUnsigned(in UnsignedType u) @trusted
868         {
869             typeof(return) that;
870             that.reversion = (u >> 0) & 1;
871             that.rel = cast(Rel)(u >> 1);
872             return that;
873         }
874 
875         /// Convert to `UnsignedType` `u`.
876         UnsignedType toUnsigned() const @trusted
877         	=> cast(UnsignedType)((cast(UnsignedType)reversion << 0) |
878 								  (cast(UnsignedType)rel << 1));
879 
880         UnsignedType opCast(UnsignedType)() const @nogc
881 			=> toUnsigned;
882     }
883 
884     static assert(is(typeof(Role.init.toUnsigned)));
885     static assert(is(typeof(Role.init.toUnsigned()) == Role.UnsignedType));
886     static assert(isStaticDenseFilterableType!Role);
887 }
888 
889 /// assignment from range
890 @safe pure unittest
891 {
892     auto set = StaticDenseSetFilter!(Role)();
893     static assert(set.sizeof == 1);
894 
895     assert(set.toString == "StaticDenseSetFilter!(Role, true)([])");
896 
897     // inserts
898     foreach (const rel; [EnumMembers!Rel])
899     {
900         assert(!set.contains(Role(rel)));
901         assert(!set.contains(Role(rel, true)));
902 
903         set.insert(Role(rel));
904         assert(set.contains(Role(rel)));
905 
906         assert(!set.contains(Role(rel, true)));
907         set.insert(Role(rel, true));
908 
909         assert(set.contains(Role(rel)));
910         assert(set.contains(Role(rel, true)));
911     }
912 
913     assert(set.toString == "StaticDenseSetFilter!(Role, true)([const(Role)(unknown, false), const(Role)(unknown, true), const(Role)(subClassOf, false), const(Role)(subClassOf, true), const(Role)(instanceOf, false), const(Role)(instanceOf, true), const(Role)(memberOf, false), const(Role)(memberOf, true)])");
914 
915     // removes
916     foreach (const rel; [EnumMembers!Rel])
917     {
918         assert(set.contains(Role(rel)));
919         assert(set.contains(Role(rel, true)));
920 
921         set.remove(Role(rel));
922         assert(!set.contains(Role(rel)));
923 
924         assert(set.contains(Role(rel, true)));
925         set.remove(Role(rel, true));
926 
927         assert(!set.contains(Role(rel)));
928         assert(!set.contains(Role(rel, true)));
929     }
930 
931     assert(set.toString == "StaticDenseSetFilter!(Role, true)([])");
932 
933     auto fullSet = StaticDenseSetFilter!(Role).asFull;
934 
935     foreach (const rel; [EnumMembers!Rel])
936     {
937         assert(fullSet.contains(Role(rel)));
938         assert(fullSet.contains(Role(rel, true)));
939     }
940 
941     auto emptySet = StaticDenseSetFilter!(Role)();
942 
943     foreach (const rel; [EnumMembers!Rel])
944     {
945         assert(!emptySet.contains(Role(rel)));
946         assert(!emptySet.contains(Role(rel, true)));
947     }
948 }
949 
950 /// set operations
951 @safe pure nothrow @nogc unittest
952 {
953     import nxt.array_help : s;
954 
955     enum E : ubyte { a, b, c, d, dAlias = d }
956 
957     auto a = StaticDenseSetFilter!(E)([E.a].s[]);
958     auto b = StaticDenseSetFilter!(E)([E.b].s[]);
959     auto c = StaticDenseSetFilter!(E)([E.b].s[]);
960 
961     auto a_or_b = StaticDenseSetFilter!(E)([E.a, E.b].s[]);
962     auto a_and_b = StaticDenseSetFilter!(E)();
963 
964     assert((a | b | c) == a_or_b);
965     assert((a & b) == a_and_b);
966 
967     a |= b;
968     assert(a == a_or_b);
969 }