/*************************************************************************
  FILE:  BddSdSub1.cpp
  DESCR: Reordering the DES in the high-level or one low-level.
  AUTH:  Raoguang Song, Yu Wang
  DATE:  (C) Jan, 2006, 2009
*************************************************************************/
#include <cassert>
#include <vector>
#include "BddSdDES.h"
#include "BddSdPubfunc.h"
#include <cstdlib>
#include <math.h>
#include "BddSdSub.h"

// #include <iostream>

namespace BDDSD
{

/**
 * DESCR:   Main DES Reorder procedure
 * PARA:    None
 * RETURN:  0
 * ACCESS:  public
 */
int CSub::DESReorder()
{
    int iNumofDES = this->GetNumofDES();
    //compute the marix storing number of shared events between every two DES
    m_piCrossMatrix = new int *[iNumofDES];
    for (int i = 0; i < iNumofDES; i++)
        m_piCrossMatrix[i] = new int[iNumofDES];
    for (int i = 0; i < iNumofDES; i++)
        for (int j = 0; j < iNumofDES; j++)
        {
            m_piCrossMatrix[i][j] =
                        NumofSharedEvents(m_pDESArr[i]->GetEventsArr(),
                                            m_pDESArr[i]->GetNumofEvents(),
                                            m_pDESArr[j]->GetEventsArr(),
                                            m_pDESArr[j]->GetNumofEvents());
        }
    //Generate an initial order
    InitialDESOrder();
    UpdatePos();

    //Algorithm with force
    DESReorder_Force();
    UpdatePos();

    //sifting algorithm
    DESReorder_Sift();
    UpdatePos();

    //clear memory
    for (int i = 0; i < iNumofDES; i++)
    {
        delete[] m_piCrossMatrix[i];
        m_piCrossMatrix[i] = NULL;
    }
    delete[] m_piCrossMatrix;
    m_piCrossMatrix = NULL;

    //Order m_pDESArr according to the order of m_piDESOrderArr.
    CDES **pDESTmp = NULL;
    pDESTmp = new CDES *[this->GetNumofDES()];
    for (int i = 0; i < this->GetNumofDES(); i++)
    {
        pDESTmp[i] = m_pDESArr[m_piDESOrderArr[i]];
    }
    for (int i = 0; i < this->GetNumofDES(); i++)
    {
        m_pDESArr[i] = pDESTmp[i];
    }
    delete[] pDESTmp;
    pDESTmp = NULL;

    return 0;
}

/*
 * DESCR:   Using sifting algorithm to reorder DES
 * PARA:    None
 * RETURN:  0
 * ACCESS:  private
 */
int CSub::DESReorder_Sift()
{
    int iNumofDES = this->GetNumofDES();
    bool bChanged = false;
    double dMinCross = 0.0;
    double dCurCross = 0.0;
    int *piCurOpt = new int[iNumofDES];
    int *piInit = new int[iNumofDES];
    int iTemp = 0;
    int iCur = 0;
    int iCount = 0;
    double dOldCross = 0.0;
    double dInitCross = 0.0;
    double dSwapCross = 0.0;

    const int ITRNVALUE = 1000;
    // when reordering DES for BDD variables, this creates an upper
    // bound for iterations in case there is not an optimal solution
    int itrnLimit =  ITRNVALUE;
    // decided to not make it size dependent
    // int itrnLimit =  ITRNVALUE * iNumofDES;

    //initialize optimal des order and loop initial order;
    for (int j = 0; j < iNumofDES; j++)
    {
        piCurOpt[j] = m_piDESOrderArr[j];
        piInit[j] = m_piDESOrderArr[j];
    }

    //initialize cross over value
    dMinCross = TotalCross_Sift(0, 0, 0, 0);
    dOldCross = dMinCross;
    dInitCross = dMinCross;

    //Initialize m_piDESPosArr
    UpdatePos();

    //Optimize the DES order
    do
    {
        iCount++;
        bChanged = false;
        for (int iDES = 0; iDES < iNumofDES; iDES++)
        {
            iCur = m_piDESPosArr[iDES];

            //move backward
            for (int i = iCur; i < iNumofDES - 1; i++)
            {
                //compute dSwapCross
                dSwapCross = TotalCross_Sift(0, 0, i, 1);

                //swap i, i+1
                iTemp = m_piDESOrderArr[i + 1];
                m_piDESOrderArr[i + 1] = m_piDESOrderArr[i];
                m_piDESOrderArr[i] = iTemp;

                //test if current order is better
                dCurCross = TotalCross_Sift(dOldCross, dSwapCross, i, 2);
                dOldCross = dCurCross;
                if (dCurCross - dMinCross < 0)
                {
                    bChanged = true;
                    dMinCross = dCurCross;
                    for (int j = 0; j < iNumofDES; j++)
                        piCurOpt[j] = m_piDESOrderArr[j];
                }
            }

            //move forward
            for (int j = 0; j < iNumofDES; j++)
                m_piDESOrderArr[j] = piInit[j];
            dOldCross = dInitCross;
            for (int i = iCur; i > 0; i--)
            {
                //compute dSwapCross
                dSwapCross = TotalCross_Sift(0, 0, i - 1, 1);

                //swap i - 1, i
                iTemp = m_piDESOrderArr[i - 1];
                m_piDESOrderArr[i - 1] = m_piDESOrderArr[i];
                m_piDESOrderArr[i] = iTemp;

                //test if current order is better
                dCurCross = TotalCross_Sift(dOldCross, dSwapCross, i - 1, 2);
                dOldCross = dCurCross;
                if (dCurCross - dMinCross < 0)
                {
                    bChanged = true;
                    dMinCross = dCurCross;
                    for (int j = 0; j < iNumofDES; j++)
                        piCurOpt[j] = m_piDESOrderArr[j];
                }
            }
            dInitCross = dMinCross;
            dOldCross = dMinCross;
            if (bChanged && (iCount < itrnLimit))
            {
                for (int j = 0; j < iNumofDES; j++)
                {
                    m_piDESOrderArr[j] = piCurOpt[j];
                    piInit[j] = m_piDESOrderArr[j];
                }
                UpdatePos();
            }
            else
            {
                for (int j = 0; j < iNumofDES; j++)
                    m_piDESOrderArr[j] = piInit[j];
            }
	}
    }   //  make sure exit when iteration limit hit
    while((bChanged == true) && (iCount < itrnLimit));

    // give statistics about iterations
//    std::cout << "DESReorder_Sift: number of DES is:" << iNumofDES  << "\n"; 
//    std::cout << "DESReorder_Sift: itrnLimit is:" << itrnLimit  << "\n"; 
//    std::cout << "DESReorder_Sift: iteration count is:" << iCount  << "\n"; 


    delete[] piCurOpt;
    piCurOpt = NULL;

    delete[] piInit;
    piInit = NULL;

    return 0;
}

/*
 * DESCR:   Compute total cross for sifting algorithm
 * PARA:    dOldCross:  old cross value
 *          dSwapCross: cross changed due to swapping
 *          iCur: current position
 *          iFlag: 0: completey compute total cross value
 *                 1: compute total cross based on the old cross and swapped DES
 *                    (much faster)
 * RETURN:  new cross value
 * ACCESS:  private
 */
double CSub::TotalCross_Sift(double dOldCross, double dSwapCross,
                             int iCur, int iFlag)
{
    double dCross = 0;

    if (iFlag == 0) //completely compute the cross
    {
        for (int i = 0; i < this->GetNumofDES(); i++)
        {
            for (int j = i + 2; j < this->GetNumofDES(); j++)
                dCross += cross(i, j);
        }
    }
    else if (iFlag == 1) //only compute iCur, iCur + 1
    {
        //iCur
        for (int i = 0; i < iCur - 1; i++)
            dCross += cross(i, iCur);
        for (int i = iCur + 2; i < this->GetNumofDES(); i++)
            dCross += cross(iCur, i);
        //iCur + 1
        for (int i = 0; i < (iCur + 1) - 1; i++)
            dCross += cross(i, iCur + 1);
        for (int i = (iCur + 1) + 2; i < this->GetNumofDES(); i++)
            dCross += cross(iCur + 1, i);
    }
    else //update
    {
        //iCur
        for (int i = 0; i < iCur - 1; i++)
            dCross += cross(i, iCur);
        for (int i = iCur + 2; i < this->GetNumofDES(); i++)
            dCross += cross(iCur, i);
        //iCur + 1
        for (int i = 0; i < (iCur + 1) - 1; i++)
            dCross += cross(i, iCur + 1);
        for (int i = (iCur + 1) + 2; i < this->GetNumofDES(); i++)
            dCross += cross(iCur + 1, i);

        dCross = dOldCross - dSwapCross + dCross;
    }
    return dCross;
}

/*
 * DESCR:   Compute the cross for DES i and DES j
 * PARA:    i,j: DES position index,
 * RETURN:  the cross for DES i and DES j
 * ACCESS:  private
 */
double CSub::cross(int i, int j)
{
    return sqrt((double)(m_piCrossMatrix[m_piDESOrderArr[i]]
                                        [m_piDESOrderArr[j]]) * (j - i - 1));
}

/*
 * DESCR:   Initialize a DES order for the sifting reorder algorithm
 *          (some ideas are from Zhonghua Zhong's STCT)
 * PARA:    None
 * RETURN:  0
 * ACCESS:  private
 */
int CSub::DESReorder_Force()
{
    int iNumofDES = this->GetNumofDES();
    int iCount = 0;

    //Optimize the DES order
    bool bChanged = false;
    double dMinCross = TotalCross_Force();
    double dCurCross = 0.0;
    do
    {
        iCount++;
        bChanged = false;
        int iOptPos = 0;
        int iDES = 0;
        for (iDES = 0; iDES < iNumofDES; iDES++)
        {
            int iPrePos = 0;
            int iNextPos = iNumofDES - 1;
            int iPos = m_piDESPosArr[iDES];
            iOptPos = iPos;
            int iNewPos = 0;
            while (true)
            {
                double dForce = Force(iPos);
                if (dForce < -0.05)
                {
                    iNextPos = iPos;
                    iNewPos = iPos - (((iPos - iPrePos) % 2 == 0)?
                        ((iPos - iPrePos) / 2):((iPos - iPrePos) / 2 + 1));
                    if (iNewPos <= iPrePos)
                        break;
                    InsertDES(iPos, iNewPos);
                    UpdatePos();

                    iPos = iNewPos;
                    dCurCross = TotalCross_Force();
                    if (dCurCross < dMinCross - 0.05)
                    {
                        iOptPos = iPos;
                        dMinCross = dCurCross;
                        bChanged = true;
                    }
                }
                else if (dForce > 0.05)
                {
                    iPrePos = iPos;
                    iNewPos = iPos + (((iNextPos - iPos) % 2 == 0)?
                        ((iNextPos - iPos) / 2):((iNextPos - iPos) / 2 + 1));
                    if (iNextPos <= iNewPos)
                        break;
                    InsertDES(iPos, iNewPos);
                    UpdatePos();

                    iPos = iNewPos;
                    dCurCross = TotalCross_Force();
                    if (dCurCross < dMinCross - 0.05)
                    {
                        iOptPos = iPos;
                        dMinCross = dCurCross;
                        bChanged = true;
                    }
                }
                else
                    break;
            }
            InsertDES(m_piDESPosArr[iDES], iOptPos);
            UpdatePos();
        }
    }while(bChanged == true);

    return 0;
}

/*
 * DESCR:   Update DES position in array m_piDESPosArr according the new order
 * PARA:    None
 * RETURN:  None
 * ACCESS:  private
 */
void CSub::UpdatePos()
{
    for (int i = 0 ; i < this->GetNumofDES(); i++)
        m_piDESPosArr[m_piDESOrderArr[i]] = i;
    return;
}

/*
 * DESCR:   Swap variables in m_piDESOrderArr for DESReorder_Force()
 * PARA:    iCur: current variable position
 *          iPos: destinate variable position
 * RETURN:  None
 * ACCESS:  private
 */
void CSub::InsertDES(int iCur, int iPos)
{
    int iDES = m_piDESOrderArr[iCur];
    if (iCur < iPos)
    {
        for (int i = iCur + 1; i <= iPos; i++)
            m_piDESOrderArr[i - 1] = m_piDESOrderArr[i];
        m_piDESOrderArr[iPos] = iDES;
    }
    else if (iCur > iPos)
    {
        for (int i = iCur - 1; i >= iPos; i--)
            m_piDESOrderArr[i + 1] = m_piDESOrderArr[i];
        m_piDESOrderArr[iPos] = iDES;
    }
    return;
}

/*
 * DESCR:   Compute total cross for DESReorder_Force()
 * PARA:    None
 * RETURN:  total cross
 * ACCESS:  private
 */
double CSub::TotalCross_Force()
{
    double dCross = 0;
    for (int i = 0; i < this->GetNumofDES(); i++)
    {
        for (int j = i + 2; j < this->GetNumofDES(); j++)
            dCross += cross(i, j);
    }
    return dCross;
}

/*
 * DESCR:   Decide to move DES_i left or right. (< 0 : move left; >0 move right)
 *          for DESReorder_Force()
 * PARA:    i: position in m_piDESOrderArr
 * RETURN:  returned force
 * ACCESS:  private
 */
double CSub::Force(int i)
{
    double dForce = 0;
    for (int j = 0; j < i - 1; j++)
        dForce += sqrt((double)m_piCrossMatrix[m_piDESOrderArr[i]]
                                            [m_piDESOrderArr[j]] * (j - i + 1));
    for (int j = i + 2; j < this->GetNumofDES(); j++)
        dForce += sqrt((double)m_piCrossMatrix[m_piDESOrderArr[i]]
                                            [m_piDESOrderArr[j]] * (j - i - 1));
    return dForce;
}

/*
 * DESCR:   Initialize a DES order
 * PARA:    None
 * RETURN:  0
 * ACCESS:  private
 */
int CSub::InitialDESOrder()
{
    int i = 0;
    int j = 0;
    int k = 0;
    int iNumofDES = this->GetNumofDES();

    //There is no DES at all
    if (iNumofDES <= 0)
        return 0;

    //Only one DES
    m_piDESOrderArr[0] = 0;
    if (iNumofDES <= 1)
        return 0;

    int iPos = 0;
    double dLeftCross = 0;
    double dRightCross = 0;
    double dNewCross = 0;
    double dOldCross = 0;
    vector<int> vecDESOrder;
    vector<int> vecShared;

    //two or more DES
    vecDESOrder.push_back(0);
    vecDESOrder.push_back(1);

    for (i = 2; i < iNumofDES; i++)
    {
        vecShared.clear();
        for (j = 0; j < i; j++)
            vecShared.push_back(m_piCrossMatrix[i][vecDESOrder[j]]);

        iPos = i;
        dOldCross = MAX_DOUBLE;
        for (j = i; j >= 0; j--)
        {
            dLeftCross = 0;
            dRightCross = 0;

            for (k = 0; k < j; k++)
            {
                dLeftCross += vecShared[k] * (j - k - 1);
            }
            for (k = j; k < i; k++)
            {
                dRightCross += vecShared[k] * (k - j);
            }
            dNewCross = dLeftCross + dRightCross;

            if (dNewCross == 0)
            {
                iPos = j;
                break;
            }
            else
            {
                if (dNewCross < dOldCross - 0.05)
                {
                    dOldCross = dNewCross;
                    iPos = j;
                }
            }
        }

        if (iPos == 0)
            vecDESOrder.insert(vecDESOrder.begin(), i);
        else if (iPos == i)
            vecDESOrder.push_back(i);
        else
        {
            vector<int>::iterator itr = vecDESOrder.begin();
            itr += iPos;
            vecDESOrder.insert(itr, i);
        }
    }

    assert((int)vecDESOrder.size() == this->GetNumofDES());

    for (i = 0; i < (int)vecDESOrder.size(); i++)
    {
        m_piDESOrderArr[i] = vecDESOrder[i];
    }
    return 0;
}

} //end of namespace BDDSD
