//---------------------------------------------------------------------------

#include "stdafx.h"

#ifdef _MSC_VER
#pragma hdrstop
#endif

using namespace std;

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

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

CD_Search::CD_Search( PLA *_pla, PLA *_implpool )
{
    source = _pla;
    implpool = _implpool;
    mutations = DEFAULT_CD_MUTATIONS;
    implcheck = DEFAULT_CD_IMPLCHECK;
	all_PIs = DEFAULT_CD_ALLPIS;
}

CD_Search::~CD_Search(void)
{
}

void CD_Search::Create_u_F( const unsigned int ov )
{
    CubeList::iterator ti;
    CubeList *onset;

    u_F.clear();
	onset = source->GetOnSet(ov)->GetData();
    for ( ti = onset->begin(); ti != onset->end(); ti++ )
        u_F.push_back(ti);
}

void CD_Search::Run(void)
{
    unsigned int ov;
    list<CubeList::iterator>::iterator ti, ti1;
    Term t(source->GetInputs(), source->GetOutputs());                    // term under construction
    TermList::iterator ti2;               // the constructed term
    unsigned int i, j;
    vector<int> candidates, candidates2;
    vector<int>::iterator vi;
    unsigned int cnt_p, cnt_n;    // counts of 1 and 0 literals in r_F
    unsigned int maxval;
    unsigned int var;        // selected split variable
    bool pol;                      // and its polarity (true = 1)
    enum { ok, NA, no } implOk;            // implicant check
	unsigned int inputs, outputs;		// local copy of source->inputs, outputs


 //   TS.start(TS_CDS);
	inputs = source->GetInputs();
	outputs = source->GetOutputs();
	for ( ov = 0; ov < outputs; ov++ ) {
        Create_u_F( ov );
        while ( !u_F.empty() ) {             // main loop
            r_F = u_F;
			t.init( inputs, outputs );
			t.origin = 1;
            do {          // term generation loop
              candidates.clear();
                    // mutations
              i = rand() % 100;
              if ( i < mutations ) {
                 for ( i = 0; i < inputs; i++ )       // mutate
                    if ( t.GetIM(i) == '-' )
                       for ( ti = r_F.begin(); ti != r_F.end(); ti++ )
                          if ( (*(*ti)).GetIM(i) == '1' ) {
                              candidates.push_back( i+1 );
                              break;
                          } else if ( (*(*ti)).GetIM(i) == '0' ) {
                              candidates.push_back( -int(i+1) );
                              break;
                          }
              } else                  // find the most frequent literal in the reduced on-set
              {
                  maxval = 0;
                  for ( i = 0; i < inputs; i++ )
                    if ( t.GetIM(i) == '-' ) {
                      cnt_p = 0;
                      cnt_n = 0;
                      for ( ti = r_F.begin(); ti != r_F.end(); ti++ )
                          if ( (*(*ti)).GetIM(i) == '1' ) cnt_p++;
                          else if ( (*(*ti)).GetIM(i) == '0' ) cnt_n++;
                      if ( cnt_p > maxval ) {
                          maxval = cnt_p;
                          candidates.clear();
                          candidates.push_back( i+1 );
                      } else if ( cnt_p == maxval && maxval > 0 ) candidates.push_back( i+1 );
                      if ( cnt_n > maxval ) {
                          maxval = cnt_n;
                          candidates.clear();
                          candidates.push_back( -int(i+1) );
                      } else if ( cnt_n == maxval && maxval > 0 ) candidates.push_back( -int(i+1) );
                    }
              }
              if ( candidates.size() == 0 ) throw BoomException( "CD-Search: on-set and off-set are not orthogonal" );

                 // perform implicant check
              if ( implcheck ) {
                 candidates2 = candidates;
                 vi = candidates2.begin();
                 do {
                     var = abs((*vi))-1;
                     pol = ((*vi) > 0);
                     t.SetIM( var, (pol)?'1':'0' );
                     if ( !source->IsImplicant( t, ov ) ) vi = candidates2.erase( vi );
                     else vi++;
                     t.SetIM( var, '-' );
                 } while ( vi != candidates2.end() );
                 if ( !candidates2.empty() ) {
					candidates = candidates2;
                    implOk = ok;
                 } else implOk = no;
              } else implOk = NA;

			  i = rand() % candidates.size();	// select one

			  if ( all_PIs && implOk == ok ) {		// put all the found PIs in the pool (except i)
				  for ( j = 0; j < candidates.size(); j++ )
					  if ( j != i ) {
						  var = abs(candidates[j])-1;
						  pol = (candidates[j] > 0);
						  t.SetIM( var, (pol)?'1':'0' );
						  ti2 = implpool->AppendTerm( t );
						  (*ti2).SetOM(ov, '1');
						  t.SetIM( var, '-' );
					  }
			  }
						
			  var = abs(candidates[i])-1;
              pol = (candidates[i] > 0);

                  // append literal to a term under construction
              t.SetIM( var, (pol)?'1':'0' );

                  // is t an implicant?
              if ( implOk == NA )
                if ( source->IsImplicant( t, ov ) ) implOk = ok; else implOk = no;
              if ( implOk == ok ) {          // add term to the pool
                  ti2 = implpool->AppendTerm( t );
                  (*ti2).SetOM(ov, '1');
                  ti = u_F.begin();                           // remove covered on-set
                  do {
					  if ( t.Cube::Contains( (**ti).GetIM() ) ) ti = u_F.erase( ti );
                      else ti++;
                  } while ( ti != u_F.end() );
                  break;
              } else {                                      // reduce on-set
                  ti = r_F.begin();
                  do {
                    if ( (*(*ti)).GetIM(var) != t.GetIM(var) ) ti = r_F.erase( ti );
                    else ti++;
                  } while ( ti != r_F.end() );
              }
            } while ( true );
        }
    }
//	TS.stop(TS_CDS);
}
