// File: CSProblem.cpp

#include "CSProblem.h"
#include "Parser.h"

using namespace std;

CSProblem::CSProblem() : curVar(NULL), propAlgorithm(NULL), varHeuristic(NULL),
		valHeuristic(NULL), numSolutions(1) {
	vv = new VarVector();
	cv = new ConstraintVector();
}


CSProblem::CSProblem(const CSProblem& csp) {
	// Copia dei vincoli
	cv = new ConstraintVector();
	for(ConstraintVector::iterator i=csp.cv->begin(); i!=csp.cv->end(); i++) {
		Constraint *nc = new Constraint(*(*i));
		cv->push_back(nc);
	}
	// Copia delle variabili
	vv = new VarVector();
	for(VarVector::iterator j=csp.vv->begin(); j!=csp.vv->end(); j++) {
		Variable *nv = new Variable(*(*j));
		vv->push_back(nv);
	}
	curVar=csp.curVar? getVariable(csp.curVar->getName()) : NULL;
	// Copia delle altre cose
	propAlgorithm=csp.propAlgorithm;
	valHeuristic=csp.valHeuristic;
	varHeuristic=csp.varHeuristic;
	numSolutions=csp.numSolutions;
	varStack=csp.varStack;
}


CSProblem& CSProblem::operator=(const CSProblem& csp) {
	// Cancello tutto
	for(ConstraintVector::iterator i=cv->begin(); i!=cv->end(); i++) 
		delete (*i);
	for(VarVector::iterator j=vv->begin(); j!=vv->end(); j++)
		delete (*j);
	delete cv;
	delete vv;
	// Copia dei vincoli
	cv = new ConstraintVector();
	for(i=csp.cv->begin(); i!=csp.cv->end(); i++) {
		Constraint *nc = new Constraint(*(*i));
		cv->push_back(nc);
	}
	// Copia delle variabili
	vv = new VarVector();
	for(j=csp.vv->begin(); j!=csp.vv->end(); j++) {
		Variable *nv = new Variable(*(*j));
		vv->push_back(nv);
	}
	curVar=csp.curVar? getVariable(csp.curVar->getName()) : NULL;
	// Copia delle altre cose
	propAlgorithm=csp.propAlgorithm;
	valHeuristic=csp.valHeuristic;
	varHeuristic=csp.varHeuristic;
	numSolutions=csp.numSolutions;
	varStack=csp.varStack;
	return *this;
}


CSProblem::~CSProblem() {
	for(ConstraintVector::iterator i=cv->begin(); i!=cv->end(); i++) 
		delete (*i);
	for(VarVector::iterator j=vv->begin(); j!=vv->end(); j++)
		delete (*j);
	delete cv;
	delete vv;
}


void CSProblem::readProgram(const string& program) throw (ParserException) {
	Parser par(program);
	par.readProgram(this);
}


string CSProblem::toString() const {
	string prg;
	prg += "Variables:\n";
	for(VarVector::iterator i= vv->begin(); i!=vv->end(); i++) {
		prg += (*i)->toString();
		prg += "\n";
	}
	prg += "Constraints:\n";
	for(ConstraintVector::iterator j= cv->begin(); j!=cv->end(); j++) {
		prg += (*j)->toString();
		prg += "\n";
	}
	prg += "\n";
	return prg;
}


void CSProblem::addVariable(Variable *v) {
	vv->push_back(v);
	if(!curVar)
		curVar=v;
}


void CSProblem::delVariable(Variable *v) {
	// Oltre alla variabile tolgo anche i vincoli in cui e' coinvolta
	ConstraintVector *dc=getConstraints(v);
	for(ConstraintVector::iterator ci=dc->begin(); ci!=dc->end(); ci++)
		delConstraint(*ci);
	delete dc;
	// Tolgo la var dal vettore la variabile
	vv->erase(&v);
	// Se è la variabile corrente si reimposta curVar
	if(curVar==v) {
		curVar= vv->size()? vv->front() : NULL;
	}
	// Cancello fisicamente la variabile
	delete v;
}


