From d3ae7832ab0beae40bac664a5ce9da21804d9916 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Sun, 16 Aug 2020 03:49:43 +0200 Subject: initial lab1 --- lab1/lib/StanfordCPPLib/grid.h | 527 +++++++++++++++++++++++++++++++++++++++++ lab1/lib/lifeutil.cpp | 23 ++ lab1/lib/lifeutil.h | 14 ++ lab1/sconstruct.py | 4 + lab1/src/life.cpp | 104 ++++++++ 5 files changed, 672 insertions(+) create mode 100644 lab1/lib/StanfordCPPLib/grid.h create mode 100644 lab1/lib/lifeutil.cpp create mode 100644 lab1/lib/lifeutil.h create mode 100644 lab1/sconstruct.py create mode 100644 lab1/src/life.cpp diff --git a/lab1/lib/StanfordCPPLib/grid.h b/lab1/lib/StanfordCPPLib/grid.h new file mode 100644 index 0000000..8e74998 --- /dev/null +++ b/lab1/lib/StanfordCPPLib/grid.h @@ -0,0 +1,527 @@ +/* + * File: grid.h + * ------------ + * This file exports the Grid class, which offers a + * convenient abstraction for representing a two-dimensional array. + */ + +#ifndef _grid_h +#define _grid_h + +#include +#include +#include +#include + +/* + * Class: Grid + * ---------------------- + * This class stores an indexed, two-dimensional array. The following code, + * for example, creates an identity matrix of size n, in which + * the elements are 1.0 along the main diagonal and 0.0 everywhere else: + * + *
+ *    Grid<double> createIdentityMatrix(int n) {
+ *       Grid<double> matrix(n, n);
+ *       for (int i = 0; i < n; i++) {
+ *          matrix[i][i] = 1.0;
+ *       }
+ *       return matrix;
+ *    }
+ *
+ */ + +template +class Grid { + +public: + + /* Forward reference */ + class GridRow; + class ConstGridRow; + + /* + * Constructor: Grid + * Usage: Grid grid; + * Grid grid(nRows, nCols); + * ------------------------------------------ + * Initializes a new grid. The second form of the constructor is + * more common and creates a grid with the specified number of rows + * and columns. Each element of the grid is initialized to the + * default value for the type. The default constructor creates an + * empty grid for which the client must call resize to + * set the dimensions. + */ + + Grid(); + Grid(int nRows, int nCols); + + /* + * Destructor: ~Grid + * ----------------- + * Frees any heap storage associated with this grid. + */ + + virtual ~Grid(); + + /* + * Method: numRows + * Usage: int nRows = grid.numRows(); + * ---------------------------------- + * Returns the number of rows in the grid. + */ + + int numRows() const; + + /* + * Method: numCols + * Usage: int nCols = grid.numCols(); + * ---------------------------------- + * Returns the number of columns in the grid. + */ + + int numCols() const; + + /* + * Method: resize + * Usage: grid.resize(nRows, nCols); + * --------------------------------- + * Reinitializes the grid to have the specified number of rows + * and columns. Any previous grid contents are discarded. + */ + + void resize(int nRows, int nCols); + + /* + * Method: inBounds + * Usage: if (grid.inBounds(row, col)) ... + * --------------------------------------- + * Returns true if the specified row and column position + * is inside the bounds of the grid. + */ + + bool inBounds(int row, int col) const; + + /* + * Method: get + * Usage: ValueType value = grid.get(row, col); + * -------------------------------------------- + * Returns the element at the specified row/col + * position in this grid. This method signals an error if the + * row and col arguments are outside + * the grid boundaries. + */ + + ValueType get(int row, int col); + const ValueType & get(int row, int col) const; + + /* + * Method: set + * Usage: grid.set(row, col, value); + * --------------------------------- + * Replaces the element at the specified row/col + * location in this grid with a new value. This method signals an error + * if the row and col arguments are outside + * the grid boundaries. + */ + + void set(int row, int col, ValueType value); + + /* + * Operator: [] + * Usage: grid[row][col] + * ---------------------- + * Overloads [] to select elements from this grid. + * This extension enables the use of traditional array notation to + * get or set individual elements. This method signals an error if + * the row and col arguments are outside + * the grid boundaries. + */ + + GridRow operator[](int row); + const ConstGridRow operator[](int row) const; + + /* + * Method: toString + * Usage: string str = grid.toString(); + * ------------------------------------ + * Converts the grid to a printable string representation. + */ + + std::string toString(); + + /* + * Method: mapAll + * Usage: grid.mapAll(fn); + * ----------------------- + * Calls the specified function on each element of the grid. The + * elements are processed in row-major order, in which + * all the elements of row 0 are processed, followed by the elements + * in row 1, and so on. + */ + + void mapAll(void (*fn)(ValueType value)) const; + void mapAll(void (*fn)(const ValueType & value)) const; + + template + void mapAll(FunctorType fn) const; + + /* + * Additional Grid operations + * -------------------------- + * In addition to the methods listed in this interface, the Grid + * class supports the following operations: + * + * - Stream I/O using the << and >> operators + * - Deep copying for the copy constructor and assignment operator + * - Iteration using the range-based for statement and STL iterators + * + * The iteration forms process the grid in row-major order. + */ + + /* Private section */ + + /**********************************************************************/ + /* Note: Everything below this point in the file is logically part */ + /* of the implementation and should not be of interest to clients. */ + /**********************************************************************/ + + /* + * Implementation notes: Grid data structure + * ----------------------------------------- + * The Grid is internally managed as a dynamic array of elements. + * The array itself is one-dimensional, the logical separation into + * rows and columns is done by arithmetic computation. The layout + * is in row-major order, which is to say that the entire first row + * is laid out contiguously, followed by the entire second row, + * and so on. + */ + + /* Instance variables */ + + ValueType *elements; /* A dynamic array of the elements */ + int nRows; /* The number of rows in the grid */ + int nCols; /* The number of columns in the grid */ + + /* Private method prototypes */ + + void checkRange(int row, int col); + + /* + * Hidden features + * --------------- + * The remainder of this file consists of the code required to + * support deep copying and iteration. Including these methods + * in the public interface would make that interface more + * difficult to understand for the average client. + */ + + /* + * Deep copying support + * -------------------- + * This copy constructor and operator= are defined to make a + * deep copy, making it possible to pass/return grids by value + * and assign from one grid to another. The entire contents of + * the grid, including all elements, are copied. Each grid + * element is copied from the original grid to the copy using + * assignment (operator=). Making copies is generally avoided + * because of the expense and thus, grids are typically passed + * by reference, however, when a copy is needed, these operations + * are supported. + */ + + void deepCopy(const Grid & grid) { + int n = grid.nRows * grid.nCols; + elements = new ValueType[n]; + for (int i = 0; i < n; i++) { + elements[i] = grid.elements[i]; + } + nRows = grid.nRows; + nCols = grid.nCols; + } + +public: + + Grid & operator=(const Grid & src) { + if (this != &src) { + delete[] elements; + deepCopy(src); + } + return *this; + } + + Grid(const Grid & src) { + deepCopy(src); + } + + /* + * Iterator support + * ---------------- + * The classes in the StanfordCPPLib collection implement input + * iterators so that they work symmetrically with respect to the + * corresponding STL classes. + */ + + class iterator : public std::iterator { + + public: + + iterator(const Grid *gp, int index) { + this->gp = gp; + this->index = index; + } + + iterator(const iterator & it) { + this->gp = it.gp; + this->index = it.index; + } + + iterator & operator++() { + index++; + return *this; + } + + iterator operator++(int) { + iterator copy(*this); + operator++(); + return copy; + } + + bool operator==(const iterator & rhs) { + return gp == rhs.gp && index == rhs.index; + } + + bool operator!=(const iterator & rhs) { + return !(*this == rhs); + } + + ValueType & operator*() { + return gp->elements[index]; + } + + ValueType *operator->() { + return &gp->elements[index]; + } + + private: + const Grid *gp; + int index; + }; + + iterator begin() const { + return iterator(this, 0); + } + + iterator end() const { + return iterator(this, nRows * nCols); + } + + /* + * Private class: Grid::GridRow + * ------------------------------------- + * This section of the code defines a nested class within the Grid template + * that makes it possible to use traditional subscripting on Grid values. + */ + + class GridRow { + public: + GridRow() { + /* Empty */ + } + + ValueType & operator[](int col) { + if (!gp->inBounds(row, col)) { + throw std::out_of_range("Grid index values out of range"); + } + return gp->elements[(row * gp->nCols) + col]; + } + + ValueType operator[](int col) const { + if (!gp->inBounds(row, col)) { + throw std::out_of_range("Grid index values out of range"); + } + return gp->elements[(row * gp->nCols) + col]; + } + + private: + GridRow(Grid *gridRef, int index) { + gp = gridRef; + row = index; + } + + Grid *gp; + int row; + friend class Grid; + }; + friend class ConstGridRow; + + /* + * Private class: Grid::ConstGridRow + * ------------------------------------- + * This section of the code defines a nested class within the Grid template + * that makes it possible to use traditional subscripting on Grid values for + * const versions of the Grid. + */ + + class ConstGridRow { + public: + ConstGridRow() { + /* Empty */ + } + + ValueType operator[](int col) const { + if (!gp->inBounds(row, col)) { + throw std::out_of_range("Grid index values out of range"); + } + return gp->elements[(row * gp->nCols) + col]; + } + + private: + ConstGridRow(const Grid *gridRef, int index) { + gp = gridRef; + row = index; + } + + const Grid *gp; + int row; + friend class Grid; + }; + friend class GridRow; + +}; + +template +Grid::Grid() { + elements = NULL; + nRows = 0; + nCols = 0; +} + +template +Grid::Grid(int nRows, int nCols) { + elements = NULL; + resize(nRows, nCols); +} + +template +Grid::~Grid() { + if (elements != NULL) delete[] elements; +} + +template +int Grid::numRows() const { + return nRows; +} + +template +int Grid::numCols() const { + return nCols; +} + +template +void Grid::resize(int nRows, int nCols) { + if (nRows < 0 || nCols < 0) { + throw std::invalid_argument("Attempt to resize grid to invalid size (" + + std::to_string(nRows) + ", " + + std::to_string(nCols) + ")"); + } + if (elements != NULL) delete[] elements; + this->nRows = nRows; + this->nCols = nCols; + elements = new ValueType[nRows * nCols]; + ValueType value = ValueType(); + for (int i = 0; i < nRows * nCols; i++) { + elements[i] = value; + } +} + +template +bool Grid::inBounds(int row, int col) const { + return row >= 0 && col >= 0 && row < nRows && col < nCols; +} + +template +ValueType Grid::get(int row, int col) { + if (!inBounds(row, col)) throw std::out_of_range("get: Grid indices out of bounds"); + return elements[(row * nCols) + col]; +} + +template +const ValueType & Grid::get(int row, int col) const { + if (!inBounds(row, col)) throw std::out_of_range("get: Grid indices out of bounds"); + return elements[(row * nCols) + col]; +} + +template +void Grid::set(int row, int col, ValueType value) { + if (!inBounds(row, col)) throw std::out_of_range("set: Grid indices out of bounds"); + elements[(row * nCols) + col] = value; +} + +template +typename Grid::GridRow Grid::operator[](int row) { + return GridRow(this, row); +} + +template +const typename Grid::ConstGridRow +Grid::operator[](int row) const { + return ConstGridRow(this, row); +} + +template +void Grid::mapAll(void (*fn)(ValueType value)) const { + for (int i = 0; i < nRows; i++) { + for (int j = 0; j < nCols; j++) { + fn(get(i, j)); + } + } +} + +template +void Grid::mapAll(void (*fn)(const ValueType & value)) const { + for (int i = 0; i < nRows; i++) { + for (int j = 0; j < nCols; j++) { + fn(get(i, j)); + } + } +} + +template +template +void Grid::mapAll(FunctorType fn) const { + for (int i = 0; i < nRows; i++) { + for (int j = 0; j < nCols; j++) { + fn(get(i, j)); + } + } +} + +template +std::string Grid::toString() { + std::ostringstream os; + os << *this; + return os.str(); +} + + +template +std::ostream & operator<<(std::ostream & os, const Grid & grid) { + os << "{"; + int nRows = grid.numRows(); + int nCols = grid.numCols(); + for (int i = 0; i < nRows; i++) { + if (i > 0) os << ", "; + os << "{"; + for (int j = 0; j < nCols; j++) { + if (j > 0) + os << ", "; + os << grid.get(i,j); + } + os << "}"; + } + return os << "}"; +} + + +#endif diff --git a/lab1/lib/lifeutil.cpp b/lab1/lib/lifeutil.cpp new file mode 100644 index 0000000..204ed6d --- /dev/null +++ b/lab1/lib/lifeutil.cpp @@ -0,0 +1,23 @@ +#include +#include +#include +#include "lifeutil.h" + +void clearConsole() +{ +#if defined(_WIN32) || defined (_WIN64) + std::system("CLS"); +#else + // assume POSIX + std::system("clear"); +#endif +} + + +void pause(int ms) +{ + if (ms > 0) + { + std::this_thread::sleep_for(std::chrono::milliseconds(ms)); + } +} diff --git a/lab1/lib/lifeutil.h b/lab1/lib/lifeutil.h new file mode 100644 index 0000000..62a18e1 --- /dev/null +++ b/lab1/lib/lifeutil.h @@ -0,0 +1,14 @@ +#ifndef LIFEUTIL_H +#define LIFEUTIL_H + +/* + * Erases all currently visible test from the output console. + */ +void clearConsole(); + +/* + * Causes the program to halt execution for the given number of milliseconds. + */ +void pause(int ms); + +#endif // LIFEUTIL_H diff --git a/lab1/sconstruct.py b/lab1/sconstruct.py new file mode 100644 index 0000000..aac58d2 --- /dev/null +++ b/lab1/sconstruct.py @@ -0,0 +1,4 @@ +env = Environment(CPPPATH=["lib", "lib/StanfordCPPLib"]) +life = env.Program("life", ["src/life.cpp", "lib/lifeutil.cpp"]) +Default(life) +AlwaysBuild(Alias("run", life, "./life")) diff --git a/lab1/src/life.cpp b/lab1/src/life.cpp new file mode 100644 index 0000000..cf5c6c9 --- /dev/null +++ b/lab1/src/life.cpp @@ -0,0 +1,104 @@ +// Gustav Sörnäs - gusso230 + +#include "grid.h" +#include "lifeutil.h" + +#include +#include +#include + +/* + * Print a representation of the grid. + * Alive cells show as 'X', dead show as '-'. + */ +void printGrid(Grid &grid) { + for (int y = 0; y < grid.numRows(); y++) { + for (int x = 0; x < grid.numCols(); x++) { + if (grid.get(y, x)) { + std::cout << 'X'; + } else { + std::cout << '-'; + } + } + std::cout << std::endl; + } +} + +/* + * Return 1 if (x, y) is in bounds and alive, otherwise 0. + */ +int checkPoint(Grid &grid, int y, int x) { + return grid.inBounds(y, x) && grid.get(y, x) ? 1 : 0; +} + +/* + * Simulate the grid one time step and update it in-place. + */ +void simulate(Grid &grid) { + Grid prevGrid(grid); + for (int y = 0; y < grid.numRows(); y++) { + for (int x = 0; x < grid.numCols(); x++) { + int numNeighbours = checkPoint(prevGrid, y-1, x-1) + + checkPoint(prevGrid, y-1, x ) + + checkPoint(prevGrid, y-1, x+1) + + checkPoint(prevGrid, y , x-1) + + checkPoint(prevGrid, y , x+1) + + checkPoint(prevGrid, y+1, x-1) + + checkPoint(prevGrid, y+1, x ) + + checkPoint(prevGrid, y+1, x+1); + if (numNeighbours < 2) { + grid.set(y, x, false); + } else if (numNeighbours == 2) { + // Do nothing. + } else if (numNeighbours == 3) { + grid.set(y, x, true); + } else { + grid.set(y, x, false); + } + } + } +} + +int main() { + Grid grid; + + std::string filepath; + std::cout << "file: "; + std::cin >> filepath; + std::ifstream input; + input.open(filepath); + int h, w; + input >> h >> w; + grid.resize(h, w); + + for (int y = 0; y < grid.numRows(); y++) { + std::string line; + std::getline(input, line); + for (int x = 0; x < grid.numCols(); x++) { + grid.set(y, x, line[x] == 'X'); + } + } + input.close(); + + char prompt; + bool running = true; + while (running && (std::cout << "[a]nimate, [t]ick, [q]uit: ") && std::cin >> prompt) { + switch (prompt) { + case 'a': + while (true) { + clearConsole(); + std::cout << std::endl; + printGrid(grid); + pause(100); + simulate(grid); + } + case 't': + simulate(grid); + printGrid(grid); + break; + case 'q': + running = false; + break; + } + } +} -- cgit v1.2.1