//
// Created by Stephane on 24/03/2020.
//

#include <assert.h>

#include "components.h"
#include "graph.h"
#include "heap.h"
#include "lists.h"
#include "sets.h"
#include "utils.h"


int *iComp = NULL; // for each vertex, the number of its component
int *compSizes;
int *compNbEdges;
int *compFirsts;
int * tableSortVComp;

//int *firstOfComp; // the first vertex of the component, useful when the component size is 1
int sizeCompMax;

int *queue = NULL, *first, *last;


void allocSearchConnectedComponents(Graph g) {
    iComp = malloc(g->n*sizeof(int));
    compSizes = malloc(g->n*sizeof(int));
    compNbEdges = malloc(g->n*sizeof(int));
    compFirsts = malloc(g->n*sizeof(int));
    tableSortVComp = malloc(g->n*sizeof(int));
    //firstOfComp = malloc(g->n*sizeof(int));
    queue = malloc(g->n*sizeof(int));
}




// Search connected components of the subgraph delimited by V
// verif is just used to verify for each vertex that it is in the current set (useless for greedy search)
int searchConnectedComponents(SET V, int S[], int n, Graph g) {

    int nbComp = 0;
    int nbNodes = 0;
    sizeCompMax = 0;

    for (int i = 0; i < n; i++)
        iComp[S[i]] = NONE;

    // Call BFS exploration from each node of S[]
    for (int i = 0; i < n; i++) {
        if (iComp[S[i]] == NONE) {
            iComp[S[i]] = nbComp;
            compSizes[nbComp] = 1;
            //firstOfComp[nbComp] = S[i];
            first = last = queue;
            *last++ = S[i];
            compExploreBFS(nbComp, V, S, n, g, 1);
            if (compSizes[nbComp] > sizeCompMax) sizeCompMax = compSizes[nbComp];
            nbNodes += compSizes[nbComp];
            nbComp++;
            if (nbNodes == n) break;
        }
    }
    return nbComp;
}



void compExploreBFS(int num, SET V, int S[], int n, Graph g, int verif) {
    while (last != first) {
        int *p = g->lists[*first];
        first = first+1;
        if (first == queue+g->n) first = queue;
        while (*p != NONE) {
            if ( ! verif || (isInSet(*p, V, S, n))) { // isInSet is OK since S[] is sorted
                if (iComp[*p] == NONE) {
                    iComp[*p] = num;
                    compSizes[num]++;
                    *last++ = *p;
                    if (last == queue + g->n) last = queue;
                }
            }
            p ++;
        }
    }
}



// Special version for separators: the neighbors of each vertex are ordered so as that those in S
// occur first. Search components for the subgraph corresponding to the heap (H->ind[] is NONE if not in the heap)
void compExploreBFSSubgraph(int num, Heap H, int nbN[], Graph g);

int searchConnectedComponentsInHeap(Heap H, int nbNiS[], Graph g) {

    int nbComp = 0;
    int nbNodes = 0;
    sizeCompMax = 0;

    for (int i = 0; i < H->n; i++)
        iComp[H->val[i]] = NONE;

    for (int i = 0; i < H->n; i++) {

        if (iComp[H->val[i]] == NONE) {

            iComp[H->val[i]] = nbComp;
            compSizes[nbComp] = 1;
            compNbEdges[nbComp] = 0;
            first = last = queue;
            *last++ = H->val[i];

            compExploreBFSSubgraph(nbComp, H, nbNiS, g);

            compNbEdges[nbComp] = compNbEdges[nbComp]/2;
            if (compSizes[nbComp] > sizeCompMax) sizeCompMax = compSizes[nbComp];
            nbNodes += compSizes[nbComp];
            nbComp ++;
            if (nbNodes == H->n) break;
        }
    }
    return nbComp;
}

void compExploreBFSSubgraph(int num, Heap H, int nbN[], Graph g) {

    while (last != first) {
        int *p = g->lists[*first];
        int *pp = p+nbN[*first];

        first = first+1;
        if (first == queue+g->n) first = queue;

        while (p != pp) {
            if (H->ind[*p] != NONE) {
                compNbEdges[num] ++;
                if (iComp[*p] == NONE) {
                    iComp[*p] = num;
                    compSizes[num] ++;
                    *last++ = *p;
                    if (last == queue + g->n) last = queue;
                }
            }
            p++;
        }
    }
}






// Special version for greedy decomposition: the exploration can be stopped
// once we know that the neighbors of the last removed vertex are all reachable

