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