/**
 *
 * @file plugins/CriticalPath/ParseDAG.cpp
 *
 * @copyright 2008-2024 Bordeaux INP, CNRS (LaBRI UMR 5800), Inria,
 *                      Univ. Bordeaux. All rights reserved.
 *
 * @author Camille Ordronneau
 * @author Johnny Jazeix
 * @author Mathieu Faverge
 *
 * @date 2024-07-17
 */
#include "ParseDAG.hpp"

typedef boost::graph_traits<graph_t>::vertex_iterator vertex_iterator_t;
typedef boost::graph_traits<graph_t>::in_edge_iterator in_edge_iterator_t;
typedef boost::graph_traits<graph_t>::edge_descriptor edge_descriptor_t;
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor_t;

int get_job_id(std::string task) {
    std::string strId = task.substr(5); // task_88 ---> 88
    int job_id = std::stoi(strId);
    return job_id;
}

std::pair<std::pair<double, size_t>, double> critical_path_length(graph_t &g, std::vector<double> &task_time) {
    /* Order the vertices topologically */
    std::deque<int> topo_order;
    topological_sort(g, std::front_inserter(topo_order),
                     vertex_index_map(identity_property_map()));

    std::pair<std::pair<double, size_t>, double> ret;
    std::pair<double, vertex_descriptor_t> length__last_task; // Returned value
    length__last_task.first = 0;
    length__last_task.second = 0;

    /* Computes the length of the longest path ending at the v
    where v is every vertex in the graph in topological order */
    int n = 1;
    for (std::deque<int>::iterator i = topo_order.begin(); i != topo_order.end(); ++i, ++n) {

        /* Task_time is a vector indexed with jobId,
        task_time.size() is the highest jobId parsed */
        g[*i].task_id = get_job_id(g[*i].task_name);
        g[*i].not_max_breadth = 0;
        if (g[*i].task_id >= (int)task_time.size()) {
            g[*i].execution_time = 0;
        }
        else {
            g[*i].execution_time = get_time(g[*i].task_id, task_time);
        }

        g[*i].time_elapsed = 0;

        if (in_degree(*i, g)) { // if g[*i] is not a root
            double max_time_elapsed = 0;
            std::pair<in_edge_iterator_t, in_edge_iterator_t> e = in_edges(*i, g);

            while (e.first != e.second) {
                edge_descriptor_t ed = *e.first;
                vertex_descriptor_t s = source(ed, g);
                max_time_elapsed = std::max(max_time_elapsed, g[s].time_elapsed);
                e.first++;
            }

            g[*i].time_elapsed = max_time_elapsed + g[*i].execution_time;
        }

        else {
            g[*i].time_elapsed = g[*i].execution_time;
            /* If the vertex is a root then its elapsed time is equal to its execution time */
        }

        /* Updating critical path length as it is the max of max_time_elapsed of all vertexes */
        if (length__last_task.first < g[*i].time_elapsed || (length__last_task.first == g[*i].time_elapsed && g[*i].execution_time == 0)) {
            length__last_task.second = *i;
            length__last_task.first = g[*i].time_elapsed;
        }
    }
    ret.first = std::move(length__last_task);
    ret.second = n - 1;
    return ret;
}

void dag_draw_critical_path(graph_t &g, int source_task) {

    while (in_degree(source_task, g)) {
        double max_value = 0;
        std::pair<in_edge_iterator_t, in_edge_iterator_t> e = in_edges(source_task, g);
        vertex_descriptor_t target_task = source_task;

        while (e.first != e.second) {
            edge_descriptor_t ed = *e.first;
            vertex_descriptor_t s = source(ed, g);
            double last_max = max_value;
            max_value = std::max(max_value, g[s].time_elapsed);

            if (max_value != last_max || max_value == 0) {
                source_task = s;
            }
            e.first++;
        }
        remove_edge(source_task, target_task, g);
        add_edge(source_task, target_task, Edge { "red" }, g);
    }
}

