Merge branch 'feature/editablesettings'

1 files changed, 326 insertions, 0 deletions

diff --git a/quackleio/dawgfactory.cpp b/quackleio/dawgfactory.cpp
new file mode 100644
index 0000000..4dd4ec3
--- /dev/null
+++ b/quackleio/dawgfactory.cpp
@@ -0,0 +1,326 @@
+/*
+ *  Quackle -- Crossword game artificial intelligence and analysis tool
+ *  Copyright (C) 2005-2014 Jason Katz-Brown and John O'Laughlin.
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 3 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+
+#include <iomanip>
+#include <ios>
+#include <iostream>
+#include <QtCore>
+#include <QCryptographicHash>
+
+#include "dawgfactory.h"
+#include "util.h"
+
+
+DawgFactory::DawgFactory(const QString &alphabetFile)
+	: m_encodableWords(0), m_unencodableWords(0), m_duplicateWords(0),
+	m_countsByLength(Quackle::FixedLengthString::maxSize, 0)
+{
+	QuackleIO::FlexibleAlphabetParameters *flexure = new QuackleIO::FlexibleAlphabetParameters;
+	flexure->load(alphabetFile);
+	m_alphas = flexure;
+
+	m_root.insmallerdict = false;
+	m_root.playability = 0;
+	m_root.c = QUACKLE_BLANK_MARK;
+	m_root.pointer = 0;
+	m_root.lastchild = true;
+
+	m_hash.int32ptr[0] = m_hash.int32ptr[1] = m_hash.int32ptr[2] = m_hash.int32ptr[3] = 0;
+}
+
+DawgFactory::~DawgFactory()
+{
+	delete m_alphas;
+}
+
+bool DawgFactory::pushWord(const UVString &word, bool inSmaller, int playability)
+{
+	UVString leftover;
+	Quackle::LetterString encodedWord = m_alphas->encode(word, &leftover);
+	if (leftover.empty())
+		return pushWord(encodedWord, inSmaller, playability);
+
+	++m_unencodableWords;
+	return false;
+}
+
+bool DawgFactory::pushWord(const Quackle::LetterString &word, bool inSmaller, int playability)
+{
+	if (m_root.pushWord(word, inSmaller, playability))
+	{
+		++m_encodableWords;
+		++m_countsByLength[word.length()];
+		hashWord(word);
+		return true;
+	}
+	++m_duplicateWords;
+	return false;
+}
+
+void DawgFactory::hashWord(const Quackle::LetterString &word)
+{
+	QCryptographicHash wordhash(QCryptographicHash::Md5);
+	wordhash.addData(word.constData(), word.length());
+	QByteArray wordhashbytes = wordhash.result();
+	m_hash.int32ptr[0] ^= ((const int32_t*)wordhashbytes.constData())[0];
+	m_hash.int32ptr[1] ^= ((const int32_t*)wordhashbytes.constData())[1];
+	m_hash.int32ptr[2] ^= ((const int32_t*)wordhashbytes.constData())[2];
+	m_hash.int32ptr[3] ^= ((const int32_t*)wordhashbytes.constData())[3];
+}
+
+void DawgFactory::generate()
+{
+	const int bucketcount = 2000;
+	vector< int > bucket[bucketcount];
+
+	m_nodelist.clear();
+	m_nodelist.push_back(&m_root);
+	m_root.print(m_nodelist);
+
+	m_nodelist[0]->letterSum();
+
+	for (unsigned int i = 0; i < m_nodelist.size(); i++)
+	{
+		bucket[m_nodelist[i]->sum % bucketcount].push_back(i);
+		m_nodelist[i]->pointer = 0;
+		m_nodelist[i]->written = false;
+		m_nodelist[i]->deleted = false;
+		m_nodelist[i]->cloneof = NULL;
+	}
+
+	for (int b = 0; b < bucketcount; b++)
+	{
+		if (bucket[b].size() == 0)
+			continue;
+		for (vector<int>::iterator it = bucket[b].begin(); it != bucket[b].end() - 1; it++)
+		{
+			if (!m_nodelist[(*it)]->deleted)
+			{	
+				for (vector<int>::iterator jt = it + 1; jt != bucket[b].end(); jt++)
+				{
+					if (!m_nodelist[(*jt)]->deleted)
+					{
+						// cout << "Comparing " << (*it) << " and " << (*jt) << endl;
+						if (m_nodelist[(*it)]->equals(m_nodelist[(*jt)][0]))
+						{
+							//cout << "Hey! " << (*it) << " == " << (*jt) << endl;
+							// ones[l].erase(jt);
+							m_nodelist[(*jt)]->deleted = true;
+							m_nodelist[(*jt)]->cloneof = m_nodelist[(*it)];
+						}
+					}
+				}
+			}
+		}
+	}
+	
+	m_nodelist.clear();
+	m_nodelist.push_back(&m_root);
+	m_root.print(m_nodelist);
+}
+
+void DawgFactory::writeIndex(const string &filename)
+{
+	ofstream out(filename.c_str(), ios::out | ios::binary);
+	unsigned char bytes[7];
+
+	bytes[0] = (m_encodableWords & 0x00FF0000) >> 16;
+	bytes[1] = (m_encodableWords & 0x0000FF00) >>  8;
+	bytes[2] = (m_encodableWords & 0x000000FF);
+
+	out.put(1); // DAWG format version 1
+	out.write(m_hash.charptr, sizeof(m_hash.charptr));
+	out.write((char*)bytes, 3);
+	out.put((char)m_alphas->length());
+	for (Quackle::Letter i = m_alphas->firstLetter(); i <= m_alphas->lastLetter(); i++)
+	{
+		QString letterText = QuackleIO::Util::uvStringToQString(m_alphas->letterParameter(i).text());
+		QByteArray utf8bytes = letterText.toUtf8();
+		string utf8LetterText(utf8bytes.constData());
+		out << utf8LetterText << ' ';
+	}
+
+	for (unsigned int i = 0; i < m_nodelist.size(); i++) {
+		//cout << m_nodelist[i]->c << " " << m_nodelist[i]->pointer << " " << m_nodelist[i]->t << " " << m_nodelist[i]->lastchild << endl;
+		Node* n = m_nodelist[i];
+		unsigned int p;
+		if (m_nodelist[i]->deleted)
+		{
+			p = (unsigned int)(m_nodelist[i]->cloneof->pointer);
+			// n = m_nodelist[i]->cloneof;
+		}
+		else
+			p = (unsigned int)(m_nodelist[i]->pointer);
+
+		bytes[0] = (p & 0x00FF0000) >> 16;
+		bytes[1] = (p & 0x0000FF00) >>  8;
+		bytes[2] = (p & 0x000000FF);
+		bytes[3] = n->c - QUACKLE_FIRST_LETTER;
+				
+		unsigned int pb = n->playability;
+		bytes[4] = (pb & 0x00FF0000) >> 16;
+		bytes[5] = (pb & 0x0000FF00) >>  8;
+		bytes[6] = (pb & 0x000000FF);
+
+		if (n->lastchild) {
+			bytes[3] |= 64;
+		}
+		if (n->insmallerdict) {
+			bytes[3] |= 128;
+		}
+
+		out.write((char*)bytes, 7);
+	}
+}
+
+string DawgFactory::letterCountString() const
+{
+	ostringstream str;
+	for (int i = 0; i < 4; i++)
+	{
+		for (int j = 0; j < 4; j++)
+		{
+			const int letterCount = j * 4 + i + 2;
+			if (j != 0)
+				str << "\t";
+			if (m_countsByLength[letterCount] > 0)
+				str << letterCount << "s: " << std::setw(7) << std::right << std::setfill(' ') << m_countsByLength[letterCount];
+		}
+		str << "\n";
+	}
+	return str.str();
+}
+
+
+void DawgFactory::Node::print(vector< Node* > &nodelist)
+{
+	written = true;
+	
+	if (children.size() == 0)
+		return;
+
+	if (!deleted)
+	{
+		//cout << "  Setting pointer to " << nodelist.size() << " before I push_back the children." << endl;
+		pointer = nodelist.size();
+	}
+	else
+	{
+		pointer = cloneof->pointer;
+		//cout << "  Setting pointer to clone's (" << pointer << ") and not pushing anything." << endl;
+	}
+
+	if (!deleted)
+	{
+		for (unsigned int i = 0; i < children.size(); i++) {
+			nodelist.push_back(&children[i]);
+		}
+
+		for (unsigned int i = 0; i < children.size(); i++) {
+			if (!children[i].deleted)
+				children[i].print(nodelist);
+			else if (!children[i].cloneof->written)
+				children[i].cloneof->print(nodelist);
+		}
+	}
+
+	if (children.size() > 0)	
+		children[children.size() - 1].lastchild = true;
+}
+
+
+// returns true if the word was actually added...false if it's a duplicate.
+bool DawgFactory::Node::pushWord(const Quackle::LetterString &word, bool inSmaller, int pb)
+{
+	bool added;
+	if (word.length() == 0) {
+		added = (playability == 0);
+		playability = (pb == 0) ? 1 : pb; // word terminators nodes are marked by nonzero playability in the v1 DAWG format
+		insmallerdict = inSmaller;
+	}
+	else {
+		char first = word[0];
+		Quackle::LetterString rest = word.substr(1, word.length() - 1);
+		int index = -1;
+ 
+		// cout << "first: " << first << ", rest: " << rest << endl;
+
+		for (unsigned int i = 0; i < children.size(); i++) {
+			if (children[i].c == first) {
+				index = i;
+				break;
+			}
+		}
+		
+		if (index == -1) {
+			Node n;
+			n.c = first;
+			n.playability = 0;
+			n.insmallerdict = false;
+			n.pointer = 0;
+			n.lastchild = false;
+			children.push_back(n);
+			index = children.size() - 1;
+		}
+
+		added = children[index].pushWord(rest, inSmaller, pb);
+	}
+
+	sumexplored = false;
+	deleted = false;
+	written = false;
+	return added;
+}
+
+
+bool DawgFactory::Node::equals(const Node &n) const
+{
+	if (playability != n.playability)
+		return false;
+	if (c != n.c)
+		return false;
+	if (children.size() != n.children.size())
+		return false;
+	if (insmallerdict != n.insmallerdict)
+		return false;
+	if (sum != n.sum)
+		return false;
+
+	for (unsigned int i = 0; i < children.size(); i++)
+		if (!children[i].equals(n.children[i]))
+			return false;
+	
+	return true;
+}
+
+int DawgFactory::Node::letterSum() const
+{
+	if (sumexplored)
+		return sum;
+	
+	sumexplored = true;
+
+	// djb2 checksum
+	sum = 5381 * 33 + (int) c;
+
+	for (unsigned int i = 0; i < children.size(); i++)
+		sum = (sum << 5) + sum + children[i].letterSum();
+
+	return sum;
+}