#include "Grille.h"
#include <string>
#include <fstream>
#include <iostream>
#include <string>
using namespace std;



Grid::Grid(const Grid& g)
  : tab(g.tab)
{
	hProb_i = g.hProb_i;
	hProb_j = g.hProb_j;

	prob_ckecked = false;
}

Grid::Grid(const string& name)
{
	load(name);
	prob_ckecked = false;
	hProb_i = 0;
	hProb_j = 0;
}

Grid& Grid::operator=(const Grid& g)
{
	for (unsigned i = 0; i < 9; ++i)
		for (unsigned j = 0; j < 9; ++j)
		{
			tab[i][j] = g.tab[i][j];
		}
		
		
	hProb_i = g.hProb_i;
	hProb_j = g.hProb_j;

	prob_ckecked = false;
	return *this;
}

int Grid::toInt(char c) {
	register int k = c - '0';
	if (k < 0 || k > 9)
		k = 0;
	return k;
}

void Grid::load(const string& name)
{
	ifstream in(name.c_str());
	string s;
	unsigned j=0;

	while(getline(in, s))
	{
		// traiter s
		for (unsigned i = 0; i < 9 ; ++i)
		{
			tab[i][j] = toInt(s[i]);
		}
		++j;
	}
}


void Grid::load(int t[9][9])
{
	for (unsigned i = 0; i < 9; ++i)
		for (unsigned j = 0; j < 9; ++j)
		{
			tab[i][j] = t[j][i];
		}
}



void Grid::actualize(unsigned _i, unsigned _j)
{
	// colonne
	int k=0;
	for (unsigned j = 0; j < 9 ; ++j)
	{
		if ((k=tab[_i][j].val) != 0)
			tab[_i][_j].possible.remove(k);
	}

	// ligne
	for (unsigned i = 0; i < 9 ; ++i)
	{
		if ((k=tab[i][_j].val) != 0)
			tab[_i][_j].possible.remove(k);
	}

	// bloc
	unsigned bI = (_i / 3) * 3;
	unsigned bJ = (_j / 3) * 3;
	for (unsigned i = bI; i < bI + 3; ++i)
		for (unsigned j = bJ; j < bJ + 3; ++j)
		{
			if ((k=tab[i][j].val) != 0)
				tab[_i][_j].possible.remove(k);
		}
}

bool Grid::line_ok (unsigned j) const
{
	register int s = 0;
	for (register unsigned i = 0; i < 9 ; ++i)
		s += tab[j][i].val;
	if (s != 45)
		return false;
	return true;
}

bool Grid::col_ok  (unsigned i) const
{
	register int s = 0;
	for (register unsigned j = 0; j < 9 ; ++j)
		s += tab[i][j].val;
	if (s != 45)
		return false;
	return true;
}


bool Grid::block_ok(unsigned ii, unsigned jj) const
{
	register int s = 0;
	register unsigned j;
	for (register unsigned i=ii;i<ii+3;++i)
		for (j=jj;j<jj+3;++j)
			s += tab[i][j].val;
	if (s != 45)
		return false;
	return true;
}



bool Grid::final() const
{
	register int s=0;
	register unsigned i,ii,jj;

	// col
	for (i = 0; i < 9 ; ++i)
	{
		if (not col_ok(i))
			return false;
	}

	// ligne
	s = 0;
	for (i = 0; i < 9 ; ++i)
	{
		if (not line_ok(i))
			return false;
	}

	// test les blocs
	for (ii=0;ii<9;ii+=3)
		for (jj=0;jj<9;jj+=3)
		{
			if (not block_ok(ii,jj))
				return false;
		}

	return true;
}


