#include "stdafx.h"

using namespace std;

#include "Complement.h"

// constructor
Complement::Complement()
{
	containment = 0;
	merge_shared = true;
	time_limit = 0;
	time_limit_exceeded = false;
}


// destructor
Complement::~Complement()
{
	
}

// setter for containment
void Complement::SetContainment(bool c)
{
	containment = c;
}

// getter for containment
bool Complement::GetContainment() const
{
	return containment;
}

// setter for merge_shared
void Complement::SetMergeShared(bool ms)
{
	merge_shared = ms;
}

// getter for merge_shared
bool Complement::GetMergeShared() const
{
	return merge_shared;
}

// setter for verbose mode
void Complement::SetVerbose(bool v)
{
	verbose = v;
}

// getter for verbode mode
bool Complement::GetVerbose() const
{
	return verbose;
}

// setter for time limit
void Complement::SetTimeLimit(int l)
{
	time_limit = l;
}

// getter for time limit
int Complement::GetTimeLimit() const
{
	return time_limit;
}

// getter for time_limit_exceeded
bool Complement::IsLimitExceeded() const
{
	return time_limit_exceeded;
}



// Returns the index of input variable
// which is the best for splitting variable.
// If the given cover if unate, no index is
// chosen and (-1) is returned. 
int Complement::BinateSelect(SoPLA * pla)
{
	int res = 0;
	int n = pla->GetInputs();
    int * p0 = new int[n];
    int * p1 = new int[n];
    int * min01 = new int[n];
    int max;

    for (int i=0; i<n; i++)
		p0[i] = p1[i] = min01[i] = 0;
    
	CubeList::const_iterator ti = pla->GetData()->begin();
	for (; ti!=pla->GetData()->end(); ti++)
	{
		for (int j=0; j<n; j++)
		{
			if (ti->GetIM(j) == '0') p0[j]++;
			if (ti->GetIM(j) == '1') p1[j]++;
		}
	}
	for (int j=0; j<n; j++)
	{
		min01[j] = min(p0[j], p1[j]);
		if ((j == 0)||(max < min01[j]))
		   max = min01[j];
	}

	if (max == 0)	// is is a unate function and no splitting variable is chosen
	{
		res = (-1);
	} else {		// looking for splitting variable
		res = 0;
		max = p0[res]+p1[res];
		for (int j=1; j<n; j++)
			if ((min01[j] > 0)&&((p0[j]+p1[j]) > max))
			{
				res = j;
				max = p0[j]+p1[j];
			}
	}

	delete p0;
	delete p1;
	delete min01;
	return res;	
}



// returns a SoPLA as a result of merging ginve SoPLAs
// ind is index of splitting variable
// uses macro CONTAINMENT which decides the behavior of
// this function: 
//	     CONTAINMENT=0   ...  MergeWithIdentity
//		 CONTAINMENT=1   ...  MergeWithContainment
SoPLA * Complement::MergeWithContainment(SoPLA* pla0, SoPLA* pla1, int ind)
{
	if ((pla0 == NULL)||(pla1 == NULL))
		throw RuntimeException("MergeWithContainment: Arguments cannot be NULL.");
	if (pla0->GetInputs() != pla1->GetInputs())
		throw RuntimeException("MergeWithContainment: Incompatible PLAs.");
	SoPLA * res;
	SoPLA * pla2 = new SoPLA(pla0->GetInputs());
	if (pla2 == NULL)
		throw RuntimeException("MergeWithContainment: Not enough memory.");
	
	unsigned int i = 0;
	unsigned int l = 0;
	while (i<pla0->GetTerms())
	{
		while (l<pla1->GetTerms())
		{
			if ((i < pla0->GetTerms())&&(l < pla1->GetTerms())&&(pla0->GetTerm(i)->EqualIM(pla1->GetTerm(l)->GetIM())))
			{
				pla2->AppendTerm(pla0->GetTerm(i)->GetIM());
				pla0->DeleteTerm(pla0->GetTerm(i));
				pla1->DeleteTerm(pla1->GetTerm(l));
			} else {
				if ((i >= pla0->GetTerms())||(l >= pla1->GetTerms()))
					break;
				else l++;
			}
		}
		i++;
	}

	if (containment)
	{
		i = 0;
		while (i<pla0->GetTerms())
		{
			l = 0;
			while (l<pla1->GetTerms())
			{
				if (pla0->GetTerm(i)->Contains(  pla1->GetTerm(l)->GetIM()   ))
				{
					pla2->AppendTerm(pla1->GetTerm(l)->GetIM());
					pla1->DeleteTerm(pla1->GetTerm(l));		
				} else l++;
			}
			i++;			
		}
		
		l = 0;
		while (l<pla1->GetTerms())
		{
			i = 0;
			while (i<pla0->GetTerms())
			{
				if (pla1->GetTerm(l)->Contains(  pla0->GetTerm(i)->GetIM()  ))
				{
					pla2->AppendTerm(pla0->GetTerm(i)->GetIM());
					pla0->DeleteTerm(pla0->GetTerm(i));	
				} else i++;
			}
			l++;
		}
	}
	
	res = pla2;
	CubeList::iterator ti;
	for(ti=pla0->GetData()->begin(); ti!=pla0->GetData()->end(); ti++)
		ti->SetIM(ind, '0');
	res->Splice(*pla0);

	for(ti=pla1->GetData()->begin(); ti!=pla1->GetData()->end(); ti++)
		ti->SetIM(ind, '1');
	res->Splice(*pla1);

	return res;
}

