#include	<stdlib.h>
#include	<fstream.h>
#include	<assert.h>
#include	<stdarg.h>
#include    <stdio.h>
#include    <math.h>
#include	<time.h>
#include    "routing_area.h"
//using namespace std;

#define     EMPTY           -100000
#define     PORTBASE        1000000

CRoutingArea::~CRoutingArea()
{
 //   delete[] m_iNetPriority;
 //   delete[] m_iPortAmount;
 //   delete[] m_pRoutingCells;
}

bool CRoutingArea::isFinished()
{
    int     i;
    for (i=0; i<m_iNetAmount; i++)
    {
        if (isRouted(i)==0)
            return false;
    }
    return true;
}

bool CRoutingArea::isnotBottleNeck(int iXPos,int iYPos)
{
    int     iTmpXPos, iTmpYPos,iOthers,iPreNet;

    if (getCell(iXPos,iYPos)>=PORTBASE)
        return false;
    iPreNet=getCell(iXPos,iYPos);

    iOthers=0;
    iTmpXPos=iXPos-1;       iTmpYPos=iYPos-1;
    if (iTmpXPos>=0 && iTmpYPos>=0)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos;       iTmpYPos=iYPos-1;
    if (iTmpYPos>=0)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && 
                iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos+1;       iTmpYPos=iYPos-1;
    if (iTmpXPos<m_iXSize && iTmpYPos>=0)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && 
                iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos+1;   iTmpYPos=iYPos;
    if (iTmpXPos<m_iXSize)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && 
                iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos+1;   iTmpYPos=iYPos+1;
    if (iTmpXPos<m_iXSize && iTmpYPos<m_iYSize)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && 
                iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos;   iTmpYPos=iYPos+1;
    if (iTmpXPos<m_iXSize && iTmpYPos<m_iYSize)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos+1;   iTmpYPos=iYPos+1;
    if (iTmpXPos<m_iXSize && iTmpYPos<m_iYSize)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos-1;   iTmpYPos=iYPos+1;
    if (iTmpXPos>=0 && iTmpYPos<m_iYSize)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }
    return true;
}

void CRoutingArea::initialize(int iNetAmount, int iMaxPortAmount)
{
    int         i,j,iPortAmount,iXPos, iYPos;

    srand(time(NULL));
    m_iNetAmount=iNetAmount;
    m_iNetPriority=new int(iNetAmount);
    for (i=0; i<iNetAmount; i++)
    {
        m_iNetPriority[i]=i;
    }
    m_iPortAmount=new int(iNetAmount);
    
    for (i=0; i<iNetAmount;i++)
    {
        iPortAmount=rand()%iMaxPortAmount;
        if (iPortAmount<=1)
            iPortAmount=2;
        m_iPortAmount[i]=iPortAmount;
        for (j=0;j<iPortAmount;j++)
        {
            do
            {
                iXPos=rand()%m_iXSize;
                iYPos=rand()%m_iYSize;
            }
            while (getCell(iXPos,iYPos)!=EMPTY);
            setCell(iXPos,iYPos,PORTBASE+i);
        }
    }
}

int CRoutingArea::getCell(int iXPos, int iYPos, int *pArea)
{
    if (pArea==NULL)
        pArea=m_pRoutingCells;
#ifdef _DEBUG
    int     iIndex;
    assert(iYPos*m_iXSize+iXPos>=0 && iYPos*m_iXSize+iXPos<(m_iXSize*m_iYSize));
    iIndex=iYPos*m_iXSize+iXPos;
    iIndex=pArea[iYPos*m_iXSize+iXPos];
#endif
    return pArea[iYPos*m_iXSize+iXPos];
}

void CRoutingArea::setCell(int iXPos, int iYPos, int iNet,int *pArea)
{
    if (pArea==NULL)
        pArea=m_pRoutingCells;
    assert(iYPos*m_iXSize+iXPos>=0 && iYPos*m_iXSize+iXPos<(m_iXSize*m_iYSize));
    pArea[iYPos*m_iXSize+iXPos]=iNet;
}

CRoutingArea::CRoutingArea(int iXSize,int iYSize)
{
    int         i,iAmount;

    m_iXSize=iXSize;
    m_iYSize=iYSize;
    iAmount=iXSize*iYSize;
    m_pRoutingCells=new int(iAmount);
    pTmpRoutingCells=new int(m_iXSize*m_iYSize);
    for (i=0; i<iAmount;i++)
    {
        m_pRoutingCells[i]=EMPTY;
    }

    iXQueue=new int(m_iXSize*m_iYSize);
    iYQueue=new int(m_iXSize*m_iYSize);
    m_iNetPriority=NULL;
    m_iPortAmount=NULL;
}

