/*
 * Copyright © 2013-2014 University of Wisconsin-La Crosse.
 *                         All rights reserved.
 * Copyright © 2016-2017 Inria.  All rights reserved.
 *
 * $COPYRIGHT$
 *
 * Additional copyrights may follow
 * See COPYING in top-level directory.
 *
 * $HEADER$
 */

#define _GNU_SOURCE	   /* See feature_test_macros(7) */
#include <stdio.h>
#include <sys/types.h>
#include <dirent.h>
#include <libgen.h>

#include <private/netloc.h>

static char *line_get_next_field(char **string);
static void read_partition_list(char *list, UT_array *array);
static int edges_sort_by_dest(netloc_edge_t *a, netloc_edge_t *b);
static int find_reverse_edges(netloc_topology_t *topology);
static int find_similar_nodes(netloc_topology_t *topology);
static int netloc_node_get_virtual_id(char *id);
static int edge_merge_into(netloc_edge_t *dest, netloc_edge_t *src, int keep);

netloc_topology_t *netloc_topology_construct(char *path)
{
    int ret;
    char *line = NULL;
    size_t linesize = 0;

    netloc_topology_t *topology = NULL;

    FILE *input = fopen(path, "r");

    if (!input ) {
        fprintf(stderr, "Cannot open topology file %s\n", path);
        perror("fopen");
        exit(-1);
    }

    int version;
    if (fscanf(input , "%d\n,", &version) != 1) {
        fprintf(stderr, "Cannot read the version number in %s\n", path);
        perror("fscanf");
        fclose(input);
        return NULL;
    } else if (version != NETLOCFILE_VERSION) {
        fprintf(stderr, "Incorrect version number, "
                "please generate your input file again\n");
        fclose(input);
        return NULL;
    }

    char *subnet;
    if (netloc_line_get(&line, &linesize, input) == -1) {
        fprintf(stderr, "Cannot read the subnet in %s\n", path);
        perror("fscanf");
        free(line);
        fclose(input);
        return NULL;
    } else {
        subnet = strdup(line);
    }

    char *hwlocpath;
    if (netloc_line_get(&line, &linesize, input) == -1) {
        fprintf(stderr, "Cannot read hwloc path in %s\n", path);
        perror("fscanf");
        free(subnet);
        fclose(input);
        return NULL;
    } else if (!strlen(line)) {
        hwlocpath = NULL;
    } else {
        hwlocpath = strdup(line);
    }

    if (hwlocpath) {
        DIR *hwlocdir;
        char *realhwlocpath;
        if (hwlocpath[0] != '/') {
            char *path_tmp = strdup(path);
            asprintf(&realhwlocpath, "%s/%s", dirname(path_tmp), hwlocpath);
            free(path_tmp);
        } else {
            realhwlocpath = strdup(hwlocpath);
        }
        if (!(hwlocdir = opendir(realhwlocpath))) {
            fprintf(stderr, "Couldn't open hwloc directory: \"%s\"\n", realhwlocpath);
            perror("opendir");
            free(subnet);
            free(realhwlocpath);
            fclose(input);
            return NULL;
        } else {
            closedir(hwlocdir);
            free(realhwlocpath);
        }
    }

    int num_nodes;
    if (fscanf(input , "%d\n", &num_nodes) != 1) {
        fprintf(stderr, "Cannot read the number of nodes in %s\n", path);
        perror("fscanf");
        free(subnet);
        fclose(input);
        return NULL;
    }

    if (num_nodes <= 0) {
        fprintf(stderr, "Oups: incorrect number of nodes (%d) in %s\n",
                num_nodes, path);
        free(subnet);
        fclose(input);
        return NULL;
    }

    /*
     * Allocate Memory
     */
    topology = (netloc_topology_t *)malloc(sizeof(netloc_topology_t) * 1);
    if( NULL == topology ) {
        free(subnet);
        fclose(input);
        return NULL;
    }

    /*
     * Initialize the structure
     */
    topology->topopath = path;
    topology->hwlocpath = hwlocpath;
    topology->subnet_id = subnet;
    topology->nodes          = NULL;
    topology->physical_links = NULL;
    topology->type           = NETLOC_TOPOLOGY_TYPE_INVALID ;
    topology->nodesByHostname = NULL;
    topology->hwloc_topos = NULL;
    utarray_new(topology->partitions, &ut_str_icd);
    utarray_new(topology->topos, &ut_str_icd);

    /* Read nodes from file */
    for (int n = 0; n < num_nodes; n++) {
        netloc_node_t *node = netloc_node_construct();
        netloc_line_get(&line, &linesize, input);
        char *remain_line = line;

        strncpy(node->physical_id, line_get_next_field(&remain_line), 20);
            /* Should be shorter than 20 */
        node->physical_id[19] = '\0'; /* If a problem occurs */
        node->logical_id = atoi(line_get_next_field(&remain_line));
        node->type = atoi(line_get_next_field(&remain_line));
        read_partition_list(line_get_next_field(&remain_line), node->partitions);
        node->description = strdup(line_get_next_field(&remain_line));
        node->hostname = strdup(line_get_next_field(&remain_line));

        HASH_ADD_STR(topology->nodes, physical_id, node);
        if (strlen(node->hostname) > 0) {
            HASH_ADD_KEYPTR(hh2, topology->nodesByHostname, node->hostname,
                    strlen(node->hostname), node);
        }
    }

    /* Read edges from file */
    for (int n = 0; n < num_nodes; n++) {
        char *field;
        netloc_node_t *node;

        netloc_line_get(&line, &linesize, input);
        char *remain_line = line;

        field = line_get_next_field(&remain_line);
        if (strlen(field) > 19)
            field[19] = '\0';
        HASH_FIND_STR(topology->nodes, field, node);

        if (!node) {
            fprintf(stderr, "Node not found: %s\n", field);
            utarray_free(topology->partitions);
            utarray_free(topology->topos);
            return NULL;
        }

        while ((field = line_get_next_field(&remain_line))) {
            /* There is an edge */
            netloc_edge_t *edge = netloc_edge_construct();

            HASH_FIND_STR(topology->nodes, field, edge->dest);
            edge->total_gbits = strtof(line_get_next_field(&remain_line), NULL);
            read_partition_list(line_get_next_field(&remain_line), edge->partitions);

            edge->node = node;
            HASH_ADD_PTR(node->edges, dest, edge);

            /* Read links */
            int num_links = atoi(line_get_next_field(&remain_line));
            assert(num_links >= 0);
            utarray_reserve(edge->physical_links, (unsigned int)num_links);
            utarray_reserve(node->physical_links, (unsigned int)num_links);
            for (int i = 0; i < num_links; i++) {
                netloc_physical_link_t *link;
                link =  netloc_physical_link_construct();

                link->id = atoi(line_get_next_field(&remain_line));

                link->src = node;
                link->dest = edge->dest;

                link->ports[0] = atoi(line_get_next_field(&remain_line));
                link->ports[1] = atoi(line_get_next_field(&remain_line));

                link->width = strdup(line_get_next_field(&remain_line));
                link->speed = strdup(line_get_next_field(&remain_line));
                link->gbits = strtof(line_get_next_field(&remain_line), NULL);
                link->description = strdup(line_get_next_field(&remain_line));
                link->other_way_id = atoi(line_get_next_field(&remain_line));

                read_partition_list(line_get_next_field(&remain_line),
                        link->partitions);

                HASH_ADD_INT(topology->physical_links, id, link);

                utarray_push_back(node->physical_links, &link);
                utarray_push_back(edge->physical_links, &link);
            }

        }
        HASH_SRT(hh, node->edges, edges_sort_by_dest);
    }

    /* Read partitions from file */
    {
        netloc_line_get(&line, &linesize, input);
        char *remain_line = line;
        char *field;

        while ((field = line_get_next_field(&remain_line))) {
            utarray_push_back(topology->partitions, &field);
        }
    }

    /* Read paths */
    while (netloc_line_get(&line, &linesize, input) != -1) {
        netloc_node_t *node;
        netloc_path_t *path;
        char *field;

        char *remain_line = line;
        char *src_id = line_get_next_field(&remain_line);
        char *dest_id = line_get_next_field(&remain_line);

        HASH_FIND_STR(topology->nodes, src_id, node);

        path = netloc_path_construct();
        strncpy(path->dest_id, dest_id, 20); /* Should be shorter than 20 */
        path->dest_id[19] = '\0'; /* If a problem occurs */

        while ((field = line_get_next_field(&remain_line))) {
            int link_id = atoi(field);
            netloc_physical_link_t *link;

            HASH_FIND_INT(topology->physical_links, &link_id, link);
            utarray_push_back(path->links, &link);
        }

        HASH_ADD_STR(node->paths, dest_id, path);
    }

    fclose(input);
    free(line);

    if (find_reverse_edges(topology) != NETLOC_SUCCESS) {
        netloc_topology_destruct(topology);
        return NULL;
    }

    ret = find_similar_nodes(topology);
    if (ret != NETLOC_SUCCESS) {
        netloc_topology_destruct(topology);
        return NULL;
    }

    return topology;
}

