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