#include <stdlib.h>
#include <math.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include "Matrix.h"

bool isPrefix(const string& prefix, const string& word) {
	return word.find(prefix)==0;
}

// ofstream als membervariabele geeft bug in Borland Builder 5
ofstream solutionStream("solution.txt");

class Puzzle {
public:
	Puzzle();
	int solvePuzzle() const;
private:
	matrix<char> theBoard;
	vector<string> theWords;
	ifstream puzzleStream;
	ifstream wordStream;

	void openFile(const char* message, ifstream& inFile, const char* defname);
	void readPuzzle();
	void readWords();
	int solveDirection(int baseRow, int baseCol, int rowDelta, int colDelta) const;
};


int Puzzle::solvePuzzle() const {
	int matches(0);
	for (int r(0); r<theBoard.numrows(); ++r)
		for (int c(0); c<theBoard.numcols(); ++c)
			for (int rd(-1); rd<=1; ++rd)
				for (int cd(-1); cd<=1; ++cd)
					if (rd!=0 || cd!=0)
						matches+=solveDirection(r, c, rd, cd);
	return matches;
}

int Puzzle::solveDirection(int baseRow, int baseCol, int rowDelta, int colDelta) const {
	int numMatches(0);
	string word;
	word=theBoard[baseRow][baseCol];
	int i(baseRow+rowDelta);
	int j(baseCol+colDelta);
	while (i>=0 && j>=0 && i<theBoard.numrows() && j<theBoard.numcols()) {
		word+=theBoard[i][j];
		vector<string>::const_iterator itr(lower_bound(theWords.begin(), theWords.end(), word));
		if (itr==theWords.end() || !isPrefix(word, *itr))
			break;
		if (*itr==word && word.size()>3) {
			numMatches++;
			solutionStream<<"Found "<<word<<" at "<<baseRow<<" "<<baseCol<<" to "<<i<<" "<<j<<endl;
		}
		i+=rowDelta;
		j+=colDelta;
	}
	return numMatches;
}

void Puzzle::openFile(const char* message, ifstream& file, const char* defname) {
	do {
		cout<<message<<" (1="<<defname<<"): ";
		string name;
		cin>>name;
		if (name=="1")
			name=defname;
		file.open(name.c_str());
	} while(!file);
}

Puzzle::Puzzle(): theBoard(0, 0) {
	openFile("Enter puzzle file", puzzleStream, "puzzle.txt");
	openFile("Enter dictionary name", wordStream, "webster.txt");
	readPuzzle();
	readWords();
}

vector<char> toVec(const string& str) {
	vector<char> v;
	copy(str.begin(), str.end(), back_inserter(v));
	return v;
}

void Puzzle::readPuzzle() {
	string oneLine;
	if (getline(puzzleStream, oneLine).eof())
		return;

	string::size_type columns(oneLine.length());
	theBoard.push_back(toVec(oneLine));

	while (!(getline(puzzleStream, oneLine)).eof()) {
		if (oneLine.length()!=columns)
			cerr<<"Puzzle is not rectangular"<<endl;
		else
			theBoard.push_back(toVec(oneLine));
	}
}

void Puzzle::readWords() {
	string thisWord;
	for (int numEntries(0); wordStream>>thisWord; ++numEntries) {
		theWords.push_back(thisWord);
		if (numEntries!=0 && theWords[numEntries]<theWords[numEntries-1]) {
			cerr<<"Dictionary is not sorted... skipping"<<endl;
			continue;
		}
	}
}

int main() {
	Puzzle p;
	cout<<"Found "<<p.solvePuzzle()<<" matches (writen to solutions.txt)."<<endl;
	cin.get();
	return 0;
}