x eagerly intersected with y.
TODO: move to container/common.d. TODO: Check that ElementType's of C1 and C2 match. Look at std.algorithm.intersection for hints.
exercise opEquals
import std.typecons : Nullable; import nxt.digest.fnv : FNV; alias K = Nullable!(ulong, ulong.max); alias X = HybridHashSet!(K, FNV!(64, true)); const n = 100; X a; foreach (const i_; 0 .. n) { const i = 1113*i_; // insert in order assert(!a.contains(K(i))); assert(!a.containsUsingLinearSearch(K(i))); assert(a.insertAndReturnElement(K(i)) == K(i)); assert(a.contains(K(i))); assert(a.containsUsingLinearSearch(K(i))); } X b; foreach (const i_; 0 .. n) { const i = 1113*(n - 1 - i_); // insert in reverse assert(!b.contains(K(i))); assert(!b.containsUsingLinearSearch(K(i))); assert(b.insertAndReturnElement(K(i)) == K(i)); assert(b.contains(K(i))); assert(b.containsUsingLinearSearch(K(i))); } assert(a == b); // bin storage must be deterministic () @trusted { assert(a._store != b._store); }();
string as key
1 import nxt.container.traits : mustAddGCRange; 2 import nxt.digest.fnv : FNV; 3 4 alias X = HybridHashSet!(string, FNV!(64, true)); 5 debug static assert(!mustAddGCRange!X); 6 debug static assert(X.sizeof == 24); // dynamic arrays also `hasAddressLikeKey` 7 8 auto x = X(); 9 10 auto testEscapeShouldFail()() @safe pure { 11 X x; 12 x.insert("a"); 13 return x.byElement; 14 } 15 16 auto testEscapeShouldFailFront()() @safe pure { 17 X x; 18 x.insert("a"); 19 return x.byElement.front; 20 } 21 22 assert(&"a"[0] is &"a"[0]); // string literals are store in common place 23 24 const aa = "aa"; 25 26 // string slices are equal when elements are equal regardless of position 27 // (.ptr) in memory 28 assert(x.insertAndReturnElement(aa[0 .. 1]) !is "a"); 29 x.insert(aa[0 .. 1]); 30 assert(x.insertAndReturnElement(aa[0 .. 1]) is aa[0 .. 1]); 31 assert(x.contains(aa[1 .. 2])); 32 assert(x.containsUsingLinearSearch(aa[1 .. 2])); 33 34 const(char)[] aa_ = "aa"; 35 assert(x.contains(aa_[1 .. 2])); 36 assert(x.containsUsingLinearSearch(aa_[1 .. 2])); 37 assert(aa_[1 .. 2] in x); 38 39 char[2] aa__; aa__ = "aa"; 40 assert(x.contains(aa__[1 .. 2])); 41 assert(x.containsUsingLinearSearch(aa__[1 .. 2])); 42 assert(aa__[1 .. 2] in x); 43 44 const bb = "bb"; 45 46 assert(x.insertAndReturnElement(bb[0 .. 1]) is bb[0 .. 1]); // returns newly added ref 47 assert(x.insertAndReturnElement(bb[0 .. 1]) !is "b"); // return other ref not equal new literal 48 x.insert(bb[0 .. 1]); 49 assert(x.contains(bb[1 .. 2])); 50 assert(x.containsUsingLinearSearch(bb[1 .. 2])); 51 52 x.remove(aa[0 .. 1]); 53 assert(!x.contains(aa[1 .. 2])); 54 assert(!x.containsUsingLinearSearch(aa[1 .. 2])); 55 assert(x.contains(bb[1 .. 2])); 56 assert(x.containsUsingLinearSearch(bb[1 .. 2])); 57 58 x.remove(bb[0 .. 1]); 59 assert(!x.contains(bb[1 .. 2])); 60 assert(!x.containsUsingLinearSearch(bb[1 .. 2])); 61 62 x.insert("a"); 63 x.insert("b"); 64 assert(x.contains("a")); 65 assert(x.containsUsingLinearSearch("a")); 66 assert(x.contains("b")); 67 assert(x.containsUsingLinearSearch("b")); 68 69 debug static assert(!__traits(compiles, { testEscapeShouldFail(); } )); 70 /+ TODO: this should fail: +/ 71 /+ TODO: debug static assert(!__traits(compiles, { testEscapeShouldFailFront(); } )); +/
string as key
import nxt.digest.fnv : FNV; alias X = HybridHashSet!(string, FNV!(64, true)); auto x = X(); char[2] cc = "cc"; // mutable chars assert(x.insertAndReturnElement(cc[]) !is cc[]); // will allocate new slice const cc_ = "cc"; // immutable chars assert(x.insertAndReturnElement(cc_[]) !is cc[]); // will not allocate
array container as value type
1 import std.meta : AliasSeq; 2 import std.typecons : Nullable; 3 import nxt.container.traits : mustAddGCRange; 4 import nxt.digest.fnv : FNV; 5 import nxt.array_help : s; 6 7 alias K = Nullable!(uint, uint.max); 8 9 alias VE = Nullable!(uint, uint.max); 10 alias V = HybridHashSet!(VE, FNV!(64, true)); 11 12 debug static assert(!mustAddGCRange!V); 13 14 foreach (X; AliasSeq!(HybridHashMap!(K, V, FNV!(64, true)))) { 15 const VE n = 600; 16 17 auto x = X(); 18 19 { // scoped range 20 auto xkeys = x.byKey; 21 assert(xkeys.length == 0); 22 foreach (ref key; xkeys) { 23 debug static assert(is(typeof(key) == const(K))); 24 assert(0); 25 } 26 foreach (ref key; X().byKey) { 27 debug static assert(is(typeof(key) == const(K))); 28 assert(0); 29 } 30 } 31 32 foreach (immutable i; 0 .. n) { 33 assert(x.length == i); 34 35 auto key = K(i); 36 auto value = V.withElements([VE(i)].s); 37 38 x[key] = value.dup; 39 assert(x.length == i + 1); 40 assert(x.contains(key)); 41 /+ TODO: assert(x.containsUsingLinearSearch(key)); +/ 42 { 43 auto valuePtr = key in x; 44 assert(valuePtr); 45 assert(*valuePtr == value); 46 } 47 48 x.remove(key); 49 assert(x.length == i); 50 assert(!x.contains(key)); 51 assert(key !in x); 52 53 x[key] = value.dup; 54 assert(x.length == i + 1); 55 assert(x.contains(key)); 56 { 57 auto valuePtr = key in x; 58 assert(valuePtr && *valuePtr == value); 59 } 60 } 61 62 assert(x is x); 63 64 x = x.dup; 65 66 auto y = x.dup; 67 assert(x !is y); 68 assert(x.length == y.length); 69 70 assert(y == x); 71 assert(x == y); 72 73 foreach (ref key; x.byKey) { 74 assert(x.contains(key)); 75 } 76 77 foreach (ref keyValue; x.byKeyValue) { 78 assert(x.contains(keyValue.key)); 79 auto keyValuePtr = keyValue.key in x; 80 assert(keyValuePtr && 81 *keyValuePtr == keyValue.value); 82 } 83 84 foreach (immutable i; 0 .. n) { 85 assert(x.length == n - i); 86 87 auto key = K(i); 88 auto value = V.withElements([VE(i)].s); 89 90 assert(x.contains(key)); 91 { 92 auto valuePtr = key in x; 93 assert(valuePtr && *valuePtr == value); 94 } 95 96 x.remove(key); 97 assert(!x.contains(key)); 98 assert(key !in x); 99 } 100 101 auto z = y.dup; 102 assert(y == z); 103 104 /* remove all elements in `y` using `removeAllMatching` and all elements 105 * in `z` using `removeAllMatching` */ 106 foreach (immutable i; 0 .. n) { 107 assert(y.length == n - i); 108 assert(z.length == n - i); 109 110 auto key = K(i); 111 auto value = V.withElements([VE(i)].s); 112 113 assert(y.contains(key)); 114 { 115 auto valuePtr = key in y; 116 assert(valuePtr && *valuePtr == value); 117 } 118 assert(z.contains(key)); 119 { 120 auto valuePtr = key in z; 121 assert(valuePtr && *valuePtr == value); 122 } 123 124 y.remove(key); 125 assert(z.removeAllMatching!((in element) => element.key is key) == 1); 126 assert(y == z); 127 128 assert(!y.contains(key)); 129 assert(!z.contains(key)); 130 131 assert(key !in y); 132 assert(key !in z); 133 } 134 }
r-value and l-value intersection
import core.lifetime : move; import std.typecons : Nullable; import nxt.digest.fnv : FNV; import nxt.array_help : s; alias K = Nullable!(uint, uint.max); alias X = HybridHashSet!(K, FNV!(64, true)); auto x = X(); { // scoped range foreach (ref _; x.byElement) { assert(0); } } auto x0 = X.init; assert(x0.length == 0); assert(x0._store.elts.length == 0); assert(!x0.contains(K(1))); auto x1 = X.withElements([K(12)].s); assert(x1.length == 1); assert(x1.contains(K(12))); auto x2 = X.withElements([K(10), K(12)].s); assert(x2.length == 2); assert(x2.contains(K(10))); assert(x2.contains(K(12))); auto x3 = X.withElements([K(12), K(13), K(14)].s); assert(x3.length == 3); assert(x3.contains(K(12))); assert(x3.contains(K(13))); assert(x3.contains(K(14))); auto z = X.withElements([K(10), K(12), K(13), K(15)].s); assert(z.length == 4); assert(z.contains(K(10))); assert(z.contains(K(12))); assert(z.contains(K(13))); assert(z.contains(K(15))); auto y = move(z).intersectedWith(x2); assert(y.length == 2); assert(y.contains(K(10))); assert(y.contains(K(12))); assert(y.containsUsingLinearSearch(K(10))); assert(y.containsUsingLinearSearch(K(12)));
r-value and r-value intersection
import std.typecons : Nullable; import nxt.digest.fnv : FNV; import nxt.array_help : s; alias K = Nullable!(uint, uint.max); alias X = HybridHashSet!(K, FNV!(64, true)); auto y = X.withElements([K(10), K(12), K(13), K(15)].s).intersectedWith(X.withElements([K(12), K(13)].s)); assert(y.length == 2); assert(y.contains(K(12))); assert(y.contains(K(13))); assert(y.containsUsingLinearSearch(K(12))); assert(y.containsUsingLinearSearch(K(13)));