/*************************************************************************
  FILE:  BddHiscSub1.cpp
  DESCR: Reordering the DES in the high-level or one low-level.
  AUTH:  Raoguang Song
  Supervisor: Dr. Ryan Leduc
  DATE:  (C) Jan, 2006
*************************************************************************/
#include <cassert>
#include <vector>
#include "BddHiscDES.h"
#include "BddHiscPubfunc.h"
#include <cstdlib>
#include <math.h>
#include "BddHiscSub.h"
#include "BddHiscProject.h"

namespace BDDHISC
{
    /**
     * 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;

        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));
 
        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 BDDHISC