// prints the personality 
// matrix to the output
// (only for testing)
void Complement::PrintPersonalityMatrix(SoPLA * pers_m)
{
	if (pers_m == NULL)
		throw RuntimeException("PrintPersonalityMatrix: Argument cannot be NULL.");
	for (CubeList::const_iterator ti=pers_m->GetData()->begin(); ti!=pers_m->GetData()->end(); ti++)
		for (unsigned int i=0; i<ti->GetInputs(); i++)
			if ((ti->GetIM(i) != '0')&&(ti->GetIM(i) != '1'))
				throw RuntimeException("PrintPersonalityMatrix: Not valid personal matrix."); 
	cout << "Personality Matrix: " << endl;
	for (CubeList::const_iterator ti=pers_m->GetData()->begin(); ti!=pers_m->GetData()->end(); ti++)
		cout << ti->GetIM() << endl;
	cout << endl;
}


// prints given v-matrix to the output
// (only for testing)
void Complement::PrintTranslationMatrix(const Cube * V)
{
	if (V == NULL)
		throw RuntimeException("PrintTranslationMatrix: Argument cannot be NULL.");
	cout << "V-Matrix: " << endl;
	cout << V->GetIM() << endl;
}


// returns the spliting variable for 
// pers_unate_complement function
int Complement::UnateComplement_SplitSelect(SoPLA * pers_mat)
{
	if (pers_mat == NULL)
		throw RuntimeException("UnateComplement_SplitSelect: Argument cannot be NULL.");

	int res = 0;
   	int n = pers_mat->GetTerms();
	int * zero_cnt = new int[n];
	if (zero_cnt == NULL) throw RuntimeException("UnateComplement_SplitSelect: Not enough memory.");
	for (int i=0; i<n; i++)
		zero_cnt[i] = 0;
		
	// search the largest cube
	int largest = 0;
	for (unsigned int i=0; i<pers_mat->GetTerms(); i++)
	{
		for (unsigned int k=0; k<pers_mat->GetInputs(); k++)
			if (pers_mat->GetTerm(i)->GetIM(k) == '0') 
				zero_cnt[i]++;
		if (zero_cnt[largest] < zero_cnt[i])
			largest = i;
	} 
	
	// select set of variables that are used in
	// the largest cube (found above)
	int * used_vars = new int[pers_mat->GetInputs()];
	if (used_vars == NULL) throw RuntimeException("UnateComplement_SplitSelect: Not enough memory.");
	CubeList::const_iterator lar_it = pers_mat->GetTerm(largest);
	for (unsigned int i=0; i<pers_mat->GetInputs(); i++)
	{
		if (lar_it->GetIM(i) == '1')
			used_vars[i] = 0;
		else used_vars[i] = (-1);
	}
	
	// count how much are these 
	// variables (selected right above) used
	// and select the varible, which
	// apears most frequently in other terms
	for (unsigned int i=0; i<pers_mat->GetInputs(); i++)
	{
		for (CubeList::const_iterator ti=pers_mat->GetData()->begin(); ti!=pers_mat->GetData()->end(); ti++)
		{
			if ((ti->GetIM(i) == '1')&&(used_vars[i] >= 0))
				used_vars[i]++;
		}
		if (used_vars[res] < used_vars[i])
			res = i;
	}

	delete zero_cnt;
	delete used_vars;
	return res;
}


// returns personal matrix cofactors
// if sign==0	M0 is returned
// if sign==1	M1 is returned
SoPLA * Complement::PersCofactors(SoPLA * pers_mat, int j, int sign)
{
	if (pers_mat == NULL)
		throw RuntimeException("PersCofactiors: Argument cannot be NULL.");
	if ((unsigned int)j >= pers_mat->GetInputs())
		throw RuntimeException("PersCofactiors: Invalid argument.");
	if ((sign != '0')&&(sign != '1'))
		throw RuntimeException("PersCofactiors: Invalid argument.");

	SoPLA * res = new SoPLA(pers_mat->GetInputs());
	if (res == NULL)
		throw RuntimeException("PersCofactiors: Not enough memory.");

	for (CubeList::const_iterator ti=pers_mat->GetData()->begin(); ti!=pers_mat->GetData()->end(); ti++)
	{
		if (sign == '0')
		{
			if (ti->GetIM(j) == '0')
				res->AppendTerm(ti->GetIM());
		} else {
			Cube x(pers_mat->GetInputs());
			x.SetIM(ti->GetIM());
			if (x.GetIM(j) != '0')
			{
				x.SetIM(j, '0');
			}	
			res->AppendTerm(x);
		}
	}
	
	return res;	
}


// Demorgan's Law - only for use in UnateComplemtation 
// !!! the input is an iterator to PersonalityMatrix term !!!
// !!! never pass a standart SoPLA term to this function !!!
SoPLA * Complement::DemorganForUC(CubeList::const_iterator term_ti)
{
	SoPLA * res = new SoPLA(term_ti->GetInputs());
	if (res == NULL)
		throw RuntimeException("Demorgan: Not enough memory.");

	for (unsigned int i=0; i<term_ti->GetInputs(); i++)
	{
		if (term_ti->GetIM(i) == '1')
		{
			Cube c(term_ti->GetInputs());
			string s;
			s.assign(term_ti->GetInputs(), '0');
			c.SetIM(s);
			c.SetIM(i, '1');
			res->AppendTerm(c);
		}
	}

	return res;
}


