diff options
author | John Fultz <jfultz@wolfram.com> | 2015-09-07 17:23:14 -0500 |
---|---|---|
committer | John Fultz <jfultz@wolfram.com> | 2015-09-07 17:23:14 -0500 |
commit | ed46987403dd923d3ba14df6eb676e1e163d1d8d (patch) | |
tree | 08fa8b962ca037f2ecf05b722097e1719c41d173 | |
parent | 5350a57f1be22b28914fca14225c73dac5b30b24 (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.cpp | 4 | ||||
-rw-r--r-- | board.h | 25 | ||||
-rw-r--r-- | generator.cpp | 70 | ||||
-rw-r--r-- | generator.h | 46 |
4 files changed, 54 insertions, 91 deletions
@@ -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(); } } } @@ -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) { |