#include <iostream>
#include <string>
#include <set>
#include "attributeset.hh"
#include "fd.hh"

AttributeSet attributeCover(const std::set<FunctionalDependency>& F, const AttributeSet& alpha)
{
	AttributeSet result = alpha;
	bool changed;
	do
	{
		changed = false;
		for(std::set<FunctionalDependency>::const_iterator fdit = F.begin(); fdit != F.end(); ++fdit)
		{
			FunctionalDependency currentFD = *fdit;
			if(result.contains(currentFD.getLeftSide()))
			{
				changed = result.add(currentFD.getRightSide());
			}
		}
	}while(changed);
	return result;
}

std::set<FunctionalDependency> linksReduktion(const std::set<FunctionalDependency>& F)
{
	std::set<FunctionalDependency> result = F;
	std::set<FunctionalDependency>::iterator it = result.begin();
	bool changed = false; //indicates whether result FDs have been changed
	while(it != result.end())
	{
		FunctionalDependency currentFD = *it;
		//check for all attributes whether they can be removed without changing the cover
		AttributeSet currentLeftSide = currentFD.getLeftSide();
		AttributeSet currentCover = attributeCover(result, currentLeftSide);
		for(AttributeSet::Iterator ait = currentLeftSide.begin(); ait!=currentLeftSide.end(); ++ait)
		{
			Attribute currentAttr = *ait;
			AttributeSet reducedLeftSide = currentLeftSide;
			reducedLeftSide.substract(currentAttr);
			AttributeSet candidateCover = attributeCover(result, reducedLeftSide);
			if(candidateCover.contains(currentFD.getRightSide()))
			{
				//construct substitute FD
				FunctionalDependency substitute(reducedLeftSide, currentFD.getRightSide());
				result.erase(it); //remove currentFD
				it = result.insert(substitute).first; //insert replacement
				changed = true;
				break;
			}
		}
		if(!changed)
			++it; //no changed, advance
		else
			changed = false; //changed result FDs, reconsider changed element
	}
	return result;
}

std::set<FunctionalDependency> rechtsReduktion(const std::set<FunctionalDependency>& F)
{
	std::set<FunctionalDependency> result = F;
	std::set<FunctionalDependency>::iterator it = result.begin();
	bool changed = false; //indicates whether result FDs have been changed
	while(it != result.end())
	{
		FunctionalDependency currentFD = *it;
		//check for all attributes whether they can be removed without changing the cover
		AttributeSet currentRightSide = currentFD.getRightSide();
		AttributeSet currentCover = attributeCover(result, currentFD.getLeftSide());
		for(AttributeSet::Iterator ait = currentRightSide.begin(); ait!=currentRightSide.end(); ++ait)
		{
			Attribute currentAttr = *ait;
			AttributeSet reducedRightSide = currentRightSide;
			reducedRightSide.substract(currentAttr);
			std::set<FunctionalDependency> candidateSet = result;
			FunctionalDependency reducedFD(currentFD.getLeftSide(), reducedRightSide);
			candidateSet.erase(currentFD);
			candidateSet.insert(reducedFD);
			AttributeSet candidateCover = attributeCover(candidateSet, currentFD.getLeftSide());
			if(candidateCover.contains(currentAttr))
			{
				//construct substitute FD
				FunctionalDependency substitute(currentFD.getLeftSide(), reducedRightSide);
				result.erase(it); //remove currentFD
				it = result.insert(substitute).first; //insert replacement
				changed = true;
				break;
			}
		}
		if(!changed)
			++it; //no changed, advance
		else
			changed = false; //changed result FDs, reconsider changed element
	}
	return result;
}

std::set<FunctionalDependency> entferneLeereFDs(const std::set<FunctionalDependency>& F)
{
	std::set<FunctionalDependency> result = F;
	std::set<FunctionalDependency>::iterator it = result.begin(); 
	while(it != result.end())
	{
		FunctionalDependency currentFD = *it;
		if(currentFD.getRightSide().empty())
		{
			result.erase(it);
			it = result.begin(); //restart
		}
		else
			++it;
	}
	return result;
}

std::set<FunctionalDependency> vereinige(const std::set<FunctionalDependency>& F)
{
	std::set<FunctionalDependency> result = F;
	std::set<FunctionalDependency>::iterator outerIT = result.begin();
	bool changed = false;
	while(outerIT != result.end())
	{
		FunctionalDependency outerFD = *outerIT;
		for(std::set<FunctionalDependency>::iterator innerIT = outerIT;
				innerIT!=result.end(); ++innerIT)
		{
			if(innerIT==outerIT)
				continue; //comparing to self does not make sense
			FunctionalDependency innerFD = *innerIT;
			if(outerFD.getLeftSide()==innerFD.getLeftSide())
			{
				//merge right sides
				AttributeSet newRightSide = outerFD.getRightSide();
				newRightSide.add(innerFD.getRightSide());
				FunctionalDependency substituteFD(outerFD.getLeftSide(), newRightSide);
				result.erase(outerFD);
				result.erase(innerFD);
				result.insert(substituteFD);
				outerIT = result.begin();
				changed = true;
				break; //restart from beginning
			}
		}
		if(!changed)
			++outerIT;
		else
			changed = false;
	}
	return result;
}


//print function for convenience
std::ostream& operator<<(std::ostream& ostream, const std::set<FunctionalDependency>& F)
{
	for(std::set<FunctionalDependency>::const_iterator cit = F.begin(); cit!= F.end(); ++cit)
	{
		ostream<<cit->getText()<<std::endl;
	}
	return ostream;
}

std::set<FunctionalDependency> kanonischeUeberdeckung(const std::set<FunctionalDependency>& F)
{
	std::set<FunctionalDependency> result = F;
	std::cout<<"Eingabe: "<<F<<std::endl;
	result = linksReduktion(result);
	std::cout<<"Nach Linksreduktion: "<<std::endl<<result<<std::endl;
	result = rechtsReduktion(result);
	std::cout<<"Nach Rechtsreduktion: "<<std::endl<<result<<std::endl;
	result = entferneLeereFDs(result);
	std::cout<<"Nach Entfernen leerer FDs: "<<std::endl<<result<<std::endl;
	result = vereinige(result);
	std::cout<<"Nach Vereinigungsregel: "<<std::endl<<result<<std::endl;
	return result;
}

int main()
{
	std::cout<<"Funktionale Abhaengigkeiten (in der Form A->BC, leere Zeile beendet):"<<std::endl;
	std::string textInput;
	std::set<FunctionalDependency> fds;
	while(true)
	{
		getline(std::cin, textInput);
		if(textInput.empty())
			break;
		FunctionalDependency fd(textInput);
		fds.insert(fd);
	}

	std::cout<<"Attribute (in der Form AB):"<<std::endl;
	std::string attributeText;
	getline(std::cin, attributeText);
	AttributeSet attributes(attributeText);
	AttributeSet result = attributeCover(fds, attributes);
	std::cout<<"Attributhuelle fuer Attribute "<<attributes.getText()<<" ist "
		<<result.getText()<<std::endl;

	std::cout<<"Starte Berechnung der Kanonischen Ueberdeckung:"<<std::endl;
	std::set<FunctionalDependency> kanonisch = kanonischeUeberdeckung(fds);
	std::cout<<"Kanonische Ueberdeckung:"<<std::endl<<kanonisch<<std::endl;

	return 0;
}