// PERMUTE_ARGS:
// TRANSFORM_OUTPUT: remove_lines("warning: rand\(\) may return deterministic values")

// 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* opBinaryRight(string op : "in")(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;
    }
}

extern (C) int rand();

uint random(const uint max = uint.max)
{
    version (Windows)
    {
        // RAND_MAX is quite low for windows, extend the range by
        // abusing multiple random values and rounding errors.
        const a = rand(), b = rand();
        const c = a < b ? double(a) / b : double(b) / a;
        return (cast(int) (c * max)) % max;
    }
    else
        return rand() % max;
}

void main()
{
    foreach(iter; 0..10) {  // Bug only happens after a few iterations.

        uint[size_t] builtin;
        LinearAA!(size_t, uint) linAA;
        uint[] nums = new uint[100_000];
        foreach(ref num; nums) {
            num = random();
        }

        foreach(i; 0..10_000) {
            auto index = random(cast(uint) nums.length);
            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);
        }
    }
}