#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <string>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;

static string CONFIG_PATH = "/data/config.ini";
static string DATA_PATH = "/data/";
static string OUTPUT_PATH = "/output/solution.txt";
const static int MAX_CLIENT = 36; // 最大的客户节点
const static int MAX_SITE = 136;  //最大的边缘节点
int clientArrLen;
int siteArrLen;
int QOS_LIMIT; // 最大延迟


// 主需要获取每个时间点所有的需求序列及其通过索引能够确定相应的客户节点的名字即可。
vector<string> timeSeqName;//时间序列的名字
vector<vector<int> > demand;//每个时间节点的贷款需求序列

/**
 * Site,即任务书中的边缘节点
 */
struct SiteNode
{
    string siteName;
    int siteIndex;
    int bandwidth; //该Site可分配的最大上限，不超过1000000MB
    int curAlloc;            //当前该节点分配到流量。
    bool ifAllocSat(int cnt) // 是否满足分配cnt流量
    {
        return curAlloc + cnt <= bandwidth;
    }
    int hot = 0;   //热度
    int timeT = 0; //高占用时间
    int Origin = 0;
} siteArr[MAX_SITE];
/**
 *
 * 客户节点
 */
struct ClientNode
{
    string clientName;
    vector<vector<pair<int, int>>> alloc; //每个时间点site节点分配的索引及流量
} clientArr[MAX_CLIENT];

struct QosTable
{
    // 初始化每个连接关系都为最大值
    int qosData[MAX_SITE][MAX_CLIENT];
    inline bool ifQosSat(int siteIndex, int clientIndex)
    {
        return qosData[siteIndex][clientIndex] < QOS_LIMIT;
    }
} qosTable;



/**
 * String split by delimiters
 */
static vector<string> split(const string& s, const string& delimiters = ",")
{
    vector<string> tokens;
    size_t lastPos = s.find_first_not_of(delimiters, 0);
    size_t pos = s.find_first_of(delimiters, lastPos);
    while (pos != string::npos || lastPos != string::npos)
    {
        tokens.emplace_back(s.substr(lastPos, pos - lastPos));
        lastPos = s.find_first_not_of(delimiters, pos);
        pos = s.find_first_of(delimiters, lastPos);
    }
    return tokens;
}
/**
 * 返回一行的数字vector
 */
static vector<int> split2(const string& s, const string& delimiters = ",")
{
    string str;
    vector<int> tokens;
    size_t lastPos = s.find_first_not_of(delimiters, 0);//查找第一个非,
    size_t pos = s.find_first_of(delimiters, lastPos);//查找第一个,
    str = s.substr(lastPos, pos - lastPos);
    lastPos = s.find_first_not_of(delimiters, pos);
    pos = s.find_first_of(delimiters, lastPos);
    while (pos != string::npos || lastPos != string::npos)
    {
        tokens.emplace_back(atoi(s.substr(lastPos, pos - lastPos).c_str()));
        lastPos = s.find_first_not_of(delimiters, pos);
        pos = s.find_first_of(delimiters, lastPos);
    }
    return tokens;
}

/**
 * read Config
 */
void readConf()
{
    ifstream config;
    config.open(CONFIG_PATH);
    string tmp_line;
    getline(config, tmp_line);
    getline(config, tmp_line);
    QOS_LIMIT = atoi(string(tmp_line.begin() + tmp_line.find('=') + 1, tmp_line.end()).c_str());
    config.close();
}
/**
 * read site_bandwidth.csv, qos.csv, demand.csv
 */
