1 // RUNNABLE_PHOBOS_TEST
2 // PERMUTE_ARGS:
3
4 import std.algorithm : map;
5 import std.random : Random, uniform, unpredictableSeed;
6 import std.range : repeat;
7 import std.stdio : writeln;
8
9 // Quick, dirty and inefficient AA using linear search, useful for testing.
LinearAA(K,V)10 struct LinearAA(K, V) {
11 K[] keys;
12 V[] values;
13
14 V opIndex(K key) {
15 foreach(i, k; keys) {
16 if(k == key) {
17 return values[i];
18 }
19 }
20
21 assert(0, "Key not present.");
22 }
23
24 V opIndexAssign(V val, K key) {
25 foreach(i, k; keys) {
26 if(k == key) {
27 return values[i] = val;
28 }
29 }
30
31 keys ~= key;
32 values ~= val;
33 return val;
34 }
35
36 V* opIn_r(K key) {
37 foreach(i, k; keys) {
38 if(key == k) {
39 return values.ptr + i;
40 }
41 }
42
43 return null;
44 }
45
46 void remove(K key) {
47 size_t i = 0;
48 for(; i < keys.length; i++) {
49 if(keys[i] == key) {
50 break;
51 }
52 }
53
54 assert(i < keys.length);
55
56 for(; i < keys.length - 1; i++) {
57 keys[i] = keys[i + 1];
58 values[i] = values[i + 1];
59 }
60
61 keys = keys[0..$ - 1];
62 values = values[0..$ - 1];
63 }
64
65 size_t length() {
66 return values.length;
67 }
68 }
69
main()70 void main() {
71 Random gen;
72 uint[] seed;
73 gen.seed(map!((a) {
74 seed ~= unpredictableSeed;
75 return seed[$-1]; })(repeat(0)));
76 writeln(seed);
77 foreach(iter; 0..10) { // Bug only happens after a few iterations.
78 writeln(iter);
79 uint[size_t] builtin;
80 LinearAA!(size_t, uint) linAA;
81 uint[] nums = new uint[100_000];
82 foreach(ref num; nums) {
83 num = uniform(0U, uint.max, gen);
84 }
85
86 foreach(i; 0..10_000) {
87 auto index = uniform(0, nums.length, gen);
88 if(index in builtin) {
89 assert(index in linAA);
90 assert(builtin[index] == nums[index]);
91 assert(linAA[index] == nums[index]);
92 builtin.remove(index);
93 linAA.remove(index);
94 } else {
95 assert(!(index in linAA));
96 builtin[index] = nums[index];
97 linAA[index] = nums[index];
98 }
99 }
100
101 assert(builtin.length == linAA.length);
102 foreach(k, v; builtin) {
103 assert(k in linAA);
104 assert(*(k in builtin) == *(k in linAA));
105 assert(linAA[k] == v);
106 }
107 }
108 }
109
110