void CRoutingArea::SingleStepRouting(bool bBlackGrid)
{
    int     i,j,k;
#ifdef _DEBUG
    int     iDEBUG;
#endif

    for (k=0; k<m_iNetAmount; k++)//choose high priority net.
    {
        for (i=0; i<m_iXSize; i++)
        {
            for (j=0; j<m_iYSize; j++)
            {
                if ((i+j)%2==bBlackGrid) //the cell is black cell.
                {
#ifdef _DEBUG
                    iDEBUG=getCell(i,j);
#endif
                    if (getCell(i,j)==m_iNetPriority[k] || 
                        getCell(i,j)-PORTBASE==m_iNetPriority[k] )
                        Expand(m_iNetPriority[k],i,j);
                }
            }
        }
    }
}

void CRoutingArea::Expand(int iNet, int iPortX, int iPortY)
{
    if (iPortX-1>=0)
    {
        Occupy(iNet, iPortX-1, iPortY);
    }

    if (iPortY+1<m_iYSize)
    {
        Occupy(iNet, iPortX, iPortY+1);
    }

    if (iPortX+1<m_iXSize)
    {
        Occupy(iNet, iPortX+1, iPortY);
    }

    if (iPortY-1>=0)
    {
        Occupy(iNet, iPortX, iPortY-1);
    }
}

bool CRoutingArea::Occupy(int iNet, int iPosX, int iPosY)
{
    if (getCell(iPosX,iPosY)==EMPTY)
    {
        setCell(iPosX,iPosY, iNet);
        return true;
    }

    if (isnotBottleNeck(iPosX,iPosY)==true)
    {
        if (isHighPriority(iNet,getCell(iPosX,iPosY))==true)
        {
            if (isPortCell(iPosX,iPosY)==EMPTY)
            {
                setCell(iPosX,iPosY,iNet);
            }
        }
    }
    return false;
}

bool CRoutingArea::isHighPriority(int iSourceNet, int iNextNet)
{
    if (iNextNet==EMPTY)
        return true;
    if (abs(m_iNetPriority[iSourceNet])>abs(m_iNetPriority[iNextNet]))
        return true;
    else
        return false;
}

int CRoutingArea::isPortCell(int iXPos,int iYPos)
{
    if (abs(getCell(iXPos,iYPos))>=PORTBASE)
        return abs(getCell(iXPos,iYPos))-PORTBASE;
    else
        return EMPTY;
}

void CRoutingArea::ModifyPriority()
{
    int     i,iRouted, iRouting;
    int     *RoutedNetPriority, *RoutingNetPriority;

    iRouted=0; 
    iRouting=0;
    RoutedNetPriority=new int(m_iNetAmount);
    RoutingNetPriority=new int(m_iNetAmount);

    for (i=0;i<m_iNetAmount;i++)
    {
        if (isRouted(i)>0)
            RoutedNetPriority[iRouted++]=i;
        else
            RoutingNetPriority[iRouting++]=i;
    }

    for (i=0; i<iRouted; i++)
    {
    }

    for (i=0; i<iRouting; i++)
    {
    }
    delete[] RoutedNetPriority;
    delete[] RoutingNetPriority;
}

