Empirical
grid.h
Go to the documentation of this file.
1 // This file is part of Empirical, https://github.com/devosoft/Empirical
2 // Copyright (C) Michigan State University, 2015-2017.
3 // Released under the MIT Software license; see doc/LICENSE
4 //
5 //
6 // Tools for building grids that can be easily navigated and have state associated with
7 // grid cells, edges, and/or intersection points.
8 // Status: BETA
9 //
10 //
11 // Grid::Board objects are templated based on which of the components they work with.
12 // They include three template arguments for the state types associated with cells,
13 // edges, and instersection points. The most commonly use types are:
14 //
15 // int -- full state; this or an enumerated type should be used for discrete states.
16 // bool -- binary state (on/off)
17 // void -- no state (or extra memory) associated with this component
18 //
19 // A Sudoku puzzle (which only uses cells and regions) might be defined as:
20 // Grid::Board<int, void, void>
21 //
22 // A Sliterlink puzzle has binary states at edges and possibly cells (inside/outside):
23 // Grid::Board<bool, bool, void>
24 //
25 // Grid::Layout describes the layout of a grid, including its size and which cells
26 // should be grouped together into a region.
27 //
28 // Grid::StateSet is a helper templated class the holds a collection of states, or is
29 // empty if given a template type of void.
30 
31 #ifndef EMP_GRID_H
32 #define EMP_GRID_H
33 
34 #include "../base/assert.h"
35 #include "../base/vector.h"
36 #include "BitVector.h"
37 
38 namespace emp {
39 namespace Grid {
40 
41  template <typename CELL_TYPE> class Cell;
42  template <typename EDGE_TYPE> class VEdge;
43  template <typename EDGE_TYPE> class HEdge;
44  template <typename POINT_TYPE> class Point;
45 
46  class Layout {
47  private:
48  int width;
49  int height;
51  public:
52  Layout(int w, int h) : width(w), height(h) { ; }
53  Layout(const Layout &) = default;
54  ~Layout() { ; }
55  Layout & operator=(const Layout &) = default;
56 
57  int GetWidth() const { return width; }
58  int GetHeight() const { return height; }
59  int GetNumRegions() const { return (int) regions.size(); }
60  const emp::vector<int> & GetRegion(int id) { return regions[id]; }
61 
62  void AddRegion(const emp::vector<int> & in_region) { regions.push_back(in_region); }
63 
64  // Helper functions
65  int GetX(int id) const { return id % width; }
66  int GetY(int id) const { return id / width; }
67  int GetID(int x, int y) const { return y*width + x; }
68 
69  int GetTopID(int id) const { return id; } // ID of edge at top
70  int GetBottomID(int id) const { return id + width; } // ID of edge at bottom
71  int GetLeftID(int id) const { return GetY(id)*(width+1) + GetX(id); } // ID of edge at left
72  int GetRightID(int id) const { return GetLeftID(id)+1; } // ID of edge at right
73  };
74 
75  template <typename STATE_TYPE>
76  class StateSet {
77  private:
78  int width;
80 
81  public:
82  StateSet(int _w, int _h) : width(_w), states(_w*_h) { ; }
83  StateSet(const StateSet &) = default;
84  ~StateSet() { ; }
85  StateSet & operator=(const StateSet &) = default;
86 
87  int GetWidth() const { return width; }
88  int GetHeight() const { return states.size() / width; }
89  int GetSize() const { return states.size(); }
90 
91  STATE_TYPE operator()(int x, int y) { return states[y*width+x]; }
92  STATE_TYPE operator()(int id) { return states[id]; }
93  STATE_TYPE operator[](int id) { return states[id]; }
94  };
95 
96  template <>
97  class StateSet<bool> {
98  private:
99  int width;
100  BitVector states;
101 
102  public:
103  StateSet(int _w, int _h) : width(_w), states(_w*_h) { ; }
104  StateSet(const StateSet &) = default;
105  ~StateSet() { ; }
106  StateSet & operator=(const StateSet &) = default;
107 
108  int GetWidth() const { return width; }
109  int GetHeight() const { return states.size() / width; }
110  int GetSize() const { return states.size(); }
111 
112  bool operator()(int x, int y) { return states[y*width+x]; }
113  bool operator()(int id) { return states[id]; }
114  bool operator[](int id) { return states[id]; }
115  };
116 
117  // StateSet is specialized on void: no data is stored.
118  template <>
119  class StateSet<void> {
120  public:
121  StateSet(int _w, int _h) { (void) _w; (void) _h; }
122  StateSet(const StateSet &) { ; }
123  ~StateSet() { ; }
124  StateSet & operator=(const StateSet &) { return *this; }
125 
126  int GetWidth() const { return -1; }
127  int GetHeight() const { return -1; }
128  int GetSize() const { return -1; }
129 
130  void operator()(int x, int y) { (void) x; (void) y; }
131  void operator()(int id) { (void) id; }
132  void operator[](int id) { (void) id; }
133  };
134 
135  template <typename CELL_TYPE=int, typename EDGE_TYPE=void, class POINT_TYPE=void>
136  class Board {
137  private:
138  const Layout & layout;
139  StateSet<CELL_TYPE> cell_states; // States of cells in grid.
140  StateSet<EDGE_TYPE> edge_states_h; // States of horizontal edges.
141  StateSet<EDGE_TYPE> edge_states_v; // States of vertical edges.
142  StateSet<POINT_TYPE> point_states; // States of points (where edges cross)
143 
144  public:
145  Board(const Layout & in_layout)
146  : layout(in_layout)
147  , cell_states(layout.GetWidth(), layout.GetHeight())
148  , edge_states_h(layout.GetWidth(), layout.GetHeight()+1)
149  , edge_states_v(layout.GetWidth()+1, layout.GetHeight())
150  , point_states(layout.GetWidth()+1, layout.GetHeight()+1)
151  {
152  // std::cout << "Built Board with " << cell_states.GetSize() << " cells!" << std::endl;
153  // std::cout << "Built Board with " << edge_states_h.GetSize() << " h edges!" << std::endl;
154  // std::cout << "Built Board with " << edge_states_v.GetSize() << " v edges!" << std::endl;
155  // std::cout << "Built Board with " << point_states.GetSize() << " points!" << std::endl
156  // << std::endl;
157  }
158 
159  const Layout & GetLayout() const { return layout; }
160 
161  CELL_TYPE GetCellValue(int id) const { return cell_states[id]; }
162  EDGE_TYPE GetEdgeHValue(int id) const { return edge_states_h[id]; }
163  EDGE_TYPE GetEdgeVValue(int id) const { return edge_states_v[id]; }
164  POINT_TYPE GetPointValue(int id) const { return point_states[id]; }
165 
166  void SetCellValue(int id, CELL_TYPE value) { cell_states[id] = value; }
167  void SetEdgeHValue(int id, EDGE_TYPE value) { edge_states_h[id] = value; }
168  void SetEdgeVValue(int id, EDGE_TYPE value) { edge_states_v[id] = value; }
169  void SetPointValue(int id, POINT_TYPE value) { point_states[id] = value; }
170  };
171 
172  template <typename CELL_TYPE>
173  class Cell {
174  private:
175  Board<CELL_TYPE> & board;
176  int id;
177  public:
178  Cell(Board &b, int in_id) : board(b), id(in_id) { ; }
179  Cell(const Cell &) = default;
180  Cell & operator=(const Cell &) = default;
181 
182  CELL_TYPE GetValue() const { return board.GetCellValue(id); }
183  void SetValue(CELL_TYPE value) { board.SetCellValue(id, value); }
184  };
185 
186  template <typename EDGE_TYPE>
187  class VEdge {
188  private:
189  Board & board;
190  int id;
191  public:
192  VEdge(Board & b, int in_id) : board(b), id(in_id) { ; }
193  VEdge(const VEdge &) = default;
194  VEdge & operator=(const VEdge &) = default;
195 
196  EDGE_TYPE GetValue() const { return board.GetEdgeVValue(id); }
197  void SetValue(EDGE_TYPE value) { board.SetEdgeVValue(id, value); }
198  };
199 
200  template <typename EDGE_TYPE>
201  class HEdge {
202  private:
203  Board & board;
204  int id;
205  public:
206  HEdge(Board & b, int in_id) : board(b), id(in_id) { ; }
207  HEdge(const HEdge &) = default;
208  HEdge & operator=(const HEdge &) = default;
209 
210  EDGE_TYPE GetValue() const { return board.GetEdgeHValue(id); }
211  void SetValue(EDGE_TYPE value) { board.SetEdgeHValue(id, value); }
212  };
213 
214  template <typename POINT_TYPE>
215  class Point {
216  private:
217  Board & board;
218  int id;
219  public:
220  Point(Board & b, int in_id) : board(b), id(in_id) { ; }
221  Point(const Point &) = default;
222  Point & operator=(const Pointe &) = default;
223 
224  POINT_TYPE GetValue() const { return board.GetPointValue(id); }
225  void SetValue(POINT_TYPE value) { board.SetPointValue(id, value); }
226  };
227 
228 }
229 }
230 
231 
232 #endif
StateSet(int _w, int _h)
Definition: grid.h:121
int GetTopID(int id) const
Definition: grid.h:69
int GetRightID(int id) const
Definition: grid.h:72
size_t size() const
Function to allow drop-in replacement with std::vector<bool>.
Definition: BitVector.h:765
int GetNumRegions() const
Definition: grid.h:59
STATE_TYPE operator[](int id)
Definition: grid.h:93
int GetWidth() const
Definition: grid.h:57
void SetPointValue(int id, POINT_TYPE value)
Definition: grid.h:169
int GetX(int id) const
Definition: grid.h:65
POINT_TYPE GetValue() const
Definition: grid.h:224
void SetValue(POINT_TYPE value)
Definition: grid.h:225
int GetID(int x, int y) const
Definition: grid.h:67
int GetLeftID(int id) const
Definition: grid.h:71
A drop-in replacement for std::vector<bool>, but with extra bitwise logic features.
Definition: BitVector.h:39
Definition: grid.h:41
void SetValue(CELL_TYPE value)
Definition: grid.h:183
int GetHeight() const
Definition: grid.h:127
int GetHeight() const
Definition: grid.h:109
A drop-in replacement for std::vector<bool>, with additional bitwise logic features.
Definition: grid.h:43
const emp::vector< int > & GetRegion(int id)
Definition: grid.h:60
void push_back(PB_Ts &&...args)
Definition: vector.h:189
VEdge(Board &b, int in_id)
Definition: grid.h:192
const Layout & GetLayout() const
Definition: grid.h:159
int GetSize() const
Definition: grid.h:89
StateSet(int _w, int _h)
Definition: grid.h:103
~Layout()
Definition: grid.h:54
size_t size() const
Definition: vector.h:151
EDGE_TYPE GetValue() const
Definition: grid.h:210
Point2D<> Point
Definition: Point2D.h:99
Layout(int w, int h)
Definition: grid.h:52
Definition: grid.h:136
bool operator()(int id)
Definition: grid.h:113
Board(const Layout &in_layout)
Definition: grid.h:145
StateSet(int _w, int _h)
Definition: grid.h:82
EDGE_TYPE GetEdgeHValue(int id) const
Definition: grid.h:162
POINT_TYPE GetPointValue(int id) const
Definition: grid.h:164
Definition: grid.h:42
Layout & operator=(const Layout &)=default
Point(Board &b, int in_id)
Definition: grid.h:220
Definition: grid.h:46
~StateSet()
Definition: grid.h:105
int GetWidth() const
Definition: grid.h:108
int GetHeight() const
Definition: grid.h:58
void AddRegion(const emp::vector< int > &in_region)
Definition: grid.h:62
bool operator[](int id)
Definition: grid.h:114
StateSet(const StateSet &)
Definition: grid.h:122
void SetEdgeHValue(int id, EDGE_TYPE value)
Definition: grid.h:167
HEdge(Board &b, int in_id)
Definition: grid.h:206
EDGE_TYPE GetEdgeVValue(int id) const
Definition: grid.h:163
int GetSize() const
Definition: grid.h:128
void SetValue(EDGE_TYPE value)
Definition: grid.h:211
void operator()(int x, int y)
Definition: grid.h:130
bool operator()(int x, int y)
Definition: grid.h:112
void operator[](int id)
Definition: grid.h:132
If we are in emscripten, make sure to include the header.
Definition: array.h:37
Cell(Board &b, int in_id)
Definition: grid.h:178
void SetEdgeVValue(int id, EDGE_TYPE value)
Definition: grid.h:168
int GetWidth() const
Definition: grid.h:126
Build a debug wrapper emp::vector around std::vector.
Definition: vector.h:42
void SetCellValue(int id, CELL_TYPE value)
Definition: grid.h:166
int GetSize() const
Definition: grid.h:110
int GetY(int id) const
Definition: grid.h:66
EDGE_TYPE GetValue() const
Definition: grid.h:196
int GetBottomID(int id) const
Definition: grid.h:70
STATE_TYPE operator()(int x, int y)
Definition: grid.h:91
STATE_TYPE operator()(int id)
Definition: grid.h:92
StateSet & operator=(const StateSet &)
Definition: grid.h:124
Definition: grid.h:44
~StateSet()
Definition: grid.h:123
CELL_TYPE GetCellValue(int id) const
Definition: grid.h:161
void SetValue(EDGE_TYPE value)
Definition: grid.h:197
int GetWidth() const
Definition: grid.h:87
Definition: grid.h:76
void operator()(int id)
Definition: grid.h:131
int GetHeight() const
Definition: grid.h:88
~StateSet()
Definition: grid.h:84
CELL_TYPE GetValue() const
Definition: grid.h:182