1 //-----------------------------------------------------------------------------
2 /** @file libboardgame_base/Geometry.h
3 @author Markus Enzenberger
4 @copyright GNU General Public License version 3 or later */
5 //-----------------------------------------------------------------------------
6
7 #ifndef LIBBOARDGAME_BASE_GEOMETRY_H
8 #define LIBBOARDGAME_BASE_GEOMETRY_H
9
10 #include <memory>
11 #include <sstream>
12 #include "ArrayList.h"
13 #include "CoordPoint.h"
14 #include "StringRep.h"
15
16 namespace libboardgame_base {
17
18 using namespace std;
19
20 //-----------------------------------------------------------------------------
21
22 /** %Geometry data of a board with a given size.
23 This class is a base class that uses virtual functions in its constructor
24 that can restrict the shape of the board to a subset of the rectangle
25 and/or to define different definitions of adjacent and diagonal neighbors
26 of a point for geometries that are not rectangular grids.
27 @tparam P An instantiation of Point (or compatible class) */
28 template<class P>
29 class Geometry
30 {
31 public:
32 using Point = P;
33
34 using IntType = typename Point::IntType;
35
36 static constexpr unsigned max_adj = 4;
37
38 static constexpr unsigned max_diag = 11;
39
40 /** On-board adjacent neighbors of a point. */
41 using AdjList = ArrayList<Point, max_adj, unsigned short>;
42
43 /** On-board diagonal neighbors of a point
44 Currently supports up to 11 diagonal points as used on boards
45 for GembloQ. */
46 using DiagList = ArrayList<Point, max_diag, unsigned short>;
47
48 /** Adjacent neighbors of a coordinate. */
49 using AdjCoordList = ArrayList<CoordPoint, max_adj>;
50
51 /** Diagonal neighbors of a coordinate. */
52 using DiagCoordList = ArrayList<CoordPoint, max_diag>;
53
54 class Iterator
55 {
56 public:
Iterator(IntType i)57 explicit Iterator(IntType i) { m_i = i; }
58
59 bool operator==(Iterator it) const { return m_i == it.m_i; }
60
61 bool operator!=(Iterator it) const { return m_i != it.m_i; }
62
63 void operator++() { ++m_i; }
64
65 Point operator*() const { return Point(m_i); }
66
67 private:
68 IntType m_i;
69 };
70
71 virtual ~Geometry();
72
73 /** Get points that share an edge with this point. */
74 virtual AdjCoordList get_adj_coord(int x, int y) const = 0;
75
76 /** Get points that share a corner but not an edge with this point.
77 The order does not matter logically but it is better to put far away
78 points first because BoardConst uses the forbidden status of the first
79 points during move generation and far away points can reject more
80 moves. */
81 virtual DiagCoordList get_diag_coord(int x, int y) const = 0;
82
83 /** Return the point type if the board has different types of points.
84 For example, in the geometry used in Blokus Trigon, there are two
85 point types (0=upward triangle, 1=downward triangle); in a regular
86 rectangle, there is only one point type. By convention, 0 is the
87 type of the point at (0,0).
88 @param x The x coordinate (may be negative and/or outside the board).
89 @param y The y coordinate (may be negative and/or outside the board). */
90 virtual unsigned get_point_type(int x, int y) const = 0;
91
92 /** Get repeat interval for point types along the x axis.
93 If the board has different point types, the layout of the point types
94 repeats in this x interval. If the board has only one point type,
95 the function should return 1. */
96 virtual unsigned get_period_x() const = 0;
97
98 /** Get repeat interval for point types along the y axis.
99 @see get_period_x(). */
100 virtual unsigned get_period_y() const = 0;
101
begin()102 Iterator begin() const { return Iterator(0); }
103
end()104 Iterator end() const { return Iterator(m_range); }
105
106 unsigned get_point_type(CoordPoint p) const;
107
108 unsigned get_point_type(Point p) const;
109
110 bool is_onboard(CoordPoint p) const;
111
112 bool is_onboard(unsigned x, unsigned y) const;
113
is_onboard(int x,int y)114 bool is_onboard(int x, int y) const { return is_onboard({x, y}); }
115
116 /** Return the point at a given coordinate.
117 @pre x < get_width()
118 @pre y < get_height()
119 @return The point or Point::null() if this coordinates are
120 off-board. */
121 Point get_point(unsigned x, unsigned y) const;
122
123 /** Return the point at a given coordinate.
124 @return The point or Point::null() if this coordinates are
125 off-board. */
126 Point get_point(int x, int y) const;
127
get_width()128 unsigned get_width() const { return m_width; }
129
get_height()130 unsigned get_height() const { return m_height; }
131
132 /** Get range used for onboard points. */
get_range()133 IntType get_range() const { return m_range; }
134
135 unsigned get_x(Point p) const;
136
137 unsigned get_y(Point p) const;
138
139 bool from_string(string::const_iterator begin, string::const_iterator end,
140 Point& p) const;
141
142 const string& to_string(Point p) const;
143
144 const AdjList& get_adj(Point p) const;
145
146 const DiagList& get_diag(Point p) const;
147
148 protected:
149 explicit Geometry(
150 unique_ptr<StringRep> string_rep = make_unique<StdStringRep>());
151
152 /** Initialize.
153 Subclasses must call this function in their constructors. */
154 void init(unsigned width, unsigned height);
155
156 /** Initialize on-board points.
157 This function is used in init() and allows the subclass to restrict the
158 on-board points to a subset of the on-board points of a rectangle to
159 support different board shapes. It will only be called with x and
160 y within the width and height of the geometry. */
161 virtual bool init_is_onboard(unsigned x, unsigned y) const = 0;
162
163 private:
164 IntType m_range;
165
166 AdjList m_adj[Point::range_onboard];
167
168 DiagList m_diag[Point::range_onboard];
169
170 Point m_points[Point::max_width][Point::max_height];
171
172 unique_ptr<StringRep> m_string_rep;
173
174 unsigned m_width;
175
176 unsigned m_height;
177
178 unsigned m_x[Point::range_onboard];
179
180 unsigned m_y[Point::range_onboard];
181
182 unsigned m_point_type[Point::range_onboard];
183
184 string m_string[Point::range];
185
186 #ifdef LIBBOARDGAME_DEBUG
is_valid(Point p)187 bool is_valid(Point p) const { return p.to_int() < m_range; }
188 #endif
189 };
190
191
192 template<class P>
Geometry(unique_ptr<StringRep> string_rep)193 Geometry<P>::Geometry(unique_ptr<StringRep> string_rep)
194 : m_string_rep(move(string_rep))
195 { }
196
197 template<class P>
198 Geometry<P>::~Geometry() = default; // Non-inline to avoid GCC -Winline warning
199
200 template<class P>
from_string(string::const_iterator begin,string::const_iterator end,Point & p)201 bool Geometry<P>::from_string(string::const_iterator begin,
202 string::const_iterator end, Point& p) const
203 {
204 unsigned x;
205 unsigned y;
206 if (! m_string_rep->read(begin, end, m_width, m_height, x, y)
207 || ! is_onboard(x, y))
208 return false;
209 p = get_point(x, y);
210 return true;
211 }
212
213 template<class P>
214 inline auto Geometry<P>::get_adj(Point p) const -> const AdjList&
215 {
216 LIBBOARDGAME_ASSERT(is_valid(p));
217 return m_adj[p.to_int()];
218 }
219
220 template<class P>
221 inline auto Geometry<P>::get_diag(Point p) const -> const DiagList&
222 {
223 LIBBOARDGAME_ASSERT(is_valid(p));
224 return m_diag[p.to_int()];
225 }
226
227 template<class P>
228 inline auto Geometry<P>::get_point(unsigned x, unsigned y) const -> Point
229 {
230 LIBBOARDGAME_ASSERT(x < m_width);
231 LIBBOARDGAME_ASSERT(y < m_height);
232 return m_points[x][y];
233 }
234
235 template<class P>
236 inline auto Geometry<P>::get_point(int x, int y) const -> Point
237 {
238 if (x < 0 || static_cast<unsigned>(x) >= m_width
239 || y < 0 || static_cast<unsigned>(y) >= m_height)
240 return Point::null();
241 return m_points[x][y];
242 }
243
244 template<class P>
get_point_type(Point p)245 inline unsigned Geometry<P>::get_point_type(Point p) const
246 {
247 LIBBOARDGAME_ASSERT(is_valid(p));
248 return m_point_type[p.to_int()];
249 }
250
251 template<class P>
get_point_type(CoordPoint p)252 inline unsigned Geometry<P>::get_point_type(CoordPoint p) const
253 {
254 return get_point_type(p.x, p.y);
255 }
256
257 template<class P>
get_x(Point p)258 inline unsigned Geometry<P>::get_x(Point p) const
259 {
260 LIBBOARDGAME_ASSERT(is_valid(p));
261 return m_x[p.to_int()];
262 }
263
264 template<class P>
get_y(Point p)265 inline unsigned Geometry<P>::get_y(Point p) const
266 {
267 LIBBOARDGAME_ASSERT(is_valid(p));
268 return m_y[p.to_int()];
269 }
270
271 template<class P>
init(unsigned width,unsigned height)272 void Geometry<P>::init(unsigned width, unsigned height)
273 {
274 LIBBOARDGAME_ASSERT(width >= 1);
275 LIBBOARDGAME_ASSERT(height >= 1);
276 LIBBOARDGAME_ASSERT(width <= Point::max_width);
277 LIBBOARDGAME_ASSERT(height <= Point::max_height);
278 m_width = width;
279 m_height = height;
280 m_string[Point::null().to_int()] = "null";
281 IntType n = 0;
282 ostringstream ostr;
283 for (unsigned y = 0; y < height; ++y)
284 for (unsigned x = 0; x < width; ++x)
285 if (init_is_onboard(x, y))
286 {
287 m_points[x][y] = Point(n);
288 m_x[n] = x;
289 m_y[n] = y;
290 ostr.str("");
291 m_string_rep->write(ostr, x, y, width, height);
292 m_string[n] = ostr.str();
293 ++n;
294 }
295 else
296 m_points[x][y] = Point::null();
297 m_range = n;
298 for (IntType i = 0; i < n; ++i)
299 {
300 Point p(i);
301 auto x = get_x(p);
302 auto y = get_y(p);
303 for (auto& p : get_adj_coord(x, y))
304 if (is_onboard(p))
305 m_adj[i].push_back(get_point(p.x, p.y));
306 for (auto& p : get_diag_coord(x, y))
307 if (is_onboard(p))
308 m_diag[i].push_back(get_point(p.x, p.y));
309 m_point_type[i] = get_point_type(x, y);
310 }
311 }
312
313 template<class P>
is_onboard(unsigned x,unsigned y)314 bool Geometry<P>::is_onboard(unsigned x, unsigned y) const
315 {
316 return x < m_width && y < m_height && ! get_point(x, y).is_null();
317 }
318
319 template<class P>
is_onboard(CoordPoint p)320 bool Geometry<P>::is_onboard(CoordPoint p) const
321 {
322 return p.is_onboard(m_width, m_height) && ! get_point(p.x, p.y).is_null();
323 }
324
325 template<class P>
to_string(Point p)326 inline const string& Geometry<P>::to_string(Point p) const
327 {
328 LIBBOARDGAME_ASSERT(p.to_int() < m_range);
329 return m_string[p.to_int()];
330 }
331
332 //-----------------------------------------------------------------------------
333
334 } // namespace libboardgame_base
335
336 #endif // LIBBOARDGAME_BASE_GEOMETRY_H
337