created drocks

4 files changed, 640 insertions, 0 deletions

diff --git a/source/app.d b/source/app.d
new file mode 100644
index 0000000..4006188
--- /dev/null
+++ b/source/app.d
@@ -0,0 +1,80 @@
+import deimos.ncurses;
+import std.string : toStringz;
+import core.stdc.locale;
+import std.format;
+import board;
+import spots;
+
+void main()
+{
+    setlocale(LC_CTYPE, ""); // ncurses locales are weird
+
+    auto stdscr = initscr();
+    scope (exit)
+        endwin();
+    cbreak(); // disables line buffering for input
+    noecho(); // input doesn't display on-screen
+    intrflush(stdscr, true);
+    keypad(stdscr, true); // allows arrow keys to work
+    scrollok(stdscr, true); // allows scrolling in up/down arrows
+    nonl(); // "return" goes through input
+
+    int x;
+    int y;
+    getmaxyx(stdscr, y, x);
+
+    auto overlay = new OverlaySource(new RandomSource());
+    auto board = new Board(overlay);
+    auto disp = new BoardDisplay(board, stdscr);
+    disp.print();
+    int rocks = 0;
+    disp.status = "0";
+    refresh();
+
+    outer: while (true)
+    {
+        auto c = getch();
+        switch (c)
+        {
+        case ',':
+        case KEY_UP:
+            disp.up();
+            break;
+        case 'o':
+        case KEY_DOWN:
+            disp.down();
+            break;
+        case 'e':
+        case KEY_RIGHT:
+            disp.right();
+            break;
+        case 'a':
+        case KEY_LEFT:
+            disp.left();
+            break;
+        case KEY_RESIZE:
+            disp.getdims();
+            break;
+        case ' ':
+            if (overlay[disp.y, disp.x].isRock())
+            {
+                overlay[disp.y, disp.x] = Spot(' ');
+                rocks++;
+                disp.status = format("%d", rocks);
+                disp.print();
+            }
+            else if (rocks > 0)
+            {
+                overlay[disp.y, disp.x] = Spot('*');
+                rocks--;
+                disp.status = format("%d", rocks);
+                disp.print();
+            }
+            break;
+        case 'q':
+            break outer;
+        default:
+            continue;
+        }
+    }
+}
diff --git a/source/board.d b/source/board.d
new file mode 100644
index 0000000..9ec996b
--- /dev/null
+++ b/source/board.d
@@ -0,0 +1,241 @@
+import std.bigint;
+import deimos.ncurses;
+import std.string : toStringz;
+import std.math : floor, ceil;
+import std.array : appender;
+import std.range;
+import std.format;
+import std.stdio;
+import spots : Spot, SpotSource;
+
+public class Board
+{
+    private SpotSource _source;
+    // uint seed;
+    // indexed as Spot = Board[y, x]
+
+    this(SpotSource source)
+    {
+        _source = source;
+    }
+
+    Spot opIndex(BigInt y, BigInt x)
+    {
+        return _source[y, x];
+    }
+
+    Spot opIndex(long y, long x)
+    {
+        // possible per improvements
+        return opIndex(BigInt(y), BigInt(x));
+    }
+
+    PartialBoard opIndex(BigInt[2] y, BigInt[2] x)
+    {
+        return new PartialBoard(y, x, _source);
+    }
+
+    PartialBoard opIndex(long[2] y, long[2] x)
+    {
+        return opIndex([BigInt(y[0]), BigInt(y[1])], [
+                BigInt(x[0]), BigInt(x[1])
+                ]);
+    }
+
+    PartialBoard opIndex(BigInt[2] y, BigInt x)
+    {
+        return opIndex(y, [x, x + 1]);
+    }
+
+    PartialBoard opIndex(long[2] y, long x)
+    {
+        return opIndex([BigInt(y[0]), BigInt(y[1])], BigInt(x));
+    }
+
+    PartialBoard opIndex(BigInt y, BigInt[2] x)
+    {
+        return opIndex([y, y + 1], x);
+    }
+
+    PartialBoard opIndex(long y, long[2] x)
+    {
+        return opIndex(BigInt(y), [BigInt(x[0]), BigInt(x[1])]);
+    }
+
+    BigInt[2] opSlice(size_t dimension)(BigInt x, BigInt y)
+            if (dimension >= 0 && dimension < 2)
+    {
+        return [x, y];
+    }
+
+    long[2] opSlice(size_t dimension)(long x, long y)
+            if (dimension >= 0 && dimension < 2)
+    {
+        return [x, y];
+    }
+    // be more generic. instead of long use T where IsIntegral!T
+}
+
+enum Edge
+{
+    LEFT,
+    RIGHT,
+    TOP,
+    BOT,
+}
+
+class BoardDisplay
+{
+    private Board _board;
+    private WINDOW* _window;
+    private int _height, _width;
+    private string _status;
+    BigInt x = 0;
+    BigInt y = 0;
+
+    this(Board board, WINDOW* window)
+    {
+        _board = board;
+        _window = window;
+        getdims();
+    }
+
+    public void getdims()
+    {
+        getmaxyx(_window, _height, _width);
+    }
+
+    private void center()
+    {
+        mvprintw(_height, 0, toStringz(_status ~ " ".replicate(_width - status.length)));
+        move(cast(int) ceil(_height / 2.0), cast(int) ceil(_width / 2.0));
+    }
+
+    @property string status()
+    {
+        return _status;
+    }
+
+    @property status(string s)
+    {
+        _status = s;
+        center();
+    }
+
+    private BigInt edge(Edge e)
+    { // templating??
+        switch (e)
+        {
+        case Edge.LEFT:
+            return BigInt(cast(int) floor(-_width / 2.0)) + x;
+        case Edge.RIGHT:
+            return BigInt(cast(int) floor(_width / 2.0)) + x;
+        case Edge.TOP:
+            return BigInt(cast(int) floor(-_height / 2.0)) + y;
+        case Edge.BOT:
+            return BigInt(cast(int) floor(_height / 2.0)) + y;
+        default:
+            assert(0);
+        }
+    }
+
+    void print()
+    {
+        import std.stdio;
+        import std.datetime;
+
+        mvprintw(0, 0, toStringz(_board[edge(Edge.TOP) .. edge(Edge.BOT),
+                    edge(Edge.LEFT) .. edge(Edge.RIGHT)].toString()));
+        center();
+    }
+
+    void up()
+    { // the cursor moves up, the map scrolls down, leaving an empty line at top
+        y--;
+        scrl(-1);
+        mvprintw(0, 0, toStringz(_board[edge(Edge.TOP),
+                    edge(Edge.LEFT) .. edge(Edge.RIGHT)].toString()));
+        center();
+    }
+
+    void down()
+    {
+        y++;
+        scrl(1);
+        mvprintw(_height - 1, 0, toStringz(_board[edge(Edge.BOT) - 1,
+                    // necessary because opSlice is exclusive
+                    edge(Edge.LEFT) .. edge(Edge.RIGHT)].toString()));
+        center();
+    }
+
+    void left()
+    {
+        x--;
+        print();
+    }
+
+    void right()
+    {
+        x++;
+        print();
+    }
+}
+
+unittest
+{
+    import std.stdio;
+    import std.datetime;
+    import lru : LRUCache;
+    import spots : RandomSource, OverlaySource;
+
+    SysTime starttime = Clock.currTime();
+    auto random = new RandomSource();
+    auto source = new OverlaySource(random);
+    foreach (j; iota(100))
+    {
+        foreach (i; iota(400))
+        {
+            source[BigInt(i), BigInt(0)];
+        }
+    }
+    writeln(Clock.currTime() - starttime);
+    foreach (j; iota(100))
+    {
+        foreach (i; iota(400))
+        {
+            random[BigInt(i), BigInt(0)];
+        }
+    }
+    writeln(Clock.currTime() - starttime);
+}
+
+class PartialBoard : Board
+{
+    private BigInt[2] _yrange, _xrange;
+    this(BigInt[2] y, BigInt[2] x, SpotSource source)
+    {
+        _yrange = y;
+        _xrange = x;
+        super(source);
+    }
+
+    override Spot opIndex(BigInt y, BigInt x)
+    {
+        return _source[y + _yrange[0], x + _xrange[0]];
+    }
+
+    override string toString()
+    {
+        auto strBuilder = appender!string;
+        strBuilder.reserve(cast(ulong)((_yrange[1] - _yrange[0] + 2) * (_xrange[1] - _xrange[0] + 1)));
+        foreach (y; iota(_yrange[0], _yrange[1]))
+        {
+            foreach (x; iota(_xrange[0], _xrange[1]))
+            {
+                strBuilder.put(_source[y, x].contents);
+            }
+            strBuilder.put("\n");
+        }
+        return strBuilder.data;
+    }
+}
diff --git a/source/lru.d b/source/lru.d
new file mode 100644
index 0000000..6d802df
--- /dev/null
+++ b/source/lru.d
@@ -0,0 +1,174 @@
+import std.array : appender;
+
+private struct Node(T)
+{
+    Node!T* prev;
+    Node!T* next;
+    T data;
+}
+
+private struct List(T)
+{
+    Node!T* head;
+    Node!T* tail;
+    size_t length;
+
+    invariant ()
+    {
+        if (length > 0)
+        {
+            assert(head !is null);
+            assert(tail !is null);
+        }
+    }
+
+    /*private void check()
+    {
+        Node!T* cur = head;
+        while (true)
+        {
+            if (cur != head)
+                assert(cur.prev);
+            if (cur == tail)
+                break;
+            else
+                assert(cur.next);
+            cur = cur.next;
+        }
+    }*/
+
+    void remove(Node!T* n)
+    {
+        if (n.next)
+            n.next.prev = n.prev;
+        if (n.prev)
+            n.prev.next = n.next;
+        if (head == n)
+            head = head.next;
+        if (tail == n)
+            tail = tail.prev;
+        length--;
+    }
+
+    void push(Node!T* n)
+    {
+        n.prev = null;
+        n.next = head;
+        head = n;
+        if (tail is null)
+            tail = head;
+        else
+            head.next.prev = head;
+        length++;
+    }
+
+    Node!T* pop()
+    in
+    {
+        assert(tail);
+    }
+    do
+    {
+        Node!T* node = tail;
+        remove(node);
+        return node;
+    }
+
+}
+
+unittest
+{
+    List!int l;
+    Node!int first;
+    l.push(&first);
+    assert(l.head == &first);
+    assert(l.tail == &first);
+    Node!int second;
+    l.push(&second);
+    assert(l.head == &second);
+    assert(l.tail == &first);
+    assert(l.pop() == &first);
+    assert(l.head == &second);
+    assert(l.tail == &second);
+    l.push(&first);
+    l.pop();
+    l.pop();
+}
+
+class LRUCache(From, To)
+{
+    private size_t _cap;
+    private struct Record
+    {
+        To val;
+        From key;
+    }
+
+    private Node!Record*[From] map;
+    private List!Record queue;
+    this(size_t cap)
+    {
+        _cap = cap;
+    }
+
+    private void checksz()
+    {
+        if (queue.length > _cap)
+        {
+            auto node = queue.pop();
+            map.remove(node.data.key);
+        }
+    }
+
+    bool opBinaryRight(string op : "in")(From key)
+    {
+        return cast(bool)(key in map);
+    }
+
+    To opIndex(From f)
+    in
+    {
+        assert(f in map);
+    }
+    do
+    {
+        auto p = map[f];
+        queue.remove(p);
+        queue.push(p);
+        return p.data.val;
+    }
+
+    void opIndexAssign(To t, From f)
+    {
+        auto p = f in map;
+        Node!Record* node;
+        bool alloc = p is null;
+        if (!alloc)
+        {
+            queue.remove(*p);
+            node = *p;
+        }
+        else
+            node = new Node!Record();
+        node.data.val = t;
+        node.data.key = f;
+        queue.push(node);
+        map[f] = node;
+        if (alloc)
+            checksz();
+    }
+}
+
+unittest
+{
+    auto cache = new LRUCache!(int, int)(2);
+    cache[0] = 1;
+    cache[4] = 2;
+    cache[5] = 1;
+    assert(0 !in cache);
+    assert(4 in cache);
+    assert(5 in cache);
+    assert(cache[5] == 1); // prioritizes
+    cache[0] = 1;
+    assert(4 !in cache);
+}
diff --git a/source/spots.d b/source/spots.d
new file mode 100644
index 0000000..0f9d8b7
--- /dev/null
+++ b/source/spots.d
@@ -0,0 +1,145 @@
+import std.bigint;
+import std.digest.crc;
+import std.random : unpredictableSeed;
+import std.range;
+import lru : LRUCache;
+import deimos.ncurses;
+
+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;
+    }
+
+    @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);
+}
+
+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;
+    }
+}
+
+class OverlaySource : SpotSource
+{
+    private SpotSource _base;
+    private Spot[BigInt[2]] _overlay;
+
+    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];
+    }
+
+    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('*'));
+    }
+}