// RUNNABLE_PHOBOS_TEST // PERMUTE_ARGS: import std.algorithm : map; import std.random : Random, uniform, unpredictableSeed; import std.range : repeat; import std.stdio : writeln; // Quick, dirty and inefficient AA using linear search, useful for testing. struct LinearAA(K, V) { K[] keys; V[] values; V opIndex(K key) { foreach(i, k; keys) { if(k == key) { return values[i]; } } assert(0, "Key not present."); } V opIndexAssign(V val, K key) { foreach(i, k; keys) { if(k == key) { return values[i] = val; } } keys ~= key; values ~= val; return val; } V* opIn_r(K key) { foreach(i, k; keys) { if(key == k) { return values.ptr + i; } } return null; } void remove(K key) { size_t i = 0; for(; i < keys.length; i++) { if(keys[i] == key) { break; } } assert(i < keys.length); for(; i < keys.length - 1; i++) { keys[i] = keys[i + 1]; values[i] = values[i + 1]; } keys = keys[0..$ - 1]; values = values[0..$ - 1]; } size_t length() { return values.length; } } void main() { Random gen; uint[] seed; gen.seed(map!((a) { seed ~= unpredictableSeed; return seed[$-1]; })(repeat(0))); writeln(seed); foreach(iter; 0..10) { // Bug only happens after a few iterations. writeln(iter); uint[size_t] builtin; LinearAA!(size_t, uint) linAA; uint[] nums = new uint[100_000]; foreach(ref num; nums) { num = uniform(0U, uint.max, gen); } foreach(i; 0..10_000) { auto index = uniform(0, nums.length, gen); if(index in builtin) { assert(index in linAA); assert(builtin[index] == nums[index]); assert(linAA[index] == nums[index]); builtin.remove(index); linAA.remove(index); } else { assert(!(index in linAA)); builtin[index] = nums[index]; linAA[index] = nums[index]; } } assert(builtin.length == linAA.length); foreach(k, v; builtin) { assert(k in linAA); assert(*(k in builtin) == *(k in linAA)); assert(linAA[k] == v); } } }