x eagerly intersected with y. TODO move to container_algorithm.d.
exercise opEquals
1 import std.typecons : Nullable; 2 import nxt.digestx.fnv : FNV; 3 4 alias K = Nullable!(ulong, ulong.max); 5 alias X = OpenHashSet!(K, FNV!(64, true)); 6 7 const n = 100; 8 9 X a; 10 foreach (const i_; 0 .. n) 11 { 12 const i = 1113*i_; // insert in order 13 assert(!a.contains(K(i))); 14 assert(!a.containsUsingLinearSearch(K(i))); 15 assert(a.insertAndReturnElement(K(i)) == K(i)); 16 assert(a.contains(K(i))); 17 assert(a.containsUsingLinearSearch(K(i))); 18 } 19 20 X b; 21 foreach (const i_; 0 .. n) 22 { 23 const i = 1113*(n - 1 - i_); // insert in reverse 24 assert(!b.contains(K(i))); 25 assert(!b.containsUsingLinearSearch(K(i))); 26 assert(b.insertAndReturnElement(K(i)) == K(i)); 27 assert(b.contains(K(i))); 28 assert(b.containsUsingLinearSearch(K(i))); 29 } 30 31 assert(a == b); 32 33 // bin storage must be deterministic 34 () @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 import nxt.dynamic_array : Array = DynamicArray; 9 10 alias K = Nullable!(uint, uint.max); 11 12 alias VE = Nullable!(uint, uint.max); 13 alias V = OpenHashSet!(VE, FNV!(64, true)); 14 15 debug static assert(!mustAddGCRange!V); 16 17 foreach (X; AliasSeq!(OpenHashMap!(K, V, FNV!(64, true)))) 18 { 19 const VE n = 600; 20 21 auto x = X(); 22 23 { // scoped range 24 auto xkeys = x.byKey; 25 assert(xkeys.length == 0); 26 foreach (ref key; xkeys) 27 { 28 debug static assert(is(typeof(key) == const(K))); 29 assert(0); 30 } 31 foreach (ref key; X().byKey) 32 { 33 debug static assert(is(typeof(key) == const(K))); 34 assert(0); 35 } 36 } 37 38 foreach (immutable i; 0 .. n) 39 { 40 assert(x.length == i); 41 42 auto key = K(i); 43 auto value = V.withElements([VE(i)].s); 44 45 x[key] = value.dup; 46 assert(x.length == i + 1); 47 assert(x.contains(key)); 48 // TODO assert(x.containsUsingLinearSearch(key)); 49 { 50 auto valuePtr = key in x; 51 assert(valuePtr && *valuePtr == value); 52 } 53 54 x.remove(key); 55 assert(x.length == i); 56 assert(!x.contains(key)); 57 assert(key !in x); 58 59 x[key] = value.dup; 60 assert(x.length == i + 1); 61 assert(x.contains(key)); 62 { 63 auto valuePtr = key in x; 64 assert(valuePtr && *valuePtr == value); 65 } 66 } 67 68 assert(x is x); 69 70 x = x.dup; 71 72 auto y = x.dup; 73 assert(x !is y); 74 assert(x.length == y.length); 75 76 assert(y == x); 77 assert(x == y); 78 79 foreach (ref key; x.byKey) 80 { 81 assert(x.contains(key)); 82 } 83 84 foreach (ref keyValue; x.byKeyValue) 85 { 86 assert(x.contains(keyValue.key)); 87 auto keyValuePtr = keyValue.key in x; 88 assert(keyValuePtr && 89 *keyValuePtr == keyValue.value); 90 } 91 92 foreach (immutable i; 0 .. n) 93 { 94 assert(x.length == n - i); 95 96 auto key = K(i); 97 auto value = V.withElements([VE(i)].s); 98 99 assert(x.contains(key)); 100 { 101 auto valuePtr = key in x; 102 assert(valuePtr && *valuePtr == value); 103 } 104 105 x.remove(key); 106 assert(!x.contains(key)); 107 assert(key !in x); 108 } 109 110 auto z = y.dup; 111 assert(y == z); 112 113 /* remove all elements in `y` using `removeAllMatching` and all elements 114 * in `z` using `removeAllMatching` */ 115 foreach (immutable i; 0 .. n) 116 { 117 assert(y.length == n - i); 118 assert(z.length == n - i); 119 120 auto key = K(i); 121 auto value = V.withElements([VE(i)].s); 122 123 assert(y.contains(key)); 124 { 125 auto valuePtr = key in y; 126 assert(valuePtr && *valuePtr == value); 127 } 128 assert(z.contains(key)); 129 { 130 auto valuePtr = key in z; 131 assert(valuePtr && *valuePtr == value); 132 } 133 134 y.remove(key); 135 assert(z.removeAllMatching!((const scope ref element) => element.key is key) == 1); 136 assert(y == z); 137 138 assert(!y.contains(key)); 139 assert(!z.contains(key)); 140 141 assert(key !in y); 142 assert(key !in z); 143 } 144 }
r-value and l-value intersection
1 import core.lifetime : move; 2 import std.typecons : Nullable; 3 import nxt.digestx.fnv : FNV; 4 import nxt.array_help : s; 5 6 version(showEntries) dbg(); 7 alias K = Nullable!(uint, uint.max); 8 alias X = OpenHashSet!(K, FNV!(64, true)); 9 10 auto x = X(); 11 12 { // scoped range 13 foreach (ref xe; x.byElement) { assert(0); } 14 } 15 16 auto x0 = X.init; 17 assert(x0.length == 0); 18 assert(x0._store.length == 0); 19 assert(!x0.contains(K(1))); 20 21 auto x1 = X.withElements([K(12)].s); 22 assert(x1.length == 1); 23 assert(x1.contains(K(12))); 24 25 auto x2 = X.withElements([K(10), K(12)].s); 26 assert(x2.length == 2); 27 assert(x2.contains(K(10))); 28 assert(x2.contains(K(12))); 29 30 auto x3 = X.withElements([K(12), K(13), K(14)].s); 31 assert(x3.length == 3); 32 assert(x3.contains(K(12))); 33 assert(x3.contains(K(13))); 34 assert(x3.contains(K(14))); 35 36 auto z = X.withElements([K(10), K(12), K(13), K(15)].s); 37 assert(z.length == 4); 38 assert(z.contains(K(10))); 39 assert(z.contains(K(12))); 40 assert(z.contains(K(13))); 41 assert(z.contains(K(15))); 42 43 auto y = move(z).intersectedWith(x2); 44 assert(y.length == 2); 45 assert(y.contains(K(10))); 46 assert(y.contains(K(12))); 47 assert(y.containsUsingLinearSearch(K(10))); 48 assert(y.containsUsingLinearSearch(K(12)));
r-value and r-value intersection
1 version(showEntries) dbg(); 2 3 import std.typecons : Nullable; 4 import nxt.digestx.fnv : FNV; 5 import nxt.array_help : s; 6 7 alias K = Nullable!(uint, uint.max); 8 alias X = OpenHashSet!(K, FNV!(64, true)); 9 10 auto y = X.withElements([K(10), K(12), K(13), K(15)].s).intersectedWith(X.withElements([K(12), K(13)].s)); 11 assert(y.length == 2); 12 assert(y.contains(K(12))); 13 assert(y.contains(K(13))); 14 assert(y.containsUsingLinearSearch(K(12))); 15 assert(y.containsUsingLinearSearch(K(13)));