// computes Complement of Personal Unate Matrix
// parametry k,n sou vstupni/vystupni
SoPLA * Complement::Pers_Unate_Complement(SoPLA * pers_mat)
{
	if (pers_mat == NULL)
		throw RuntimeException("Pers_Unate_Complement: Argument cannot be NULL.");
	SoPLA * res = new SoPLA(pers_mat->GetInputs());
	if (res == NULL) throw RuntimeException("Pers_Unate_Complement: Not enough memory.");

	string all0s;
	all0s.assign(pers_mat->GetInputs(), '0');

	// 1. special case - given M is empty
	// the complement is tautology
	if (pers_mat->empty())
	{
		Cube c(pers_mat->GetInputs());
		c.SetIM(all0s);
		res->AppendTerm(c);
		return res;
	}

	// 2. secial case - there is a row of all0s
	// the complement is empty
	for (CubeList::const_iterator ti=pers_mat->GetData()->begin(); ti!=pers_mat->GetData()->end(); ti++)
	{
		if (ti->GetIM() == all0s)
			return res;
	}

	// 3. special case - M has only one term
	// we use Demorgan's law to compute the complement
	if (pers_mat->GetTerms() == 1)
	{
		SoPLA * dem = DemorganForUC(pers_mat->GetTerm(0));
		res->Splice(*dem);
		delete dem;
		return res;
	}

	// if no special case ocured, choose 
	// the plitting variable and use
	// recursive Pers_Unate_Complement
	int j = UnateComplement_SplitSelect(pers_mat);
	SoPLA * M0 = PersCofactors(pers_mat, j, '0');
	SoPLA * M1 = PersCofactors(pers_mat, j, '1');

	SoPLA * M0_non = Pers_Unate_Complement(M0);
	SoPLA * M1_non = Pers_Unate_Complement(M1);
	

	/************************************************************/
	CubeList::iterator ti0=M0_non->GetData()->begin();
	while (ti0!=M0_non->GetData()->end())
	{
		CubeList::iterator ti1=M1_non->GetData()->begin();
		bool pom = false;
		while (ti1!=M1_non->GetData()->end())
		{
			if (ti0->EqualIM(ti1->GetIM()))
			{
				res->AppendTerm(ti1->GetIM());
				ti1 = M1_non->DeleteTerm(ti1);
				ti0 = M0_non->DeleteTerm(ti0);
				//cout << "DUPLICITA !!!" << endl;
				pom = true;
				break;
			} else ti1++;
		}
		if (!pom) ti0++;
	}
	/************************************************************/


	// merging process
	for (CubeList::iterator ti=M0_non->GetData()->begin(); ti!=M0_non->GetData()->end(); ti++)
		ti->SetIM(j, '1');
	res->Splice(*M0_non);
	res->Splice(*M1_non);
	
	delete M0;
	delete M1;
	delete M0_non;
	delete M1_non;

	return res;
}

// computes the peronality matrix
// of given unate function
SoPLA * Complement::GeneratePersonalMatrix(SoPLA * pla)
{
	if (pla == NULL)
		throw RuntimeException("GeneratePersonalMatrix: Argument cannot be NULL.");
	SoPLA * pers_m = new SoPLA(pla->GetInputs());
    if (pers_m == NULL) throw RuntimeException("GeneratePersonalMatrix: Not enough memory.");
	for (CubeList::const_iterator ti=pla->GetData()->begin(); ti!=pla->GetData()->end(); ti++)
	{
		Cube c(pla->GetInputs());
		for (unsigned int i=0; i<ti->GetInputs(); i++)
		{
			if ((ti->GetIM(i) == '0')||(ti->GetIM(i) == '1'))
				c.SetIM(i, '1');
			else c.SetIM(i, '0');
		}
		pers_m->AppendTerm(c);
	}
	return pers_m;
}


// computes the translation matrix, which
// says whether the given function is monotone
// increasing or decreasing in each variable
Cube * Complement::Monotone(SoPLA * pla)
{
	if (pla == NULL)
		throw RuntimeException("Monotone: Argument cannot be NULL.");
	Cube * V = new Cube(pla->GetInputs());
	if (V == NULL) throw RuntimeException("Monotone: Not enough memory.");
	for (unsigned int i=0; i<pla->GetInputs(); i++)
		V->SetIM(i, '-');

	for (CubeList::const_iterator ti=pla->GetData()->begin(); ti!=pla->GetData()->end(); ti++)
	{
		for (unsigned int i=0; i<pla->GetInputs(); i++)
		{
			if (ti->GetIM(i) == '1')
				V->SetIM(i, '1');
			if (ti->GetIM(i) == '0')
				V->SetIM(i, '0');
		}
	}

	return V;
}

// translates given personality matrix
// back to function cover
SoPLA* Complement::Translate(SoPLA * pers_mat, Cube * V)
{
	if ((pers_mat == NULL)||(V == NULL))
		throw RuntimeException("Translate: Arguments cannot be NULL.");
	SoPLA * res = new SoPLA(pers_mat->GetInputs());
	if (res == NULL) throw RuntimeException("Translate: Not enough memory.");

	for (CubeList::const_iterator ti=pers_mat->GetData()->begin(); ti!=pers_mat->GetData()->end(); ti++)
	{
		Cube c(pers_mat->GetInputs());
		for (unsigned int i=0; i<ti->GetInputs(); i++)
		{
			if (ti->GetIM(i) == '0')
				c.SetIM(i, '-');
			else {
			   if (V->GetIM(i) == '0')
				   c.SetIM(i, '1');
			   if (V->GetIM(i) == '1')
				   c.SetIM(i, '0');
			} 
		}
		res->AppendTerm(c);
	}

	return res;
}


