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;
    this(char c)
    {
        _contents = c;
    }

    string toString()
    {
        import std.format : format;

        return format("'%c'", _contents);
    }

    void fromString(S)(S s) if (isSomeString!S)
    {
        _contents = cast(char) s[1];
    }

    @property contents()
    {
        return _contents;
    }

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

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

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

class RandomSource : SpotSource
{
    uint seed;
    double density = .0025;
    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.iteration;

        _base.load(f);
        foreach (char[] line; f.lines)
        {
            if (line == terminator)
                break;
            auto trim = line.filter!(a => a == ' ' || a == '\r' || a == '\n').array;
            auto parts = trim.splitter(':');
            auto ints = parts.moveFront.splitter(',').map!(to!BigInt);
            BigInt[2] coord;
            coord[0] = ints.moveFront;
            coord[1] = ints.front;
            auto s = new Spot();
            (*s).fromString(parts.front);
            _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('*'));
    }
}