test various things
1 version(showEntries) dbg(); 2 const n = 100; 3 4 void testEmptyAll(K, V, X)(ref X x, size_t n, 5 scope K[] keys) 6 { 7 assert(x.length == n); 8 foreach (key; keys) 9 { 10 static if (X.hasValue) 11 { 12 const element = X.ElementType(key, V.init); 13 } 14 else 15 { 16 alias element = key; 17 } 18 19 assert(x.length == n - key.get); 20 21 const hitPtr = key in x; 22 static if (X.hasValue) 23 { 24 assert(hitPtr && *hitPtr is element.value); 25 } 26 else 27 { 28 assert(hitPtr && *hitPtr is element); 29 } 30 31 assert(x.remove(key)); 32 assert(x.length == n - key.get - 1); 33 34 static if (!X.hasValue) 35 { 36 assert(!x.contains(key)); 37 assert(!x.containsUsingLinearSearch(key)); 38 } 39 assert(key !in x); 40 assert(!x.remove(key)); 41 assert(x.length == n - key.get - 1); 42 } 43 44 assert(x.length == 0); 45 46 x.clear(); 47 assert(x.length == 0); 48 } 49 50 X testDup(X)(scope ref X x, size_t n) 51 { 52 typeof(return) y = x.dup; 53 54 assert(x._store.ptr !is y._store.ptr); 55 assert(x.length == y.length); 56 assert(y.length == n); 57 // non-symmetric algorithm so both are needed 58 assert(y == x); 59 assert(x == y); 60 61 static if (X.hasValue) 62 { 63 assert(equal(x.byKey, 64 y.byKey)); 65 assert(equal(x.byValue, 66 y.byValue)); 67 assert(equal(x.byKeyValue, 68 y.byKeyValue)); 69 } 70 else 71 { 72 assert(equal(x.byElement, 73 y.byElement)); 74 } 75 76 debug static assert(!__traits(compiles, { const _ = x < y; })); // no ordering 77 78 return y; 79 } 80 81 alias NullableUlong = Nullable!(ulong, ulong.max); 82 83 static class SomeSimpleClass 84 { 85 @safe pure nothrow @nogc 86 this(ulong value) 87 { 88 this._value = value; 89 } 90 91 @safe pure nothrow @nogc 92 ulong get() const 93 { 94 return _value; 95 } 96 97 @property void toString(scope void delegate(scope const(char)[]) sink) const 98 { 99 import std.format : formattedWrite; 100 sink.formattedWrite(typeof(this).stringof, "(%s)", _value); 101 } 102 103 @property bool opEquals(const scope typeof(this) rhs) const 104 { 105 return _value == rhs._value; 106 } 107 108 private ulong _value; 109 } 110 111 debug static assert(mustAddGCRange!string); 112 113 foreach (K; AliasSeq!(SomeSimpleClass, 114 NullableUlong)) 115 { 116 foreach (V; AliasSeq!(string, 117 int, 118 void)) 119 { 120 alias X = OpenHashMapOrSet!(K, V, FNV!(64, true)); 121 122 auto k11 = make!K(11); 123 auto k12 = make!K(12); 124 auto k13 = make!K(13); 125 126 static if (!X.hasValue) 127 { 128 auto x = X.withElements([k11, k12, k13].s); 129 130 import std.algorithm : count; 131 132 // ByLvalueElement 133 auto xr = x.byElement; 134 135 alias R = typeof(xr); 136 import std.range.primitives : isInputRange; 137 import std.traits : ReturnType; 138 debug static assert(is(typeof(R.init) == R)); 139 debug static assert(is(ReturnType!((R xr) => xr.empty) == bool)); 140 141 debug static assert(!__traits(compiles, { xr.front == K.init; })); // always head-const 142 auto f = xr.front; 143 static if (is(K == class)) 144 { 145 debug static assert(is(typeof(f) == K)); // tail-mutable 146 } 147 else 148 { 149 debug static assert(is(typeof(f) == const(K))); // tail-const 150 } 151 152 debug static assert(is(typeof((R xr) => xr.front))); 153 debug static assert(!is(ReturnType!((R xr) => xr.front) == void)); 154 debug static assert(is(typeof((R xr) => xr.popFront))); 155 156 debug static assert(isInputRange!(typeof(xr))); 157 158 assert(x.byElement.count == 3); 159 160 X y; 161 size_t ix = 0; 162 foreach (ref e; x.byElement) 163 { 164 assert(x.contains(e)); 165 assert(x.containsUsingLinearSearch(e)); 166 assert(!y.contains(e)); 167 assert(!y.containsUsingLinearSearch(e)); 168 static if (is(K == class)) 169 { 170 y.insert(cast(K)e); // ugly but ok in tests 171 } 172 else 173 { 174 y.insert(e); 175 } 176 assert(y.contains(e)); 177 assert(y.containsUsingLinearSearch(e)); 178 ix++; 179 } 180 181 assert(y.byElement.count == 3); 182 assert(x == y); 183 184 const z = X(); 185 assert(z.byElement.count == 0); 186 187 immutable w = X(); 188 assert(w.byElement.count == 0); 189 190 { 191 auto xc = X.withElements([k11, k12, k13].s); 192 assert(xc.length == 3); 193 assert(xc.contains(k11)); 194 assert(xc.containsUsingLinearSearch(k11)); 195 196 // TODO http://forum.dlang.org/post/kvwrktmameivubnaifdx@forum.dlang.org 197 xc.removeAllMatching!(_ => _ == k11); 198 199 assert(xc.length == 2); 200 assert(!xc.contains(k11)); 201 assert(!xc.containsUsingLinearSearch(k11)); 202 203 xc.removeAllMatching!(_ => _ == k12); 204 assert(!xc.contains(k12)); 205 assert(!xc.containsUsingLinearSearch(k12)); 206 assert(xc.length == 1); 207 208 xc.removeAllMatching!(_ => _ == k13); 209 assert(!xc.contains(k13)); 210 assert(!xc.containsUsingLinearSearch(k13)); 211 assert(xc.length == 0); 212 213 // this is ok 214 foreach (e; xc.byElement) {} 215 } 216 217 { // ByRvalueElement 218 auto k = X.withElements([k11, k12].s).filtered!(_ => _ != k11).byElement; 219 debug static assert(isInputRange!(typeof(k))); 220 assert(k.front == k12); 221 222 debug static assert(!__traits(compiles, { k.front = K.init; })); // head-const 223 static if (is(K == class)) 224 { 225 debug static assert(is(typeof(k.front) == K)); // tail-mutable 226 } 227 else 228 { 229 debug static assert(is(typeof(k.front) == const(K))); // tail-const 230 } 231 232 k.popFront(); 233 assert(k.empty); 234 } 235 236 { 237 X q; 238 auto qv = [make!K(11U), make!K(12U), make!K(13U), make!K(14U)].s; 239 q.insertN(qv[]); 240 foreach (e; qv[]) 241 { 242 assert(q.contains(e)); 243 assert(q.containsUsingLinearSearch(e)); 244 } 245 q.clear(); 246 assert(q.empty); 247 } 248 } 249 250 static if (is(V == string)) 251 { 252 debug static assert(mustAddGCRange!V); 253 debug static assert(mustAddGCRange!(V[1])); 254 debug static assert(mustAddGCRange!(X.T)); 255 } 256 257 auto x1 = X(); // start empty 258 259 // fill x1 260 261 import std.array : Appender; 262 Appender!(K[]) keys; 263 264 foreach (immutable key_; 0 .. n) 265 { 266 auto key = make!K(key_); 267 keys.put(key); 268 269 // create elements 270 static if (X.hasValue) 271 { 272 auto value = V.init; 273 auto element = X.ElementType(key, value); 274 } 275 else 276 { 277 // no assignment because Nullable.opAssign may leave rhs in null state 278 auto element = key; 279 } 280 281 assert(key !in x1); 282 283 assert(x1.length == key.get); 284 assert(x1.insert(element) == X.InsertionStatus.added); 285 assert(x1.length == key.get + 1); 286 287 static if (X.hasValue) 288 { 289 import std.conv : to; 290 auto e2 = X.ElementType(key, (42 + key_).to!V); 291 assert(x1.insert(e2) == X.InsertionStatus.modified); 292 assert(x1.contains(key)); 293 assert(x1.get(key, V.init) == (42 + key_).to!V); 294 295 assert(x1.remove(key)); 296 assert(!x1.contains(key)); 297 298 x1[key] = value; // restore value 299 assert(x1.contains(key)); 300 } 301 302 assert(x1.length == key.get + 1); 303 304 const hitPtr = key in x1; 305 static if (X.hasValue) 306 { 307 assert(hitPtr && *hitPtr == value); 308 } 309 else 310 { 311 assert(hitPtr && *hitPtr is key); 312 } 313 314 auto status = x1.insert(element); 315 assert(status == X.InsertionStatus.unmodified); 316 static if (X.hasValue) 317 { 318 assert(x1.insert(key, value) == X.InsertionStatus.unmodified); 319 } 320 assert(x1.length == key.get + 1); 321 322 assert(key in x1); 323 } 324 325 static if (X.hasValue) 326 { 327 import nxt.dynamic_array : Array = DynamicArray; 328 Array!(X.ElementType) a1; // remember the keys 329 330 foreach (const ref key; x1.byKey) 331 { 332 auto keyPtr = key in x1; 333 assert(keyPtr); 334 a1 ~= X.ElementType(cast(K)key, (*keyPtr)); 335 } 336 337 assert(x1.length == a1.length); 338 339 foreach (ae; a1[]) 340 { 341 auto keyPtr = ae.key in x1; 342 assert(keyPtr); 343 assert((*keyPtr) is ae.value); 344 } 345 } 346 347 assert(x1.length == n); 348 349 auto x2 = testDup(x1, n); 350 351 testEmptyAll!(K, V)(x1, n, keys.data); 352 353 testEmptyAll!(K, V)(x2, n, keys.data); // should be not affected by emptying of x1 354 } 355 }
version(showEntries) dbg(); alias X = OpenHashMapOrSet!(Nullable!(size_t, size_t.max), size_t, FNV!(64, true)); import nxt.dynamic_array : Array = DynamicArray; X x; // TODO these segfault: // TODO auto a = Array!(X.KeyType).withElementsOfRange_untested(x.byKey); // l-value byKey // TODO auto b = Array!(X.KeyType).withElementsOfRange_untested(X().byKey); // r-value byKey
manual Nullable type
static class Zing { @safe pure nothrow @nogc: this(ulong value) { this._value = value; } private ulong _value; } debug static assert(isNullable!Zing); enum Alt { unknown, a, b, c, d } struct ZingRelation { Zing zing; Alt alts; alias nullifier = zing; static immutable nullValue = typeof(this).init; bool opEquals(const scope typeof(this) that) const @safe pure nothrow @nogc { return (this.zing is that.zing && this.alts == that.alts); } } debug static assert(isNullable!ZingRelation); alias X = OpenHashSet!(ZingRelation, FNV!(64, true)); debug static assert(X.sizeof == 32); // TODO fix hole handling and change to 24 X x; auto e = ZingRelation(new Zing(42), Alt.init); assert(!x.contains(e)); assert(!x.containsUsingLinearSearch(e)); assert(x.insert(e) == X.InsertionStatus.added); assert(x.contains(e)); assert(x.containsUsingLinearSearch(e));
abstract class value type
static abstract class Zing { @safe pure nothrow @nogc: } static class Node : Zing { @safe pure nothrow @nogc: } alias X = OpenHashSet!(Zing); X x; const Zing cz = new Node(); x.insert(cz); // ok to insert const Zing z = new Node(); x.insert(z); // ok to insert mutable because hashing is on address by default
class type with default hashing
1 static class Base 2 { 3 static size_t dtorCount = 0; // number of calls to this destructor 4 @safe nothrow @nogc: 5 ~this() @nogc { dtorCount += 1; } 6 pure: 7 this(ulong value) { this._value = value; } 8 @property bool opEquals(const scope typeof(this) rhs) const 9 { 10 return _value == rhs._value; 11 } 12 override hash_t toHash() const 13 { 14 return hashOf(_value); 15 } 16 private ulong _value; 17 } 18 19 /** Node containing same data members but different type. */ 20 static class Node : Base 21 { 22 @safe pure nothrow @nogc: 23 this(ulong value) { super(value); } 24 } 25 debug static assert(is(Node : Base)); 26 27 import nxt.hash_functions : hashOfPolymorphic; // neede to separate hash of `Base(N)` from `Node(N)` 28 alias X = OpenHashSet!(Base, hashOfPolymorphic, "a && b && (typeid(a) is typeid(b)) && a.opEquals(b)"); 29 debug static assert(X.sizeof == 24); 30 X x; 31 32 // top-class 33 auto b42 = new Base(42); 34 assert(!x.contains(b42)); 35 assert(!x.containsUsingLinearSearch(b42)); 36 assert(x.insert(b42) == X.InsertionStatus.added); 37 assert(x.contains(b42)); 38 assert(x.containsUsingLinearSearch(b42)); 39 assert(x.tryGetElementFromCtorParams!Base(42) !is null); 40 assert(Base.dtorCount == 1); 41 assert(x.tryGetElementFromCtorParams!Base(42)._value == 42); 42 assert(Base.dtorCount == 2); 43 assert(x.tryGetElementFromCtorParams!Base(41) is null); 44 assert(Base.dtorCount == 3); 45 46 // top-class 47 const b43 = new Base(43); 48 assert(!x.contains(b43)); 49 assert(!x.containsUsingLinearSearch(b43)); 50 assert(x.insert(b43) == X.InsertionStatus.added); 51 assert(x.contains(b43)); 52 assert(x.containsUsingLinearSearch(b43)); 53 assert(x.tryGetElementFromCtorParams!Base(43) !is null); 54 assert(Base.dtorCount == 4); 55 assert(x.tryGetElementFromCtorParams!Base(43)._value == 43); 56 assert(Base.dtorCount == 5); 57 58 // sub-class 59 assert(x.tryGetElementFromCtorParams!Node(42) is null); 60 assert(Base.dtorCount == 6); 61 immutable n42 = new Node(42); 62 assert(!x.contains(n42)); // mustn't equal to `b42` 63 assert(!x.containsUsingLinearSearch(n42)); // mustn't equal to `b42` 64 assert(x.insert(n42) == X.InsertionStatus.added); // added as separate type 65 assert(x.contains(n42)); 66 assert(x.containsUsingLinearSearch(n42)); 67 assert(x.tryGetElementFromCtorParams!Node(42) !is null); 68 assert(Base.dtorCount == 7); 69 assert(x.tryGetElementFromCtorParams!Node(42)._value == 42); 70 assert(Base.dtorCount == 8); 71 72 assert(hashOf(b42) == hashOf(n42)); 73 74 // sub-class 75 assert(x.tryGetElementFromCtorParams!Node(43) is null); 76 assert(Base.dtorCount == 9); 77 auto n43 = new Node(43); 78 assert(!x.contains(n43)); // mustn't equal to `b43` 79 assert(!x.containsUsingLinearSearch(n43)); // mustn't equal to `b43` 80 assert(x.insert(n43) == X.InsertionStatus.added); // added as separate type 81 assert(x.contains(n43)); 82 assert(x.containsUsingLinearSearch(n43)); 83 assert(x.tryGetElementFromCtorParams!Node(43) !is null); 84 assert(Base.dtorCount == 10); 85 assert(x.tryGetElementFromCtorParams!Node(43)._value == 43); 86 assert(Base.dtorCount == 11); 87 88 assert(hashOf(b43) == hashOf(n43));
enumeration key
enum Alt { nullValue, // trait a, b, c, d } alias X = OpenHashSet!(Alt, FNV!(64, true)); X x; assert(!x.contains(Alt.a)); assert(x.insert(Alt.a) == X.InsertionStatus.added); assert(x.contains(Alt.a)); assert(x.containsUsingLinearSearch(Alt.a)); assert(!x.contains(Alt.b)); assert(!x.contains(Alt.c)); assert(!x.contains(Alt.d)); assert(!x.containsUsingLinearSearch(Alt.b)); assert(!x.containsUsingLinearSearch(Alt.c)); assert(!x.containsUsingLinearSearch(Alt.d)); assert(x.remove(Alt.a)); assert(!x.contains(Alt.a)); assert(!x.containsUsingLinearSearch(Alt.a));
static struct Rel { static immutable nullValue = typeof(this).init; string name; // relation name. WARNING compiler crashes when qualified with `package` } alias X = OpenHashSet!(Rel, FNV!(64, true)); X x; foreach (const i; 0 .. 100) { const char[1] ch = ['a' + i]; assert(!x.contains(Rel(ch.idup))); assert(!x.containsUsingLinearSearch(Rel(ch.idup))); x.insert(Rel(ch.idup)); assert(x.contains(Rel(ch.idup))); /* TODO assert(x.containsUsingLinearSearch(Rel(ch.idup))); */ }
SSOString as set key type
1 import nxt.sso_string : SSOString; 2 alias K = SSOString; 3 static assert(isHoleable!K); 4 alias X = OpenHashSet!(K, FNV!(64, true)); 5 const n = 100; 6 7 X a; 8 foreach (const i; 0 .. n) 9 { 10 const char[1] ch = ['a' + i]; 11 const k = K(ch); // @nogc 12 13 assert(!a.contains(k)); 14 assert(!a.containsUsingLinearSearch(k)); 15 16 assert(a.insert(K(ch)) == X.InsertionStatus.added); 17 // TODO assert(a.insertAndReturnElement(K(ch)) == k); 18 assert(a.contains(k)); 19 assert(a.containsUsingLinearSearch(k)); 20 21 assert(a.remove(k)); 22 assert(!a.contains(k)); 23 assert(a.insert(K(ch)) == X.InsertionStatus.added); 24 25 assert(a.remove(ch[])); 26 assert(!a.contains(k)); 27 assert(a.insert(K(ch)) == X.InsertionStatus.added); 28 } 29 30 X b; 31 foreach (const i; 0 .. n) 32 { 33 const char[1] ch = ['a' + (n - 1 - i)]; 34 const k = K(ch); // @nogc 35 36 assert(!b.contains(k)); 37 assert(!b.containsUsingLinearSearch(k)); 38 39 assert(b.insert(K(ch)) == X.InsertionStatus.added); 40 // TODO assert(b.insertAndReturnElement(K(ch)) == k); 41 42 assert(b.contains(k)); 43 assert(b.containsUsingLinearSearch(k)); 44 45 assert(b.remove(k)); 46 assert(!b.contains(k)); 47 48 assert(b.insert(K(ch)) == X.InsertionStatus.added); 49 } 50 51 assert(a == b); 52 53 const us = K("_"); 54 assert(!a.contains(us)); 55 a ~= us; 56 assert(a.contains(us));
test opIndexOpAssign
import nxt.sso_string : SSOString; alias K = SSOString; alias V = long; alias X = OpenHashMap!(K, V, FNV!(64, true)); X x; const a = K("a"); const b = K("b"); x[a] = 17; assert(x[a] == 17); x[a] += 10; // opIndexOpAssign!("+=") with existing key assert(x[a] == 27); x[b] += 10; // opIndexOpAssign!("+=") with non-existing key assert(x[b] == 10); x[b] *= 10; // opIndexOpAssign!("*=") with non-existing key assert(x[b] == 100); assert(x.length == 2); assert(x.contains(a)); assert(x.contains(a[])); assert(a in x); assert(a[] in x); assert(x.contains(b)); assert(x.contains(b[])); assert(b in x); assert(b[] in x); const c = K("c"); assert(!x.contains(c)); assert(!x.contains(c[])); assert(c !in x); assert(c[] !in x);
SSOString as map key type
1 import nxt.sso_string : SSOString; 2 alias K = SSOString; 3 alias V = long; 4 alias X = OpenHashMap!(K, V, FNV!(64, true)); 5 const n = 100; 6 7 immutable default_k = K("miss"); 8 9 X a; 10 11 // insert all 12 foreach (const i; 0 .. n) 13 { 14 const char[1] ch = ['a' + i]; 15 const k = K(ch); // @nogc 16 assert(k[] == ch[]); 17 18 assert(!a.contains(k)); 19 assert(!a.contains(ch[])); // @nogc 20 assert(a.getKeyRef(k, default_k)[] is default_k[]); // on miss use `default_k` 21 // TODO assert(a.getKeyRef(ch, default_k)[] is default_k[]); // on miss use `default_k` 22 23 a[k] = V.init; 24 25 assert(a.contains(k)); 26 assert(a.contains(ch[])); // @nogc 27 assert(a.getKeyRef(k, default_k)[] !is k[]); // on hit doesn't use `default_k` 28 assert(a.getKeyRef(k, default_k)[] == ch); 29 // TODO assert(a.getKeyRef(ch, default_k)[] !is k[]); // on hit doesn't use `default_k` 30 // assert(a.getKeyRef(ch, default_k)[] == ch); 31 } 32 assert(a.length == n); 33 34 // remove all 35 foreach (const i; 0 .. n) 36 { 37 const char[1] ch = ['a' + i]; 38 const k = K(ch); // @nogc 39 assert(a.contains(k)); 40 assert(a.remove(k)); 41 assert(!a.contains(k)); 42 } 43 assert(a.length == 0); 44 45 // insert all again 46 foreach (const i; 0 .. n) 47 { 48 const char[1] ch = ['a' + i]; 49 const k = K(ch); // @nogc 50 assert(k[] == ch[]); 51 52 assert(!a.contains(k)); 53 assert(!a.contains(ch[])); // @nogc 54 assert(a.getKeyRef(k, default_k)[] is default_k[]); // on miss use `default_k` 55 // TODO assert(a.getKeyRef(ch, default_k)[] is default_k[]); // on miss use `default_k` 56 57 a[k] = V.init; 58 } 59 assert(a.length == n); 60 61 X b; 62 foreach (const i; 0 .. n) 63 { 64 const char[1] ch = ['a' + (n - 1 - i)]; 65 const k = K(ch); // @nogc 66 67 assert(!b.contains(k)); 68 69 b[k] = V.init; 70 71 assert(b.contains(k)); 72 } 73 74 assert(a == b);