// computes complement of a unate function
SoPLA * Complement::UnateComplement(SoPLA * pla)
{
	if (pla == NULL)
		throw RuntimeException("UnateComplement: Argument cannot be NULL.");

	SoPLA * res = NULL;

	// compute personality matrix
	SoPLA * pers_m = GeneratePersonalMatrix(pla);

	// compute translation matrix V
	Cube * V = Monotone(pla);

	SoPLA * M_non = Pers_Unate_Complement(pers_m);
	res = Translate(M_non, V);

	delete V;
	delete pers_m;
	delete M_non;

	return res;
}


// This function says, whether given
// SoPLA is unate or not.
// This funcion is not used in the
// complement-algorithm. CheckSpecialCases
// is used instead.
bool Complement::IsUnate(SoPLA * pla)
{
	if (pla == NULL)
		throw RuntimeException("IsUnate: Argument cannot be NULL.");
	if (pla->GetTerms() == 0) 
		return NULL;					//throw RuntimeException("IsUnate: Zero terms in pla.");
	if (pla->GetTerms() == 1)			// je li tam jen jedna krychle tak to je UNATE FUNCTION
		return NULL;
	bool res = true;

	int n = pla->GetInputs();
	Cube c(n);
	std::string s;
	s.assign(n, '-');
	c.SetIM(s);
	CubeList::const_iterator ti = pla->GetData()->begin();
	for (; ti!=pla->GetData()->end(); ti++)
	{
		for (int i=0; i<n; i++)
		{
			char z = ti->GetIM(i);
			if (z == '1')
			{
				if (c.GetIM(i) == '-') c.SetIM(i, '1');
				if (c.GetIM(i) == '0') res = false;	
			}
			if (z == '0')
			{
				if (c.GetIM(i) == '-') c.SetIM(i, '0');
				if (c.GetIM(i) == '1') res = false;
			}
		}
	} 
	return res;
}


// This function is used to check 
// all the three special cases that
// can ocure at the beginning of
// SingleOutputComplement function.
// If the given SoPLA is unate, the return value is NULL
// If the given SoPLA contains a row of all 2s ('-') -> the
//		retuen value is an instance of MultiResult Class 
//		containin variable 'all2s' set to TRUE
// If the given function contains at least one column of 
//      all 0s or all 1s -> the instance of MultiResult Class
//		indicates which columns these are.
// The instance of MultiResult Class also says, which variable
// should be chosen as SPLITTING VARIABLE
// (more about MultiResult Class can be found in Complement.h)
Complement::MultiResult* Complement::CheckSpecialCases(SoPLA * pla)
{
	if (pla == NULL)
		throw RuntimeException("IsUnate: Argument cannot be NULL.");
	if (pla->GetTerms() == 0) 
		return NULL;					//throw RuntimeException("IsUnate: Zero terms in pla.");
	if (pla->GetTerms() == 1)			// je li tam jen jedna krychle tak to je UNATE FUNCTION
		return NULL;
	
	
	int res = 0;
	int n = pla->GetInputs();
    int * p0 = new int[n];
    int * p1 = new int[n];
    int * min01 = new int[n];
	int max;
	bool all2s;

	Cube * mapa = new Cube(n);
	string s;
	s.assign(n, '-');
	mapa->SetIM(s);

    for (int i=0; i<n; i++)
		p0[i] = p1[i] = min01[i] = 0;
  
	CubeList::const_iterator ti = pla->GetData()->begin();
	for (; ti!=pla->GetData()->end(); ti++)
	{
		all2s = true;
		for (int j=0; j<n; j++)
		{
			if (ti->GetIM(j) == '0')
			{
				p0[j]++;
				all2s = false;
			}
			if (ti->GetIM(j) == '1')
			{
				p1[j]++;
				all2s = false;
			}
		}
		if (all2s)
		{
			delete p0;
			delete p1;
			delete min01;
			return new MultiResult(mapa, 0, true);
		}
	}
	for (int j=0; j<n; j++)
	{
		min01[j] = min(p0[j], p1[j]);
		if ((j == 0)||(max < min01[j]))
		   max = min01[j];
		if (max(p0[j], p1[j]) == pla->GetTerms())
		{
			if (p0[j] == pla->GetTerms()) mapa->SetIM(j, '0');
			if (p1[j] == pla->GetTerms()) mapa->SetIM(j, '1');
		}
	}

	if (max == 0)	// it is a unate function and no splitting variable is chosen
	{
		res = (-1);
	} else {		// looking for splitting variable
		
		// heuristika H3: kombinovana heuristika (scitaci + nasobici)
		/*
		res = 0;
		while ((p0[res] == 0) && (p1[res] == 0)) res++;
		max = p0[res] + p1[res];
		for (int j=res+1; j<n; j++)
		  if (min01[j] > 0)
		  {
			if ( p0[j] + p1[j]  >  max)
			{
				res = j;
				max = p0[j] + p1[j];
			} else {
				if ( p0[j] + p1[j]  ==  max)
					if (p0[j] * p1[j] > p0[res] * p1[res])
						res = j;
			}
		  }	
		*/

		// to je mereni2 - heuristika scitaci
		res = 0;
		while ((p0[res] == 0) || (p1[res] == 0)) res++;
		max = p0[res] + p1[res];
		for (int j=res+1; j<n; j++)
		  if (min01[j] > 0)
		  {
			if ( p0[j] + p1[j]  >  max)
			{
				res = j;
				max = p0[j] + p1[j];
			} 
		  }	


		// Heuristika H1 - nasobici
		/*
		res = 0;
		while (p0[res] * p1[res] == 0) res++;
		max = p0[res] * p1[res];
		for (int j=res+1; j<n; j++)
			if (p0[j] * p1[j] > max)
			{
				res = j;
				max = p0[j] * p1[j];
			}
		*/

	}

	delete p0;
	delete p1;
	delete min01;

	if (res == -1)
	{
		delete mapa;
		return NULL;
	} else {
		MultiResult * mr = new MultiResult(mapa, res, false);
		return mr;
	}
}



