#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <queue>
#include <numeric>
#include <iostream>

#include "private_arrays_search.h"
#include "../Utils/SgUtils.h"

using namespace std;

void print_info(LoopGraph* loop)
{
    cout << "loopSymbol: " << loop->loopSymbol << endl;
    for (const auto& ops : loop->writeOpsForLoop)
    {
        cout << "Array name: " << ops.first->GetShortName() << endl;
        for (const auto i : ops.second)
        {
            i.printInfo();
        }
    }
    if (!loop->children.empty())
    {
        for (const auto child : loop->children)
        {
            print_info(child);
        }
    }
}

static bool isParentStmt(SgStatement* stmt, SgStatement* parent)
{
    for (; stmt; stmt = stmt->controlParent())
        if (stmt == parent)
        {
            return true;
        }
    return false;
}

/*returns head block and loop*/
pair<SAPFOR::BasicBlock*, unordered_set<SAPFOR::BasicBlock*>> GetBasicBlocksForLoop(LoopGraph* loop, vector<SAPFOR::BasicBlock*> blocks)
{
    unordered_set<SAPFOR::BasicBlock*> block_loop;
    SAPFOR::BasicBlock* head_block = nullptr;
    auto loop_operator = loop->loop->GetOriginal();
    for (const auto& block : blocks)
    {
        if (!block || (block->getInstructions().size() == 0))
        {
            continue;
        }
        SgStatement* first = block->getInstructions().front()->getInstruction()->getOperator();
        SgStatement* last = block->getInstructions().back()->getInstruction()->getOperator();
        if (isParentStmt(first, loop_operator) && isParentStmt(last, loop_operator))
        {
            block_loop.insert(block);

            if ((!head_block) && (first == loop_operator) && (last == loop_operator) &&
                (block->getInstructions().size() == 2) &&
                (block->getInstructions().back()->getInstruction()->getOperation() == SAPFOR::CFG_OP::JUMP_IF))
            {
                head_block = block;
            }

        }
    }
    return { head_block, block_loop };
}


void BuildLoopIndex(map<string, LoopGraph*>& loopForIndex, LoopGraph* loop) {
    string index = loop->loopSymbol;
    loopForIndex[index] = loop;
    for (const auto& childLoop : loop->children) {
        BuildLoopIndex(loopForIndex, childLoop);
    }
}

string FindIndexName(int pos, SAPFOR::BasicBlock* block, map<string, LoopGraph*>& loopForIndex) {
    unordered_set<SAPFOR::Argument*> args = {block->getInstructions()[pos]->getInstruction()->getArg1()};

    for (int i = pos-1; i >= 0; i--) {
        SAPFOR::Argument* res = block->getInstructions()[i]->getInstruction()->getResult();
        if (res && args.find(res) != args.end()) {
            SAPFOR::Argument* arg1 = block->getInstructions()[i]->getInstruction()->getArg1();
            SAPFOR::Argument* arg2 = block->getInstructions()[i]->getInstruction()->getArg2();
            if (arg1) {
                string name = arg1->getValue();
                int idx = name.find('%');
                if (idx != -1 && loopForIndex.find(name.substr(idx + 1)) != loopForIndex.end())
                    return name.substr(idx + 1);
                else {
                    args.insert(arg1);
                }
            }
            if (arg2) {
                string name = arg2->getValue();
                int idx = name.find('%');
                if (idx != -1 && loopForIndex.find(name.substr(idx + 1)) != loopForIndex.end())
                    return name.substr(idx + 1);
                else {
                    args.insert(arg2);
                }
            }
        }
    }
    return "";
}

