#include <stdio.h>
#include <string.h>

#include "nauty/nausparse.h"
#include "nauty/gtools.h"
#include "jmgraph.h"
#include "formulas.h"


void initializeGraph(jmgraph *g, int n, int maxDegree) {
    g->n = n;
    g->maxDegree = maxDegree;
    
    g->e = (int **) malloc(sizeof(int *) * g->n);
    for (int i = 0; i < g->n; i++) {
        g->e[i] = (int *) malloc(sizeof(int) * g->maxDegree);
        for (int j = 0; j < g->maxDegree; j++)
            g->e[i][j] = -1;
    }
}


void destroyGraph(jmgraph *g) {
    for (int i = 0; i < g->n; i++) {
        free(g->e[i]);
    }
    free(g->e);
    free(g);
}


jmgraph *copyJmGraph(jmgraph *g) {
    jmgraph *h = (jmgraph *) malloc(sizeof(jmgraph));
    initializeGraph(h, g->n, g->maxDegree);
    for (int v = 0; v < h->n; v++)
        for (int i = 0; i < h->maxDegree; i++)
            h->e[v][i] = g->e[v][i];
    return h;
}


jmgraph *newCubicGraph(int n) {
    jmgraph *g = (jmgraph *) malloc(sizeof(jmgraph));
    initializeGraph(g, n, 3);
    return g;
}


void printGraph(jmgraph *g) {
    char *s = writeGraph6(g);
    printf("%s\n%d\n", s, g->n);
    free(s);
    for (int i = 0; i < g->n; i++) {
        printf("%d: ", i);
        for (int j = 0; j < g->maxDegree; j++)
            printf("%d ", g->e[i][j]);
        printf("\n");
    }
}


jmgraph *readGraph6(char *s) {
    sparsegraph sg;
    SG_INIT(sg);
    int num_loops;
    stringtosparsegraph(s, &sg, &num_loops);
    jmgraph *g = newCubicGraph(sg.nv);
    for (int i = 0; i < g->n; i++) {
        for (int j = 0; j < sg.d[i]; j++)
            g->e[i][j] = sg.e[sg.v[i] + j];
        for (int j = sg.d[i]; j < 3; j++)
            g->e[i][j] = -1;
    }    
    SG_FREE(sg);
    return g;
}


jmgraph **readGraphsFromFileG6(const char *fileName, int *count) {
    FILE *in = fopen(fileName, "r");
    if (in == NULL) {
        fprintf(stderr, "Cannot open input file %s\n", fileName);
        exit(1);
    }    
    *count = 0;
    char buffer[1000000];
    while (fgets(buffer, sizeof(buffer), in) != NULL)
        *count += 1;
    rewind(in);
    jmgraph **result = (jmgraph **) malloc(sizeof(jmgraph *) * (*count));
    char *line = NULL;
    size_t len = 0;
    int i = 0;
    while (getline(&line, &len, in) != -1) {
        result[i++] = readGraph6(line); 
        free(line);
        line = NULL;
    }
    fclose(in);
    return result;
}


char *getlineBA(FILE *f) {
    char *line = NULL;
    size_t len = 0;
    while (1) {
        int r = getline(&line, &len, f);
        if (r == -1) {
            fprintf(stderr, "incorrect input file for Bratislava format\n");
            exit(1);
        }
        if (line[0] != '{')
            break;
        else {
            free(line);
            line = NULL;
        }
    }
    return line;
}


jmgraph **readGraphsFromFileBA(const char *fileName, int *count) {
    FILE *in = fopen(fileName, "r");
    if (in == NULL) {
        fprintf(stderr, "Cannot open input file %s\n", fileName);
        exit(1);
    }
    char *line = getlineBA(in);
    if (sscanf(line, "%d", count) < 1) {
        fprintf(stderr, "Incorrect input file %s: does not start with the number of graphs\n", fileName);
        exit(1);
    }
    free(line);
    
    jmgraph **result = (jmgraph **) malloc(sizeof(jmgraph *) * (*count));
    for (int i = 0; i < *count; i++) {
        free(getlineBA(in)); // ignore the graph number
        int order;
        line = getlineBA(in);
        if (sscanf(line, "%d", &order) < 1) {
            fprintf(stderr, "Incorrect input file %s: unexpected line %s\n", fileName, line);
            exit(1);
        }
        free(line);
        jmgraph *g = newCubicGraph(order);
        for (int j = 0; j < order; j++) {
            line = getlineBA(in);
            if (sscanf(line, "%d %d %d", &g->e[j][0], &g->e[j][1], &g->e[j][2]) < 3) {
                fprintf(stderr, "Incorrect input file %s: unexpected line %s\n", fileName, line);
                exit(1);
            }
            ;
            free(line);
        }
        result[i] = g;
    }
    fclose(in);
    return result;
}


