
#include "stdafx.h"

#ifdef _MSC_VER
#pragma hdrstop
#endif

using namespace std;

#include "../../Kernel/kernelincludes.h"

#include "defaults.h"
//#include "TimeStamp.h"
#include "FC_Min.h"
//---------------------------------------------------------------------------

FC_Min::FC_Min( PLA *_pla, PLA *_implpool, int iterations, TermQueue * tq_out)
{
	source = _pla;
	implpool = _implpool;
	DF = DEFAULT_DF;
	trials = 0;
	hits = 0;
	this->iterations = iterations;
	this->tq_out = tq_out;
	for (unsigned i = 0; i < source->outputs(); i++) {
		source->GenerateOnSet(i);
		source->GenerateOffSet(i);
	}
}

/*FC_Min::~FC_Min(void)
{
}*/

bool FC_Min::GenerateImplicant( const set<Term*> &Cover, const string &Mask )
{
	unsigned int i;
	TermList *data;
	Term *t;
	set<Term*>::const_iterator ci;
	TermList::const_iterator ti;

	data = source->getData();
	t = new Term( source->inputs(), source->outputs() );
	if ( t == NULL) throw RuntimeException( "FC_Min: Not enough memory" );

	// generate the term
	for ( ci = Cover.begin(); ci != Cover.end(); ++ci ) 
		if ( ci == Cover.begin() ) t->setCube((*ci)->getCube());
		else for ( i = 0; i < source->inputs(); i++ ) 
			if ( (*ci)->getLit(i) != t->getLit(i) ) t->setLit_dc(i);

	// is it valid?
	for ( i = 0; i < source->outputs(); i++ )
		if ( Mask[i] == '1' && !source->isImplicant(*t, i) ) {
			delete t;
			return false;
		}
	t->setOM(Mask);
	t->origin = 2;
	//implpool->AppendTerm(*t);
	tq_out->push(*t);
	delete t;
	return true;
}

void FC_Min::Run(void)
{
	for (int iter = 0; iter < iterations; iter++) {
		TermList *data;
		TermList::iterator ti;
		set<Term*> Cover;
		string Mask;
		unsigned int i;
		unsigned int cnt, mx, hsize, vsize;
		vector<TermList::iterator> candidates;
		bool valid;
		set<Term*>::iterator ci;
		bool covered;
		bool onefound;
		bool terminate;

		//	TS.start(TS_FC);

		sourcecopy = *source;			// make a copy of source PLA
		data = sourcecopy.getData();

		// remove all-zero terms
		ti = data->begin();
		do {
			for ( i = 0; i < source->outputs(); i++ )
				if ( (*ti).isOM_1(i) ) break;
			if ( i == source->outputs() ) ti = sourcecopy.DeleteTerm(ti);
			else ti++;
		} while ( ti != data->end() );

		do {				// main loop
			do {			// implicant generation loop
				Cover.clear();
				Mask.assign( source->outputs(), '1' );
				hsize = source->outputs();
				vsize = 0;
				do {
					// Find "widest" term
					candidates.clear();
					mx = 0;
					for ( ti = data->begin(); ti != data->end(); ++ti ) {
						if ( Cover.find(&(*ti)) == Cover.end() ) {
							cnt = source->outputs();
							onefound = false;
							for ( i = 0; i < source->outputs(); i++ )
								if ( Mask[i] == '0' || ti->isOM_0(i) || ti->isOM_undef(i) ) {
									cnt--;
									if ( cnt*(vsize+1) < hsize*vsize ) break; // no chance for improvement
								} else if ( Mask[i] == '1' && ti->isOM_1(i) ) onefound = true;
							if ( cnt*(vsize+1) >= hsize*vsize && onefound ) {			// can be included
								if ( cnt > mx ) {
									candidates.clear();
									candidates.push_back(ti);
									mx = cnt;
								} else if ( cnt == mx ) candidates.push_back(ti);
							}
						}
					}
					// select candidate term
					if ( candidates.empty() ) break;             // no further improvement possible
					ti = candidates[rand() % candidates.size()];

					// include it into the cover
					Cover.insert(&(*ti));
					vsize++;
					for ( i = 0; i < source->outputs(); i++ ) {
						if ( ti->isOM_0(i) || ti->isOM_undef(i) )
							if ( Mask[i] == '1' ) {
								Mask[i] = '0';
								hsize--;
							}
							if ( ti->isOM_dc(i) || ti->isOM_undef(i) ) Mask[i] = '~';
					}
					terminate = (unsigned int)( rand() % 100 ) >= DF;		// here is DF
				} while (!terminate);
				valid = GenerateImplicant( Cover, Mask );		// generate minimum term
				trials++;
				if ( valid ) hits++;
			} while ( !valid );
			// remove covered on-set
			for ( ci = Cover.begin(); ci != Cover.end(); ci++ ) {
				covered = true;
				for ( i = 0; i < source->outputs(); i++ ) {
					if ( Mask[i] == '1' ) (*ci)->setOM_undef(i);
					if ( (*ci)->isOM_1(i) ) covered = false;
				}
				if ( covered ) (*ci)->setUnwanted();
			}
			sourcecopy.Purge();
		} while ( sourcecopy.getTerms() != 0 );
		//	TS.stop(TS_FC);
	}
}
