x eagerly intersected with y.
TODO: move to container_algorithm.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.digestx.fnv : FNV; alias K = Nullable!(ulong, ulong.max); alias X = OpenHashSet!(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 version(showEntries) dbg(); 2 import nxt.container_traits : mustAddGCRange; 3 import nxt.digestx.fnv : FNV; 4 5 alias X = OpenHashSet!(string, FNV!(64, true)); 6 debug static assert(!mustAddGCRange!X); 7 debug static assert(X.sizeof == 24); // dynamic arrays also `hasAddressLikeKey` 8 9 auto x = X(); 10 11 auto testEscapeShouldFail()() @safe pure 12 { 13 X x; 14 x.insert("a"); 15 return x.byElement; 16 } 17 18 auto testEscapeShouldFailFront()() @safe pure 19 { 20 X x; 21 x.insert("a"); 22 return x.byElement.front; 23 } 24 25 assert(&"a"[0] is &"a"[0]); // string literals are store in common place 26 27 const aa = "aa"; 28 29 // string slices are equal when elements are equal regardless of position 30 // (.ptr) in memory 31 assert(x.insertAndReturnElement(aa[0 .. 1]) !is "a"); 32 x.insert(aa[0 .. 1]); 33 assert(x.insertAndReturnElement(aa[0 .. 1]) is aa[0 .. 1]); 34 assert(x.contains(aa[1 .. 2])); 35 assert(x.containsUsingLinearSearch(aa[1 .. 2])); 36 37 const(char)[] aa_ = "aa"; 38 assert(x.contains(aa_[1 .. 2])); 39 assert(x.containsUsingLinearSearch(aa_[1 .. 2])); 40 assert(aa_[1 .. 2] in x); 41 42 char[2] aa__; aa__ = "aa"; 43 assert(x.contains(aa__[1 .. 2])); 44 assert(x.containsUsingLinearSearch(aa__[1 .. 2])); 45 assert(aa__[1 .. 2] in x); 46 47 const bb = "bb"; 48 49 assert(x.insertAndReturnElement(bb[0 .. 1]) is bb[0 .. 1]); // returns newly added ref 50 assert(x.insertAndReturnElement(bb[0 .. 1]) !is "b"); // return other ref not equal new literal 51 x.insert(bb[0 .. 1]); 52 assert(x.contains(bb[1 .. 2])); 53 assert(x.containsUsingLinearSearch(bb[1 .. 2])); 54 55 x.remove(aa[0 .. 1]); 56 assert(!x.contains(aa[1 .. 2])); 57 assert(!x.containsUsingLinearSearch(aa[1 .. 2])); 58 assert(x.contains(bb[1 .. 2])); 59 assert(x.containsUsingLinearSearch(bb[1 .. 2])); 60 61 x.remove(bb[0 .. 1]); 62 assert(!x.contains(bb[1 .. 2])); 63 assert(!x.containsUsingLinearSearch(bb[1 .. 2])); 64 65 x.insert("a"); 66 x.insert("b"); 67 assert(x.contains("a")); 68 assert(x.containsUsingLinearSearch("a")); 69 assert(x.contains("b")); 70 assert(x.containsUsingLinearSearch("b")); 71 72 debug static assert(!__traits(compiles, { testEscapeShouldFail(); } )); 73 // TODO: this should fail: 74 // TODO: debug static assert(!__traits(compiles, { testEscapeShouldFailFront(); } ));
string as key
version(showEntries) dbg(); import nxt.digestx.fnv : FNV; alias X = OpenHashSet!(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.digestx.fnv : FNV; 5 import nxt.array_help : s; 6 version(showEntries) dbg(); 7 8 alias K = Nullable!(uint, uint.max); 9 10 alias VE = Nullable!(uint, uint.max); 11 alias V = OpenHashSet!(VE, FNV!(64, true)); 12 13 debug static assert(!mustAddGCRange!V); 14 15 foreach (X; AliasSeq!(OpenHashMap!(K, V, FNV!(64, true)))) 16 { 17 const VE n = 600; 18 19 auto x = X(); 20 21 { // scoped range 22 auto xkeys = x.byKey; 23 assert(xkeys.length == 0); 24 foreach (ref key; xkeys) 25 { 26 debug static assert(is(typeof(key) == const(K))); 27 assert(0); 28 } 29 foreach (ref key; X().byKey) 30 { 31 debug static assert(is(typeof(key) == const(K))); 32 assert(0); 33 } 34 } 35 36 foreach (immutable i; 0 .. n) 37 { 38 assert(x.length == i); 39 40 auto key = K(i); 41 auto value = V.withElements([VE(i)].s); 42 43 x[key] = value.dup; 44 assert(x.length == i + 1); 45 assert(x.contains(key)); 46 // TODO: assert(x.containsUsingLinearSearch(key)); 47 { 48 auto valuePtr = key in x; 49 assert(valuePtr && *valuePtr == value); 50 } 51 52 x.remove(key); 53 assert(x.length == i); 54 assert(!x.contains(key)); 55 assert(key !in x); 56 57 x[key] = value.dup; 58 assert(x.length == i + 1); 59 assert(x.contains(key)); 60 { 61 auto valuePtr = key in x; 62 assert(valuePtr && *valuePtr == value); 63 } 64 } 65 66 assert(x is x); 67 68 x = x.dup; 69 70 auto y = x.dup; 71 assert(x !is y); 72 assert(x.length == y.length); 73 74 assert(y == x); 75 assert(x == y); 76 77 foreach (ref key; x.byKey) 78 { 79 assert(x.contains(key)); 80 } 81 82 foreach (ref keyValue; x.byKeyValue) 83 { 84 assert(x.contains(keyValue.key)); 85 auto keyValuePtr = keyValue.key in x; 86 assert(keyValuePtr && 87 *keyValuePtr == keyValue.value); 88 } 89 90 foreach (immutable i; 0 .. n) 91 { 92 assert(x.length == n - i); 93 94 auto key = K(i); 95 auto value = V.withElements([VE(i)].s); 96 97 assert(x.contains(key)); 98 { 99 auto valuePtr = key in x; 100 assert(valuePtr && *valuePtr == value); 101 } 102 103 x.remove(key); 104 assert(!x.contains(key)); 105 assert(key !in x); 106 } 107 108 auto z = y.dup; 109 assert(y == z); 110 111 /* remove all elements in `y` using `removeAllMatching` and all elements 112 * in `z` using `removeAllMatching` */ 113 foreach (immutable i; 0 .. n) 114 { 115 assert(y.length == n - i); 116 assert(z.length == n - i); 117 118 auto key = K(i); 119 auto value = V.withElements([VE(i)].s); 120 121 assert(y.contains(key)); 122 { 123 auto valuePtr = key in y; 124 assert(valuePtr && *valuePtr == value); 125 } 126 assert(z.contains(key)); 127 { 128 auto valuePtr = key in z; 129 assert(valuePtr && *valuePtr == value); 130 } 131 132 y.remove(key); 133 assert(z.removeAllMatching!((const scope ref element) => element.key is key) == 1); 134 assert(y == z); 135 136 assert(!y.contains(key)); 137 assert(!z.contains(key)); 138 139 assert(key !in y); 140 assert(key !in z); 141 } 142 }
r-value and l-value intersection
import core.lifetime : move; import std.typecons : Nullable; import nxt.digestx.fnv : FNV; import nxt.array_help : s; version(showEntries) dbg(); alias K = Nullable!(uint, uint.max); alias X = OpenHashSet!(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.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
version(showEntries) dbg(); import std.typecons : Nullable; import nxt.digestx.fnv : FNV; import nxt.array_help : s; alias K = Nullable!(uint, uint.max); alias X = OpenHashSet!(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)));