#include "global.h"

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>    //define random_shuffle, copy

using namespace std;

int generateG1(std::vector<std::vector<int> >& G1R, std::vector<std::vector<int> >& netConnectionsR, std::vector<int>& netConnectionsFilledColR, std::vector<int>& parta, std::vector<int>& partb, std::vector<int>& unlockeda, std::vector<int>& unlockedb, int& node2swapX, int& node2swapY)
{
    int N = pad_offset+1;        //set N to number of total nodes
    int extraN = 4;         //how many extra columns added to G1
    int G1_Init = -1;       //initial values for G1 vector
    int node = 0, connectingNode = 0;
    int k = 0;
    int cutsize = 0;
    bool inA = false, inB = false;
    bool firstTime = false;              //set firstTime to false. If G1 was not resized this time, it will be set to true.

    if(N % 2)               //if N is odd (true), dummy row was added during parseFile
        N += 1;             //account for additional dummy row, N should be even always

    if(int(G1R.size()) != N)     //if G1R is not N x something, then do initial resize
    {
        G1R.resize(N, vector<int>(N, G1_Init)); //resize G1 to create a N x N matrix with G1_Init
        for(int i = 0; i < N; i++)
        {
            G1R[i].resize(N+extraN, 0); //resize G1 to create a N x N+extraN matrix with zeros
        }

        firstTime = true;
    }

    if(firstTime != true)
    {
        //cout << "in G1 node: " << node2swapX << "goes to partB now" << endl;
        //cout << "in G1 node: " << node2swapY << "goes to partA now" << endl;

        for(int i = 0; i <= 1; i++)
        {
            switch(i){                  //select node2swapX or node2swapX depending on i
                case 0:
                    node = node2swapX;  //set node to node2swapX
                    G1R[node][N] = 2;   //set that this node is going to partB, so make x(1) to y(2)
                    break;
                case 1:
                    node = node2swapY;  //set node to node2swapY
                    G1R[node][N] = 1;   //set that this node is going to partB, so make y(2) to x(1)
                    break;
                default:
                    break;
            }//switch

            for(int j = 0; j < (netConnectionsFilledColR[node]); j++)  //cycle through all the connections to node2swap
            {
                connectingNode = netConnectionsR[node][j];          //save connected node of node2swapX

                switch(G1R[node][connectingNode]){          //rows of swap have x's switched to y's and vice versa
                    case 11:
                        G1R[node][connectingNode] = 12;     //was Ax, now is Ay
                        cutsize++;
                        break;
                    case 12:
                        G1R[node][connectingNode] = 11;     //was Ay, now is Ax
                        break;
                    case 21:
                        G1R[node][connectingNode] = 22;     //was Bx, now is By
                        break;
                    case 22:
                        G1R[node][connectingNode] = 21;     //was By, now is Bx
                        break;
                    default:
                        break;
                }//switch

                switch(G1R[connectingNode][node]){          //columns of swap have x's switched to y's and vice versa
                    case 11:
                        G1R[connectingNode][node] = 21;     //was Ax, now is Bx
                        G1R[connectingNode][N+1] -= 1;      //subtract one A
                        G1R[connectingNode][N+2] += 1;      //plus one B
                        break;
                    case 12:
                        G1R[connectingNode][node] = 22;     //was Ay, now is By
                        G1R[connectingNode][N+1] -= 1;      //subtract one A
                        G1R[connectingNode][N+2] += 1;      //plus one B
                        break;
                    case 21:
                        G1R[connectingNode][node] = 11;     //was Bx, now is Ax
                        G1R[connectingNode][N+1] += 1;      //plus one A
                        G1R[connectingNode][N+2] -= 1;      //subtract one B
                        break;
                    case 22:
                        G1R[connectingNode][node] = 12;     //was By, now is Ay
                        G1R[connectingNode][N+1] += 1;      //plus one A
                        G1R[connectingNode][N+2] -= 1;      //subtract one B
                        break;
                    default:
                        break;
                }//switch

            }//cycle through all the connections to node2swap

        }//end for node2swap


        //find gain
        for(int i = 0; i < N; i++)
        {
            if(G1R[i][N] == 1)                            //check if at position N, it is 1(x) or 2(y)
                G1R[i][N+3] = G1R[i][N+2] - G1R[i][N+1];  //Since this row is marked as 1(Zx), do counts(B - A) = G

            else
                G1R[i][N+3] = G1R[i][N+1] - G1R[i][N+2];  //Since this row is marked as 2(Zy), do counts(A - B) = G
        }//for find gain




            for(int i = 0; i < N/2; i++)                //go through partA, looking for node2swapX
            {
                if(parta[i] == node2swapX)              //when node2swapX is found in partA
                {
                    parta.erase(parta.begin() + i);            //remove node2swapX
                    unlockeda.erase(unlockeda.begin() + i);    //remove node2swapX and lock away
                    partb.push_back(node2swapX);               //push node2swapX onto partB
                    break;
                }
            }

            for(int i = 0; i < int(partb.size()); i++)  //go through partB, looking for node2swapY
            {
                if(partb[i] == node2swapY)              //when node2swapY is found in partB
                {
                    partb.erase(partb.begin() + i);            //remove node2swapY
                    unlockedb.erase(unlockedb.begin() + i);    //remove node2swapY and lock away
                    parta.push_back(node2swapY);               //push node2swapY onto partA
                    break;
                }
            }

        /*cout << "after swap unlocked nodes are" << endl;
        for(std::vector<int>::iterator it = unlockeda.begin(); it!=unlockeda.end(); ++it)
        cout << ' ' << *it;
        cout << '\n' ;

        for(std::vector<int>::iterator it = unlockedb.begin(); it!=unlockedb.end(); ++it)
        cout << ' ' << *it;
        cout << '\n' ;
        */


    }//if not firstTime


    else                                //else firstTime != false, meaning it is the first time
    {
        for(int i = 0; i < N/2; i++)    //cycle through partA
        {
            node = parta[i];            //select node in partA

            for(int j = 0; j < (netConnectionsFilledColR[node]); j++)  //cycle through all the connections to node
            {
                //cout << "netConnectionsFilledCol: " << netConnectionsFilledColR[node] << endl;
                k = 0;
                while(k < N/2 && inA == false && inB == false)  //look for sink node in partA and partB
                {
                    if(parta[k] == netConnectionsR[node][j])     //sink node in partA, so mark as 11(Ax)
                    {
                        inA = true;                                                      //found sink node in partA
                        connectingNode = netConnectionsR[node][j];                       //save sink node
                        //cout << "inA: " << inA << endl;
                        //cout << "partAk: " << parta[k] << endl;
                        //cout << "netConnections: " << netConnectionsR[node][j] << endl;
                    }
                    if(partb[k] == netConnectionsR[node][j])     //sink node in partB, so mark as 21(Bx)
                    {
                        inB = true;                                                      //found sink node in partB
                        connectingNode = netConnectionsR[node][j];                       //save sink node
                        //cout << "inB: " << inB << endl;
                        //cout << "partBk: " << partb[k] << endl;
                        //cout << "netConnections: " << netConnectionsR[node][j] << endl;
                    }

                    k++; //increment to next node in partitions, until N/2
                }

                if(inA == true) //in partA
                {
                    G1R[node][connectingNode] = 11;                         //set G1R to 11(Ax), (sink in A, source in A)
                    G1R[connectingNode][node] = 11;                         //set G1R to 11(Ax), (sink in A, source in A), transpose nodes

                    G1R[node][N+1] += 1;                                      //save count of A's in N of the row for the node
                                                                        //don't count G1R[connectingNode][N] += 1, causes overcount
                    G1R[node][N] = 1;                                     //set that this node is in partA, 1(Zx)
                    //cout << "G1: " << G1R[node][connectingNode] << endl;
                    inA = false;
                }
                if(inB == true) //in partB
                {
                    G1R[node][connectingNode] = 21;                         //set G1R to 21(Bx), (sink in B, source in A)
                    G1R[connectingNode][node] = 12;                         //set G1R to 12(Ay), (sink in A, source in B), transpose nodes

                    G1R[node][N+2] += 1;                                    //save count of B's in N of the row for the node
                    G1R[connectingNode][N+1] += 1;                            //save count of A's in N of the row for the connectingNode

                    G1R[node][N] = 1;                                     //set that this node is in partA, 1(Zx)
                    G1R[connectingNode][N] = 2;                           //set that this node is in partB, 2(Zy)

                    cutsize++;                                              //cutsize adds by one for each pair of Ay, Bx pairs
                    //cout << "G1: " << G1R[node][connectingNode] << endl;
                    inB = false;
                }

            }//cycle through all the connections to node


        }//cycle through partA


        /* Since the last section found three out of 4 possible combinations of source and sink nodes in the partitions, */
        /* we can only look at partition B now, and just check if the sink nodes exist in B and mark accordingly. */

        for(int i = 0; i < N/2; i++)    //cycle through partB
        {
            node = partb[i];            //select node in partB

            for(int j = 0; j < (netConnectionsFilledColR[node]); j++)  //cycle through all the connections to node
            {
                //cout << "netConnectionsFilledCol: " << netConnectionsFilledColR[node] << endl;
                k = 0;
                while(k < N/2 && inA == false && inB == false)  //look for sink node in partB
                {
                    if(partb[k] == netConnectionsR[node][j])     //sink node in partB, so mark as 22(By)
                    {
                        inB = true;                                                      //found sink node in partB
                        connectingNode = netConnectionsR[node][j];                       //save sink node
                        //cout << "inB: " << inB << endl;
                        //cout << "partBk: " << partb[k] << endl;
                        //cout << "netConnections: " << netConnectionsR[node][j] << endl;
                    }

                    k++; //increment to next node in partitions, until N/2
                }

                if(inB == true) //in partB
                {
                    G1R[node][connectingNode] = 22;                         //set G1R to 22(By), (sink in B, source in B)
                    G1R[connectingNode][node] = 22;                         //set G1R to 22(By), (sink in B, source in B), transpose nodes

                    G1R[node][N+2] += 1;                                    //save count of B's in N+1 of the row for the node
                                                                        //don't count G1R[connectingNode][N+1] += 1, causes overcount
                    G1R[node][N] = 2;                                     //set that this node is in partA, 2(Zy)
                    //cout << "G1: " << G1R[node][connectingNode] << endl;
                    inB = false;
                }

            }//cycle through all the connections to node

        }//cycle through partB



        //find gain
        for(int i = 0; i < N; i++)
        {
            if(G1R[i][N] == 1)
                G1R[i][N+3] = G1R[i][N+2] - G1R[i][N+1];  //Since this row is marked as 1(Zx), do counts(B - A) = G

            else
                G1R[i][N+3] = G1R[i][N+1] - G1R[i][N+2];  //Since this row is marked as 2(Zy), do counts(A - B) = G
        }

    }//end else firstTime != false, meaning it is the first time



    //print out G1
    /*for(int m = 0 ; m < N; m++) //rows
    {
        cout << m << ": ";

        for(int n = 0; n < N+extraN; n++)   //columns
        {
            cout << G1R[m][n] << " ";
        }
        cout << "" << endl;
    }*/

    //cout << "Cutsize: " << cutsize << endl;
    return cutsize;

}