/**CFile****************************************************************

  FileName    [llb1Cluster.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [BDD based reachability.]

  Synopsis    [Clustering algorithm.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]
 
  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: llb1Cluster.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

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

#include "llbInt.h"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_ManComputeCommonQuant( Llb_Mtr_t * p, int iCol1, int iCol2 )
{
    int iVar, Weight = 0;
    for ( iVar = 0; iVar < p->nRows - p->nFfs; iVar++ )
    {
        // count each removed variable as 2
        if ( p->pMatrix[iCol1][iVar] == 1 && p->pMatrix[iCol2][iVar] == 1 && p->pRowSums[iVar] == 2 )
            Weight += 2;
        // count each added variale as -1
        else if ( (p->pMatrix[iCol1][iVar] == 1 && p->pMatrix[iCol2][iVar] == 0) || 
                  (p->pMatrix[iCol1][iVar] == 0 && p->pMatrix[iCol2][iVar] == 1) )
            Weight--;
    }
    return Weight;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_ManComputeBestQuant( Llb_Mtr_t * p )
{
    int i, k, WeightBest = -100000, WeightCur, RetValue = -1;
    for ( i = 1; i < p->nCols-1; i++ )
    for ( k = i+1; k < p->nCols-1; k++ )
    {
        if ( p->pColSums[i] == 0 || p->pColSums[i] > p->pMan->pPars->nClusterMax )
            continue;
        if ( p->pColSums[k] == 0 || p->pColSums[k] > p->pMan->pPars->nClusterMax )
            continue;

        WeightCur = Llb_ManComputeCommonQuant( p, i, k );
        if ( WeightCur <= 0 )
            continue;
        if ( WeightBest < WeightCur )
        {
            WeightBest = WeightCur;
            RetValue   = (i << 16) | k;
        }
    }
//    printf( "Choosing best quant Weight %4d\n", WeightCur );
    return RetValue;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
float ** Llb_ManComputeQuant( Llb_Mtr_t * p )
{
    float ** pCosts;
    int i, k;
    // alloc and clean
    pCosts = (float **)Extra_ArrayAlloc( p->nCols, p->nCols, sizeof(float) );
    for ( i = 0; i < p->nCols; i++ )
    for ( k = 0; k < p->nCols; k++ )
        pCosts[i][i] = 0.0;
    // fill up
    for ( i = 1; i < p->nCols-1; i++ )
    for ( k = i+1; k < p->nCols-1; k++ )
        pCosts[i][k] = pCosts[k][i] = Llb_ManComputeCommonQuant( p, i, k );
    return pCosts;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
float Llb_ManComputeCommonAttr( Llb_Mtr_t * p, int iCol1, int iCol2 )
{
    int iVar, CountComm = 0, CountDiff = 0;
    for ( iVar = 0; iVar < p->nRows - p->nFfs; iVar++ )
    {
        if ( p->pMatrix[iCol1][iVar] == 1 && p->pMatrix[iCol2][iVar] == 1 )
            CountComm++;
        else if ( p->pMatrix[iCol1][iVar] == 1 || p->pMatrix[iCol2][iVar] == 1 )
            CountDiff++;
    }
/*
    printf( "Attr cost for %4d and %4d:  %4d %4d (%5.2f)\n", 
        iCol1, iCol2, 
        CountDiff, CountComm, 
        -1.0 * CountDiff / ( CountComm + CountDiff ) );
*/
    return -1.0 * CountDiff / ( CountComm + CountDiff );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_ManComputeBestAttr( Llb_Mtr_t * p )
{
    float WeightBest = -100000, WeightCur;
    int i, k, RetValue = -1;
    for ( i = 1; i < p->nCols-1; i++ )
    for ( k = i+1; k < p->nCols-1; k++ )
    {
        if ( p->pColSums[i] == 0 || p->pColSums[i] > p->pMan->pPars->nClusterMax )
            continue;
        if ( p->pColSums[k] == 0 || p->pColSums[k] > p->pMan->pPars->nClusterMax )
            continue;
        WeightCur = Llb_ManComputeCommonAttr( p, i, k );
        if ( WeightBest < WeightCur )
        {
            WeightBest = WeightCur;
            RetValue   = (i << 16) | k;
        }
    }
    return RetValue;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
float ** Llb_ManComputeAttr( Llb_Mtr_t * p )
{
    float ** pCosts;
    int i, k;
    // alloc and clean
    pCosts = (float **)Extra_ArrayAlloc( p->nCols, p->nCols, sizeof(float) );
    for ( i = 0; i < p->nCols; i++ )
    for ( k = 0; k < p->nCols; k++ )
        pCosts[i][i] = 0.0;
    // fill up
    for ( i = 1; i < p->nCols-1; i++ )
    for ( k = i+1; k < p->nCols-1; k++ )
        pCosts[i][k] = pCosts[k][i] = Llb_ManComputeCommonAttr( p, i, k );
    return pCosts;
}


/**Function*************************************************************

  Synopsis    [Returns the number of variables that will be saved.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_MtrCombineSelectedColumns( Llb_Mtr_t * p, int iGrp1, int iGrp2 )
{
    int iVar;
    assert( iGrp1 >= 1 && iGrp1 < p->nCols - 1 );
    assert( iGrp2 >= 1 && iGrp2 < p->nCols - 1 );
    assert( p->pColGrps[iGrp1] != NULL );
    assert( p->pColGrps[iGrp2] != NULL );
    for ( iVar = 0; iVar < p->nRows; iVar++ )
    {
        if ( p->pMatrix[iGrp1][iVar] == 1 && p->pMatrix[iGrp2][iVar] == 1 )
            p->pRowSums[iVar]--;
        if ( p->pMatrix[iGrp1][iVar] == 0 && p->pMatrix[iGrp2][iVar] == 1 )
        {
            p->pMatrix[iGrp1][iVar] = 1;
            p->pColSums[iGrp1]++;
        }
        if ( p->pMatrix[iGrp2][iVar] == 1 )
            p->pMatrix[iGrp2][iVar] = 0;
    }
    p->pColSums[iGrp2] = 0;
}


/**Function*************************************************************

  Synopsis    [Combines one pair of columns.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManClusterOne( Llb_Mtr_t * p, int iCol1, int iCol2 )
{
    int fVerbose = 0;
    Llb_Grp_t * pGrp;
    int iVar;

    if ( fVerbose )
    {
        printf( "Combining %d and %d\n", iCol1, iCol2 );
        for ( iVar = 0; iVar < p->nRows; iVar++ )
        {
            if ( p->pMatrix[iCol1][iVar] == 0 && p->pMatrix[iCol2][iVar] == 0 )
                continue;
            printf( "%3d : %c%c\n", iVar, 
                p->pMatrix[iCol1][iVar]? '*':' ', 
                p->pMatrix[iCol2][iVar]? '*':' ' );
        }
    }
    pGrp = Llb_ManGroupsCombine( p->pColGrps[iCol1], p->pColGrps[iCol2] );
    Llb_MtrCombineSelectedColumns( p, iCol1, iCol2 );
    p->pColGrps[iCol1] = pGrp;
    p->pColGrps[iCol2] = NULL;
}

/**Function*************************************************************

  Synopsis    [Removes empty columns.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManClusterCompress( Llb_Mtr_t * p )
{
    int i, k = 0;
    for ( i = 0; i < p->nCols; i++ )
    {
        if ( p->pColGrps[i] == NULL )
        {
            assert( p->pColSums[i] == 0 );
            assert( p->pMatrix[i] != NULL );
            ABC_FREE( p->pMatrix[i] );
            continue;
        }
        p->pMatrix[k]  = p->pMatrix[i];
        p->pColGrps[k] = p->pColGrps[i];
        p->pColSums[k] = p->pColSums[i];
        k++;
    }
    p->nCols = k;
}

/**Function*************************************************************

  Synopsis    [Combines one pair of columns.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManCluster( Llb_Mtr_t * p )
{
    int RetValue;
    do
    {
        do {
            RetValue = Llb_ManComputeBestQuant( p );
            if ( RetValue > 0 )
                Llb_ManClusterOne( p, RetValue >> 16, RetValue & 0xffff );
        }
        while ( RetValue > 0 );

        RetValue = Llb_ManComputeBestAttr( p );
        if ( RetValue > 0 )
            Llb_ManClusterOne( p, RetValue >> 16, RetValue & 0xffff );

        Llb_MtrVerifyMatrix( p );
    }
    while ( RetValue > 0 );

    Llb_ManClusterCompress( p );

    Llb_MtrVerifyMatrix( p );
}


////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END