
#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 )
{
    source = _pla;
    implpool = _implpool;
	DF = DEFAULT_DF;
	trials = 0;
	hits = 0;
}

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->GetInputs(), source->GetOutputs() );
	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->SetIM((*ci)->GetIM());
		else for ( i = 0; i < source->GetInputs(); i++ ) 
			if ( (*ci)->GetIM(i) == '-' || (*ci)->GetIM(i) != t->GetIM(i) ) t->SetIM(i, '-');

		// is it valid?
	for ( ti = data->begin(); ti != data->end(); ti++ )
		if ( t->Cube::Intersects((*ti).GetIM()) ) 
			for ( i = 0; i < source->GetOutputs(); i++ )
				if ( Mask[i] == '1' && (*ti).GetOM(i) == '0' ) {
					delete t;
					return false;
				}
	t->SetOM(Mask);
	t->origin = 2;
	implpool->AppendTerm(*t);
	delete t;
	return true;
}

void FC_Min::Run(void)
{
    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->GetOutputs(); i++ )
			if ( (*ti).GetOM(i) == '1' ) break;
		if ( i == source->GetOutputs() ) ti = sourcecopy.DeleteTerm(ti);
		else ti++;
	} while ( ti != data->end() );

	do {				// main loop
		do {			// implicant generation loop
			Cover.clear();
			Mask.assign( source->GetOutputs(), '1' );
			hsize = source->GetOutputs();
			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->GetOutputs();
					onefound = false;
					for ( i = 0; i < source->GetOutputs(); i++ )
						if ( Mask[i] == '0' || (*ti).GetOM(i) == '0' || (*ti).GetOM(i) == '~') {
							cnt--;
							if ( cnt*(vsize+1) < hsize*vsize ) break; // no chance for improvement
						} else if ( Mask[i] == '1' && (*ti).GetOM(i) == '1' ) 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->GetOutputs(); i++ ) {
				   if ( (*ti).GetOM(i) == '0'  || (*ti).GetOM(i) == '~' )
					   if ( Mask[i] == '1' ) {
						   Mask[i] = '0';
						   hsize--;
					   }
				   if ( (*ti).GetOM(i) == '-' || (*ti).GetOM(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->GetOutputs(); i++ ) {
				if ( Mask[i] == '1' ) (*ci)->SetOM( i, '~' );
				if ( (*ci)->GetOM(i) == '1' ) covered = false;
			}
			if ( covered ) (*ci)->SetUnwanted();
		}
		sourcecopy.Purge();
	} while ( sourcecopy.GetTerms() != 0 );

//	TS.stop(TS_FC);
}