int GetDefUseArray(SAPFOR::BasicBlock* block, LoopGraph* loop, ArrayAccessingIndexes& def, ArrayAccessingIndexes& use) {
    auto instructions = block->getInstructions();
    map<string, LoopGraph*> loopForIndex;
    BuildLoopIndex(loopForIndex, loop);
    for(int i = 0; i < instructions.size(); i++)
    {
        auto instruction = instructions[i];
        if(!instruction->getInstruction()->getArg1()) {
            continue;
        }
        auto operation = instruction->getInstruction()->getOperation();
        auto type = instruction->getInstruction()->getArg1()->getType();
        if ((operation == SAPFOR::CFG_OP::STORE && type == SAPFOR::CFG_ARG_TYPE::ARRAY) ||
            (operation == SAPFOR::CFG_OP::LOAD && type == SAPFOR::CFG_ARG_TYPE::ARRAY))
        {

            vector<SAPFOR::Argument*> index_vars;
            vector<int> refPos;
            string array_name;
            if (operation == SAPFOR::CFG_OP::STORE)
            {
                array_name = instruction->getInstruction()->getArg1()->getValue();
            }
            else
            {
                array_name = instruction->getInstruction()->getArg2()->getValue();
            }
            int j = i - 1;
            while (j >= 0 && instructions[j]->getInstruction()->getOperation() == SAPFOR::CFG_OP::REF)
            {
                index_vars.push_back(instructions[j]->getInstruction()->getArg1());
                refPos.push_back(j);
                j--;
            }
            /*to choose correct dimension*/
            int n = index_vars.size();
            if (operation == SAPFOR::CFG_OP::STORE)
            {
                if (def[array_name].empty())
                {
                    def[array_name].resize(n);
                }
            }
            else
            {
                if (use[array_name].empty())
                {
                    use[array_name].resize(n);
                }
            }

            SgArrayRefExp* ref = (SgArrayRefExp*)instruction->getInstruction()->getExpression();
            vector<pair<int, int>> coefsForDims;
            for (int i = 0; i < ref->numberOfSubscripts(); ++i)
            {
                const vector<int*>& coefs = getAttributes<SgExpression*, int*>(ref->subscript(i), set<int>{ INT_VAL });
                if (coefs.size() == 1)
                {
                    const pair<int, int> coef(coefs[0][0], coefs[0][1]);
                    coefsForDims.push_back(coef);
                }
                
            }

            while (!index_vars.empty())
            {
                auto var = index_vars.back();
                int currentVarPos = refPos.back();
                pair currentCoefs = coefsForDims.back();
                ArrayDimension current_dim;
                if (var->getType() == SAPFOR::CFG_ARG_TYPE::CONST) {
                    current_dim = { stoul(var->getValue()), 1, 1 };
                }
                else
                {
                    string name, full_name = var->getValue();
                    int pos = full_name.find('%');
                    LoopGraph* currentLoop;
                    if (pos != -1) {
                        name = full_name.substr(pos+1);
                        if (loopForIndex.find(name) != loopForIndex.end()) {
                            currentLoop = loopForIndex[name];
                        }
                        else {
                            return -1;
                        }
                    }
                    else {
                        name = FindIndexName(currentVarPos, block, loopForIndex);
                        if (name == "") {
                            return -1;
                        }
                        if (loopForIndex.find(name) != loopForIndex.end()) {
                            currentLoop = loopForIndex[name];
                        }
                        else {
                            return -1;
                        }
                    }
                    uint64_t start = currentLoop->startVal * currentCoefs.first + currentCoefs.second;
                    uint64_t step = currentCoefs.first;
                    current_dim = { start, step, (uint64_t)currentLoop->calculatedCountOfIters };
                }
                if (operation == SAPFOR::CFG_OP::STORE)
                {
                    def[array_name][n - index_vars.size()].push_back(current_dim);
                }
                else
                {
                    use[array_name][n - index_vars.size()].push_back(current_dim);
                }
                index_vars.pop_back();
                refPos.pop_back();
                coefsForDims.pop_back();
            }
        }
    }
    return 0;

}

vector<uint64_t> FindParticularSolution(const ArrayDimension& dim1, const ArrayDimension& dim2) 
{
    for (uint64_t i = 0; i < dim1.tripCount; i++) 
    {
        uint64_t leftPart = dim1.start + i * dim1.step;
        for (uint64_t j = 0; j < dim2.tripCount; j++) 
        {
            uint64_t rightPart = dim2.start + j * dim2.step;
            if (leftPart == rightPart) 
            {
                return {i, j};
            }
        }
    }
    return {};
}
/* dim1 /\ dim2 */
ArrayDimension* IntersectDimension(const ArrayDimension& dim1, const ArrayDimension& dim2) 
{
    vector<uint64_t> partSolution =  FindParticularSolution(dim1, dim2);
    if (partSolution.empty()) 
    {
        return NULL;
    }
    int64_t x0 = partSolution[0], y0 = partSolution[1];
    /* x = x_0 + c * t */
    /* y = y_0 + d * t */
    int64_t c = dim2.step / gcd(dim1.step, dim2.step);
    int64_t d = dim1.step / gcd(dim1.step, dim2.step);
    int64_t tXMin, tXMax, tYMin, tYMax;
    tXMin = -x0 / c;
    tXMax = (dim1.tripCount - 1 - x0) / c;
    tYMin = -y0 / d;
    tYMax = (dim2.tripCount - 1 - y0) / d;
    int64_t tMin = max(tXMin, tYMin);
    uint64_t tMax = min(tXMax, tYMax);
    if (tMin > tMax) 
    {
        return NULL;
    }
    uint64_t start3 = dim1.start + x0 * dim1.step;
    uint64_t step3 = c * dim1.step;
    ArrayDimension* result = new(ArrayDimension){ start3, step3, tMax + 1 };
    return result;
}

