1 /***********************************************************************
2 *
3 * Copyright (C) 2009, 2012, 2013, 2014 Graeme Gott <graeme@gottcode.org>
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 *
18 ***********************************************************************/
19
20 #include "pattern.h"
21
22 #include "word.h"
23
24 #include <algorithm>
25
26 //-----------------------------------------------------------------------------
27
Pattern(WordList * words)28 Pattern::Pattern(WordList* words)
29 : m_current(0,0), m_words(words), m_count(0), m_length(0), m_seed(0), m_cancelled(false) {
30 Q_ASSERT(words != 0);
31 }
32
33 //-----------------------------------------------------------------------------
34
~Pattern()35 Pattern::~Pattern() {
36 if (isRunning()) {
37 m_cancelled_mutex.lock();
38 m_cancelled = true;
39 m_cancelled_mutex.unlock();
40 wait();
41 }
42 cleanUp();
43 }
44
45 //-----------------------------------------------------------------------------
46
setCount(int count)47 void Pattern::setCount(int count) {
48 m_count = counts().value(count, 4);
49 }
50
51 //-----------------------------------------------------------------------------
52
setLength(int length)53 void Pattern::setLength(int length) {
54 m_length = qBound(minimumLength(), length, maximumLength()) - 1;
55 m_words->setLength(m_length);
56 }
57
58 //-----------------------------------------------------------------------------
59
setSeed(unsigned int seed)60 void Pattern::setSeed(unsigned int seed) {
61 m_seed = seed;
62 }
63
64 //-----------------------------------------------------------------------------
65
create(WordList * words,int type)66 Pattern* Pattern::create(WordList* words, int type) {
67 Pattern* pattern = 0;
68 switch (type) {
69 case 0:
70 pattern = new ChainPattern(words);
71 break;
72 case 1:
73 pattern = new FencePattern(words);
74 break;
75 case 2:
76 pattern = new RingsPattern(words);
77 break;
78 case 3:
79 pattern = new StairsPattern(words);
80 break;
81 case 4:
82 pattern = new TwistyPattern(words);
83 break;
84 case 5:
85 pattern = new WavePattern(words);
86 break;
87 default:
88 break;
89 }
90 return pattern;
91 }
92
93 //-----------------------------------------------------------------------------
94
addRandomWord(Qt::Orientation orientation)95 Word* Pattern::addRandomWord(Qt::Orientation orientation) {
96 // Filter words on what characters are on the board
97 QString known_letters;
98 QPoint pos = m_current;
99 QPoint delta = (orientation == Qt::Horizontal) ? QPoint(1, 0) : QPoint(0, 1);
100 for (int i = 0; i <= wordLength(); ++i) {
101 QChar c = at(pos);
102 known_letters.append(c.isNull() ? QChar('.') : c);
103 pos += delta;
104 }
105 QStringList words = m_words->filter(known_letters);
106
107 // Find word
108 QString result = !words.isEmpty() ? words.at(randomInt(words.count())) : QString();
109 if (result.isEmpty()) {
110 return 0;
111 }
112
113 // Remove anagrams of word
114 m_words->addAnagramFilter(result);
115
116 return new Word(result, m_current, orientation, m_random);
117 }
118
119 //-----------------------------------------------------------------------------
120
at(const QPoint & pos) const121 QChar Pattern::at(const QPoint& pos) const {
122 for (Word* word : m_solution) {
123 QList<QPoint> positions = word->positions();
124 for (int i = 0; i < positions.count(); ++i) {
125 if (positions.at(i) == pos) {
126 return word->at(i);
127 }
128 }
129 }
130 return QChar();
131 }
132
133 //-----------------------------------------------------------------------------
134
run()135 void Pattern::run() {
136 if (m_words->isEmpty()) {
137 return;
138 }
139
140 m_random.seed(m_seed);
141
142 // Add words
143 cleanUp();
144 int s = steps();
145 int count = counts().value(wordCount());
146 for (int i = 0; i < count; ++i) {
147 Word* word = addWord(i % s);
148 if (word) {
149 m_solution.append(word);
150 } else {
151 cleanUp();
152 i = -1;
153 }
154
155 QMutexLocker locker(&m_cancelled_mutex);
156 if (m_cancelled) {
157 return;
158 }
159 }
160
161 // Move words so that no positions are negative
162 int x1 = 0x7FFFFFFF;
163 int x2 = -x1;
164 int y1 = x1;
165 int y2 = x2;
166 for (Word* word : m_solution) {
167 QList<QPoint> positions = word->positions();
168 for (const QPoint& pos : positions) {
169 x1 = std::min(x1, pos.x());
170 y1 = std::min(y1, pos.y());
171 x2 = std::max(x2, pos.x());
172 y2 = std::max(y2, pos.y());
173 }
174 }
175 m_size = QSize(x2 - x1 + 1, y2 - y1 + 1);
176
177 QPoint delta = QPoint(-x1, -y1);
178 for (Word* word : m_solution) {
179 word->moveBy(delta);
180 }
181
182 m_words->resetAnagramFilters();
183
184 emit generated();
185 }
186
187 //-----------------------------------------------------------------------------
188
cleanUp()189 void Pattern::cleanUp() {
190 qDeleteAll(m_solution);
191 m_solution.clear();
192 m_words->resetAnagramFilters();
193 m_current = QPoint(0,0);
194 }
195
196 //-----------------------------------------------------------------------------
197
addWord(int)198 Word* Pattern::addWord(int) {
199 return 0;
200 }
201
202 //-----------------------------------------------------------------------------
203
addWord(int step)204 Word* ChainPattern::addWord(int step) {
205 Word* result = 0;
206 switch (step) {
207 case 0:
208 result = addRandomWord(Qt::Vertical);
209 break;
210 case 1:
211 result = addRandomWord(Qt::Horizontal);
212 m_current += QPoint(wordLength(), 0);
213 break;
214 case 2:
215 result = addRandomWord(Qt::Vertical);
216 m_current += QPoint(-wordLength(), wordLength());
217 break;
218 case 3:
219 result = addRandomWord(Qt::Horizontal);
220 m_current += QPoint(wordLength() - 1, wordLength() / -2);
221 break;
222 case 4:
223 result = addRandomWord(Qt::Horizontal);
224 m_current = QPoint(m_current.x() + wordLength() - 1, 0);
225 break;
226 default:
227 break;
228 }
229 return result;
230 }
231
232 //-----------------------------------------------------------------------------
233
addWord(int step)234 Word* FencePattern::addWord(int step) {
235 Word* result = 0;
236 switch (step) {
237 case 0:
238 result = addRandomWord(Qt::Vertical);
239 m_current += QPoint(0, 1);
240 break;
241 case 1:
242 result = addRandomWord(Qt::Horizontal);
243 m_current += QPoint(0, 2);
244 break;
245 case 2:
246 result = addRandomWord(Qt::Horizontal);
247 m_current += QPoint(wordLength(), -3);
248 break;
249 case 3:
250 result = addRandomWord(Qt::Vertical);
251 break;
252 case 4:
253 result = addRandomWord(Qt::Horizontal);
254 m_current += QPoint(0, 2);
255 break;
256 case 5:
257 result = addRandomWord(Qt::Horizontal);
258 m_current += QPoint(wordLength(),- 2);
259 break;
260 default:
261 break;
262 }
263 return result;
264 }
265
266 //-----------------------------------------------------------------------------
267
addWord(int step)268 Word* RingsPattern::addWord(int step) {
269 Word* result = 0;
270 switch (step) {
271 case 0:
272 result = addRandomWord(Qt::Horizontal);
273 break;
274 case 1:
275 result = addRandomWord(Qt::Vertical);
276 m_current += QPoint(0, wordLength());
277 break;
278 case 2:
279 result = addRandomWord(Qt::Horizontal);
280 m_current += QPoint(wordLength(), -wordLength());
281 break;
282 case 3:
283 result = addRandomWord(Qt::Vertical);
284 m_current = QPoint(m_current.x() - 2, m_current.y() ? 0 : (wordLength() - 2));
285 break;
286 default:
287 break;
288 }
289 return result;
290 }
291
292 //-----------------------------------------------------------------------------
293
addWord(int step)294 Word* StairsPattern::addWord(int step) {
295 Word* result = 0;
296 switch (step) {
297 case 0:
298 result = addRandomWord(Qt::Horizontal);
299 m_current += QPoint(wordLength() - 1, 0);
300 break;
301 case 1:
302 result = addRandomWord(Qt::Vertical);
303 m_current += QPoint(0, wordLength());
304 break;
305 default:
306 break;
307 }
308 return result;
309 }
310
311 //-----------------------------------------------------------------------------
312
addWord(int step)313 Word* TwistyPattern::addWord(int step) {
314 return step ? stepTwo() : stepOne();
315 }
316
317 //-----------------------------------------------------------------------------
318
stepOne()319 Word* TwistyPattern::stepOne() {
320 QList<QPoint> positions;
321 for (int i = 0; i <= wordLength(); ++i) {
322 positions.append(m_current + QPoint(0, i));
323 }
324
325 while (!positions.isEmpty()) {
326 QPoint pos = positions.takeAt(randomInt(positions.count()));
327
328 // Define possible range for word
329 int right = wordLength() + pos.x() - 1;
330 int left = -wordLength() + pos.x() + 1;
331
332 // Check for conflicting words on the right side of range for word
333 for (int x = 1; x <= wordLength(); ++x) {
334 for (int y = -1; y < 2; ++y) {
335 QPoint test(pos.x() + x, pos.y() + y);
336 if (!at(test).isNull()) {
337 right = x + pos.x() - 2;
338 x = wordLength();
339 break;
340 }
341 }
342 }
343
344 // Check for conflicting words on the left side of range for word
345 for (int x = -1; x >= -wordLength(); --x) {
346 for (int y = -1; y < 2; ++y) {
347 QPoint test(pos.x() + x, pos.y() + y);
348 if (!at(test).isNull()) {
349 left = x + pos.x() + 2;
350 x = -wordLength();
351 break;
352 }
353 }
354 }
355
356 // Randomly place word in range if it can fit
357 int length = right - left;
358 int offset = length - wordLength();
359 if (offset >= 0) {
360 left += offset ? randomInt(offset) : 0;
361 right = left + wordLength();
362 m_current = QPoint(left, pos.y());
363 return addRandomWord(Qt::Horizontal);
364 }
365 }
366
367 return 0;
368 }
369
370 //-----------------------------------------------------------------------------
371
stepTwo()372 Word* TwistyPattern::stepTwo() {
373 QList<QPoint> positions;
374 for (int i = 0; i <= wordLength(); ++i) {
375 positions.append(m_current + QPoint(i, 0));
376 }
377
378 while (!positions.isEmpty()) {
379 QPoint pos = positions.takeAt(randomInt(positions.count()));
380
381 // Define possible range for word
382 int bottom = wordLength() + pos.y() - 1;
383 int top = -wordLength() + pos.y() + 1;
384
385 // Check for conflicting words on the bottom of range for word
386 for (int y = 1; y <= wordLength(); ++y) {
387 for (int x = -1; x < 2; ++x) {
388 QPoint test(pos.x() + x, pos.y() + y);
389 if (!at(test).isNull()) {
390 bottom = y + pos.y() - 2;
391 y = wordLength();
392 break;
393 }
394 }
395 }
396
397 // Check for conflicting words on the top of range for word
398 for (int y = -1; y >= -wordLength(); --y) {
399 for (int x = -1; x < 2; ++x) {
400 QPoint test(pos.x() + x, pos.y() + y);
401 if (!at(test).isNull()) {
402 top = y + pos.y() + 2;
403 y = -wordLength();
404 break;
405 }
406 }
407 }
408
409 // Randomly place word in range if it can fit
410 int length = bottom - top;
411 int offset = length - wordLength();
412 if (offset >= 0) {
413 top += offset ? randomInt(offset) : 0;
414 bottom = top + wordLength();
415 m_current = QPoint(pos.x(), top);
416 return addRandomWord(Qt::Vertical);
417 }
418 }
419
420 return 0;
421 }
422
423 //-----------------------------------------------------------------------------
424
addWord(int step)425 Word* WavePattern::addWord(int step) {
426 Word* result = 0;
427 switch (step) {
428 case 0:
429 result = addRandomWord(Qt::Horizontal);
430 m_current += QPoint(wordLength(), 0);
431 break;
432 case 1:
433 result = addRandomWord(Qt::Vertical);
434 m_current += QPoint(0, wordLength());
435 break;
436 case 2:
437 result = addRandomWord(Qt::Horizontal);
438 m_current += QPoint(wordLength(), -wordLength());
439 break;
440 case 3:
441 result = addRandomWord(Qt::Vertical);
442 break;
443 default:
444 break;
445 }
446 return result;
447 }
448