int netloc_topology_destruct(netloc_topology_t *topology)
{
    /*
     * Sanity Check
     */
    if( NULL == topology ) {
        fprintf(stderr, "Error: Detaching from a NULL pointer\n");
        return NETLOC_ERROR;
    }

    free(topology->topopath);
    free(topology->hwlocpath);
    free(topology->subnet_id);

    /* Nodes */
    netloc_node_t *node, *node_tmp;
    HASH_ITER(hh, topology->nodes, node, node_tmp) {
        HASH_DELETE(hh, topology->nodes, node);
    }

    netloc_topology_iter_nodes(topology, node, node_tmp) {
        HASH_DELETE(hh, topology->nodes, node);
        netloc_node_destruct(node);
    }

    /** Partition List */
    utarray_free(topology->partitions);

    /** Physical links */
    netloc_physical_link_t *link, *link_tmp;
    HASH_ITER(hh, topology->physical_links, link, link_tmp) {
        HASH_DEL(topology->physical_links, link);
        netloc_physical_link_destruct(link);
    }

    /** Hwloc topology List */
    for (unsigned int t = 0; t < utarray_len(topology->topos); t++) {
        if (topology->hwloc_topos[t])
            hwloc_topology_destroy(topology->hwloc_topos[t]);
    }
    free(topology->hwloc_topos);

    /** Hwloc topology name List */
    utarray_free(topology->topos);

    free(topology);

    return NETLOC_SUCCESS;
}