#define UNVISITED_NEIGHBOR -2
#define IGNORED_NODE -3
int nbNeighborsToVisit;

void compExploreBFSAF(int u, int num, SET V, Heap heap, Graph g) {
    while (last != first) {
        int *p = g->lists[*first];
        first = first+1;
        if (first == queue+g->n) first = queue;
        while (*p != NONE) {
            if (heap->ind[*p] != NONE) { // (isInSet(*p, V, S, n)) should be false here (S[] not ordered)
                if ((iComp[*p] == NONE) || (iComp[*p] == UNVISITED_NEIGHBOR)) {
                    if (iComp[*p] == UNVISITED_NEIGHBOR) {
                        if ((-- nbNeighborsToVisit == 0) && (num == 0)) // first component, all neighbors have been discovered
                            return;
                    }
                    iComp[*p] = num;
                    compSizes[num]++;
                    *last++ = *p;
                    if (last == queue + g->n) last = queue;
                }
            }
            p ++;
        }
    }
}


int searchConnectedComponentsGreedy(SET V, Heap heap, Graph g, int removedVertex) {
    int nbComp = 0;
    int nbNodes = 0;
    sizeCompMax = 0;
    nbNeighborsToVisit = 0;

    for (int i = 0; i < heap->n; i++)
        iComp[heap->val[i]] = NONE;

    // Mark neighbors which are in the heap
    for (int *p = g->lists[removedVertex]; *p != NONE; p ++) {
        if (conHeap->ind[*p] != NONE) { // (isInSet(*p, V, S, n)) not good (suppose vertices are ordered in S[]
            iComp[*p] = UNVISITED_NEIGHBOR;
            nbNeighborsToVisit++;
        }
        else iComp[*p] = IGNORED_NODE;
    }

    // NORMAL !! if (nbNeighborsToVisit != nbN4Con[removedVertex]) {printf("%d %d\n", nbNeighborsToVisit, nbN4Con[removedVertex]); exit(0);}

    for (int *p = g->lists[removedVertex]; *p != NONE; p ++) {
        if (iComp[*p] == UNVISITED_NEIGHBOR) {
            iComp[*p] = nbComp;
            compSizes[nbComp] = 1;
            nbNeighborsToVisit --;
            if ((nbNeighborsToVisit == 0) && (nbComp == 0)) return 1; // a unique neighbor

            first = last = queue;
            *last++ = *p;
            compExploreBFSAF(*p, nbComp, V, heap, g);

            if ((nbNeighborsToVisit == 0) && (nbComp == 0)) return 1;
            if (compSizes[nbComp] > sizeCompMax) sizeCompMax = compSizes[nbComp];
            nbNodes += compSizes[nbComp];
            nbComp++;
            if (nbNodes == heap->n) break;
        }
    }
    return nbComp;
}




int nbCCE = 0;

void compExplore(int u, int num, SET V, int S[], int n, Graph g, int depth) {
    LIST q = g->adj[u];
    int nbNeighbors = 0;
    nbCCE ++;

    //if (nbCCE >= 2011872) printf("depth=%d n=%d  u=%d size=%d\n", depth, n, u, compSizes[num]);

    while (q != NULL) {
        nbNeighbors ++;
        if (nbNeighbors > g->nadj[u]) {printf("too many neighbors !\n"); exit(0);}
        if ((isInSet(q->val, V, S, n)) && (iComp[q->val] == NONE)) { //((IN(q->val, V)) && (iComp[q->val] == NONE)) {
            iComp[q->val] = num;
            compSizes[num] ++;
            compExplore(q->val, num, V, S, n, g, depth+1);
        }
        q = q->suiv;
    }
}



//
// utils
//


// the vertices in S[] are ordered by their component number. sizes[] are initialized.
// Uses iComp[] and compSizes[] returned by searchConnectedComponentsGreedy() or
// searchConnectedComponents()
void sortListByComponent(int S[], int n, int nbComp, int sizes[]) {

    for (int i = 0; i < n; i ++) {
        tableSortVComp[i] = S[i];
    }
    compFirsts[0] = 0;
    sizes[0] = compSizes[0];
    for (int i = 1; i < nbComp; i ++) {
        sizes[i] = compSizes[i];
        compFirsts[i] = compFirsts[i - 1] + compSizes[i - 1];
    }

    for (int *p = tableSortVComp; p < tableSortVComp+n; p ++) {
        int pos = compFirsts[iComp[*p]];
        compFirsts[iComp[*p]] ++;
        S[pos] = *p;
    }
}