// this function computes the complement of given
// single output function (OnSet-DcSet)
SoPLA * Complement::SingleOutputComplement(SoPLA * fd)
{
	if (fd == NULL)
		throw RuntimeException("SingleOutputComplement: Argument cannot be NULL.");
	
	SoPLA * result = new SoPLA(fd->GetInputs());
	if (result == NULL) 
		throw RuntimeException("SingleOutputComplement: Not enough memory.");
	
	// check th time limit
	if (time_limit > 0)
	{
		int c = (int)GetMyCPUTime();
		if (c > time_limit)
		{
			time_limit_exceeded = true;
			return result;
		}
	}

	MultiResult * u = CheckSpecialCases(fd);

	// First Special Case
	// If this function contains a cube of all 2s,
	// the complement is empty
	if ((u != NULL)&&(u->all2s))		
	{
		return result;
	}

	// Second Special Case
	// given function is unate
	if (u == NULL)
	{
		result = UnateComplement(fd);
		return result;
	}

	// Third Special Case
	// The function contains a comlumn of either all 0s or all 1s
	// we use Demorgan's Law
	Cube c(fd->GetInputs());
	c.SetIM(u->mapa->GetIM());
	string myEmptyCube;
	myEmptyCube.assign(fd->GetInputs(), '-');
	if (c.GetIM() != myEmptyCube)
	{
		SoPLA * pom = new SoPLA(fd->GetInputs());
		if (pom == NULL) throw RuntimeException("SingleOutputComplement: Not enough memory.");
		pom->AppendTerm(c);
		
		SoPLA * pom_res = UnateComplement(pom);
		result->Splice(*pom_res);

		delete pom_res;
		pom_res = NULL;
		delete pom;
		pom = NULL;
		
		pom = PLA_op().Cofactor(*fd, c);
		fd->clear();
		fd->Splice(*pom);
		delete pom;
	}

	// other posibilities
	// first choosing the splitting variable,
	// then using recursive calling SingleOutputComplement
	// finally calling MergeWithContainment	
	int j = u->split_var;

	Cube xj(fd->GetInputs());
	Cube xj_non(fd->GetInputs());
	string s;
	s.assign(fd->GetInputs(), '-');
	xj.SetIM(s);
	xj.SetIM(j, '1');
	xj_non.SetIM(s);
	xj_non.SetIM(j, '0');
	
	SoPLA* cc1 = PLA_op().Cofactor(*fd, xj);
	SoPLA* cc2 = PLA_op().Cofactor(*fd, xj_non);
	
	SoPLA * cc1_non = SingleOutputComplement(cc1);
	SoPLA * cc2_non = SingleOutputComplement(cc2);

	SoPLA * x = MergeWithContainment(cc2_non, cc1_non, j);  	
	x->Splice(*result);

	delete u;

	delete result;

	delete cc1_non;
	delete cc2_non;

	delete cc1;
	delete cc2;

	return x;
}



// this function returns the SoPLA containing
// the OnSet+DcSet of the i-th output function
SoPLA * Complement::ExtractOnsetAndDcSet(PLA * pla, int i, int dc_man)
{
	if (pla == NULL)
		throw RuntimeException("ExtractOnsetAndDcSet: Argument cannot be NULL.");

	SoPLA * result = new SoPLA(pla->GetInputs());
	if (result == NULL) throw RuntimeException("ExtractOnsetAndDcSet: Not enough memory.");
	
	if ((unsigned int)i>=pla->GetOutputs()) throw RuntimeException("ExtractOnsetAndDcSet: Invalid index.");
	if (pla->GetType().f)		// solves f, fd, fdr types 
	{
		result->AppendPLA(  *(pla->GetOnSet(i))  );			// getting OnSet 
		if ((pla->GetType().d)&&(dc_man == 0))
			result->AppendPLA(  *(pla->GetDCSet(i))  );		// if FD-type, getting DcSet
	} else {
		if (pla->GetType().r && !pla->GetType().d)			// R-type
		{
			// this should never be called
			throw "Neco se pokazilo";
		}
		if (pla->GetType().r && pla->GetType().d)			// RD-type
		{
			// this should never be called
			throw "Neco se pokazilo";
		}
	}

	return result;
}


