#include <vector>
#include <fstream>
#include <iomanip>
#include <algorithm>    // std::set_difference, std::sort

using namespace std;

#include "global.h"

int makeZones(std::vector<int >& colWithNetUP_R, std::vector<int>& colWithNetDOWN_R, std::vector< std::vector<int> >& Sr, std::vector< std::vector<int> >& zonesR, std::vector<int>& zoneColEndR, string outputFileName)
{
    std::vector<int>::iterator it;  //declare iteratior
    std::vector<int> vdiff;         //declare vector that stores difference of two sets

    bool startRecNetinCol = false;  //declare start column bool
    bool newZone = false;           //sets true when new zone made
    bool startPrintSi = false;      //sets true when first S(i) is printed in the output file
    bool startPrintZone = false;    //sets true when first zone is printed in the output file
    int startNet = 0;               //holds column where net starts
    int stopNet = 0;                //holds column where net stops
    int maxTracks = 0;              //stores number of max tracks

    ofstream outputFile;                            //declare outputFile stream
    outputFile.open(outputFileName, ofstream::app); //append to file

    zoneColEndR.push_back(1);       //set start of zone as column 1

    Sr.resize(numColumns + 1);      //resize to number of columns + 1, 0 not used


    /**************************************Load S(i) with nets at corresponding columns***************************************/
    for (int net = 1; net <= numNets; net++)        //go through all nets (loading S(i))
    {
        for (int col = 1; col <= numColumns; col++) //go through all columns first and search if net exists in each column
        {
            if (colWithNetUP_R[col] == net || colWithNetDOWN_R[col] == net) //if net exists in either column array
            {
                if (startRecNetinCol == false)      //record which column net starts if false, else block saving a new start net column
                {
                    startRecNetinCol = true;        //record which column net starts, then block so start isnt altered
                    startNet = col;                 //save first column occurance of net
                }//if startRecNetinCol is false
                else
                    stopNet = col;                  //record column everytime onwards, until all columns are swept for each net

            }//if net exists in the column
        }//search colummn for net

        for (int m = startNet; m <= stopNet; m++)   //go from first column net was found to last column
            Sr[m].push_back(net);                   //push net onto column in S(i)

        startRecNetinCol = false;                       //reset for next net
        
    }//end for loading S(i)


    /**************************************Decides how to Make Zones***************************************/
    for (int i = 1; i < numColumns; i++)                //cycle through columns
    {       
        vdiff.resize(Sr[i - 1].size() + Sr[i].size());  //resize vector to size of S(i) + S(i+1)

        it = set_difference(Sr[i - 1].begin(), Sr[i - 1].end(), Sr[i].begin(), Sr[i].end(), vdiff.begin()); //check if anything from previous s(i) got removed in this s(i)
        vdiff.resize(it - vdiff.begin());   //compact vdiff, size is zero if no difference

        if (!vdiff.empty()) //if vector is not empty, means nets were dropped from i-1 to i, so maybe make new zone
        {   
            //if S(i) is not a subset of S(i-1), make new zone
            if (!includes(Sr[i - 1].begin(), Sr[i - 1].end(), Sr[i].begin(), Sr[i].end()))  //must be sorted, already is anyway from loading S(i) sequentially for loop
            {
                zoneColEndR.push_back(i - 1);                                               //only push on the column where zone ends
                newZone = true;                                                             //new zone true
            }
        }
    }//end for

    zoneColEndR.push_back(numColumns);          //push on final column to zones to create final zone


    /**************************************Populate Zones with Maximal Elements***************************************/
    for (int n = 0; n < int(zoneColEndR.size())-1; n++)
    {
        for (int i = zoneColEndR[n] + 1; i <= zoneColEndR[n + 1]; i++)
        {
            if ((zoneColEndR[n + 1] - zoneColEndR[n]) == 1)
            {
                zonesR.resize(n + 2);                                       //attach new 1-D onto zones
                zonesR[n+1].clear();                                        //clear new zone vector
                zonesR[n+1].resize(Sr[i].size());                           //resize to size of S(i+1) for zone(n)
                copy(Sr[i].begin(), Sr[i].end(), zonesR[n+1].begin());      //copy S(i) into zone(n)
                break;
            }
            
            if (i != zoneColEndR[n]+1)
            {   
                if ((Sr[i].size() > Sr[i - 1].size()))
                {
                    zonesR.resize(n + 2);
                    zonesR[n+1].clear();
                    zonesR[n+1].resize(Sr[i].size());
                    copy(Sr[i].begin(), Sr[i].end(), zonesR[n+1].begin());
                }
                
            }
            else
            {
                zonesR.resize(n + 2);
                zonesR[n + 1].clear();
                zonesR[n + 1].resize(Sr[i].size());
                copy(Sr[i].begin(), Sr[i].end(), zonesR[n + 1].begin());
            }
        }//loop through range of particuar zone

        if (int(zonesR[n + 1].size()) > maxTracks)
            maxTracks = zonesR[n + 1].size();

    }//loop through all zones


    //print columns and S(i)
    if (outputFile.is_open())
    {
        if (startPrintSi == false)
        {
            outputFile << endl;                     //new line
            outputFile << "Column " << "S(i)";      //print header info
            startPrintSi = true;                    //make sure it doesn't print again
            outputFile << endl;                                 //new line
        }

        for (int i = 1; i < int(Sr.size()); i++)            //go through zones
        {
            outputFile << left << setw(6) << i << " ";              //output column number

            for (int j = 0; j < int(Sr[i].size()); j++)     //go through elements of S(i)
            {
                outputFile << Sr[i][j] << " ";          //output maximal S(i)
            }

            outputFile << endl;                             //new line
        }

    }//end if file open


    //print zones and maximal S(i)
    if (outputFile.is_open())
    {
        if (startPrintZone == false)
        {
            outputFile << endl;                                 //new line
            outputFile << "Zone " << "Maximal S(i)";            //print header info
            startPrintZone = true;                              ////make sure it doesn't print again
            outputFile << endl;                                 //new line
        }

        for (int i = 1; i < int(zonesR.size()); i++)            //go through zones
        {
            outputFile << left << setw(4) << i << " ";                  //output zone number

            for (int j = 0; j < int(zonesR[i].size()); j++)     //go through elements of zones
            {
                
                outputFile << zonesR[i][j] << " ";              //output maximal S(i)
            }

            outputFile << endl;                                 //new line      
        }
    }//end if file open


    outputFile.close();     //close the file


    return maxTracks;

}// end makeZone