int netloc_topology_find_partition_idx(netloc_topology_t *topology, char *partition_name)
{
    if (!partition_name)
        return -1;

    /* Find the selected partition in the topology */
    unsigned int p = 0;
    int found = 0;
    while (p < utarray_len(topology->partitions)) {
        char *current_name = *(char **)utarray_eltptr(topology->partitions, p);

        if (!strcmp(current_name, partition_name)) {
            found = 1;
            break;
        }
        p++;
    }

    if (!found)
        return -2;

    assert(p <= INT_MAX);

    return (int)p;
}

static char *line_get_next_field(char **string)
{
    return netloc_line_get_next_token(string, ',');
}

static void read_partition_list(char *list, UT_array *array)
{
    char *partition;
    if (!strlen(list))
        return;
    while ((partition = netloc_line_get_next_token(&list, ':'))) {
        int partition_num = atoi(partition);
        utarray_push_back(array, &partition_num);
    }
}

static int edges_sort_by_dest(netloc_edge_t *a, netloc_edge_t *b)
{
    return strcmp(a->dest->physical_id, b->dest->physical_id);
}

static int find_reverse_edges(netloc_topology_t *topology)
{
    netloc_node_t *node, *node_tmp;
    HASH_ITER(hh, topology->nodes, node, node_tmp) {
        netloc_edge_t *edge, *edge_tmp;
        netloc_node_iter_edges(node, edge, edge_tmp) {
            netloc_node_t *dest = edge->dest;
            if (dest > node) {
                netloc_edge_t *reverse_edge;
                HASH_FIND_PTR(dest->edges, &node, reverse_edge);
                if (reverse_edge == NULL) {
                    return NETLOC_ERROR;
                }
                edge->other_way = reverse_edge;
                reverse_edge->other_way = edge;
            }
        }
    }
    return NETLOC_SUCCESS;
}