int Complement::JoinInd(string a, string b)
{
	if (a.length() != b.length())
		throw RuntimeException("JoinInd: Incompatible arguments.");
	int res = -1;
	int diff = 0;
	for (unsigned int i = 0; i<a.length(); i++)
	{
		if (a.at(i) != b.at(i))
		{
			diff++;
			res = i;
		}
	}
	return ((diff == 1)? res : (-1));
}

// computes PLA complement as an iteration 
// over all single aoutput funcions
PLA * Complement::PLAComplement(PLA * pla, int dc_man)
{
	if (pla == NULL)
		throw RuntimeException("PLAComplement: Argument cannot be NULL.");

	PLA * result;					// the result;
	SoPLA * fd;						// ONset + DCset of a single output function
	int m;							// the number of output functions
	SoPLA * hlp;					// the result of SingleOutputComplement function
	CubeList::const_iterator ti;

	result = new PLA(pla->GetInputs(), pla->GetOutputs());
	if (result == NULL) throw RuntimeException("Complement: Not enough memory.");
	m = pla->GetOutputs();			
	for (int i=0; i<m; i++)		    // complementation of each single output function
	{
		// check the time limit
		if (time_limit > 0)
		{
			if (time_limit_exceeded)
				break;
			if(GetMyCPUTime() > time_limit)
			{
				time_limit_exceeded = true;
				break;
			}
		}
		if (pla->GetType().r)
		{
			string my_output;
			my_output.assign(pla->GetOutputs(), '~');
			Cube pom(pla->GetOutputs());
			pom.SetIM(my_output);
			pom.SetIM(i, '1');
			SoPLA * ofs = pla->GetOffSet(i);
			for (CubeList::iterator ci = ofs->GetData()->begin(); ci!=ofs->GetData()->end(); ci++)
				result->AppendTerm(ci->GetIM(), pom.GetIM());
			if ((pla->GetType().d)&&(dc_man == 1))
			{
				SoPLA * dcs = pla->GetDCSet(i);
				for (CubeList::iterator ci = dcs->GetData()->begin(); ci!=dcs->GetData()->end(); ci++)
					result->AppendTerm(ci->GetIM(), pom.GetIM());
			}
			if (verbose) cout << i+1 << ". output done" << endl;
			continue;
		}
		if (pla->GetType().f && !pla->GetType().r)
		{
		   fd = ExtractOnsetAndDcSet(pla, i, dc_man);  	
		   hlp = SingleOutputComplement(fd);
			
		   string my_output;
		   my_output.assign(pla->GetOutputs(), '~');
		   Cube pom(pla->GetOutputs());
		   pom.SetIM(my_output);
		   pom.SetIM(i, '1');

		   // add the single-output complement to the result
		   for (ti=hlp->GetData()->begin(); ti!=hlp->GetData()->end(); ti++)
		   	   result->AppendTerm(ti->GetIM(), pom.GetIM()); 

		   delete fd;
		   delete hlp;
		   hlp = fd = NULL;
		   if (verbose) cout << i+1 << ". output done" << endl;
		}	
	}

	// search for shared terms and merge them
	if (merge_shared)
	{
		if (verbose)
			cout << "Merging shared terms, please wait..." << endl;
		result->MergeTerms();
	}

	PLA_type t;
	t.f = true;
	t.d = false;
	t.r = false;
	result->SetType(t);

	return result;
}

void Complement::printHelp() const
{
	cout << endl;
	cout << "*******************************************************************************" << endl;
	cout << "********************** Help for Complement ************************************" << endl;
	cout << endl << "Complement is an application for computing " << endl; 
    cout << "complement of multiple-output logic functions (PLA)." << endl;
	cout << "Jan Kucera (2010)" << endl << endl;
	
	cout << endl << "Syntax: \nComplement -n file [-d dc_man] [-o file] [-m on|off] [-p on|off] [-t time] [-v]" << endl;
	cout << endl << "Options: " << endl;
	cout << "\t -n \t ..... \t name of the input PLA file." << endl;
	cout << "\t\t\t This argument is mandatory." << endl;
	cout << endl;
	cout << "\t -d \t ..... \t DontCare manipulation for FD and RD types." << endl; 
	cout << "\t\t\t This argument is voluntary." << endl;
	cout << "\t\t\t\t so \t stick to onset" << endl;
	cout << "\t\t\t\t sc \t stick to complement (default)" << endl;
	cout << endl;	
	cout << "\t -o \t ..... \t name of the output PLA file." << endl;
	cout << "\t\t\t This argument is voluntary." << endl;
	cout << endl;
	cout << "\t -m \t ..... \t merging shared terms." << endl;
	cout << "\t\t\t This argument is voluntary." << endl;
	cout << "\t\t\t\t on \t merging is switched on" << endl;
	cout << "\t\t\t\t off\t merging is switched off (default)" << endl;
	cout << "\t\t\t (merging needs more time !!!)" << endl;
	cout << endl;
	cout << "\t -p \t ..... \t print the result to the screen." << endl;
	cout << "\t\t\t This argument is voluntary." << endl;
	cout << "\t\t\t\t on \t the result is printed (default)" << endl;
	cout << "\t\t\t\t off\t the result isn't printed" << endl;
	cout << endl;
	cout << "\t -c \t ..... \t check containment while inner-merging." << endl;
	cout << "\t\t\t This argument is voluntary." << endl;
	cout << "\t\t\t This argument has nothing to do with -m merging opt." << endl;
	cout << "\t\t\t\t on \t switch the containment on (default)" << endl;
	cout << "\t\t\t\t off\t switch the containment off" << endl;
	cout << "\t\t\t (containment needs more time !!!)" << endl;
	cout << endl;
	cout << "\t -t \t ..... \t sets the time limit (in seconds)" << endl;
	cout << "\t\t\t This argument is voluntary." << endl;
	cout << "\t\t\t This argument must be integer value." << endl;
	cout << "\t\t\t The limit doesn't take care of the final merge (-m)!" << endl;
	cout << "\t\t\t 0 means no limit (default)." << endl;
	cout << endl;
	cout << "\t -v \t ..... \t verbose mode." << endl;
	cout << "\t\t\t This argument is voluntary." << endl;
	cout << endl;
	cout << endl;

	cout << "*******************************************************************************" << endl;
	cout << "*******************************************************************************" << endl;
	cout << endl;
}





