1 /****************************************************************************
2
3 Copyright (C) 2002-2014 Gilles Debunne. All rights reserved.
4
5 This file is part of the QGLViewer library version 2.7.2.
6
7 http://www.libqglviewer.com - contact@libqglviewer.com
8
9 This file may be used under the terms of the GNU General Public License
10 versions 2.0 or 3.0 as published by the Free Software Foundation and
11 appearing in the LICENSE file included in the packaging of this file.
12 In addition, as a special exception, Gilles Debunne gives you certain
13 additional rights, described in the file GPL_EXCEPTION in this package.
14
15 libQGLViewer uses dual licensing. Commercial/proprietary software must
16 purchase a libQGLViewer Commercial License.
17
18 This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
19 WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
20
21 *****************************************************************************/
22
23 #include "board.h"
24 #include <algorithm>
25 #include <functional>
26 #include <sstream>
27
28 using namespace std;
29 using namespace dvonn;
30
31 namespace {
resetStatus(pair<Stack,int> & b)32 void resetStatus(pair<Stack, int> &b) { b.second = -1; }
clearStacks(pair<Stack,int> & b)33 void clearStacks(pair<Stack, int> &b) { b.first.clear(); }
hasLessPieces(const pair<Stack,int> & s,const pair<Stack,int> & t)34 unsigned int hasLessPieces(const pair<Stack, int> &s,
35 const pair<Stack, int> &t) {
36 return s.first.height() < t.first.height();
37 }
38 } // namespace
nameOf(const Color p)39 const char *dvonn::nameOf(const Color p) {
40 return p == White ? "White" : (p == Red ? "Red" : "Black");
41 }
42 //************************************************************
43 // Implementation of Piece
44 //************************************************************
color() const45 Color Piece::color() const { return color_; }
isWhite() const46 bool Piece::isWhite() const { return color_ == White; }
isBlack() const47 bool Piece::isBlack() const { return color_ == Black; }
isRed() const48 bool Piece::isRed() const { return color_ == Red; }
is(Color c) const49 bool Piece::is(Color c) const { return color_ == c; }
Piece(Color c)50 Piece::Piece(Color c) : color_(c) {}
operator <<(ostream & s,const Piece & p)51 ostream &operator<<(ostream &s, const Piece &p) {
52 static const char *v[nbColors] = {"R", "W", "B"};
53 return s << v[p.color()];
54 }
55 //************************************************************
56 // Implementation of Stack
57 //************************************************************
height() const58 unsigned int Stack::height() const { return size(); }
hasRed() const59 bool Stack::hasRed() const {
60 return find_if(begin(), end(), mem_fun(&Piece::isRed)) != end();
61 }
hasPieces() const62 bool Stack::hasPieces() const { return !empty(); }
onTop() const63 const Piece *Stack::onTop() const { return hasPieces() ? back() : NULL; }
Stack()64 Stack::Stack() {}
operator <<(ostream & s,const Stack & t)65 ostream &operator<<(ostream &s, const Stack &t) {
66 s << (t.hasRed() ? '*' : ' ') << t.size();
67 if (t.hasPieces())
68 s << (*t.onTop());
69 else
70 s << ' ';
71 return s;
72 }
73 //************************************************************
74 // Implementation of Board
75 //************************************************************
nbSpacesMaxOnRow()76 unsigned int Board::nbSpacesMaxOnRow() { return 11; }
nbRows()77 unsigned int Board::nbRows() { return 5; }
isValid(Coord c)78 bool Board::isValid(Coord c) {
79 const int yL = nbRows() / 2;
80 const int yR = nbRows() - nbRows() / 2;
81 const int nC = nbRows() % 2;
82 return ((c.y() >= 0 && c.y() < yL && c.x() >= 0 &&
83 c.x() <= static_cast<int>(nbSpacesMaxOnRow()) - (yL - c.y()) - nC) ||
84 (nC == 1 && c.y() == yL && c.x() >= 0 &&
85 c.x() < static_cast<int>(nbSpacesMaxOnRow())) ||
86 (c.y() >= yR && c.y() < static_cast<int>(nbRows()) &&
87 c.x() >= c.y() - yR + nC &&
88 c.x() < static_cast<int>(nbSpacesMaxOnRow())));
89 }
areAligned(Coord c0,Coord c1)90 bool Board::areAligned(Coord c0, Coord c1) {
91 const int dx = c1.x() - c0.x();
92 const int dy = c1.y() - c0.y();
93 return dx == 0 || dy == 0 || dx == dy;
94 }
distance(Coord c0,Coord c1)95 unsigned int Board::distance(Coord c0, Coord c1) {
96 const int dx = c1.x() - c0.x();
97 const int dy = c1.y() - c0.y();
98 return max(abs(dx), abs(dy));
99 }
nbPieces(Color c)100 unsigned int Board::nbPieces(Color c) {
101 switch (c) {
102 case Red:
103 return 3;
104 case White:
105 return 23;
106 case Black:
107 return 23;
108 }
109 return 0;
110 }
Board()111 Board::Board() : spaces_(nbSpacesMaxOnRow() * nbRows()) {
112 reinit();
113 for (unsigned int n = 0; n < nbColors; ++n) {
114 Color c = static_cast<Color>(n);
115 for (unsigned int i = 0; i < nbPieces(c); ++i) {
116 pieces_.push_back(Piece(c));
117 }
118 }
119 }
reinit()120 void Board::reinit() {
121 unplaced_[0] = stack<const Piece *>();
122 unplaced_[1] = stack<const Piece *>();
123 unplaced_[2] = stack<const Piece *>();
124 for (deque<Piece>::const_iterator iter = pieces_.begin();
125 iter != pieces_.end(); ++iter) {
126 unplaced_[iter->color()].push(&(*iter));
127 }
128 for_each(spaces_.begin(), spaces_.end(), resetStatus);
129 for_each(spaces_.begin(), spaces_.end(), clearStacks);
130 redSpaces_.clear();
131 }
~Board()132 Board::~Board() {}
coord2idx(Coord c)133 unsigned int Board::coord2idx(Coord c) {
134 return c.x() + c.y() * nbSpacesMaxOnRow();
135 }
idx2coord(unsigned int n)136 Board::Coord Board::idx2coord(unsigned int n) {
137 return Coord(n % nbSpacesMaxOnRow(), n / nbSpacesMaxOnRow());
138 }
stackAt(Coord c) const139 Board::ConstStackHandle Board::stackAt(Coord c) const {
140 return ConstStackHandle(c, &(spaces_[coord2idx(c)]));
141 }
stackAt(int x,int y) const142 Board::ConstStackHandle Board::stackAt(int x, int y) const {
143 return stackAt(Coord(x, y));
144 }
stacks_begin() const145 Board::ConstStackIterator Board::stacks_begin() const {
146 return ConstStackIterator(Coord(0, 0), &(spaces_[0]), this);
147 }
stacks_end() const148 Board::ConstStackIterator Board::stacks_end() const {
149 return ConstStackIterator(Coord(-1, -1), NULL, this);
150 }
prettyPrinted(const char * prefix) const151 string Board::prettyPrinted(const char *prefix) const {
152 ostringstream os;
153 const int yL = nbRows() / 2;
154 const int yR = nbRows() - nbRows() / 2;
155 const int nC = nbRows() % 2;
156 for (int y = nbRows() - 1; y >= yR; --y) {
157 os << prefix << string(2 * (y - yR + nC), ' ');
158 for (int x = y - yR + nC; x < static_cast<int>(nbSpacesMaxOnRow()); ++x) {
159 os << (*stackAt(Coord(x, y))) << ' ';
160 }
161 os << '\n';
162 }
163 if (nC == 1) {
164 os << prefix;
165 for (int x = 0; x < static_cast<int>(nbSpacesMaxOnRow()); ++x) {
166 os << (*stackAt(Coord(x, yL))) << ' ';
167 }
168 os << endl;
169 }
170 for (int y = yL - 1; y >= 0; --y) {
171 os << prefix << string(2 * (yL - y + nC - 1), ' ');
172 for (int x = 0; x <= static_cast<int>(nbSpacesMaxOnRow()) - (yL - y) - nC;
173 ++x) {
174 os << (*stackAt(Coord(x, y))) << ' ';
175 }
176 os << '\n';
177 }
178 return os.str();
179 }
nbUnplacedPieces(Color c) const180 unsigned int Board::nbUnplacedPieces(Color c) const {
181 return unplaced_[c].size();
182 }
getUnplacedPiece(Color c) const183 const Piece *Board::getUnplacedPiece(Color c) const {
184 if (unplaced_[c].empty())
185 return NULL;
186 return unplaced_[c].top();
187 }
188 /*!
189 * You can place only a piece at a valid coord, and a piece that is
190 * unplaced. So you must first get it with getUnplacedPiece(). Once it is
191 * placed, calling this function again with the same piece will do nothing.
192 */
place(const Piece * p,Coord c)193 void Board::place(const Piece *p, Coord c) {
194 if (p && p == getUnplacedPiece(p->color()) && isValid(c)) {
195 spaces_[coord2idx(c)].first.push_back(p);
196 unplaced_[p->color()].pop();
197 if (p->color() == Red) {
198 redSpaces_[p] = c;
199 }
200 }
201 }
202 /*!
203 * A move is made only if src and dst are valid.
204 */
move(Coord src,Coord dst,bool killDeads)205 Board::Ghosts Board::move(Coord src, Coord dst, bool killDeads) {
206 Ghosts ghosts;
207 if (isValid(src) && isValid(dst)) {
208 Stack &s = spaces_[coord2idx(src)].first;
209 Stack &d = spaces_[coord2idx(dst)].first;
210 // If the src destination was containing a red
211 Stack::const_iterator fter =
212 find_if(s.begin(), s.end(), mem_fun(&Piece::isRed));
213 if (fter != s.end()) {
214 redSpaces_[*fter] = dst;
215 }
216 // Move the pieces from src to dst
217 d.insert(d.end(), s.begin(), s.end());
218 s.clear();
219 updateStatus(ghosts, killDeads);
220 }
221 return ghosts;
222 }
updateStatus(Ghosts & ghosts,bool killDeads)223 void Board::updateStatus(Ghosts &ghosts, bool killDeads) {
224 // We now need to update the status of the cases
225 for_each(spaces_.begin(), spaces_.end(), resetStatus);
226 stack<Coord> toVisit;
227 // Start from the reds...
228 for (map<const Piece *, Coord>::const_iterator iter = redSpaces_.begin();
229 iter != redSpaces_.end(); ++iter) {
230 int i = coord2idx(iter->second);
231 spaces_[i].second = i;
232 toVisit.push(iter->second);
233 }
234 /// ...and propagate.
235 while (!toVisit.empty()) {
236 Coord c = toVisit.top();
237 toVisit.pop();
238 int l = spaces_[coord2idx(c)].second;
239 Coord n[6] = {Coord(c.x() - 1, c.y()), Coord(c.x() + 1, c.y()),
240 Coord(c.x(), c.y() - 1), Coord(c.x(), c.y() + 1),
241 Coord(c.x() - 1, c.y() - 1), Coord(c.x() + 1, c.y() + 1)};
242 for (unsigned int i = 0; i < 6; ++i) {
243 if (!isValid(n[i]))
244 continue;
245 unsigned int p = coord2idx(n[i]);
246 Space &s = spaces_[p];
247 if (s.second == -1 && s.first.hasPieces()) {
248 s.second = l;
249 toVisit.push(n[i]);
250 }
251 }
252 }
253 // Now get rid of the dead
254 if (killDeads) {
255 unsigned int i = 0;
256 for (vector<Space>::iterator iter = spaces_.begin(); iter != spaces_.end();
257 ++iter, ++i) {
258 if (iter->second == -1 && iter->first.hasPieces()) {
259 ghosts.push_back(Ghost(idx2coord(i), iter->first));
260 iter->first.clear();
261 }
262 }
263 }
264 }
isFree(const Board::ConstStackHandle & h) const265 bool Board::isFree(const Board::ConstStackHandle &h) const {
266 Coord c = h.stackCoord();
267
268 if (!isValid(c) || !stackAt(c)->hasPieces())
269 return false;
270
271 Coord c0 = Coord(c.x() + 1, c.y());
272 Coord c1 = Coord(c.x() - 1, c.y());
273 Coord c2 = Coord(c.x(), c.y() + 1);
274 Coord c3 = Coord(c.x(), c.y() - 1);
275 Coord c4 = Coord(c.x() + 1, c.y() + 1);
276 Coord c5 = Coord(c.x() - 1, c.y() - 1);
277 return ((!isValid(c0) || !stackAt(c0)->hasPieces()) ||
278 (!isValid(c1) || !stackAt(c1)->hasPieces()) ||
279 (!isValid(c2) || !stackAt(c2)->hasPieces()) ||
280 (!isValid(c3) || !stackAt(c3)->hasPieces()) ||
281 (!isValid(c4) || !stackAt(c4)->hasPieces()) ||
282 (!isValid(c5) || !stackAt(c5)->hasPieces()));
283 }
heightMax() const284 unsigned int Board::heightMax() const {
285 return max_element(spaces_.begin(), spaces_.end(), hasLessPieces)
286 ->first.height();
287 }
state() const288 Board::State Board::state() const {
289 State s;
290 s.spaces_ = spaces_;
291 s.redSpaces_ = redSpaces_;
292 s.unplaced_[0] = unplaced_[0];
293 s.unplaced_[1] = unplaced_[1];
294 s.unplaced_[2] = unplaced_[2];
295 return s;
296 }
restore(State s)297 void Board::restore(State s) {
298 spaces_ = s.spaces_;
299 redSpaces_ = s.redSpaces_;
300 unplaced_[0] = s.unplaced_[0];
301 unplaced_[1] = s.unplaced_[1];
302 unplaced_[2] = s.unplaced_[2];
303 }
304 //************************************************************
305 // Implementation of Board::Coord
306 //************************************************************
Coord(int x,int y)307 Board::Coord::Coord(int x, int y) : x_(x), y_(y) {}
x() const308 int Board::Coord::x() const { return x_; }
y() const309 int Board::Coord::y() const { return y_; }
operator ==(const Board::Coord other) const310 bool Board::Coord::operator==(const Board::Coord other) const {
311 return x_ == other.x_ && y_ == other.y_;
312 }
operator !=(const Board::Coord other) const313 bool Board::Coord::operator!=(const Board::Coord other) const {
314 return !operator==(other);
315 }
operator <(const Board::Coord other) const316 bool Board::Coord::operator<(const Board::Coord other) const {
317 return x_ < other.x_ || (x_ == other.x_ && y_ < other.y_);
318 }
operator <<(ostream & s,const Board::Coord c)319 ostream &operator<<(ostream &s, const Board::Coord c) {
320 return s << '[' << ((char)(c.x() + (int)'A')) << c.y() << ']';
321 }
322 //************************************************************
323 // Implementation of Board::ConstStackHandle
324 //************************************************************
~ConstStackHandle()325 Board::ConstStackHandle::~ConstStackHandle() {}
operator bool() const326 Board::ConstStackHandle::operator bool() const { return space_ != NULL; }
operator ->() const327 const Stack *Board::ConstStackHandle::operator->() const {
328 return &(space_->first);
329 }
operator *() const330 const Stack &Board::ConstStackHandle::operator*() const {
331 return space_->first;
332 }
operator ==(const ConstStackHandle & other) const333 bool Board::ConstStackHandle::operator==(const ConstStackHandle &other) const {
334 return (space_ == other.space_ && coord_ == other.coord_);
335 }
operator !=(const ConstStackHandle & other) const336 bool Board::ConstStackHandle::operator!=(const ConstStackHandle &other) const {
337 return !operator==(other);
338 }
stackCoord() const339 Board::Coord Board::ConstStackHandle::stackCoord() const { return coord_; }
stackStatus() const340 int Board::ConstStackHandle::stackStatus() const { return space_->second; }
ConstStackHandle()341 Board::ConstStackHandle::ConstStackHandle() : coord_(-1, -1), space_(NULL) {}
ConstStackHandle(Coord c,const Space * s)342 Board::ConstStackHandle::ConstStackHandle(Coord c, const Space *s)
343 : coord_(c), space_(s) {}
setCoord(Coord c)344 void Board::ConstStackHandle::setCoord(Coord c) { coord_ = c; }
setSpace(const Space * s)345 void Board::ConstStackHandle::setSpace(const Space *s) { space_ = s; }
space() const346 const Board::Space *Board::ConstStackHandle::space() const { return space_; }
isNull() const347 bool Board::ConstStackHandle::isNull() const { return !(*this); }
null()348 Board::ConstStackHandle Board::ConstStackHandle::null() {
349 return ConstStackHandle();
350 }
operator <<(ostream & s,const dvonn::Board::ConstStackHandle & h)351 ostream &operator<<(ostream &s, const dvonn::Board::ConstStackHandle &h) {
352 if (h)
353 return s << '(' << h.stackCoord() << " : " << (*h) << ')';
354
355 return s << "null";
356 }
357 //************************************************************
358 // Implementation of Board::ConstStackIterator
359 //************************************************************
~ConstStackIterator()360 Board::ConstStackIterator::~ConstStackIterator() {}
361 bool Board::ConstStackIterator::
operator ==(const ConstStackHandle & other) const362 operator==(const ConstStackHandle &other) const {
363 const ConstStackIterator *pother =
364 dynamic_cast<const ConstStackIterator *>(&other);
365 if (!pother)
366 return ConstStackHandle::operator==(other);
367 return operator==(*pother);
368 }
369 bool Board::ConstStackIterator::
operator !=(const ConstStackHandle & other) const370 operator!=(const ConstStackHandle &other) const {
371 return !operator==(other);
372 }
373 /*!
374 * To be equal, they must have same board, and same handle.
375 */
376 bool Board::ConstStackIterator::
operator ==(const ConstStackIterator & other) const377 operator==(const ConstStackIterator &other) const {
378 return (board_ == other.board_ && ConstStackHandle::operator==(other));
379 }
380 bool Board::ConstStackIterator::
operator !=(const ConstStackIterator & other) const381 operator!=(const ConstStackIterator &other) const {
382 return !operator==(other);
383 }
operator ++()384 Board::ConstStackIterator &Board::ConstStackIterator::operator++() {
385 if (!operator bool())
386 return *this;
387
388 int x = stackCoord().x();
389 int y = stackCoord().y();
390 do {
391 if (++x >= static_cast<int>(nbSpacesMaxOnRow())) {
392 x = 0;
393 if (++y >= static_cast<int>(nbRows())) {
394 setSpace(NULL);
395 setCoord(Coord(-1, -1));
396 return *this;
397 }
398 }
399 } while (!isValid(Coord(x, y)));
400
401 setCoord(Coord(x, y));
402 setSpace(&(board_->spaces_[Board::coord2idx(Coord(x, y))]));
403
404 return *this;
405 }
406 /*!
407 * Rk: the default ConstStackIterator is not equal to the stacks_end()
408 * iterator of a Board.
409 */
ConstStackIterator()410 Board::ConstStackIterator::ConstStackIterator()
411 : Board::ConstStackHandle(), board_(NULL) {}
ConstStackIterator(Coord c,const Space * s,const Board * b)412 Board::ConstStackIterator::ConstStackIterator(Coord c, const Space *s,
413 const Board *b)
414 : Board::ConstStackHandle(c, s), board_(b) {}
415 //************************************************************
416 // Implementation of Board::Ghost
417 //************************************************************
Ghost(Board::Coord c,const Stack & s)418 Board::Ghost::Ghost(Board::Coord c, const Stack &s)
419 : coord(c), stack(s.begin(), s.end()) {}
420