/* dim1 / dim2 */
vector<ArrayDimension> DimensionDifference(const ArrayDimension& dim1, const ArrayDimension& dim2)
{
    ArrayDimension* intersection = IntersectDimension(dim1, dim2);
    if (!intersection) 
    {
        return {dim1, dim2};
    }
    vector<ArrayDimension> result;
    /* add the part before intersection */
    if (dim1.start < intersection->start)
    {
        result.push_back({ dim1.start, dim1.step, (intersection->start - dim1.start) / dim1.step });
    }
    /* add the parts between intersection steps */
    uint64_t start = (intersection->start - dim1.start) / dim1.step;
    uint64_t interValue = intersection->start;
    for (int64_t i = start; dim1.start + i * dim1.step <= intersection->start + intersection->step * (intersection->tripCount - 1); i++)
    {
        uint64_t centerValue = dim1.start + i * dim1.step;
        if (centerValue == interValue)
        {
            if (i - start  > 1)
            {
                result.push_back({ dim1.start + (start + 1) * dim1.step, dim1.step, i - start - 1 });
                start = i;
            }
            interValue += intersection->step;
        }
    }
    /* add the part after intersection */
    if (intersection->start + intersection->step * (intersection->tripCount - 1) < dim1.start + dim1.step * (dim1.tripCount - 1))
    {
        /* first value after intersection */
        uint64_t right_start = intersection->start + intersection->step * (intersection->tripCount - 1) + dim1.step;
        uint64_t tripCount = (dim1.start + dim1.step * dim1.tripCount - right_start) / dim1.step;
        result.push_back({right_start, dim1.step, tripCount});
    }
    delete(intersection);
    return result;
}


void FindPrivateArrays(map<string, vector<LoopGraph*>> &loopGraph, map<FuncInfo*, vector<SAPFOR::BasicBlock*>>& FullIR)
{  
    for (const auto& curr_graph_pair: loopGraph)
    {
        for (const auto& curr_loop : curr_graph_pair.second)
        {
            auto block_loop = GetBasicBlocksForLoop(curr_loop, (*FullIR.begin()).second);
            for (const auto& bb : block_loop.second) {
                ArrayAccessingIndexes def, use;
                //GetDefUseArray(bb, curr_loop, def, use);
            }
            ArrayAccessingIndexes loopDimensionsInfo;
            //GetDimensionInfo(curr_loop, loopDimensionsInfo, 0);
            //print_info(curr_loop);
        }
    }

}

void GetDimensionInfo(LoopGraph* loop, map<DIST::Array*, vector<vector<ArrayDimension>>>& loopDimensionsInfo, int level)
{
    cout << "line_num: " << loop->lineNum << endl;
    for (const auto& writeOpPairs : loop->writeOpsForLoop)
    {
        vector<vector<ArrayDimension>> arrayDimensions(writeOpPairs.first->GetDimSize());
        loopDimensionsInfo[writeOpPairs.first] = arrayDimensions;
        for (const auto& writeOp : writeOpPairs.second)
        {
            for (const auto& coeficient_pair : writeOp.coefficients)
            {
                uint64_t start, step, tripCount;
                start = loop->startVal * coeficient_pair.first.first + coeficient_pair.first.second;
                step = loop->stepVal * coeficient_pair.first.first;
                tripCount = (loop->endVal - coeficient_pair.first.second) / step;
                if (start <= loop->endVal)
                {
                    loopDimensionsInfo[writeOpPairs.first][level].push_back({start, step, tripCount});
                    cout << "level: " << level << endl;
                    cout << "start: " << start << endl;
                    cout << "step: " << step << endl;
                    cout << "trip_count: " << tripCount << endl;
                    cout << endl;
                }
                
                
            }
        }
    }
    cout << "line_num_after: " << loop->lineNumAfterLoop << endl;
    if (!loop->children.empty())
    {
        for (const auto& childLoop : loop->children)
        {
            GetDimensionInfo(childLoop, loopDimensionsInfo, level+1);
        }
    }
}