/* implementation of nested classes *************************************************************************/
/************************************************************************************************************/

Complement::MultiResult::MultiResult(Cube * c, int s, bool all2s)
{
	mapa = c;
	split_var = s;
	this->all2s = all2s;
}

Complement::MultiResult::~MultiResult()
{
	delete mapa;
} 

/************************************************************************************************************/
/************************************************************************************************************/











int main(int argc, char* argv[])
{
	// name of input file
	char * ifile_name = NULL;

	// name of output file
	char * ofile_name = NULL;
    
	// DC-set manipulation
	//     0 ... stick to input (-d so)
	//     1 ... stick to complement (-d sc)
	int dc_manipulation = 1;

	// for merging shared terms
	bool merging = false;

	// containment
	bool containment = true;

	// print the result to the screen
	bool screen_print = true;

	// time limit for complement computing
	int time_limit = 0;

	// verbose mode
	bool verbose = false;

	// complement instance
	Complement cpl;


	// check the number of arguments
	if (argc <= 2)
	{
		cout << "Not enough arguments." << endl;
		cpl.printHelp();
		return 0;
	}
	
	// now we go through the arguments
	// and set the option values 
	int i = 1;
	while (i < argc)
	{
		if (strcmp(argv[i], "-n") == 0)
		{
			if (i == (argc - 1))
			{
				cout << "No value for -n option." << endl;
				cpl.printHelp();
				if (ifile_name != NULL)
					delete ifile_name;
				if (ofile_name != NULL)
					delete ofile_name;
				return 0;
			}
			if (ifile_name != NULL)
			{
				cout << "The input file name redefined!" << endl;
				if (ifile_name != NULL)
					delete ifile_name;
				if (ofile_name != NULL)
					delete ofile_name;
				return 0;
			}
			int len = strlen(argv[i+1]) + 1;
			ifile_name = (char*)malloc(sizeof(char) * len);
			strcpy_s(ifile_name, len*sizeof(char), argv[i+1]);
			ifile_name[len-1] = '\0';
			i += 2;
			continue;
		}
		if (strcmp(argv[i], "-o") == 0)
		{
			if (i == (argc - 1))
			{
				cout << "No value for -o option." << endl;
				cpl.printHelp();
				if (ifile_name != NULL)
					delete ifile_name;
				if (ofile_name != NULL)
					delete ofile_name;
				return 0;
			}
			if (ofile_name != NULL)
			{
				cout << "Output file name redefined!" << endl;
				if (ifile_name != NULL)
					delete ifile_name;
				if (ofile_name != NULL)
					delete ofile_name;
				return 0;
			}
			int len = strlen(argv[i+1]) + 1;
			ofile_name = (char*)malloc(sizeof(char) * len);
			strcpy_s(ofile_name, len*sizeof(char), argv[i+1]);
			ofile_name[len-1] = '\0';
			i += 2;
			continue;
		}
		if (strcmp(argv[i], "-d") == 0)
		{
			if (i == (argc - 1))
			{
				cout << "No value for -d option." << endl;;
				cpl.printHelp();
				if (ifile_name != NULL)
					delete ifile_name;
				if (ofile_name != NULL)
					delete ofile_name;
				return 0;
			}
			if (strcmp(argv[i+1], "so") == 0)
			{
				dc_manipulation = 0;
				i += 2;
				continue;
			}
			if (strcmp(argv[i+1], "sc") == 0)
			{
				dc_manipulation = 1;
				i += 2;
				continue;
			}
			cout << "Unknown value for -d option." << endl;
			cpl.printHelp();
			if (ifile_name != NULL)
				delete ifile_name;
			if (ofile_name != NULL)
				delete ofile_name;
			return 0;
		}
		if (strcmp(argv[i], "-m") == 0)
		{
			if (i == (argc - 1))
			{
				cout << "No value for -m option." << endl;;
				cpl.printHelp();
				if (ifile_name != NULL)
					delete ifile_name;
				if (ofile_name != NULL)
					delete ofile_name;
				return 0;
			}
			if (strcmp(argv[i+1], "on") == 0)
			{
				merging = true;
				i += 2;
				continue;
			}
			if (strcmp(argv[i+1], "off") == 0)
			{
				merging = false;
				i += 2;
				continue;
			}
			cout << "Unknown value for -m option." << endl;
			cpl.printHelp();
			if (ifile_name != NULL)
				delete ifile_name;
			if (ofile_name != NULL)
				delete ofile_name;
			return 0;
		}
		if (strcmp(argv[i], "-p") == 0)
		{
			if (i == (argc - 1))
			{
				cout << "No value for -p option." << endl;;
				cpl.printHelp();
				if (ifile_name != NULL)
					delete ifile_name;
				if (ofile_name != NULL)
					delete ofile_name;
				return 0;
			}
			if (strcmp(argv[i+1], "on") == 0)
			{
				screen_print = true;
				i += 2;
				continue;
			}
			if (strcmp(argv[i+1], "off") == 0)
			{
				screen_print = false;
				i += 2;
				continue;
			}
			cout << "Unknown value for -p option." << endl;
			cpl.printHelp();
			if (ifile_name != NULL)
				delete ifile_name;
			if (ofile_name != NULL)
				delete ofile_name;
			return 0;
		}
		if (strcmp(argv[i], "-c") == 0)
		{
			if (i == (argc - 1))
			{
				cout << "No value for -c option." << endl;;
				cpl.printHelp();
				if (ifile_name != NULL)
					delete ifile_name;
				if (ofile_name != NULL)
					delete ofile_name;
				return 0;
			}
			if (strcmp(argv[i+1], "on") == 0)
			{
				containment = true;
				i += 2;
				continue;
			}
			if (strcmp(argv[i+1], "off") == 0)
			{
				containment = false;
				i += 2;
				continue;
			}
			cout << "Unknown value for -c option." << endl;
			cpl.printHelp();
			if (ifile_name != NULL)
				delete ifile_name;
			if (ofile_name != NULL)
				delete ofile_name;
			return 0;
		}
		if (strcmp(argv[i], "-t") == 0)
		{
			if (i == (argc - 1))
			{
				cout << "No value for -t option." << endl;;
				cpl.printHelp();
				if (ifile_name != NULL)
					delete ifile_name;
				if (ofile_name != NULL)
					delete ofile_name;
				return 0;
			}
			
			time_limit = 0;
			bool tl_is_int = true;
			int delka = strlen(argv[i+1]);
			for (int k=0; k<delka; k++)
			{
				if ((argv[i+1][k] >= '0')&&(argv[i+1][k] <= '9'))
				{
					time_limit = time_limit*10 + (argv[i+1][k] - '0');
				} else {
					tl_is_int = false;
					time_limit = 0;
					break;
				}
			}
			if (tl_is_int == false)
			{
				cout << "Unknown or wrong value for -t option." << endl;
				cpl.printHelp();
				if (ifile_name != NULL)
					delete ifile_name;
				if (ofile_name != NULL)
					delete ofile_name;
				return 0;
			}
			i+=2;
			continue;
		}
		if (strcmp(argv[i], "-v") == 0)
		{
			verbose = true;
			i++;
			continue;
		}
		cout << "Unknown option: " << argv[i] << endl;
		cpl.printHelp();
		if (ifile_name != NULL)
			delete ifile_name;
		if (ofile_name != NULL)
			delete ofile_name;
		return 0;
	}

	if (ifile_name == NULL)
	{
		cout << "No input file was passed." << endl;
		cpl.printHelp();
		if (ifile_name != NULL)
			delete ifile_name;
		if (ofile_name != NULL)
			delete ofile_name;
		return 0;
	}

	// loading the input PLA
	PLA * inp = new PLA();
	try
	{
		inp->LoadPLA(ifile_name);
	} catch (RuntimeException e)
	  {
		  cout << "The input file could not be found or opened (" << e.GetMsg() << ")." << endl;
		  if (ifile_name != NULL)
			delete ifile_name;
		  if (ofile_name != NULL)
			delete ofile_name;
		  return 0;
	  }
	  catch (...)
	  {
		  cout << "The input file could not be found or opened." << endl;
		  if (ifile_name != NULL)
			delete ifile_name;
		  if (ofile_name != NULL)
			delete ofile_name;
		  return 0;	
	  }

	// let's compute the complement
	if (merging == false) cpl.SetMergeShared(false);
	cpl.SetVerbose(verbose);
	cpl.SetContainment(containment);
	cpl.SetTimeLimit(time_limit);
	PLA * res = cpl.PLAComplement(inp, dc_manipulation);
    
	// check time limit
	if (!cpl.IsLimitExceeded())
	{
		// print the result to the command line
		if (screen_print)
		{
			cout << endl << "Result: " << endl;
			if (!res->empty())
			{
				TermList::iterator ti;
				for (ti=res->GetData()->begin(); ti!=res->GetData()->end(); ti++)
					cout << ti->GetIM() << "   " << ti->GetOM() << endl;
				cout << endl;
			} else cout << "<empty complement>" << endl;
		}

		// saving the result to file
		if (ofile_name != NULL)
		{
			try
			{
				res->SavePLA(ofile_name);
			} catch (RuntimeException e)
			  {
		          cout << "The result could not be saved to file. The output file may already exist or you don't have appropriate access rights (" << e.GetMsg() << ")." << endl;
			  }
			  catch (...)
			  {
				  cout << "The result could not be saved to file. The output file may already exist or you don't have appropriate access rights." << endl;
			  }			  
		}

		cout << "Time: " << GetMyCPUTime() << endl;

	} else {
		cout << "Time limit exceeded!" << endl;
	}

	delete inp;
	delete res;
	if (ifile_name != NULL)
		delete ifile_name;
	if (ofile_name != NULL)
		delete ofile_name;
	
	return 0;
}