std::vector<int> critical_path(graph_t &g, int source_task) {
    std::vector<int> criticalPath; // Returned value
    while (in_degree(source_task, g)) {
        criticalPath.push_back(g[source_task].task_id);
        double max_recorded_value = 0;
        std::pair<in_edge_iterator_t, in_edge_iterator_t> e = in_edges(source_task, g);
        vertex_descriptor_t target_task = source_task;

        while (e.first != e.second) {
            edge_descriptor_t ed = *e.first;
            vertex_descriptor_t s = source(ed, g);
            double last_max = max_recorded_value;
            max_recorded_value = std::max(max_recorded_value, g[s].time_elapsed);

            if (max_recorded_value != last_max || max_recorded_value == 0) {
                source_task = s;
            }
            e.first++;
        }
        remove_edge(source_task, target_task, g);
        add_edge(source_task, target_task, Edge { "red" }, g);
    }
    criticalPath.push_back(g[source_task].task_id);
    return criticalPath;
}

std::vector<int> critical_last_tasks(graph_t &g, double max_value) {
    std::vector<int> critical_last_tasks;
    for (std::pair<vertex_iterator_t, vertex_iterator_t> vp = vertices(g);
         vp.first != vp.second; ++vp.first) {

        if (g[*vp.first].time_elapsed == max_value && out_degree(*vp.first, g) == 0) {
            critical_last_tasks.push_back(*vp.first);
        }
    }
    return critical_last_tasks;
}

std::pair<double, pair> get_number_processing(graph_t &g, double begin, double end) {
    std::pair<double, pair> ret; // Returned Value
    ret.first = 0; // ret.first is the max breadth
    ret.second.first = begin;
    ret.second.second = end;
    // ret.second is a pair representing the interval where this max breadth was achieved
    if (end <= begin) {
        return ret;
    }

    double count = 0;
    double count_right = 0;
    double count_left = 0;
    double new_begin = ret.second.first;
    double new_end = ret.second.second;

    for (std::pair<vertex_iterator_t, vertex_iterator_t> vp = vertices(g);
         vp.first != vp.second; ++vp.first) {

        double task_start = g[*vp.first].time_elapsed - g[*vp.first].execution_time;
        double task_end = g[*vp.first].time_elapsed;

        if (g[*vp.first].execution_time > 0) {

            /**** Smaller Full Overlapping ****/
            if ((begin <= task_start && task_end <= end) && (begin != task_start || task_end != end)) {
                /* If a task is strictly within (begin-end) just return because (begin - end)
                cannot possibly be the exact interval where the max breadth is obtained.
                But the max breadth can be achived in an interval within (begin - end)*/

                ret.first = -1;
                ret.second.first = 0;
                ret.second.second = 0;
                return ret;
            }

            /**** Right Overlapping ****/
            if ((begin <= task_start && task_start < end) && end < task_end) {
                /* We update the right interval which overlaps with most other tasks
                    (This interval is now (new_begin - end)) */

                if (task_start > new_begin) {
                    new_begin = task_start;
                }
                count_right++; // Incrementing right overlapping counter
            }

            /**** Left Overlapping ****/
            else if (task_start < begin && (begin < task_end && task_end <= end)) {
                /* We update the left interval which overlaps with most other tasks
                    (This interval is now (begin - new_end)*/

                if (task_end < new_end) {
                    new_end = task_end;
                }
                count_left++; // Incrementing left overlapping counter
            }

            /**** Bigger Full Overlapping ****/
            else if (task_start <= begin && end <= task_end) {
                /* If a task is overlapping and strictly bigger than (begin-end),
                    then we increase our normal count */
                g[*vp.first].not_max_breadth = 1;
                count++;
            }
        }
    }

    /* We then update ret.first with count + max(count_right, count_left),
        and we update the correspondant side of the interval */
    if (count_right > count_left) {
        ret.second.first = new_begin;
    }
    else if (count_right < count_left) {
        ret.second.second = new_end;
    }
    count += std::max(count_right, count_left);
    ret.first = count;
    return ret;
}

std::pair<double, pair> max_breadth(graph_t &g) {
    std::pair<double, pair> max_breadth; // Returned value
    std::pair<double, pair> num_process;
    max_breadth.first = 0;

    for (std::pair<vertex_iterator_t, vertex_iterator_t> vp = vertices(g);
         vp.first != vp.second; ++vp.first) {
        if (g[*vp.first].not_max_breadth == 0) {
            num_process = get_number_processing(g, g[*vp.first].time_elapsed - g[*vp.first].execution_time,
                                                g[*vp.first].time_elapsed);
            if (num_process.first > max_breadth.first) {
                max_breadth = num_process;
            }
        }
    }
    return max_breadth;
}