import std.bigint;
import std.digest.crc;
import std.random : unpredictableSeed;
import std.range;
import std.stdio;
import lru : LRUCache;
import std.traits : isSomeString;

private BigInt positive(BigInt n) {
    if (n >= 0)
        return n * 2;
    else
        return -n * 2 - 1;
}

private BigInt pair(BigInt n, BigInt m) {
    // https://stackoverflow.com/a/919661
    return (positive(n) + positive(m)) * (positive(n) + positive(m) + 1) / 2 + positive(m);
}

struct Spot {
    private char _contents;
    private int _id;
    this(char c) {
        _contents = c;
    }

    this(char c, int id) {
        this(c);
        _id = id;
    }

    import std.format : format, formattedRead;

    string toString() {

        return format!`'%c' %d`(_contents, _id);
    }

    void fromString(Range)(auto ref Range s) {
        s.formattedRead!`'%c' %d`(_contents, _id);
    }

    @property contents() {
        return _contents;
    }

    @property id() {
        return _id;
    }

    bool opEqual(const Spot s) {
        return s._contents == _contents;
    }

    bool isSpace() {
        return _contents == ' ';
    }

    bool isRock() {
        return _contents == '*';
    }

    bool isPortal() {
        return _contents == '/';
    }
}

interface SpotSource {
    Spot opIndex(BigInt y, BigInt x);
    void save(File);
    void load(File);
}

class RandomSource : SpotSource {
    uint seed;
    double density = .00025;
    private LRUCache!(BigInt[2], Spot) cache;

    this() {
        seed = unpredictableSeed;
        cache = new LRUCache!(BigInt[2], Spot)(50000);
    }

    this(uint seed) {
        this.seed = seed;
    }

    this(uint seed, double density) {
        this.density = density;
        this(seed);
    }

    private uint hash(BigInt n) {
        CRC32 crc;
        crc.start();
        crc.put((cast(ubyte*)&seed)[0 .. seed.sizeof]);
        foreach (i; iota(n.ulongLength)) {
            auto digit = n.getDigit(i);
            crc.put((cast(ubyte*)&digit)[0 .. digit.sizeof]);
        }
        auto result = crc.finish();
        auto hash = *(cast(uint*)&result);
        return hash;
    }

    public Spot opIndex(BigInt y, BigInt x) {
        if ([y, x] in cache)
            return cache[[y, x]];
        auto roll = cast(double) hash(pair(y, x)) / uint.max;
        Spot ret;
        if (roll < density)
            ret = Spot('*');
        else
            ret = Spot(' ');
        cache[[y, x]] = ret;
        return ret;
    }

    public void save(File f) {
        f.writefln!"%d %f"(seed, density);
    }

    public void load(File f) {
        f.readf!"%d %f\n"(seed, density);
        cache = new LRUCache!(BigInt[2], Spot)(50000);
    }
}

class OverlaySource : SpotSource {
    private SpotSource _base;
    private Spot[BigInt[2]] _overlay;
    immutable private string terminator = "END OVERLAY\n";

    this(SpotSource base) {
        _base = base;
    }

    void opIndexAssign(Spot spot, BigInt y, BigInt x) {
        Spot* p = [y, x] in _overlay;
        if (p !is null && spot == _base[y, x]) {
            _overlay.remove([y, x]);
        } else {
            _overlay[[y, x]] = spot;
        }
    }

    Spot opIndex(BigInt y, BigInt x) {
        Spot* p = [y, x] in _overlay;
        if (p !is null)
            return *p;
        else
            return _base[y, x];
    }

    void save(File f) {
        _base.save(f);
        foreach (coord; _overlay.keys()) {
            f.writefln!"%s %s: %s"(coord[0], coord[1], _overlay[coord]);
        }
        f.write(terminator);
    }

    void load(File f) {
        import std.conv : to;
        import std.algorithm;

        //_overlay = _overlay.init;
        _base.load(f);
        foreach (char[] line; f.lines) {
            if (line == terminator)
                break;

            auto ints = line.until(':').array.splitter(' ').map!(to!BigInt);
            BigInt[2] coord;
            coord[0] = ints.front;
            ints.popFront;
            coord[1] = ints.front;

            auto s = Spot();
            s.fromString(line.find(':').find('\''));
            _overlay[coord] = s;
        }
    }

    unittest {
        auto base = new RandomSource(0, 0.0);
        auto src = new OverlaySource(base);
        src[BigInt(0), BigInt(0)] = Spot('*');
        src[BigInt(0), BigInt(1)] = Spot('*');
        assert(src[BigInt(0), BigInt(0)] == Spot('*'));
        assert(src[BigInt(0), BigInt(1)] == Spot('*'));
    }
}