summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJohn Fultz <jfultz@wolfram.com>2015-09-07 17:23:14 -0500
committerJohn Fultz <jfultz@wolfram.com>2015-09-07 17:23:14 -0500
commited46987403dd923d3ba14df6eb676e1e163d1d8d (patch)
tree08fa8b962ca037f2ecf05b722097e1719c41d173
parent5350a57f1be22b28914fca14225c73dac5b30b24 (diff)
Fix another alphabet length limitation
The 'crosses' code for checking "fit between" plays was using a 32-bit integer as a bitfield. Now it's using C++ bitfields (including the C++11 all() operation...hopefully that doesn't cause any problems). This removes another place in the code that was limiting alphabets to 32 letters.
-rw-r--r--board.cpp4
-rw-r--r--board.h25
-rw-r--r--generator.cpp70
-rw-r--r--generator.h46
4 files changed, 54 insertions, 91 deletions
diff --git a/board.cpp b/board.cpp
index bf60e84..452501b 100644
--- a/board.cpp
+++ b/board.cpp
@@ -744,8 +744,8 @@ void Board::prepareEmptyBoard()
{
m_letters[i][j] = QUACKLE_NULL_MARK;
m_isBlank[i][j] = false;
- m_vcross[i][j] = Utility::Max;
- m_hcross[i][j] = Utility::Max;
+ m_vcross[i][j].set();
+ m_hcross[i][j].set();
}
}
}
diff --git a/board.h b/board.h
index 30c6dcf..ce5aa8f 100644
--- a/board.h
+++ b/board.h
@@ -20,6 +20,7 @@
#define QUACKLE_BOARD_H
#include <vector>
+#include <bitset>
#include "alphabetparameters.h"
#include "bag.h"
@@ -27,7 +28,9 @@
#include "rack.h"
using namespace std;
-
+
+typedef bitset<QUACKLE_MAXIMUM_ALPHABET_SIZE> LetterBitset;
+
#define QUACKLE_MAXIMUM_BOARD_SIZE LETTER_STRING_MAXIMUM_LENGTH
#define QUACKLE_MINIMUM_BOARD_SIZE 7
@@ -122,11 +125,11 @@ public:
bool isBlank(int row, int col) const;
bool isBritish(int row, int col) const;
- int vcross(int row, int col) const;
- void setVCross(int row, int col, int vcross);
+ const LetterBitset &vcross(int row, int col) const;
+ void setVCross(int row, int col, const LetterBitset &vcross);
- int hcross(int row, int col) const;
- void setHCross(int row, int col, int hcross);
+ const LetterBitset &hcross(int row, int col) const;
+ void setHCross(int row, int col, const LetterBitset &hcross);
protected:
int m_width;
@@ -137,8 +140,8 @@ protected:
bool m_isBlank[QUACKLE_MAXIMUM_BOARD_SIZE][QUACKLE_MAXIMUM_BOARD_SIZE];
bool m_isBritish[QUACKLE_MAXIMUM_BOARD_SIZE][QUACKLE_MAXIMUM_BOARD_SIZE];
- int m_vcross[QUACKLE_MAXIMUM_BOARD_SIZE][QUACKLE_MAXIMUM_BOARD_SIZE];
- int m_hcross[QUACKLE_MAXIMUM_BOARD_SIZE][QUACKLE_MAXIMUM_BOARD_SIZE];
+ LetterBitset m_vcross[QUACKLE_MAXIMUM_BOARD_SIZE][QUACKLE_MAXIMUM_BOARD_SIZE];
+ LetterBitset m_hcross[QUACKLE_MAXIMUM_BOARD_SIZE][QUACKLE_MAXIMUM_BOARD_SIZE];
inline bool isNonempty(int row, int column) const;
};
@@ -163,22 +166,22 @@ inline bool Board::isBritish(int row, int col) const
return m_isBritish[row][col];
}
-inline int Board::vcross(int row, int col) const
+inline const LetterBitset &Board::vcross(int row, int col) const
{
return m_vcross[row][col];
}
-inline void Board::setVCross(int row, int col, int vcross)
+inline void Board::setVCross(int row, int col, const LetterBitset &vcross)
{
m_vcross[row][col] = vcross;
}
-inline int Board::hcross(int row, int col) const
+inline const LetterBitset &Board::hcross(int row, int col) const
{
return m_hcross[row][col];
}
-inline void Board::setHCross(int row, int col, int hcross)
+inline void Board::setHCross(int row, int col, const LetterBitset &hcross)
{
m_hcross[row][col] = hcross;
}
diff --git a/generator.cpp b/generator.cpp
index f2923b8..d20b320 100644
--- a/generator.cpp
+++ b/generator.cpp
@@ -132,7 +132,7 @@ void Generator::allCrosses()
int col = vcols[i];
if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) {
- board().setVCross(row, col, 0);
+ board().setVCross(row, col, LetterBitset());
}
else {
LetterString pre;
@@ -167,7 +167,7 @@ void Generator::allCrosses()
#endif
if (pre.empty() && suf.empty()) {
- board().setVCross(row, col, Utility::Max);
+ board().setVCross(row, col, LetterBitset().set());
}
else {
board().setVCross(row, col, fitbetween(pre, suf));
@@ -184,7 +184,7 @@ void Generator::allCrosses()
int col = hcols[i];
if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) {
- board().setHCross(row, col, 0);
+ board().setHCross(row, col, LetterBitset());
}
else {
LetterString pre;
@@ -214,7 +214,7 @@ void Generator::allCrosses()
}
}
if (pre.empty() && suf.empty()) {
- board().setHCross(row, col, Utility::Max);
+ board().setHCross(row, col, LetterBitset().set());
}
else {
board().setHCross(row, col, fitbetween(pre, suf));
@@ -340,7 +340,7 @@ void Generator::makeMove(const Move &move, bool regenerateCrosses)
int row = vrows[i];
int col = vcols[i];
if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) {
- board().setVCross(row, col, 0);
+ board().setVCross(row, col, LetterBitset());
}
else {
LetterString pre;
@@ -374,7 +374,7 @@ void Generator::makeMove(const Move &move, bool regenerateCrosses)
#endif
if ((pre.empty()) && (suf.empty())) {
- board().setVCross(row, col, Utility::Max);
+ board().setVCross(row, col, LetterBitset().set());
}
else {
board().setVCross(row, col, fitbetween(pre, suf));
@@ -391,7 +391,7 @@ void Generator::makeMove(const Move &move, bool regenerateCrosses)
int col = hcols[i];
if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) {
- board().setHCross(row, col, 0);
+ board().setHCross(row, col, LetterBitset());
}
else {
LetterString pre;
@@ -425,7 +425,7 @@ void Generator::makeMove(const Move &move, bool regenerateCrosses)
#endif
if ((pre.empty()) && (suf.empty())) {
- board().setHCross(row, col, Utility::Max);
+ board().setHCross(row, col, LetterBitset().set());
}
else {
board().setHCross(row, col, fitbetween(pre, suf));
@@ -486,13 +486,13 @@ bool Generator::checksuffix(int i, const LetterString &suffix) {
}
}
-int Generator::gaddagFitbetween(const LetterString &pre, const LetterString &suf)
+LetterBitset Generator::gaddagFitbetween(const LetterString &pre, const LetterString &suf)
{
// UVcout << "fit "
// << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre)
// << "_"
// << QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl;
- int crosses = 0;
+ LetterBitset crosses;
/* process the suffix once */
const GaddagNode *sufNode = QUACKLE_LEXICON_PARAMETERS->gaddagRoot();
int sufLen = suf.length();
@@ -518,13 +518,13 @@ int Generator::gaddagFitbetween(const LetterString &pre, const LetterString &suf
}
if (n && n->isTerminal()) {
- crosses |= Utility::Bits[(int)(childLetter - QUACKLE_FIRST_LETTER)];
+ crosses.set(childLetter - QUACKLE_FIRST_LETTER);
}
}
return crosses;
}
-int Generator::fitbetween(const LetterString &pre, const LetterString &suf)
+LetterBitset Generator::fitbetween(const LetterString &pre, const LetterString &suf)
{
if (QUACKLE_LEXICON_PARAMETERS->hasGaddag()) {
return gaddagFitbetween(pre, suf);
@@ -533,7 +533,7 @@ int Generator::fitbetween(const LetterString &pre, const LetterString &suf)
//UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) << "_" <<
// QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl;
- int crosses = 0;
+ LetterBitset crosses;
for (Letter c = QUACKLE_FIRST_LETTER; c <= QUACKLE_ALPHABET_PARAMETERS->lastLetter(); c++) {
/*
@@ -544,7 +544,7 @@ int Generator::fitbetween(const LetterString &pre, const LetterString &suf)
*/
if (checksuffix(1, pre + c + suf)) {
// subtract first letter because crosses hold values starting from zero
- crosses |= Utility::Bits[c - QUACKLE_FIRST_LETTER];
+ crosses.set(c - QUACKLE_FIRST_LETTER);
//UVcout << " that's a word" << endl;
// UVcout << c;
}
@@ -565,12 +565,12 @@ UVString Generator::counts2string()
return ret;
}
-UVString Generator::cross2string(int cross)
+UVString Generator::cross2string(const LetterBitset &cross)
{
UVString ret;
for (int i = 0; i < QUACKLE_ALPHABET_PARAMETERS->length(); i++)
- if (cross & Utility::Bits[i])
+ if (cross.test(i))
ret += QUACKLE_ALPHABET_PARAMETERS->userVisible(QUACKLE_FIRST_LETTER + i);
return ret;
@@ -811,7 +811,7 @@ void Generator::gordongen(int pos, const LetterString &word, const GaddagNode *n
currow += pos;
}
- int cross;
+ LetterBitset cross;
if (m_gordonhoriz) {
cross = board().vcross(currow, curcol);
}
@@ -835,7 +835,7 @@ void Generator::gordongen(int pos, const LetterString &word, const GaddagNode *n
Letter childLetter = child->letter();
if ((m_counts[childLetter] <= 0)
- || !(cross & Utility::Bits[(int)(childLetter - QUACKLE_FIRST_LETTER)])) {
+ || !cross.test(childLetter - QUACKLE_FIRST_LETTER)) {
continue;
}
@@ -862,7 +862,7 @@ void Generator::gordongen(int pos, const LetterString &word, const GaddagNode *n
break;
}
- if (cross & Utility::Bits[(int)(childLetter - QUACKLE_FIRST_LETTER)]) {
+ if (cross.test(childLetter - QUACKLE_FIRST_LETTER)) {
m_counts[QUACKLE_BLANK_MARK]--;
m_laid++;
// UVcout << " yeah that'll work" << endl;
@@ -917,14 +917,14 @@ void Generator::extendright(const LetterString &partial, int i,
if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(rowpos, colpos))) {
if (m_counts[c] >= 1) {
- int cross;
+ LetterBitset cross;
if (horizontal) {
cross = board().vcross(rowpos, colpos);
}
else {
cross = board().hcross(rowpos, colpos);
}
- if (cross & Utility::Bits[(int)(c - QUACKLE_FIRST_LETTER)]) {
+ if (cross.test(c - QUACKLE_FIRST_LETTER)) {
if (t) {
bool couldend = true;
if (dirpos < edgeDirpos) {
@@ -953,7 +953,7 @@ void Generator::extendright(const LetterString &partial, int i,
int laid = move.wordTilesWithNoPlayThru().length();
bool onetilevert = (!move.horizontal) && (laid == 1);
- bool ignore = onetilevert && (board().hcross(row, col) != Utility::Max);
+ bool ignore = onetilevert && !board().hcross(row, col).all();
if (1 || !ignore)
{
@@ -982,14 +982,14 @@ void Generator::extendright(const LetterString &partial, int i,
}
}
if ((m_counts[QUACKLE_BLANK_MARK] >= 1)) {
- int cross;
+ LetterBitset cross;
if (horizontal) {
cross = board().vcross(rowpos, colpos);
}
else {
cross = board().hcross(rowpos, colpos);
}
- if (cross & Utility::Bits[(int)(c - QUACKLE_FIRST_LETTER)]) {
+ if (cross.test(c - QUACKLE_FIRST_LETTER)) {
if (t) {
bool couldend = true;
if (dirpos < edgeDirpos) {
@@ -1015,7 +1015,7 @@ void Generator::extendright(const LetterString &partial, int i,
int laid = move.wordTilesWithNoPlayThru().length();
bool onetilevert = (!move.horizontal) && (laid == 1);
- bool ignore = onetilevert && (board().hcross(row, col) != Utility::Max);
+ bool ignore = onetilevert && !board().hcross(row, col).all();
if (1 || !ignore)
{
@@ -1106,7 +1106,7 @@ void Generator::extendright(const LetterString &partial, int i,
int laid = move.wordTilesWithNoPlayThru().length();
bool onetilevert = (!move.horizontal) && (laid == 1);
- bool ignore = onetilevert && (board().hcross(row, col) != Utility::Max);
+ bool ignore = onetilevert && !board().hcross(row, col).all();
if (1 || !ignore)
{
@@ -1206,7 +1206,7 @@ Move Generator::generate()
// what defines an anchor square?
bool anchor = false;
- if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && (board().vcross(row, col) != Utility::Max)) {
+ if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && !board().vcross(row, col).all()) {
if (col == 0) {
anchor = true;
}
@@ -1229,7 +1229,7 @@ Move Generator::generate()
{
// UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl;
- if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i)) && (board().vcross(row, i) == Utility::Max)) {
+ if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i)) && board().vcross(row, i).all()) {
if (i == 0) {
k++;
}
@@ -1256,7 +1256,7 @@ Move Generator::generate()
// what defines an anchor square?
anchor = false;
- if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && (board().hcross(row, col) != Utility::Max)) {
+ if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && !board().hcross(row, col).all()) {
if (row == 0) {
anchor = true;
}
@@ -1277,7 +1277,7 @@ Move Generator::generate()
int k = 0;
for (int i = row - 1; i >= 0; i--) {
// UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl;
- if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col)) && (board().hcross(i, col) == Utility::Max)) {
+ if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col)) && board().hcross(i, col).all()) {
if (i == 0) {
k++;
}
@@ -1313,7 +1313,7 @@ Move Generator::gordongenerate()
// generate horizontal plays
// what defines an anchor square?
bool anchor = false;
- if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && (board().vcross(row, col) != Utility::Max)) {
+ if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && !board().vcross(row, col).all()) {
if (col == 0) {
if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col + 1))) {
anchor = true;
@@ -1350,7 +1350,7 @@ Move Generator::gordongenerate()
}
for (int i = col - k - 1; i >= 0; i--) {
// UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl;
- if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i)) && (board().vcross(row, i) == Utility::Max)) {
+ if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i)) && board().vcross(row, i).all()) {
if (i == 0) {
k++;
}
@@ -1380,7 +1380,7 @@ Move Generator::gordongenerate()
// what defines an anchor square?
anchor = false;
- if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && (board().hcross(row, col) != Utility::Max)) {
+ if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && !board().hcross(row, col).all()) {
if (row == 0) {
if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row + 1, col))) {
anchor = true;
@@ -1417,7 +1417,7 @@ Move Generator::gordongenerate()
}
for (int i = row - k - 1; i >= 0; i--) {
// UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl;
- if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col)) && (board().hcross(i, col) == Utility::Max)) {
+ if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col)) && board().hcross(i, col).all()) {
if (i == 0) {
k++;
}
@@ -1609,7 +1609,7 @@ Move Generator::exchange()
{
LetterString thrown;
for (int j = 0; j < rackSize; j++)
- if (i & Utility::Bits[j])
+ if (i & (1 << j))
thrown += rack().tiles()[j];
Move move;
diff --git a/generator.h b/generator.h
index 70908b1..6d207e0 100644
--- a/generator.h
+++ b/generator.h
@@ -125,7 +125,7 @@ private:
void readFromDawg(int index, unsigned int &p, Letter &letter, bool &t, bool &lastchild, bool &british, int &playability) const;
bool checksuffix(int i, const LetterString &suffix);
- int fitbetween(const LetterString &pre, const LetterString &suf);
+ LetterBitset fitbetween(const LetterString &pre, const LetterString &suf);
void extendright(const LetterString &partial, int i,
int row, int col, int edge, int righttiles,
bool horizontal);
@@ -134,7 +134,7 @@ private:
void spit(int i, const LetterString &prefix, int flags);
void wordspit(int i, const LetterString &prefix, int flags);
- int gaddagFitbetween(const LetterString &pre, const LetterString &suf);
+ LetterBitset gaddagFitbetween(const LetterString &pre, const LetterString &suf);
void gaddagAnagram(const GaddagNode *node, const LetterString &prefix, int flags);
void gordongen(int pos, const LetterString &word, const GaddagNode *node);
void gordongoon(int pos, char L, LetterString word, const GaddagNode *node);
@@ -143,7 +143,7 @@ private:
// debug stuff
UVString counts2string();
- UVString cross2string(int cross);
+ UVString cross2string(const LetterBitset &cross);
Move best;
@@ -167,46 +167,6 @@ private:
int m_anchorrow, m_anchorcol;
};
-namespace Utility
-{
- const int Max = 0xFFFFFFFF;
-
- const int Bits[32] =
- {
- 1 << 0,
- 1 << 1,
- 1 << 2,
- 1 << 3,
- 1 << 4,
- 1 << 5,
- 1 << 6,
- 1 << 7,
- 1 << 8,
- 1 << 9,
- 1 << 10,
- 1 << 11,
- 1 << 12,
- 1 << 13,
- 1 << 14,
- 1 << 15,
- 1 << 16,
- 1 << 17,
- 1 << 18,
- 1 << 19,
- 1 << 20,
- 1 << 21,
- 1 << 22,
- 1 << 23,
- 1 << 24,
- 1 << 25,
- 1 << 26,
- 1 << 27,
- 1 << 28,
- 1 << 29,
- 1 << 30,
- 1 << 31
- };
-};
inline void Generator::setPosition(const GamePosition &position)
{