void CSProblem::addVariable(const string &v) throw (ParserException) {
	Parser par(v);
	addVariable(par.readVariableWithDomain());
}


void CSProblem::delVariable(const string &v) throw (VarException) {
	delVariable(getVariable(v));
}


bool CSProblem::isDeclared(const string &v) const {
	for(VarVector::iterator i = vv->begin(); i != vv->end(); i++)
		if((*i)->getName()==v)
			return true;
	return false;	
}


Variable *CSProblem::getVariable(const string &v) const throw (VarException) {
	for(VarVector::iterator i = vv->begin(); i != vv->end(); i++)
		if((*i)->getName()==v)
			return (*i);
	throw VarException("Variable " + v + " not declared.");
}


void CSProblem::addConstraint(Constraint *c) throw (VarException) {
	StringSet *ss=c->getVariables();
	// controllo che tutte le variabili siano state dichiarate
	for(StringSet::iterator i=ss->begin(); i!=ss->end(); i++)
		if(!isDeclared(*i))
			throw VarException("Variable " + (*i) + " not declared in constraint " + c->toString() + ".");
	cv->push_back(c);
}


void CSProblem::delConstraint(Constraint *c) {
	cv->erase(&c);
	delete c;
}


void CSProblem::addConstraint(const string &v) throw (VarException, ParserException) {
	Parser par(v);
	addConstraint(par.readConstraint());
}


CSProblem *CSProblem::applyArcConsistency() {
	CSProblem *csp = new CSProblem(*this);
	ArcConsistency ac;
	ac.propagate(csp);
	return csp;
}


SolutionVector *CSProblem::solve() throw (VarException) {
	// Prima di tutto controllo che siano stati specificati algoritmi ed euristiche
	if(varHeuristic==NULL)
		throw VarException("Variable heuristic not specified.");
	if(valHeuristic==NULL)
		throw VarException("Value heuristic not specified.");
	if(propAlgorithm==NULL)
		throw VarException("Propagation algorithm not specified.");
	// Applico la consistenza prima di inziare la risoluzione vera e propria
	if(typeid(*propAlgorithm)==typeid(ArcConsistency)) {
		ArcConsistency ac;
		ac.propagate(this);
	}
	else {
		NodeConsistency nc;
		nc.propagate(this);
	}
	// Risolvo effettivamente il problema
	SolutionVector *sv=new SolutionVector();
	solve1(sv);
	// Ripristino lo stato iniziale delle variabili
	while(!varStack.empty()) 
		restoreVariables();
	return sv;
}


bool CSProblem::solve1(SolutionVector *sv) throw (VarException) {
	// Se è stata raggiunta una soluzione
	if(allIstantiatedVariables()) {
		// Aggiunta della soluzione al vettore
		Environment *env = new Environment();
		for(VarVector::iterator i=vv->begin(); i!=vv->end(); i++)
			env->insert((*i)->getName(),(*i)->getValue());
		Solution *s = new Solution(env);
		sv->push_back(s);
		// Backtracking o terminazione a seconda
		if(numSolutions==sv->size()) 
			return true;
		else
			return false;
	}
	// Scelta della variabile
	curVar = getVariableHeuristic()->selectVariable(this);
	// Se l'euristica per errore ha scelto una variabile gia' istanziata
	// prendo la prima variabile futura che c'è
	if(curVar->isIstantiated()) {
		VarVector *fv=getFutureVariables();
		if(fv->empty())
			throw VarException("No Variables to select from");
		curVar = fv->front();
		delete fv;
	}
	return solve2(sv);
}