/*
	Si y'a qu'une seule possibilité alors on la met !
	et on fixe !
*/
bool Grid::once()
{
	unsigned i,j;
	bool ret = false;
	

	for (j = 0; j < 9; ++j)
	{
		for (i = 0; i < 9; ++i)
		{
			Case *ptr = &tab[i][j];
			if (ptr->val == 0 && ptr->possible.size() == 1)
			{
				// on remplace par la possiblité !
				ptr->val = *(ptr->possible.begin());
				ptr->possible.clear();
				ret = true;

				actualize(i,j);
			}
		}
	}
	
	if (prob_ckecked)
	{
	// si un nombre apparait qu'a un seul endroit,
	// on le met
	unsigned k = 0;

	// check les lignes
	for (j=0;j<9;++j)
	for (i=0;i<9;++i)
	{
		if (tab[i][j].val !=0)
		{
			Case *ptr = &tab[i][j];
			bool is_in = true;

			for (list<int>::const_iterator iter = ptr->possible.begin();
			                               iter!= ptr->possible.end(); ++iter)
			{
				is_in = false;
				for (k=0;k<9;++k)
				{
					if (k != i && std::find(tab[k][j].possible.begin(),tab[k][j].possible.end(), *iter) != tab[k][j].possible.end())
						is_in = true;
				}
				if (not is_in)
				{
					// single possiblitiy for *iter in (i,j)
					ptr->val = *iter;
					ptr->possible.clear();
					actualize(i,j);
				}
			}
		}
	}

	// check les colonnes
	for (i=0;i<9;++i)
	for (j=0;j<9;++j)
	{
		if (tab[i][j].val !=0)
		{
			Case *ptr = &tab[i][j];
			bool is_in = true;

			for (list<int>::const_iterator iter = ptr->possible.begin();
			                               iter!= ptr->possible.end(); ++iter)
			{
				is_in = false;
				for (k=0;k<9;++k)
				{
					if (k != i && std::find(tab[i][k].possible.begin(),tab[i][k].possible.end(), *iter) != tab[i][k].possible.end())
						is_in = true;
				}
				if (not is_in)
				{
					// single possiblitiy for *iter in (i,j)
					ptr->val = *iter;
					ptr->possible.clear();
					actualize(i,j);
				}
			}
		}
	}

	//
	//
	}
	return ret;
}


bool Grid::best()
{
	// test the best value
	bool ret = false;
	cout << "(#) Best value from (" << hProb_i << ',' << hProb_j << ") = ";

	try {
		int value = getFirstValue(hProb_i, hProb_j, ret);
		cout << value << endl;
		if (ret)
		{
			cout << "284 - best... ret = true" << endl;
			tab[hProb_i][hProb_j].val = value;
			// remove the value from old possibility
			tab[hProb_i][hProb_j].possible.remove(value);
			tab[hProb_i][hProb_j].proba.pop();
			simplify();
			once();
			setProbability();
		}
		return ret;
	}
	catch(...) { 
		return false; 
	}
	return false;
}


void Grid::simplify()
{
	unsigned i;
	for (unsigned j = 0; j < 9; ++j)
	{
		for (i = 0; i < 9; ++i)
		{
			if (tab[i][j].val == 0)
				actualize(i,j);
			else
				tab[i][j].possible.clear();
		}
	}
}

bool Grid::impossible(int value, unsigned ii, unsigned jj)
{
	register unsigned i=0,j=0;
	for (i=0;i<9;++i) // matter les lignes de la col j
		if (i != ii && (std::find(tab[i][jj].possible.begin(),tab[i][jj].possible.end(), value) != tab[i][jj].possible.end()))
			return true;

	for (j=0;j<9;++j) // matter les lignes de la col j
		if (j != jj && (std::find(tab[ii][j].possible.begin(),tab[ii][j].possible.end(), value) != tab[ii][j].possible.end()))
			return true;

	// bloc
	unsigned bI = (ii / 3) * 3;
	unsigned bJ = (jj / 3) * 3;
	for (unsigned i = bI; i < bI + 3; ++i)
		for (unsigned j = bJ; j < bJ + 3; ++j)
		{
			if (j != jj && i != ii && (std::find(tab[i][j].possible.begin(),tab[i][j].possible.end(), value) != tab[i][j].possible.end()))
				return true;
		}

	return false;
}



