Conway's Game of Life in C++

main.cpp

#include <iostream>
#include <set>

using namespace std;

struct Cell {
    const long x, y;

    Cell(long sx, long sy) : x(sx), y(sy) { }

    inline bool operator==(const Cell &rhs) const {
        return (x == rhs.x) && (y == rhs.y);
    }

    inline bool operator<(const Cell &rhs) const {
        return (x == rhs.x) ? (y < rhs.y) : (x < rhs.x);
    }

    friend ostream &operator<<(ostream &out, const Cell &c) {
        return out << "(" << c.x << ", " << c.y << ")";
    }
};

ostream &operator<<(ostream &out, const set<Cell> &field) {
    for (auto &c : field) {
        out << c << endl;
    }
    return out;
}

namespace life {

    template<typename F>
    void foreachInProximity(const Cell &c, F op) {
        for (int x = -1; x <= 1; ++x) {
            for (int y = -1; y <= 1; ++y) {
                if ((x != 0) || (y != 0)) {
                    op(Cell(c.x + x, c.y + y));
                }
            }
        }
    }

    int countNeighbours(const set<Cell> &field, const Cell &cell) {
        int result = 0;

        foreachInProximity(cell, [&](const Cell &c) {
            if (field.find(c) != field.cend())
                ++result;
        });

        return result;
    }

    set<Cell> advance(set<Cell> &field) {
        set<Cell> hull;

        // create hull
        for (auto &aliveCell : field) {
            foreachInProximity(aliveCell, [&](const Cell &c) {
                if (field.find(c) == field.cend()) // would be much faster with hash_set
                    hull.insert(c);
            });
        }

        // leave in the hull only those that will be alive next turn
        for (auto ic = hull.begin(); ic != hull.end();) {
            if (countNeighbours(field, *ic) != 3)
                ic = hull.erase(ic);
            else
                ++ic;
        }

        // move alive cells from field to hull
        for (auto ic = field.cbegin(), end = field.cend(); ic != end; ++ic) {
            int nAlive = countNeighbours(field, *ic);
            if (nAlive == 2 || nAlive == 3) {
                hull.insert(*ic);
            }
        }

        return hull;
    }

    template<class Render>
    set<Cell> play(set<Cell> field, int nTurns, Render render) {
        for (int i = 0; i < nTurns; ++i) {
            render(field);
            field = advance(field);
        }
        return field;
    }
}

void renderField(const set<Cell> &field) {
    cout << "Field: " << endl << field << endl;
}

/*
 * Test driver.
 */

template<class T>
void test(const string &name, const T &expected, const T &actual) {
    if (expected != actual) {
        cerr << "Test '" << name << "' failed." << endl;
        cerr << "Expected: " << expected << endl;
        cerr << "Actual: " << actual << endl;
    } else {
        cout << "Test '" << name << "' succeeded." << endl;
    }
}

int main() {
    // Testing countNeighbours
    {
        set<Cell> field{Cell(1, 1), Cell(2, 2)};
        auto actual = life::countNeighbours(field, Cell(2, 1));
        test("countNeighbours", 2, actual);
    }

    // Testing play
    {
        /* Test 1
         * x_
         * _x
         * should be empty
         * after 1 turn
         */
        set<Cell> initialState{Cell(1, 1), Cell(2, 2)};
        set<Cell> expected{};

        auto actual = life::play(initialState, 1, renderField);
        test("field should be empty after one turn", expected, actual);
    }

    {
        /* Test 2
         * xx_
         * _x_
         * ___
         * should become
         * xx_
         * xx_
         * ___
         * after 1 turn
         */
        set<Cell> initialState{Cell(1, 1), Cell(1, 2), Cell(2, 2)};
        set<Cell> expected{Cell(1, 1), Cell(1, 2), Cell(2, 1), Cell(2, 2)};

        auto actual = life::play(initialState, 1, renderField);
        test("cell should become live", expected, actual);
    }

    {
        /* Test 3
            (0, 1)
            (1, 2)
            (2, 0)
            (2, 1)
            (2, 2)
            (-2000000000000, -2000000000000)
            (-2000000000001, -2000000000001)
          i.e.
            _x__
            __x_
            xxx_
            ____
         * should become
         * ____
         * x_x_
         * _xx_
         * _x__
         * after 1 turn
         */
        set<Cell> initialState{Cell(0, 1), Cell(1,2), Cell(2, 0), Cell(2,1), Cell(2,2),
                               Cell(-2000000000000, -2000000000000), Cell(-2000000000001, -2000000000001) };
        set<Cell> expected{Cell(1, 0), Cell(1, 2), Cell(2, 1), Cell(2, 2), Cell(3, 1)};

        auto actual = life::play(initialState, 1, renderField);
        test("original input test", expected, actual);
    }


    return 0;
}