bool CSProblem::solve2(SolutionVector *sv) throw (VarException) {
	// Se c'è almeno una variabile con dominio vuoto bisogna fare backtracking
	if(!noEmptyDomains()) 
		return false; 
	// Selezione del valore
	int curVal = getValueHeuristic()->selectValue(getCurrentVariable()->getDomain());
	// Salvataggio dello stato delle variabili
	string oldCurVar = curVar->getName();
	storeVariables();
	curVar = getVariable(oldCurVar);
	curVar->setValue(curVal);
	// Propagazione dei vincoli
	getPropagationAlgorithm()->propagate(this);
	// Chiamata ricorsiva per passare alla variabile sucessiva
	if(solve1(sv))
		return true;
	else {
		// Se c'è stato un fallimento ripristino lo stato precedente delle variabili
		restoreVariables();	
		curVar = getVariable(oldCurVar);
		// e rimuovo il valore corrente
		curVar->getDomain()->removeElement(curVal);
		// quindi chiamata ricorsiva per passare al valore successivo
		return solve2(sv);
	}
}


SolutionVector *CSProblem::solveSB() throw (VarException) {
	if(varHeuristic==NULL)
		throw VarException("Variable heuristic not specified.");
	if(valHeuristic==NULL)
		throw VarException("Value heuristic not specified.");
	SolutionVector *sv=new SolutionVector();
	solveSB1(sv);
	while(!varStack.empty()) 
		restoreVariables();
	return sv;
}


bool CSProblem::solveSB1(SolutionVector *sv) throw (VarException) {
	// Se ci sono vincoli violati faccio backtracking
	if(!checkConstraints())
		return false;
	// Se è stata raggiunta una soluzione
	if(allIstantiatedVariables()) {
		// Aggiunta della soluzione al vettore
		Environment *env = new Environment();
		for(VarVector::iterator i=vv->begin(); i!=vv->end(); i++)
			env->insert((*i)->getName(),(*i)->getValue());
		Solution *s = new Solution(env);
		sv->push_back(s);
		// Backtracking o terminazione a seconda
		if(numSolutions==sv->size()) 
			return true;
		else
			return false;
	}
	// Scelta della variabile
	curVar = getVariableHeuristic()->selectVariable(this);
	// Se l'euristica per errore ha scelto una variabile gia' istanziata
	// prendo la prima variabile futura che c'è
	if(curVar->isIstantiated()) {
		VarVector *fv=getFutureVariables();
		if(fv->empty())
			throw VarException("No Variables to select from");
		curVar = fv->front();
		delete fv;
	}
	return solveSB2(sv);
}


bool CSProblem::solveSB2(SolutionVector *sv) throw (VarException) {
	// Se c'è almeno una variabile con dominio vuoto bisogna fare backtracking
	if(!noEmptyDomains()) 
		return false; 
	// Selezione del valore
	int curVal = getValueHeuristic()->selectValue(getCurrentVariable()->getDomain());
	// Salvataggio dello stato delle variabili
	string oldCurVar = curVar->getName();
	storeVariables();
	curVar = getVariable(oldCurVar);
	curVar->setValue(curVal);
	// Chiamata ricorsiva per passare alla variabile sucessiva
	if(solveSB1(sv))
		return true;
	else {
		// Se c'è stato un fallimento ripristino lo stato precedente delle variabili
		restoreVariables();	
		curVar = getVariable(oldCurVar);
		// e rimuovo il valore corrente
		curVar->getDomain()->removeElement(curVal);
		// quindi chiamata ricorsiva per passare al valore successivo
		return solveSB2(sv);
	}
}


void CSProblem::storeVariables() {
	VarVector *nvv = new VarVector();
	for(VarVector::iterator j=vv->begin(); j!=vv->end(); j++) {
		Variable *nv = new Variable(**j);
		nvv->push_back(nv);
	}
	varStack.push(vv);
	vv=nvv;
}


void CSProblem::restoreVariables() {
	for(VarVector::iterator j=vv->begin(); j!=vv->end(); j++) {
		delete (*j);
	}
	delete vv;
	vv=varStack.top();
	varStack.pop();
}


