//---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//---------------------------------------------------------------------------
#include "conf.h"
#include "boom.h"
#include "tboolfnct.h"
#include "fcmin.h"
#include "tpfnct.h"
//---------------------------------------------------------------------------
int ValidExp( TBoolFnct * fn, int j )
{
  int l;
  TPfnct * ff;

  ff = fn->parent->fnct;
  while ( ff != 0 )
  {
    if ( Intersects( fn->index[j]->iv, ff->iv, fn->inpvars ) )
    {
      for ( l = 0; l < fn->outvars; l++ )
        if ( fn->index[j]->ov[l] - ff->ov[l] == 1 )
          break;
      if ( l != fn->outvars ) break;
    }
    ff = ff->next;
  }
  return ( ff == 0 );
}
//---------------------------------------------------------------------------
TBoolFnct * Expand2( TBoolFnct * fn )
{
  int i, j, k, l;
  TPfnct * ff, * ff1;
  char * * expmask;
  char tmp;
  int cnt;
  int exps;
  FILE * f;

  f = fopen( "expand.log", "wt" );

  expmask = new char * [fn->terms];

  fn->Reindex();
  do
  {
    cnt = 0; // initialize the mask
    for ( i = 0; i < fn->terms; i++ )
    {
      expmask[i] = new char[fn->inpvars];
      fn->index[i]->tmp = fn->inpvars - fn->GetDim( fn->index[i]->iv );
      for ( j = 0; j < fn->inpvars; j++ )
        if ( fn->index[i]->iv[j] != '-' )
        {
          tmp = fn->index[i]->iv[j];
          fn->index[i]->iv[j] = '-';
          if ( !ValidExp( fn, i ) )
          {
            expmask[i] [j] = '2'; // non-expandable
            fn->index[i]->tmp--;
          }
          else
          {
            expmask[i] [j] = '0'; // expandable
            cnt++;
          }
          fn->index[i]->iv[j] = tmp;
        }
        else
          expmask[i] [j] = '1'; // DC
    }

    exps = 0;
    for ( i = 0; i < cnt; i++ )
    { // try to expand all literals
      j = random( fn->terms ); // select random term
      while ( fn->index[j]->tmp == 0 )
      {
        j++;
        j %= fn->terms;
      }
      k = random( fn->inpvars ); // select random var
      while ( expmask[j] [k] != '0' )
      {
        k++;
        k %= fn->inpvars;
      }
      tmp = fn->index[j]->iv[k];
      fn->index[j]->iv[k] = '-'; // expand
      expmask[j] [k] = tmp + 3;
      fn->index[j]->tmp--;
      // check for validity
      if ( !ValidExp( fn, j ) ) fn->index[j]->iv[k] = tmp;
      else
      { // OK, remove output DCs
        exps++;
        /* ff = fn->parent->fnct; while (ff != 0) { if (ff != fn->index[j] && Intersects(ff->iv, fn->index[j]->iv, fn->inpvars)) {
        for (l = 0; l < fn->outvars; l++) { if (fn->index[j]->ov[l] == '~' && ff->ov[l] == '0') fn->index[j]->ov[l] = '0';
        //  if (ff->ov[l] == '~' && fn->index[j]->ov[l] == '0') //     ff->ov[l] = '0'; } } ff = ff->next; }*/
      }
    }

    fprintf( f, "%i\n", exps ); fflush( f );

    for ( i = 0; i < fn->terms; i++ )
      for ( j = 0; j < fn->inpvars; j++ )
        if ( expmask[i] [j] == '3' || expmask[i] [j] == '4' )
        {
          fn->index[i]->iv[j] = expmask[i] [j] - 3;
          expmask[i] [j] = '0';
        }
  }
  while ( true );

  for ( i = 0; i < fn->terms; i++ ) delete[] expmask[i];
  delete[] expmask;
  return fn;
}
//---------------------------------------------------------------------------
TBoolFnct * Expand( TBoolFnct * fn, TGauge gauge )
{
  int i, j, k, l;
  TPfnct * ff, * ff1;
  char * * expmask;
  char tmp;
  int cnt;

  expmask = new char * [fn->terms];

  fn->Reindex();
  cnt = 0;
  for ( i = 0; i < fn->terms; i++ )
  {
    expmask[i] = new char[fn->inpvars];
    fn->index[i]->tmp = fn->inpvars - fn->GetDim( fn->index[i]->iv );
    for ( j = 0; j < fn->inpvars; j++ )
      if ( fn->index[i]->iv[j] != '-' )
      {
        expmask[i] [j] = '0';
        cnt++;
      }
      else
        expmask[i] [j] = '1';
  }
  gauge.NewGauge( "Expanding terms", cnt, 1 );
  for ( j = 0; j < fn->terms; j++ )
    while ( fn->index[j]->tmp != 0 )
    {
      k = random( fn->inpvars ); // select random var
      while ( expmask[j] [k] == '1' )
      {
        k++;
        k %= fn->inpvars;
      }
      tmp = fn->index[j]->iv[k];
      fn->index[j]->iv[k] = '-'; // expand
      expmask[j] [k] = '1';
      fn->index[j]->tmp--;
      // check for validity
      if ( !ValidExp( fn, j ) ) fn->index[j]->iv[k] = tmp;
      else
      { // OK, remove output DCs
        fn->index[j]->dim++;
        ff = fn->parent->fnct;
        while ( ff != 0 )
        {
          if ( Intersects( ff->iv, fn->index[j]->iv, fn->inpvars ) )
          {
            for ( l = 0; l < fn->outvars; l++ )
            {
              if ( fn->index[j]->ov[l] == '~' && ff->ov[l] == '0' )
                fn->index[j]->ov[l] = '0';
            }
          }
          ff = ff->next;
        }
        gauge.GaugeStep( i, 0 );
      }
    }

  for ( i = 0; i < fn->terms; i++ ) delete[] expmask[i];
  delete[] expmask;
  gauge.CloseGauge();
  return fn;
}
//---------------------------------------------------------------------------
TBoolFnct * MultiExpand( TBoolFnct * fn, TGauge gauge )
{
  int i, j, k, l;
  TPfnct * ff, * ff1;
  char * * expmask;
  char tmp;
  int cnt;
  int lit;
  int succ, nonexp, dcs;
  int cyc;

  FILE * f;

  f = fopen( "o://Multiexpand.dat", "wt" );
  cyc = 0;
  nonexp = 0;
  dcs = 0;

  expmask = new char * [fn->terms]; // '1' = DC, '0' = expandable, '2' = non-expandable, '3' = 0 expanded, '4' = 1 expanded

  fn->Reindex();
  cnt = 0;
  for ( i = 0; i < fn->terms; i++ )
  {
    expmask[i] = new char[fn->inpvars];
    fn->index[i]->tmp = fn->inpvars - fn->GetDim( fn->index[i]->iv );
    for ( j = 0; j < fn->inpvars; j++ )
      if ( fn->index[i]->iv[j] != '-' )
      {
        expmask[i] [j] = '0';
        cnt++;
      }
      else
      {
        expmask[i] [j] = '1';
        dcs++;
      }
  }

  fprintf( f, "Inputs: %i\n", fn->inpvars );
  fprintf( f, "Outputs: %i\n", fn->outvars );
  fprintf( f, "Source terms: %i\n\n", fn->parent->terms );
  fprintf( f, "Terms: %i\n", fn->terms );
  fprintf( f, "DCs: %i\n", dcs );
  fprintf( f, "Non-expandable: %i\n", nonexp );
  fprintf( f, "Expandable: %i\n\n", cnt );

  gauge.NewGauge( "Expanding terms", cnt, 1 );

  // identify non-expandable literals
  for ( i = 0; i < fn->terms; i++ )
    for ( j = 0; j < fn->inpvars; j++ )
      if ( expmask[i] [j] == '0' )
      {
        tmp = fn->index[i]->iv[j];
        fn->index[i]->iv[j] = '-';
        if ( !ValidExp( fn, i ) )
        {
          expmask[i] [j] = '2';
          fn->index[i]->tmp--;
          cnt--;
          nonexp++;
        }
        fn->index[i]->iv[j] = tmp;
      }
  // main loop

  do
  {
    succ = 0;
    for ( j = 0; j < fn->terms; j++ ) // try to expand all literals
           while ( fn->index[j]->tmp != 0 )
           {
             k = random( fn->inpvars ); // select random var
             while ( expmask[j] [k] != '0' )
             {
               k++;
               k %= fn->inpvars;
             }
             tmp = fn->index[j]->iv[k];
             fn->index[j]->iv[k] = '-'; // expand
             expmask[j] [k] = tmp + 3;
             fn->index[j]->tmp--;
             // check for validity
             if ( !ValidExp( fn, j ) ) fn->index[j]->iv[k] = tmp;
             else
             { // OK, remove output DCs
               succ++;
               fn->index[j]->dim++;
               ff = fn->parent->fnct;
               /* while (ff != 0) { if (Intersects(ff->iv, fn->index[j]->iv, fn->inpvars)) {
               for (l = 0; l < fn->outvars; l++) { if (fn->index[j]->ov[l] == '~' && ff->ov[l] == '0')
               fn->index[j]->ov[l] = '0'; } } ff = ff->next; } */
               gauge.GaugeStep( i, 0 );
             }
           }

         fn->GetInfo();
    lit = fn->info.liters;
    fprintf( f, "%i %i %i\n", cyc++, lit, succ ); fflush( f );
    for ( i = 0; i < fn->terms; i++ )
      for ( j = 0; j < fn->inpvars; j++ )
      {
        if ( expmask[i] [j] != '1' && expmask[i] [j] != '2' ) fn->index[i]->tmp++;
        if ( expmask[i] [j] == '3' || expmask[i] [j] == '4' )
        {
          fn->index[i]->iv[j] = expmask[i] [j] - 3;
          fn->index[i]->dim--;
          expmask[i] [j] = '0';
        }
      }

  }
  while ( true );
  for ( i = 0; i < fn->terms; i++ ) delete[] expmask[i];
  delete[] expmask;
  gauge.CloseGauge();
  return fn;
}
//---------------------------------------------------------------------------
TBoolFnct * FCMinimize( TBoolFnct * srcf, MinimizeOptions * mo, TGauge gauge )
{
  char * * ocover;
  int cov, icov;
  int i, j, m, n, cnt, d, k;
  int mlen;
  char * mask;
  char * vctmask;
  int * bestq;
  char * iv;
  int cnt_1;
  TPfnct * ff, * ff1;
  int aterm;
  int len; // # of covered vectors
  TBoolFnct * minf;
  int hits;
  int tries;
  int DF, DF_d;
  FILE * f;
  int r;

#if (mintrck > 0)
  f = fopen( "FC_hits.dat", "at" );
#endif

  bestq = new int[srcf->terms * srcf->outvars];
  mask = new char[srcf->outvars + 1];
  mask[srcf->outvars] = 0;
  iv = new char[srcf->inpvars + 1];
  iv[srcf->inpvars] = 0;
  vctmask = new char[srcf->terms + 1];
  vctmask[srcf->terms] = 0;
  ocover = new char * [srcf->terms];

  hits = 0;
  tries = 0;

  minf = srcf->CreateChildFnct();
  minf->type = 0;

  ff = srcf->fnct;
  cov = 0;
  i = 0;
  while ( ff != 0 )
  {
    ocover[i] = new char[srcf->outvars];
    for ( j = 0; j < srcf->outvars; j++ )
    {
      ocover[i] [j] = ff->ov[j];
      if ( ocover[i] [j] == '1' ) cov++;
    }
    i++;
    ff = ff->next;
  }
  icov = cov;
  gauge.NewGauge( "Minimizing PLA using FC-Min", icov, 1 );
  aterm = 0;
  mlen = 0;
  do
  { // main loop
    do
    {
      setmem( vctmask, srcf->terms, '0' );
      setmem( mask, srcf->outvars, '1' );
      n = 0;
      do
      {
        m = -1; // find best o. vector for inclusion
        cnt = 0;
        ff = srcf->fnct;
        i = 0;
        while ( ff != 0 )
        {
          if ( vctmask[i] == '0' )
          {
            k = 0;
            for ( j = 0; j < srcf->outvars; j++ )
              if ( ocover[i] [j] == '1' && mask[j] == '1' ) k++;
            if ( k == m ) bestq[cnt++] = i;
            if ( k > 0 && k > m )
            {
              bestq[0] = i;
              cnt = 1;
              m = k;
            }
          }
          ff = ff->next;
          i++;
        }
        if ( cnt > 0 )
        {
          i = bestq[random( cnt )];
          k = 0; // include variable
          if ( n > 0 )
          {
            for ( j = 0; j < srcf->outvars; j++ )
              if ( ocover[i] [j] == '0' && mask[j] == '1' ) k++;
            d = ( cnt_1 - k ) * ( n + 1 ) - cnt_1 * n; // improvement
          }
          if ( mo->FC_DF_dir == 2 )
          {
            DF_d = random( 2 );
            DF = random( mo->FC_DF + 1 );
          }
          else
          {
            DF_d = mo->FC_DF_dir;
            DF = mo->FC_DF;
          }
          r = random( DF + 1 );
          if ( n == 0 || ( d >= 0 && ( ( DF_d == 1 && r > 0 ) || ( DF_d == 0 && r == 0 ) ) ) )
          {
            vctmask[i] = '1';
            n++;
            cnt_1 = 0;
            for ( j = 0; j < srcf->outvars; j++ )
            {
              if ( ocover[i] [j] == '0' ) mask[j] = '0';
              if ( ocover[i] [j] == '~' && mask[j] == '1' && n == 1 ) mask[j] = '~';
              if ( mask[j] == '1' ) cnt_1++;
            }
          }
          else
            cnt = 0;
        }
      }
      while ( cnt > 0 );
      len = n;
      tries++;
      // find 1-intersections
      ff = srcf->fnct;
      i = 0;
      n = 0;
      while ( ff != 0 && n != len )
      {
        if ( vctmask[i] == '1' )
        {
          if ( n == 0 ) memcpy( iv, ff->iv, srcf->inpvars );
          else
            JoinCubes( iv, ff->iv, srcf->inpvars );
          n++;
        }
        ff = ff->next;
        i++;
      }
      // OK ?
      ff = srcf->fnct;
      i = 0;
      while ( ff != 0 )
      {
        if ( vctmask[i] == '0' && Intersects( iv, ff->iv, srcf->inpvars ) )
        {
          for ( k = 0; k < srcf->outvars; k++ )
            if ( abs( ff->ov[k] - mask[k] ) == 1 ) break;
          if ( k != srcf->outvars ) break;
        }
        ff = ff->next;
        i++;
      }
      if ( ff == 0 )
      {
        ff1 = srcf->fnct;
        i = 0;
        while ( ff1 != 0 )
        {
          if ( vctmask[i] == '0' && Intersects( iv, ff1->iv, srcf->inpvars ) )
          {
            for ( k = 0; k < srcf->outvars; k++ )
            {
              if ( ff1->ov[k] == '0' && mask[k] == '~' )
                mask[k] = '0';
            }
          }
          ff1 = ff1->next;
          i++;
        }
      }
    }
    while ( ff != 0 );
    hits++;
    // accept
    k = 0;
    ff = srcf->fnct;
    i = 0;
    while ( ff != 0 )
    {
      if ( vctmask[i] == '1' )
        for ( j = 0; j < srcf->outvars; j++ )
          if ( mask[j] == '1' && ocover[i] [j] == '1' )
          {
            ocover[i] [j] = '~';
            k++;
          }
      ff = ff->next;
      i++;
    }
    cov -= k;
    minf->AddTermToEnd( iv, mask, minf->GetDim( iv ) )->origin = 2;
    if ( gauge.GaugeStep( icov - cov, 0 ) == 2 ) break;
  }
  while ( cov != 0 );

  gauge.CloseGauge();

  if ( cov == 0 ) minf = Expand( minf, gauge );
  else minf = 0;

  delete[] mask;
  delete[] vctmask;
  delete[] bestq;
  for ( i = 0; i < srcf->terms; i++ )
    delete[] ocover[i];
  delete[] ocover;
  delete[] iv;

  minf->hits = hits;
  minf->tries = tries;

  return minf;
}
//---------------------------------------------------------------------------