bool Grid::deprecated()
{
	if (not moreChoice() || (full() && not final()))
		return true;
	else
	{
		register unsigned i,j;
		for (i=0;i<9;++i)
		for (j=0;j<9;++j)
		{
			if (tab[i][j].val == 0)
			{
				if (tab[i][j].possible.size() == 0)
					return true;

				bool nested = false;
				int v = getFirstValue(i, j, nested);
				if (not nested || impossible(v,i,j))
					return true;
			}
		}
	}
	return false;
}



void Grid::setProbability()
{
	using namespace std;

	unsigned bJ,bI;
	unsigned i,j;
	

	prob_ckecked = true;

	hProb_i = hProb_j = 0;
	unsigned hProb_max = 81;

	// for each case, you calculate the probability of possible numbers
	// P(x) = nb(X) in Possibles cases
	for (j = 0; j < 9; ++j)
	{
		for (i = 0; i < 9; ++i)
		{
			Case *ptr = &tab[i][j];
			if (ptr->val == 0)
			{
				std::priority_queue<Token> proba;
				// clear probas
				ptr->proba = proba;

				// mettre les probabilités uniquement par blocs
				bJ = (j/3) * 3;
				bI = (i/3) * 3;

				// pour chaque nombre de la liste de possiblités
				for (list<int>::const_iterator iter = ptr->possible.begin();
				                               iter!= ptr->possible.end();
				                             ++iter)
				{
					register unsigned occ=0;
					register unsigned ii,jj;

					// checker les lignes et les colonnes
					for (ii=0;ii<9;++ii)
						if (std::find(tab[ii][j].possible.begin(),tab[ii][j].possible.end(), *iter) != tab[ii][j].possible.end())
							++occ;

					for (jj=0;jj<9;++jj)
						if (std::find(tab[i][jj].possible.begin(),tab[i][jj].possible.end(), *iter) != tab[i][jj].possible.end())
							++occ;

					// checker dans le bloc
					for (ii = bI; ii < bI + 3; ++ii)
					{
						for (jj = bJ; jj < bJ + 3; ++jj)
						{
							if (std::find(tab[ii][jj].possible.begin(),tab[ii][jj].possible.end(), *iter) != tab[ii][jj].possible.end())
								++occ;
						}
					}
					//------------------
					ptr->proba.push(Token(*iter, occ));

					//set max information
					if (hProb_max > occ)
					{
						hProb_max = occ;
						hProb_i = i;
						hProb_j = j;
					}
				}
			}
		}
	}
}


void print(ostream& out, const Grid& g)
{
	for (unsigned j = 0; j < 9; ++j)
	{
		for (unsigned i = 0; i < 9; ++i)
		{
			print(out, g.tab[i][j]);
		}
		out << endl;
	}
}


ostream& operator<<(ostream& out, const Grid& g)
{
	for (unsigned j = 0; j < 9; ++j)
	{
		for (unsigned i = 0; i < 9; ++i)
		{
			out << g.tab[i][j];
		}
		out << endl;
	}
	return out;
}


// Save as CMB file
void save(const Grid& g, const string& s)
{
	int t[81][81];
	float posX = 0.0f, posY = 0.0f;
	float incr= 0.09f;



	unsigned i,j;
	for (i=0;i<64;++i)
	{
		// diag sup et inf
		if (i+1<64 && i+1>0) t[i][i+1] = 1;
		if (i-1<64 && i-1>0) t[i][i-1] = 1;
	}


	for (i=0;i<8;++i)
		for (j=0;j<8;++j)
		{
			if (j + 1 < 8)
				t[8*j+(g.tab[i][j].val - 1) ][8*(j+1)+(g.tab[i][j+1].val - 1)] = 1;
		}

	ofstream out(s.c_str());
	posY = 0.09f;
	for (i=0;i<8;i++)
	{
		posX = 0.0f;
		for (j=0;j<8;++j)
		{
			out << 8*i+j+1 << ' ' << (posX += incr) << ' ' << (posY);
			for (unsigned k = 0; k < 64; ++k)
			{
				if (t[8*i+j][k] == 1)
					out << ' ' << k + 1;
			}
			out << endl;
		}
		posY += incr;
	}
}