bool CSProblem::noEmptyDomains() const {
	for(VarVector::iterator i = vv->begin(); i!=vv->end(); i++)
		if((*i)->getDomain()->isEmpty())
			return false;
	return true;
}


bool CSProblem::allIstantiatedVariables() const {
	for(VarVector::iterator i = vv->begin(); i!=vv->end(); i++)
		if(!(*i)->isIstantiated())
			return false;
	return true;
}


bool CSProblem::checkConstraints() const throw (VarException) {
	bool check=true;
	// scorro tutti i vincoli
	for(ConstraintVector::iterator i=cv->begin(); i!=cv->end() && check; i++) {
		StringSet *ss=(*i)->getVariables();
		bool allist=true;
		Environment *env=new Environment();
		// controllo che tutte le variabili siano istanziate
		// e nel frattempo costruisco l'environment per quelle istanziate
		for(StringSet::iterator j=ss->begin(); j!=ss->end(); j++) {
			Variable *tempv=getVariable(*j);
			if(!tempv->isIstantiated()) {
				allist=false;
				break;
			}
			else
				env->insert(tempv->getName(),tempv->getValue());
		}
		// se sono tutte istanziate provo a vedere se il vincolo è soddisfatto
		if(allist)
			if(!(*i)->isSatisfied(env))
				check=false;
		delete env;
	}
	return check;
}


Variable *CSProblem::getCurrentVariable() const {
	return curVar;
}


VarVector *CSProblem::getFutureVariables() const {
	VarVector *fv = new VarVector();
	for(VarVector::iterator i = vv->begin(); i!=vv->end(); i++)
		if(!(*i)->isIstantiated())
			fv->push_back(*i);
	return fv;
}


VarVector *CSProblem::getIstantiatedVariables() const {
	VarVector *fv = new VarVector();
	for(VarVector::iterator i = vv->begin(); i!=vv->end(); i++)
		if((*i)->isIstantiated())
			fv->push_back(*i);
	return fv;
}


VarVector *CSProblem::getInvolvedVariables(Constraint *c) const throw(VarException) {
	VarVector *fv = new VarVector();
	StringSet *ss = c->getVariables();
	for(StringSet::iterator k=ss->begin(); k!=ss->end(); k++) 
		fv->push_back(getVariable(*k));
	//delete ss;
	return fv;
}


VarVector *CSProblem::getInvolvedVariables(ConstraintVector *c) const throw(VarException) {
	VarVector *fv = new VarVector();
	StringSet *ss = new StringSet();
	for(ConstraintVector::iterator i=c->begin(); i!=c->end(); i++) {
		StringSet *sp=(*i)->getVariables();
		for(StringSet::iterator j=sp->begin(); j!=sp->end(); j++)
			ss->insert(*j);
		//delete sp;
	}
	for(StringSet::iterator k=ss->begin(); k!=ss->end(); k++) 
		fv->push_back(getVariable(*k));
	delete ss;
	return fv;
}


ConstraintVector *CSProblem::getConstraints(Variable *v) const {
	ConstraintVector *cc = new ConstraintVector();
	for(ConstraintVector::iterator i=cv->begin(); i!=cv->end(); i++) {
		StringSet *ss=(*i)->getVariables();
		if(ss->find(v->getName()) != ss->end())
			cc->push_back(*i);
		//delete ss;
	}
	return cc;
}


ConstraintVector *CSProblem::getConstraints(VarVector *v) const {
	ConstraintVector *cc = new ConstraintVector();
	for(ConstraintVector::iterator i=cv->begin(); i!=cv->end(); i++) {
		StringSet *ss=(*i)->getVariables();
		bool allFound=true;
		for(VarVector::iterator j=v->begin(); j!=v->end(); j++) {
			if(ss->find((*j)->getName()) == ss->end()) {
				allFound=false;
				break;
			}
		}
		if(allFound)
			cc->push_back(*i);
		//delete ss;
	}
	return cc;
}