void readData()
{
    vector<string> tmp_vec;
    vector<int> tmp_vec2;
    ifstream data;
    string tmp_line;
    unsigned int index = 0;
    //初始化边缘节点列表以及每个边缘节点的带宽上限
    data.open(DATA_PATH + "demand.csv");
    string client_temp;
    getline(data, client_temp);
    data.close();
    data.clear();
    data.open(DATA_PATH + "site_bandwidth.csv");
    getline(data, tmp_line);
    // cout << tmp_line << endl;
    while (getline(data, tmp_line))
    {
        tmp_vec = split(tmp_line, ",");
        siteArr[index].siteName = tmp_vec[0];
        siteArr[index].bandwidth = atoi(tmp_vec[1].c_str());
        siteArr[index].curAlloc = 0;
        siteArr[index].siteIndex = index;
        index++;
    }
    siteArrLen = index;
    data.close();
    data.clear();

    //客户节点和边缘节点的Qos
    string tmp_name;
    data.open(DATA_PATH + "qos.csv");
    getline(data, tmp_name);
    // cout << tmp_line << endl;
    tmp_vec = split(client_temp, ",");
    for (index = 0; index < tmp_vec.size() - 1; index++)
    {
        clientArr[index].clientName = tmp_vec[static_cast<std:: vector<std::string, std::allocator<std::string>>::size_type>(index)+1];
    }
    clientArrLen = index;
    while (clientArr[clientArrLen - 1].clientName[clientArr[clientArrLen - 1].clientName.length() - 1] == '\r')
        clientArr[clientArrLen - 1].clientName.erase(clientArr[clientArrLen - 1].clientName.end() - 1);

    // 处理每个节点的Qos
    while (getline(data, tmp_line))
    {
        string sitename_temp = tmp_line.substr(0, tmp_line.find(','));
        for (int i = 0; i < siteArrLen; i++) {
            if (siteArr[i].siteName == sitename_temp) {
                index = i;
                break;
            }
        }
        tmp_vec2 = split2(tmp_line, ",");
        string tttmp;
        if (tmp_name[tmp_name.length()] == '\r')
            tttmp = tmp_name.substr(0, tmp_name.length() - 1);
        else
            tttmp = tmp_name;
        auto xxvec = split(tttmp, ",");
        int k = 0, sum = 0;
        while (sum != clientArrLen) 
        {
            for (int i = 0; i < clientArrLen; i++) 
            {
                if (clientArr[i].clientName == xxvec[sum + 1])
                {
                    k = i;
                    break;
                }
            }
            qosTable.qosData[index][k] = tmp_vec2[sum];
            sum++;
        }
    }
    data.close();
    data.clear();

    //客户节点在不同时刻的带宽需求信息
    data.open(DATA_PATH + "demand.csv");
    getline(data, tmp_line);
    index = 0;
    while (getline(data, tmp_line))
    {
        timeSeqName.push_back(tmp_line.substr(0, tmp_line.find_first_of(",")));
        demand.push_back(split2(tmp_line, ","));
    }
    data.close();
    data.clear();
}

bool cmpHot(const SiteNode& a, const SiteNode& b)
{
    return a.hot > b.hot;
} //按热度排序

void allocateBandwith(int timeIndex, ostream& fout) //最简化版，暂未考虑溢出，热度与95%的阻止
{
    for (int i = 0; i < siteArrLen; i++)
    {
        siteArr[i].curAlloc = 0;
        siteArr[i].Origin = 0;
    }

    for (int i = 0; i < clientArrLen; ++i)//主要逻辑
    {
        //TODO：写入客户名字
        fout << clientArr[i].clientName << ':';
        if (demand[timeIndex][i] == 0)
        {
            fout << '\n';
            continue;
        }
        vector<int> avIndex;
        for (int j = 0; j < siteArrLen; ++j)
        {
            if (qosTable.ifQosSat(siteArr[j].siteIndex, i))
            {
                if (siteArr[j].timeT < 0.05 * siteArrLen-1)
                {
                    avIndex.push_back(j);
                }
            }

        }
        //main
        string temp;
        int shengYu = 0;
        int tempD = demand[timeIndex][i] / (avIndex.size());
        vector<int> alloc(siteArrLen);
        for (auto j : avIndex)
        {
            siteArr[j].Origin = siteArr[j].curAlloc;
        }
        for (auto j : avIndex)  //计算总可分配流量
        {
            if (siteArr[j].timeT >= timeSeqName.size() * 0.05 - 1)
            {
                continue;
            }
            //计算alloc
            siteArr[j].curAlloc += tempD;
            if (j == *(avIndex.end() - 1))//最后一个节点要把所有的带宽都补上
            {
                siteArr[j].curAlloc -= tempD;
                siteArr[j].curAlloc += demand[timeIndex][i] - (avIndex.size() - 1) * tempD;
            }
            siteArr[j].curAlloc += shengYu;
            if (siteArr[j].curAlloc > siteArr[j].bandwidth)//如果超出限额了，就给下一个节点
            {
                shengYu = siteArr[j].curAlloc - siteArr[j].bandwidth;
                siteArr[j].curAlloc = siteArr[j].bandwidth;
                if (j == *(avIndex.end() - 1))//如果该节点为最后一个节点，则开启新一轮循环
                {
                    for (auto k : avIndex)
                    {
                        siteArr[k].curAlloc += shengYu;
                        if (siteArr[k].curAlloc > siteArr[k].bandwidth)
                        {
                            shengYu = siteArr[k].curAlloc - siteArr[k].bandwidth;
                            siteArr[k].curAlloc = siteArr[k].bandwidth;
                            alloc[k] = siteArr[k].curAlloc - siteArr[k].Origin;//TODO:写入带宽
                        }
                        else
                        {
                            alloc[k] = siteArr[k].curAlloc - siteArr[k].Origin;
                            break;
                        }
                    }
                }
            }
            else
            {
                shengYu = 0;
            }
            alloc[j] = siteArr[j].curAlloc - siteArr[j].Origin;//TODO:写入带宽
        }
        for (auto j : avIndex)//输出alloc
        {
            if (alloc[j] != 0)
                temp += "<" + siteArr[j].siteName + "," + to_string(alloc[j]) + ">,";
        }
        if (temp != "")
            temp.erase(temp.end() - 1);
        temp += '\n';
        fout << temp;
        shengYu = 0;
    }
    for (int i = 0; i < siteArrLen; i++)
    {
        if (siteArr[i].curAlloc > siteArr[i].bandwidth * 0.95)//如果超出0.95，高占用++
        {
            siteArr[i].timeT++;
        }
    }
}