sparsegraph *jmToSparse(jmgraph *g) {
    sparsegraph *sg = (sparsegraph *) malloc(sizeof(sparsegraph));
    sg->nde = 0;
    sg->nv = g->n;
    sg->vlen = g->n;
    sg->dlen = g->n;
    sg->elen = g->maxDegree * g->n;
    sg->wlen = 0;
    sg->v = (size_t *) malloc(sizeof(size_t) * sg->vlen);
    sg->d = (int *) malloc(sizeof(int) * sg->dlen);
    sg->e = (int *) malloc(sizeof(int) * sg->elen);
    sg->w = NULL;

    int edgeCounter = 0;
    for (int v = 0; v < g->n; v++) {        
        sg->d[v] = 0;
        sg->v[v] = edgeCounter;
        for (int i = 0; i < g->maxDegree; i++) {
            int u = g->e[v][i];
            if (u != -1) {
                sg->d[v]++;
                sg->e[edgeCounter++] = u;
            } else {
                break;
            }
        }
    }
    return sg;
}


char *writeGraph6(jmgraph *g) {
    sparsegraph *sg = jmToSparse(g);
    char *result = sgtog6(sg);
    SG_FREE(*sg);
    free(sg);
    result[strlen(result)-1] = '\0'; // remove the newline
    return strdup(result);
}


/* ========================= operations ============================= */

// remove all the edges adjacent to v
void isolateVertex(jmgraph *g, int v) {
    while (g->e[v][0] != -1) {
        removeEdge(g, v, 0);
    }
}


// remove edge from v to g->e[v][i]
void removeEdge(jmgraph *g, int v, int i) {
    int u = g->e[v][i];
    if (u == -1)
        return;
    g->e[v][i] = -1;
    for (int j = i; j < g->maxDegree - 1; j++) {
        g->e[v][j] = g->e[v][j+1];
    }
    g->e[v][g->maxDegree-1] = -1;
    int shift = 0;
    for (int j = 0; j < g->maxDegree; j++) {
        if (g->e[u][j] == v)
            shift = 1;
        if (j < g->maxDegree-1)
            g->e[u][j] = g->e[u][j+shift];            
        else
            g->e[u][j] = -1;
    }    
}


int getFirstFreeEdgePosition(jmgraph *g, int v) {
    int i = 0;
    while (g->e[v][i] != -1) {
        i++;
        if (i >= g->maxDegree) {
            fprintf(stderr, "maxDegree exceeded\n");
            return -1;
        }
    }
    return i;
}


// add edge from u to v
// assumes that both deg(u) and deg(v) < maxDegree
void addEdge(jmgraph *g, int u, int v) {
    g->e[u][getFirstFreeEdgePosition(g, u)] = v;
    g->e[v][getFirstFreeEdgePosition(g, v)] = u;
}


void suppressEdge(jmgraph *g, int u, int v) {
    int v1, v2, u1, u2;
    if (g->e[u][0] == v) {
        u1 = g->e[u][1];
        u2 = g->e[u][2];
    }
    if (g->e[u][1] == v) {
        u1 = g->e[u][0];
        u2 = g->e[u][2];
    }
    if (g->e[u][2] == v) {
        u1 = g->e[u][0];
        u2 = g->e[u][1];
    }

    if (g->e[v][0] == u) {
        v1 = g->e[v][1];
        v2 = g->e[v][2];
    }
    if (g->e[v][1] == u) {
        v1 = g->e[v][0];
        v2 = g->e[v][2];
    }
    if (g->e[v][2] == u) {
        v1 = g->e[v][0];
        v2 = g->e[v][1];
    }
    isolateVertex(g, u);
    isolateVertex(g, v);
    addEdge(g, u1, u2);
    addEdge(g, v1, v2);
}


/* ========================= invariants ============================= */

int deg(jmgraph *g, int v) {
    for (int i = 0; i < g->maxDegree; i++) {
        if (g->e[v][i] == -1)
            return i;
    }
    return g->maxDegree;
}


// distance from v to u in g
int distance(jmgraph *g, int v, int u) {
    int *q = malloc(sizeof(int) * g->n);
    int *distance = malloc(sizeof(int) * g->n);
    for (int i = 0; i < g->n; i++) {
        q[i] = -1;
        distance[i] = -1;
    }
    distance[v] = 0;
    q[0] = v;
    int qIndex = 0, qNext = 0;
    
    int x;
    while ((x = q[qIndex++]) != -1) {
        // continuing bfs from x
        for (int i = 0; i < g->maxDegree && g->e[x][i] != -1; i++) {
            int xx = g->e[x][i];
            if (distance[xx] == -1) {
                distance[xx] = distance[x] + 1;                
                if (xx == u)
                    return distance[xx];
                q[qNext++] = xx;
            }
        }
    }
    return -1; // unreachable
}