static int find_similar_nodes(netloc_topology_t * topology)
{
    int ret;

    /* Build edge lists by node */
    int num_nodes = HASH_COUNT(topology->nodes);
    netloc_node_t **nodes = (netloc_node_t **)malloc(num_nodes*sizeof(netloc_node_t *));
    netloc_node_t ***edgedest_by_node = (netloc_node_t ***)malloc(num_nodes*sizeof(netloc_node_t **));
    int *num_edges_by_node = (int *)malloc(num_nodes*sizeof(int));
    netloc_node_t *node, *node_tmp;
    int idx = -1;
    netloc_topology_iter_nodes(topology, node, node_tmp) {
        idx++;
        if (netloc_node_is_host(node)) {
            nodes[idx] = NULL;
            edgedest_by_node[idx] = NULL;
            continue;
        }
        int num_edges = HASH_COUNT(node->edges);
        nodes[idx] = node;
        num_edges_by_node[idx] = num_edges;
        edgedest_by_node[idx] = (netloc_node_t **)malloc(num_edges*sizeof(netloc_node_t *));

        netloc_edge_t *edge, *edge_tmp;
        int edge_idx = 0;
        netloc_node_iter_edges(node, edge, edge_tmp) {
            edgedest_by_node[idx][edge_idx] = edge->dest;
            edge_idx++;
        }
    }

    /* We compare the edge lists to find similar nodes */
    UT_array *similar_nodes;
    utarray_new(similar_nodes, &ut_ptr_icd);
    for (int idx1 = 0; idx1 < num_nodes; idx1++) {
        netloc_node_t *node1 = nodes[idx1];
        netloc_node_t *virtual_node = NULL;
        netloc_edge_t *first_virtual_edge = NULL;
        if (!node1)
            continue;
        for (int idx2 = idx1+1; idx2 < num_nodes; idx2++) {
            netloc_node_t *node2 = nodes[idx2];
            if (!node2)
                continue;
            if (num_edges_by_node[idx2] != num_edges_by_node[idx1])
                continue;
            if (idx2 == idx1)
                continue;

            int equal = 1;
            for (int i = 0; i < num_edges_by_node[idx1]; i++) {
                if (edgedest_by_node[idx2][i] != edgedest_by_node[idx1][i]) {
                    equal = 0;
                    break;
                }
            }

            /* If we have similar nodes */
            if (equal) {
                /* We create a new virtual node to contain all of them */
                if (!virtual_node) {
                    virtual_node = netloc_node_construct();
                    netloc_node_get_virtual_id(virtual_node->physical_id);

                    virtual_node->type = node1->type;
                    utarray_concat(virtual_node->physical_links, node1->physical_links);
                    virtual_node->description = strdup(virtual_node->physical_id);

                    utarray_push_back(virtual_node->subnodes, &node1);
                    utarray_concat(virtual_node->partitions, node1->partitions);

                    // TODO paths

                    /* Set edges */
                    netloc_edge_t *edge1, *edge_tmp1;
                    netloc_node_iter_edges(node1, edge1, edge_tmp1) {
                        netloc_edge_t *virtual_edge = netloc_edge_construct();
                        if (!first_virtual_edge)
                            first_virtual_edge = virtual_edge;
                        virtual_edge->node = virtual_node;
                        virtual_edge->dest = edge1->dest;
                        ret = edge_merge_into(virtual_edge, edge1, 0);
                        if (ret != NETLOC_SUCCESS) {
                            netloc_edge_destruct(virtual_edge);
                            goto ERROR;
                        }
                        HASH_ADD_PTR(virtual_node->edges, dest, virtual_edge);

                        /* Change the reverse edge of the neighbours (reverse nodes) */
                        netloc_node_t *reverse_node = edge1->dest;
                        netloc_edge_t *reverse_edge = edge1->other_way;

                        netloc_edge_t *reverse_virtual_edge =
                            netloc_edge_construct();
                        reverse_virtual_edge->dest = virtual_node;
                        reverse_virtual_edge->node = reverse_node;
                        reverse_virtual_edge->other_way = virtual_edge;
                        virtual_edge->other_way = reverse_virtual_edge;
                        HASH_ADD_PTR(reverse_node->edges, dest, reverse_virtual_edge);
                        ret = edge_merge_into(reverse_virtual_edge, reverse_edge, 1);
                        if (ret != NETLOC_SUCCESS) {
                            goto ERROR;
                        }
                        HASH_DEL(reverse_node->edges, reverse_edge);
                    }

                    /* We remove the node from the list of nodes */
                    HASH_DEL(topology->nodes, node1);
                    HASH_ADD_STR(topology->nodes, physical_id, virtual_node);
                    printf("First node found: %s (%s)\n", node1->description, node1->physical_id);
                }

                utarray_concat(virtual_node->physical_links, node2->physical_links);
                utarray_push_back(virtual_node->subnodes, &node2);
                utarray_concat(virtual_node->partitions, node2->partitions);

                /* Set edges */
                netloc_edge_t *edge2, *edge_tmp2;
                netloc_edge_t *virtual_edge = first_virtual_edge;
                netloc_node_iter_edges(node2, edge2, edge_tmp2) {
                    /* Merge the edges from the physical node into the virtual node */
                    ret = edge_merge_into(virtual_edge, edge2, 0);
                    if (ret != NETLOC_SUCCESS) {
                        goto ERROR;
                    }

                    /* Change the reverse edge of the neighbours (reverse nodes) */
                    netloc_node_t *reverse_node = edge2->dest;
                    netloc_edge_t *reverse_edge = edge2->other_way;

                    netloc_edge_t *reverse_virtual_edge;
                    HASH_FIND_PTR(reverse_node->edges, &virtual_node,
                            reverse_virtual_edge);
                    ret = edge_merge_into(reverse_virtual_edge, reverse_edge, 1);
                    if (ret != NETLOC_SUCCESS) {
                        goto ERROR;
                    }
                    HASH_DEL(reverse_node->edges, reverse_edge);

                    /* Get the next edge */
                    virtual_edge = virtual_edge->hh.next;
                }

                /* We remove the node from the list of nodes */
                HASH_DEL(topology->nodes, node2);
                printf("\t node found: %s (%s)\n", node2->description, node2->physical_id);

                nodes[idx2] = NULL;
            }
        }
        utarray_clear(similar_nodes);
    }

    ret = NETLOC_SUCCESS;
ERROR:
    free(nodes);

    for (int idx = 0; idx < num_nodes; idx++) {
        if (edgedest_by_node[idx])
            free(edgedest_by_node[idx]);
    }
    free(edgedest_by_node);
    free(num_edges_by_node);
    free(similar_nodes);
    return ret;
}

static int netloc_node_get_virtual_id(char *id)
{
    static int virtual_id = 0;
    sprintf(id, "virtual%d", virtual_id++);
    return 0;
}

static int edge_merge_into(netloc_edge_t *dest, netloc_edge_t *src, int keep)
{
    if (!dest || !src) {
        return NETLOC_ERROR;
    }

    utarray_concat(dest->physical_links, src->physical_links);
    dest->total_gbits += src->total_gbits;
    utarray_concat(dest->partitions, src->partitions);
    /* it will keep the duplicated edges */
    if (keep)
        utarray_push_back(dest->subnode_edges, &src);

    return NETLOC_SUCCESS;
}