void allocateBandwith2(int timeIndex, ostream& fout) //剩余5%的时间
{
    for (int i = 0; i < siteArrLen; i++)
    {
        siteArr[i].curAlloc = 0;
        siteArr[i].Origin = 0;
    }
    for (int i = 0; i < clientArrLen; i++)//主要逻辑
    {
        //TODO：写入客户名字
        fout << clientArr[i].clientName << ':';
        if (demand[timeIndex][i] == 0)
        {
            fout << '\n';
            continue;
        }
        vector<int> avIndex;//寻找延迟符合条件的节点
        for (int j = 0; j < siteArrLen; ++j)
        {
            if (qosTable.ifQosSat(siteArr[j].siteIndex, i))
            {
                avIndex.push_back(j);
            }

        }
        int shengYu = 0;
        string temp;
        for (auto j : avIndex)
        {
            siteArr[j].Origin = siteArr[j].curAlloc;
        }
        int flag2 = 0;
        for (auto j : avIndex)  //计算总可分配流量
        {
            if (siteArr[j].timeT >= timeSeqName.size() * 0.05 - 1)
            {
                continue;
            }
            //TODO：写入边缘节点名字
            if (flag2 == 0)
            {
                siteArr[j].curAlloc += demand[timeIndex][i];
            }
            siteArr[j].curAlloc += shengYu;
            if (siteArr[j].curAlloc > siteArr[j].bandwidth)//如果超出限额了，就给下一个节点，同时高占用++
            {
                shengYu = siteArr[j].curAlloc - siteArr[j].bandwidth;
                siteArr[j].curAlloc = siteArr[j].bandwidth;
                flag2 = 1;
                if (siteArr[j].curAlloc == siteArr[j].Origin)
                    continue;
                int alloc = siteArr[j].curAlloc - siteArr[j].Origin;//TODO:写入带宽
                temp += "<" + siteArr[j].siteName + "," + to_string(alloc) + ">,";
                continue;
            }
            if (siteArr[j].curAlloc == siteArr[j].Origin)
                break;
            int alloc = siteArr[j].curAlloc - siteArr[j].Origin;//TODO:写入带宽
            temp += "<" + siteArr[j].siteName + "," + to_string(alloc) + ">,";
            break;
        }
        if (temp != "")
            temp.erase(temp.end() - 1);
        temp += '\n';
        fout << temp;
        shengYu = 0;
    }
    for (int i = 0; i < siteArrLen; i++)
    {
        if (siteArr[i].curAlloc > siteArr[i].bandwidth * 0.95)//如果超出0.95，高占用++
        {
            siteArr[i].timeT++;
        }
    }
}


void testIO()
{
    readConf();
    readData();
}

int main()
{
    ofstream output(OUTPUT_PATH, ios::out);
    testIO();
    for (int j = 0; j < siteArrLen; ++j)    //获得热度
    {
        for (int i = 0; i < clientArrLen; ++i)
        {
            if (qosTable.ifQosSat(siteArr[j].siteIndex, i))
            {
                siteArr[j].hot++;
            }
        }
    }
    sort(siteArr, siteArr + siteArrLen, cmpHot); //按热度排序
    for (int time = 0; time < int(timeSeqName.size()); ++time) {
        if (time <= 0.95 * timeSeqName.size())
            allocateBandwith(time, output);
        else
            allocateBandwith2(time, output);
    }
    output.close();
    // system("truncate -s -1 /output/solution.txt");
    return 0;
}