#define PERL_NO_GET_CONTEXT	/* we want efficiency */
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

#include "ppport.h"

/* attribute 'node level' - level of node (from root) */

#include "at_node_level.h"
#include <limits.h>

/* Temporarily abuse sorted list as array of booleans */
#define at_level_assigned	level_sorted_vertex

static aglo_signed at_node_level_tree(aglo_graph graph, aglo_vertex v) {
    aglo_edge_record p;
    aglo_signed kid_level=1;

    if (graph->at_level_assigned[v]) return graph->at_level[v];

    graph->at_level_assigned[v] = true;
    graph->at_level[v] = 0;

    for (p=graph->edge_table[v];p;p=p->next)
        if (p->forward) {
            aglo_signed k = at_node_level_tree(graph, p->tail);
            if (k < kid_level) kid_level = k;
        }

    return graph->at_level[v] = kid_level - 1;
}

static void at_contract_node_level_tree(aglo_graph graph) {
    aglo_boolean change;

    do {
        aglo_unsigned i;
        aglo_edge_record p;

        change=false;
        for (i=0; i<graph->vertices; i++) {
            aglo_signed max_p_level = -INT_MAX;
            for (p=graph->edge_table[i]; p; p=p->next)
                if (!p->forward)
                    if (max_p_level < graph->at_level[p->tail])
                        max_p_level = graph->at_level[p->tail];
            if (max_p_level == -INT_MAX) continue;
            max_p_level++;
            if (max_p_level < graph->at_level[i]) {
                graph->at_level[i] = max_p_level;
                change=true;
            }
        }
    } while (change);
}

static void at_make_node_level_lists(aglo_graph graph, aglo_signed level) {
    aglo_vertex i, vcount;
    aglo_signed levels;
    aglo_vertex **level_ptr, *vertex_ptr;

    levels = -1;
    for (i=0; i<graph->vertices; i++) {
        graph->at_level[i] -= level;
        if (graph->at_level[i] < 0) 
            croak("Vertex %"UVuf" has negative node level %"IVdf, 
                  (UV) i, (IV) graph->at_level[i]);
        if (graph->at_level[i] > levels) levels = graph->at_level[i];
    }
    levels++;

    if (graph->level2nodes) {
        Safefree(graph->level2nodes);
        graph->level2nodes = NULL;
    }
    New(__LINE__, graph->level2nodes, levels+2, aglo_vertex *);
    
    level_ptr   = graph->level2nodes;
    vertex_ptr  = graph->level_sorted_vertex;
    vcount = 0;		/* doublecheck */
    for (level = 0; vcount < graph->vertices; level++) {
        aglo_vertex tvcount = vcount;

        *level_ptr++ = vertex_ptr;
        for (i=0; i<graph->vertices; i++)
            if (graph->at_level[i] == level) {
                *vertex_ptr++ = i;
                vcount++;
            }
        if (vcount == tvcount) croak("no nodes at level %"IVdf, (IV) level);
    }
    if (level != levels) croak("Expected %"IVdf" levels, found %"IVdf, 
                               (IV) levels, (IV) level);
    *level_ptr++ = vertex_ptr;
    *level_ptr++ = vertex_ptr;
    graph->nr_levels = levels;
}

static void at_calculate_node_level(aglo_graph graph) {
    aglo_vertex i;
    aglo_signed lev;
    aglo_signed min_level = INT_MAX;

    if (graph->at_level) {
        Safefree(graph->at_level);
        graph->at_level = NULL;
    }
    if (graph->level_sorted_vertex) {
        Safefree(graph->level_sorted_vertex);
        graph->level_sorted_vertex = NULL;
    }
    New(__LINE__, graph->at_level, graph->vertices, aglo_signed);
    Newz(__LINE__, graph->level_sorted_vertex, graph->vertices, aglo_vertex);

    /* initial assignement */
    for (i=0; i<graph->vertices; i++) {
        lev = at_node_level_tree(graph, i);
        if (lev < min_level) min_level = lev;
    }

    /* contraction */
    at_contract_node_level_tree(graph);
    at_make_node_level_lists(graph, min_level);
}

void at_setup_node_level(aglo_graph graph) {
    if (!graph->done) 
        croak("Won't calculate node levels on an unfinished topology");
    if (!graph->level_sequence) {
        at_calculate_node_level(graph);
        graph->level_sequence = 1;
    }
}

MODULE = Graph::Layout::Aesthetic::Dummy::NodeLevel	PACKAGE = Graph::Layout::Aesthetic::Dummy