From 5e5d414c57d5c7dd8a3037dda1555db5fb7eb486 Mon Sep 17 00:00:00 2001 From: John Fultz Date: Sat, 22 Aug 2015 01:39:47 -0500 Subject: Add versioning of DAWGs. If we're going to start writing these into user directories, then we'd better start versioning them so we don't end up generating bugs in the future. LexiconParameters::loadDawg() implements a tiny class factory which allows backward compatibility of DAWGs. I'll soon be adding a "version 1" in addition to the legacy "version 0". For now, version 1 is just dummied in. --- generator.cpp | 11 +---------- 1 file changed, 1 insertion(+), 10 deletions(-) (limited to 'generator.cpp') diff --git a/generator.cpp b/generator.cpp index 2bfc199..f2923b8 100644 --- a/generator.cpp +++ b/generator.cpp @@ -440,16 +440,7 @@ void Generator::makeMove(const Move &move, bool regenerateCrosses) void Generator::readFromDawg(int index, unsigned int &p, Letter &letter, bool &t, bool &lastchild, bool &british, int &playability) const { - index *= 7; - p = (QUACKLE_LEXICON_PARAMETERS->dawgAt(index) << 16) + (QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 1) << 8) + (QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 2)); - letter = QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 3); - - t = (letter & 32) != 0; - lastchild = (letter & 64) != 0; - british = !(letter & 128); - letter = (letter & 31) + QUACKLE_FIRST_LETTER; - - playability = (QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 4) << 16) + (QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 5) << 8) + (QUACKLE_LEXICON_PARAMETERS->dawgAt(index + 6)); + QUACKLE_LEXICON_PARAMETERS->dawgAt(index, p, letter, t, lastchild, british, playability); } bool Generator::checksuffix(int i, const LetterString &suffix) { -- cgit v1.2.3 From ed46987403dd923d3ba14df6eb676e1e163d1d8d Mon Sep 17 00:00:00 2001 From: John Fultz Date: Mon, 7 Sep 2015 17:23:14 -0500 Subject: 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. --- board.cpp | 4 ++-- board.h | 25 +++++++++++---------- generator.cpp | 70 +++++++++++++++++++++++++++++------------------------------ generator.h | 46 +++------------------------------------ 4 files changed, 54 insertions(+), 91 deletions(-) (limited to 'generator.cpp') 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 +#include #include "alphabetparameters.h" #include "bag.h" @@ -27,7 +28,9 @@ #include "rack.h" using namespace std; - + +typedef bitset 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) { -- cgit v1.2.3