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