Post top tier code

Can be yours or not, I just want to see something good.

Here's a grid graph implemetation of mine, complete with ascii print too. Main feature is the 1-1 encoding of edges to bits, so for a grid of size WxH, exactly 2HW - H - W bits of memory (in theory -- I don't expect std::vector<bool> to behave exactly like that) are used to represent the edges. The magic of this is in the functions Index2Edge and Edge2Index which translate an edge {u, v} to its corresponding index i in the bool vector.

I'm posting it because I think it's kinda relevant to what >>13 does, I think his code does something for ICFP '14?

#include <vector>
#include <deque>
#include <iostream>
#include <algorithm>
#include <cstdlib>

class Grid {
public:
typedef struct { int x, y; } Point;
typedef struct { Point u, v; } Edge;
Grid(void);
Grid(int, int, bool = false);
void Init(int, int, bool = false);
bool IsCorner(const Point&) const;
bool IsOuter(const Point&) const;
bool IsInner(const Point&) const;
int N(const Point&) const;
int N(const Point&, std::deque<Point>&) const;
int Neighbours(const Point&) const;
int Neighbours(const Point&, std::deque<Point>&) const;
void AddEdge(const Edge&);
void RemoveEdge(const Edge&);
bool ExistsEdge(const Edge&) const;
void Print(std::ostream& o, const char * = nullptr) const;
int GetHeight(void) const;
int GetWidth(void) const;
void Edge2Index(const Edge&, int&) const;
void Index2Edge(int, Edge&) const;
private:
int w, h;
std::vector<bool> edges;
};

Grid::Grid(void) {
;
}

Grid::Grid(int w, int h, bool value) {
Grid::Init(w, h, value);
}

void Grid::Init(int w, int h, bool value) {
Grid::w = w;
Grid::h = h;
Grid::edges.resize(2 * h*w - h - w, value);
}

int Grid::GetHeight(void) const {
return Grid::h;
}

int Grid::GetWidth(void) const {
return Grid::w;
}

/* Number of neighbours connected to p */
int Grid::N(const Grid::Point& p) const {
int i, n = 0;
if (p.x != 0) {
Grid::Edge2Index({ p, { p.x - 1, p.y } }, i);
n += Grid::edges[i];
}
if (p.y != 0) {
Grid::Edge2Index({ p, { p.x, p.y - 1 } }, i);
n += Grid::edges[i];
}
if (p.x != Grid::w - 1) {
Grid::Edge2Index({ p, { p.x + 1, p.y } }, i);
n += Grid::edges[i];
}
if (p.y != Grid::h - 1) {
Grid::Edge2Index({ p, { p.x, p.y + 1 } }, i);
n += Grid::edges[i];
}
return n;
}

/* Number and deque list of neighbours connected to p */
int Grid::N(const Grid::Point& p, std::deque<Point>& d) const {
int i, n = 0;
if (p.x != 0) {
Grid::Edge2Index({ p, { p.x - 1, p.y } }, i);
if (Grid::edges[i]) {
n++;
d.push_back({ p.x - 1, p.y });

}
}
if (p.y != 0) {
Grid::Edge2Index({ p, { p.x, p.y - 1 } }, i);
if (Grid::edges[i]) {
n++;
d.push_back({ p.x, p.y - 1 });
}
}
if (p.x != Grid::w - 1) {
Grid::Edge2Index({ p, { p.x + 1, p.y } }, i);
if (Grid::edges[i]) {
n++;
d.push_back({ p.x + 1, p.y });
}
}
if (p.y != Grid::h - 1) {
Grid::Edge2Index({ p, { p.x, p.y + 1 } }, i);
if (Grid::edges[i]) {
n++;
d.push_back({ p.x, p.y + 1 });
}
}
return n;
}

/* Number of points that can possibly be connected to p */
int Grid::Neighbours(const Point& p) const {
if (IsInner(p)) return 4;
else if (IsCorner(p)) return 2;
else return 3;
}

/* List of points that can possibly be connected to p */
int Grid::Neighbours(const Point& p, std::deque<Point>& d) const {
int n = 0;
if (p.x > 0)
n++, d.push_back({ p.x - 1, p.y });
if (p.y > 0)
n++, d.push_back({ p.x, p.y - 1 });
if (p.x < w - 1)
n++, d.push_back({ p.x + 1, p.y });
if (p.y < h - 1)
n++, d.push_back({ p.x, p.y + 1 });
return n;
}

bool Grid::IsCorner(const Grid::Point& p) const {
return (p.x == 0 || p.x == Grid::w - 1)
&& (p.y == 0 || p.y == Grid::h - 1);
}

bool Grid::IsOuter(const Grid::Point& p) const {
return !p.x || !p.y || p.x == Grid::w - 1 || p.y == Grid::h - 1;
}

bool Grid::IsInner(const Grid::Point& p) const {
return p.x && p.y && p.x != Grid::w - 1 && p.y != Grid::h - 1;
}

/* Converts a user edge {p, q} to private class index for the edges vector */
void Grid::Edge2Index(const Grid::Edge& e, int &i) const {
if (e.u.y == e.v.y)
i = e.u.y * (w - 1) + std::min({ e.u.x, e.v.x });
else
i = h*(w - 1) + std::min({ e.u.y, e.v.y }) * w + e.u.x;
}

/* Translates an index to an edge {p, q} */
void Grid::Index2Edge(int i, Grid::Edge& e) const {
div_t x;
if (i < (w - 1)*h) {
x = div(i, w - 1);
e.v.x = 1 + (e.u.x = x.rem);
e.u.y = e.v.y = x.quot;
}
else {
i -= (w - 1)*h;
x = div(i, w);
e.u.x = e.v.x = x.rem;
e.v.y = 1 + (e.u.y = x.quot);
}
}

void Grid::AddEdge(const Grid::Edge& e) {
int i;
Grid::Edge2Index(e, i);
Grid::edges[i] = true;
}

void Grid::RemoveEdge(const Grid::Edge& e) {
int i;
Grid::Edge2Index(e, i);
Grid::edges[i] = false;
}

bool Grid::ExistsEdge(const Grid::Edge& e) const {
int i;
Grid::Edge2Index(e, i);
return Grid::edges[i];
}

void Grid::Print(std::ostream& o, const char *prefix) const {
for (int j = 0; j < Grid::h; j++) {
if (prefix) o << prefix;
for (int i = 0; i < Grid::w; i++) {
if (Grid::N({ i, j }))
o << '*';
else
o << ' ';
if (i != Grid::w - 1) {
if (Grid::ExistsEdge({ { i, j }, { i + 1, j } }))
o << "---";
else
o << " ";
}
}
o << std::endl;
if (prefix) o << prefix;
if (j != Grid::h - 1)
for (int i = 0; i < Grid::w; i++) {
if (Grid::ExistsEdge({ { i, j }, { i, j + 1 } }))
o << '|';
else
o << ' ';
if (i != Grid::w - 1)
o << " ";
}
o << std::endl;
}
}