int edgePairDistance(jmgraph *g, edgePair *p) {
    int u = p->u, uu = g->e[p->u][p->j];
    int v = p->v, vv = g->e[p->v][p->i];
    int min = distance(g, v, u);
    int d = distance(g, v, uu);
    if (d < min) min = d;
    d = distance(g, vv, u);
    if (d < min) min = d;
    d = distance(g, vv, uu);
    if (d < min) min = d;
    return min;
}


// shortest cycle through v in g
int shortestCycle(jmgraph *g, int v) {
    int m = g->n + 2;
    for (int i = 0; i < g->maxDegree; i++) {
        if (g->e[v][i] != -1) {
            jmgraph *h = copyJmGraph(g); 
            removeEdge(h, v, i);
            int d = distance(h, v, g->e[v][i]);
            if ((d != -1) && (d + 1 < m))
                m = d + 1;
            destroyGraph(h);
        }
    }
    return (m < g->n) ? m : -1;
}


int girth(jmgraph *g) {
    int m = g->n + 1;
    for (int v = 0; v < g->n; v++) {
        int new = shortestCycle(g, v);
        if ((new != -1) && (new < m))
            m = new;
    }
    return (m < g->n) ? m : -1;
}

//added by vician to check formula
char *testFormula(jmgraph *g) {
	printf(%s, formula_sat_edge(g, g->maxDegree));
    return formula_sat_edge(g, g->maxDegree);
}

// checks for existence of a Delta-edge-colouring of a graph
int isColourable(jmgraph *g) {

    char *formula = formula_sat_edge(g, g->maxDegree);
    char command[1000000];
    //printf("formula: %s\n",formula); //TODO delete
    //printf("#######################\n");
    //printf("command %s\n",command); //TODO delete
//  sprintf(command, "echo \"%s\" | ./plingeling > /dev/null", formula);
    //sprintf(command, "echo \"%s\" | /home/vicko/Desktop/lingeling-bbc-9230380-160707-druplig-009/lingeling/plingeling > /dev/null", formula);
    sprintf(command, "echo \"%s\" | ../lingeling-bbc-9230380-160707-druplig-009/lingeling/plingeling > /dev/null", formula);
    
    free(formula);

    int result = system(command);
    if (WIFEXITED(result)) {
        //printf("%d\n",result); //TODO delete
        //printf("false ret val: %d\n",WEXITSTATUS(result) == 11); //TODO delete
        //printf("ret val: %d\n",WEXITSTATUS(result) == 10); //TODO delete
        return WEXITSTATUS(result) == 10;
    } else {
        printf("something went wrong\n");
        exit(1);
    }
}


// assumes the input is a snark
int isIrreducible(jmgraph *g) {    
    for (int u = 0; u < g->n; u++) {
        printf("removing %3d xxx\n", u);
        for (int v = u+1; v < g->n; v++) {
            jmgraph *h = copyJmGraph(g);
            isolateVertex(h, u);
            isolateVertex(h, v);
            int r = !isColourable(h);
            destroyGraph(h);
            if (r)
                return 0;            
        }
    }
    return 1;
}


int isStrongSnark(jmgraph *g) {
    if (isColourable(g))
        return 0;
    for (int u = 0; u < g->n; u++) {
        printf("removing %3d xxx\n", u);
        for (int i = 0; i < 3; i++) {
            int v = g->e[u][i];
            if (v < u)
                continue;
            jmgraph *h = copyJmGraph(g);
            isolateVertex(h, u);
            isolateVertex(h, v);
            int r = isColourable(h);
            destroyGraph(h);
            if (r) {
                printf("Pair %d %d is non-removable\n", u, v);
                return 0;            
            }
        }
    }
    return 1;
}


int isRemovableEdgePair(jmgraph *g, edgePair *p) {
    jmgraph *h = copyJmGraph(g);
    removeEdge(h, p->v, p->i);
    removeEdge(h, p->u, p->j);
    int result = !isColourable(h);
    destroyGraph(h);
    return result;
}


int isRemovableVertexPair(jmgraph *g, int u, int v) {
    jmgraph *h = copyJmGraph(g);
    isolateVertex(h, u);
    isolateVertex(h, v);
    int r = !isColourable(h);
    destroyGraph(h);
    return r;
}