int CRoutingArea::isRouted(int iNet)
{
    int     i,j;
    int     iQueueStart,iQueueEnd,iAmount=0,iXPos,iYPos,iPortCount;

    for (i=0; i<m_iXSize*m_iYSize;i++)
    {
        pTmpRoutingCells[i]=m_pRoutingCells[i];
    }

    iPortCount=0;
    for (i=0; i<m_iXSize; i++)
    {
        for (j=0; j<m_iYSize; j++)
        {
            if (getCell(i,j,pTmpRoutingCells)==iNet || isPortCell(i,j)==iNet)
            {
                iXQueue[0]=i;    iYQueue[0]=j;
                iQueueStart=0;  iQueueEnd=1;
                iAmount++;
                
                if (isPortCell(i,j)==iNet)
                {
                    iPortCount++;
                    setCell(i,j,-iNet-PORTBASE,pTmpRoutingCells);
                }
                else
                    setCell(i,j,-iNet,pTmpRoutingCells);
                while (iQueueStart!=iQueueEnd)
                {
                    iXPos=iXQueue[iQueueStart];
                    iYPos=iYQueue[iQueueStart++];

                    if (iXPos-1>=0 && 
                        (getCell(iXPos-1,iYPos,pTmpRoutingCells)==getCell(iXPos,iYPos) ||
                        getCell(iXPos-1,iYPos,pTmpRoutingCells)==getCell(iXPos,iYPos)-PORTBASE))
                    {
                        iXQueue[iQueueEnd]=iXPos-1;
                        iYQueue[iQueueEnd++]=iYPos;
                        iAmount++;
                        setCell(iXPos-1,iYPos,-getCell(iXPos,iYPos),pTmpRoutingCells);
                        if (isPortCell(iXPos-1,iYPos)==iNet)
                            iPortCount++;
                    }

                    if (iXPos+1<m_iXSize && 
                        (getCell(iXPos+1,iYPos,pTmpRoutingCells)==getCell(iXPos,iYPos) ||
                        getCell(iXPos+1,iYPos,pTmpRoutingCells)==getCell(iXPos,iYPos)-PORTBASE))
                    {
                        iXQueue[iQueueEnd]=iXPos+1;
                        iYQueue[iQueueEnd++]=iYPos;
                        iAmount++;
                        setCell(iXPos+1,iYPos,-getCell(iXPos,iYPos),pTmpRoutingCells);
                        if (isPortCell(iXPos+1,iYPos)==iNet)
                            iPortCount++;
                    }

                    if (iYPos-1>=0 && 
                        (getCell(iXPos,iYPos-1,pTmpRoutingCells)==getCell(iXPos,iYPos) ||
                        getCell(iXPos,iYPos-1,pTmpRoutingCells)==getCell(iXPos,iYPos)-PORTBASE))
                    {
                        iXQueue[iQueueEnd]=iXPos;
                        iYQueue[iQueueEnd++]=iYPos-1;
                        iAmount++;
                        setCell(iXPos,iYPos-1,-getCell(iXPos,iYPos),pTmpRoutingCells);
                        if (isPortCell(iXPos,iYPos-1)==iNet)
                            iPortCount++;
                    }

                    if (iYPos+1<m_iYSize && 
                        (getCell(iXPos,iYPos+1,pTmpRoutingCells)==getCell(iXPos,iYPos) ||
                        getCell(iXPos,iYPos+1,pTmpRoutingCells)==getCell(iXPos,iYPos)-PORTBASE))
                    {
                        iXQueue[iQueueEnd]=iXPos;
                        iYQueue[iQueueEnd++]=iYPos+1;
                        iAmount++;
                        setCell(iXPos,iYPos+1,-getCell(iXPos,iYPos),pTmpRoutingCells);
                        if (isPortCell(iXPos,iYPos+1)==iNet)
                            iPortCount++;
                    }
                }


                if (iPortCount==m_iPortAmount[iNet])
                    return iAmount;
                else
                    return 0;
            }
            //廣度優(yōu)先遍歷，如果找到的Port數(shù)等于線網(wǎng)Port數(shù)，則該線網(wǎng)已連接。并給出占用單元數(shù)
        }
    }

    return 0;
}

void CRoutingArea::Print()
{
    int     i,j;

    for (i=0; i<m_iYSize; i++)
    {
        for (j=0; j<m_iXSize; j++)
        {
            if (getCell(j,i)>=PORTBASE)
                printf("%d@",(getCell(j,i)-PORTBASE));
            else
            {
                if (abs(getCell(j,i))!=abs(EMPTY))
                    printf("%d",abs(getCell(j,i)));
                else
                    printf("-");
            }

            printf("\t");
        }
        printf("\n");
    }
}
/*

ostream& operator<<(ostream& os,CRoutingArea &Area)
{
    int     i,j;

    for (i=0; i<Area.m_iYSize; i++)
    {
        for (j=0; j<Area.m_iXSize; j++)
        {
            if (Area.getCell(j,i)>=PORTBASE)
                os<<(Area.getCell(j,i,.Area.m_pRoutingCells)-PORTBASE)<<"*";
            else
                os<<abs(Area.getCell(j,i,Area.m_pRoutingCells));

            os<<"\t";
        }
        os<<endl;
    }
    return os;
}

  */
/*
1. 待連接的線網(wǎng)應比已連接的線網(wǎng)擴展快，
2. 其它子線網(wǎng)的擴展必須不破壞任何已連接線網(wǎng)的連接性；
3. 為避免振蕩，不允許任何兩個子線網(wǎng)具有相同的優(yōu)先度；
4. 不允許一個子線網(wǎng)擴展到另一子線網(wǎng)的節(jié)點所在的區(qū)域中。


Bottleneck. 沿一定方向搜索，若此8個單元中的線網(wǎng)號由中心單元的線網(wǎng)號變化為其它線網(wǎng)
號或未用單元、障礙單元的次數(shù)小于2次，則該單元一定不是瓶頸單元。

運用瓶頸單元概念，一個子線網(wǎng)要擴展到另一個線網(wǎng)已占的單元中必須滿足下列條件：
(1). 該單元不是另一個線網(wǎng)的瓶頸單元；
(2). 擴展的線網(wǎng)應具有比已占該單元的線網(wǎng)更高的擴展優(yōu)先權(quán)；
(3). 該單元不是另一個線網(wǎng)的節(jié)點；

在這種布線方法中，采用三種優(yōu)先權(quán)：
(1). 未布通線網(wǎng)的子線網(wǎng)具有比已布線網(wǎng)更高的擴展優(yōu)先權(quán)；
(2). 已布通線網(wǎng)的擴展優(yōu)先權(quán)隨其所占單元數(shù)的增加而減小；未布通線網(wǎng)的每個子線網(wǎng)
隨著它們之間的距離縮短，擴展優(yōu)先權(quán)上升；
*/