/*
 *  main.cpp
 *  SemestralniProjekt PAR
 *
 *  Created by Martin Mates and Frantisek Szabo on 20.10.10.
 *
 */

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

#define _DEBUG_ true
#define MAX_FILE_LINE 200 // Maximalni delka radky vstupniho souboru
#define MAX_NODES 100 // Maximalni pocet uzlu grafu
#define STACK_SIZE 100 // Delka zasobniku

int loadGraph(FILE *fr, int **graph, int *numberOfNodes);
int rateGraph(FILE *fr, char *path);
void push(char **stack, char *value, int *index);
char* pop(char **stack, int *stack_index);
char* lookAtTop(char **stack, int stack_index);
int expand(char **stack, int *stack_index, int numberOfNodes);
int edgeCut(char *verticies, int numberOfNodes, int **graph);
void printStack(char **stack, int *stack);


int main (int argc, char **argv) {
    FILE *fr; // Soubor s grafem pro cteni
    int numberOfNodes; // Pocet uzlu grafu
    int minCut = 1000000; // Minimalni rez
    char* resultSets; // Vysledna mnozina bodu

    int **graph = new int* [MAX_NODES]; // Matice s grafem
    for (int i = 0; i < MAX_NODES; i++) {
        graph[i] = new int[MAX_NODES];
    }

    if (_DEBUG_ == false) {
        // Zpracovani vstupnich parametru -----------------------------
        if (argc > 1) {
            if ((fr = fopen(argv[1], "r")) == NULL) { // Otevreni souboru s grafem
                printf("Soubor %s se nepodarilo otevrit.\n", argv[1]);
                return 0;
            }
            if (argc > 2) {
                if (strcmp(argv[2], "-c") == 0) {
                    rateGraph(fr, argv[1]);
                    fclose(fr);
                    return(0);
                } else {
                    printf("Druhy parametr je chybny. \n");
                    fclose(fr);
                    return 0;
                }
            }
        } else {
            printf("Nebyly zadany zadne parametry. \n");
            printf("Help: \n");
            printf("   Prvni parametr: [filename] Cesta k .txt souboru s grafem [povinny] \n");
            printf("   Druhy parametr: [-c] Ohodnoti neohodnoceny graf a ulozi ho do souboru [volitelny] \n");
            return 0;
        }
        // -----------------------------------------------------------
    } else {
        fr = fopen("/Volumes/Macintosh HDD 2/graf50_40_rated.txt", "r");
    }


    loadGraph(fr, graph, &numberOfNodes); // Nacteni grafu ze souboru

    // Print graph
    for (int i = 0; i < numberOfNodes; i++) {
        for (int j = 0; j < numberOfNodes; j++) {
            printf("%i ", graph[i][j]);
        }
        printf("\n");
    }

    // Deklarace zasobniku
    char **stack = new char* [STACK_SIZE];
    for (int i = 0; i < STACK_SIZE; i++) {
        stack[i] = new char[numberOfNodes + 1];
    }
    int stack_index = 0;

    // Alokovani resultSetu
    resultSets = (char *) malloc(numberOfNodes + 1);


    char *initString;
    initString  = (char *) malloc(numberOfNodes + 1);
    for (int i = 0; i < numberOfNodes; i++) {
        initString[i] = 'x';
    }
    initString[numberOfNodes] = '\0';

    push(stack, initString, &stack_index);
    printStack(stack, &stack_index);
    while (stack_index > 0) {

        if (_DEBUG_) {
            printf("MinCut = %d \n", minCut);
            printf("Stack index: %d\n", stack_index);
        }

        // Vypocita se edgeCut z posledni hodnoty zasobiku
        int localEdgeCut = edgeCut(lookAtTop(stack, stack_index - 1), numberOfNodes, graph);

        // Pokud je edgeCut 0, expandujeme. Nejspis jsou sama x nebo jsou vsechny body v 1 mnozine
        if (localEdgeCut == 0) {
            // Expandujeme
            expand(stack, &stack_index, numberOfNodes);
        } else {
            // Pokud je edgeCut mensi nez globalni minCut pokracujeme. Jinak zahazujeme
            if (localEdgeCut < minCut) {
                // Expandujeme
                if (expand(stack, &stack_index, numberOfNodes) == 0) {
                    // Pokud uz nejde expandovat jsme ve spodni vetvy a mame novy min rez
                    minCut = localEdgeCut;
                    strcpy(resultSets, lookAtTop(stack, stack_index));
                }
            } else {
                if (_DEBUG_) {
                    printf("ZAHAZUJI: %s\n", lookAtTop(stack, stack_index - 1));
                }
                // Zahazujeme neperspektivni vetev
                pop(stack, &stack_index);
            }
        }

        printStack(stack, &stack_index);

        printf("----------------------------------------------------------\n");
    }



    fclose(fr);

    printf("MINIMAL CUT IS: %d\n", minCut);
    printf("RESULT SESTS: %s\n", resultSets);
}


void printStack(char **stack, int *stack_index) {
    for (int i = 0; i < *stack_index; i++) {
        printf("[%s],", stack[i]);
    }
    printf("\n");
}

void push(char **stack, char *str, int *stack_index) {
    strcpy(stack[*stack_index], str);
    *stack_index = *stack_index + 1;
    if (*stack_index > STACK_SIZE) {
        printf("[error] Stack overflow.\n");
    }
}

char* pop(char **stack, int *stack_index) {
    *stack_index = *stack_index - 1;
    if (*stack_index > -1) {
        return stack[*stack_index];
    } else {
        return 0;
    }
}

char* lookAtTop(char **stack, int stack_index) {
    if (stack_index > -1) {
        return stack[stack_index];
    } else {
        return 0;
    }
}

int expand(char **stack, int *stack_index, int numberOfNodes) {

    char *str;
    str  = (char *) malloc(numberOfNodes + 1);

    int indexToExpand = -1;
    strcpy(str, pop(stack, stack_index));


    for (int i = 0; i < numberOfNodes; i++) {
        if (str[i] == 'x') {
            indexToExpand = i;
            break;
        }
    }

    if (indexToExpand == -1) { // Uz nejde expandovat
        return 0;
    }

    if (_DEBUG_) {
        //printf("index to expand: %d \n", indexToExpand);
        printf("item to expand: %s \n", str);
        //printf("strlen: %d \n", strlen(str));
        //printf("str[1] = %c\n", str[1]);
    }

    str[indexToExpand] = '0';
    push(stack, str, stack_index);
    str[indexToExpand] = '1';
    push(stack, str, stack_index);


    return 1;
}

/*
 * Vypocita hranovy rez grafu podle zadaneho stringu
 */
int edgeCut(char *verticies, int numberOfNodes, int **graph) {
    // Mnoziny bodu a jejich vynulovani
    int setA[numberOfNodes];
    int setB[numberOfNodes];
    for (int i = 0; i < numberOfNodes; i++) {
        setA[i] = setB[i] = 0;
    }

    // Rozdeleni stringu do mnozin A a B
    for (int i = 0; i < numberOfNodes; i++) {
        if (verticies[i] != 'x') {
            if (verticies[i] == '0') {
                setA[i] = 1;
            } else {
                setB[i] = 1;
            }
        }
    }

    unsigned int result = 0;
    for (int i = 0; i < numberOfNodes; i++) { // projedeme vsechny radky
        if (setA[i] == 1) { // resime jen spravne radky
            for (int j = 0; j < numberOfNodes; j++) {
                if (setB[j] == 1) result += graph[i][j]; // vynechavame sloupce
            }
        }
    }


    if (_DEBUG_) {
        printf("Counting edgeCut from %s:\n", verticies);
        printf("setA:");
        for (int i = 0; i < numberOfNodes; i++) {
            printf("%d,", setA[i]);
        }
        printf("\nsetB:");
        for (int i = 0; i < numberOfNodes; i++) {
            printf("%d,", setB[i]);
        }
        printf("\n");
        printf("EDGE CUT = %i\n", result);
    }


    return result;
}

/*
 * Ohodnoti graf ze souboru s matici incidence
 * a vytvori soubor s takto ohodnocenym grafem
 */
int rateGraph(FILE *fr, char *path) {
    char str[MAX_FILE_LINE]; // Prectena radka
    int lineNumber = 0; // Cislo aktualne ctene radky
    int lineLenght; // Pocet znaku na aktualne ctene radce
    int j; // Pomocna promenna, index radku
    int graph[MAX_NODES][MAX_NODES];
    int numberOfNodes; // Pocet uzlu grafu precteny z prvni radky souboru
    FILE *fw; // Vystupni soubor a grafem

    srand (time(NULL)); // Seed random function

    j = 0; // Index radku pole pro graf
    while (fgets(str, MAX_FILE_LINE, fr) != NULL) {
        lineLenght = strlen(str);

        if (lineLenght == (MAX_FILE_LINE - 1) && str[lineLenght - 1] != '\n') {
            printf("Radka vstupniho souboru je prilis dlouha.");
            return 0;
        }

        if (str[lineLenght - 1] == '\n') {
            str[lineLenght - 1] = '\0'; // odstraneni konce radky a nahrazeni koncem retezce
        }

        if (lineNumber != 0) {
            for (int i = 0; i < lineLenght-1; i++) {

                if (j <= i) { // jen pro horni trojuhelnikovou matici a diagonalu
                    graph[j][i] = str[i] - 48;
                    if (graph[j][i] == 1) {
                        graph[j][i] = rand() % 255 + 1;
                    }
                    graph[i][j] = graph[j][i];
                }

            }
            j++; // Dalsi radek zvetsime index

        } else { // Prvni radka souboru, nacte se pocet uzlu
            numberOfNodes = atoi(str);
        }

        lineNumber++;
    }

    // Cesta k vystupnimu souboru stejna jako ke vstupnimu, jen se prida _rated do nazvu
    char *ext;
    ext = strstr(path, ".txt");
    strncpy(ext, "_rated.txt", 11);

    if ((fw = fopen(path , "w")) == NULL) {
        printf("Vystupni soubor %s s grafem se nepodarilo vytvorit.", path);
        return 0;
    }

    // Zapis do souboru
    fprintf(fw, "%i\n", numberOfNodes);
    for (int i = 0; i < numberOfNodes; i++) {
        for (int j = 0; j < numberOfNodes; j++) {
            fprintf(fw, "%i,", graph[i][j]);
        }
        fprintf(fw, "\n");
    }
    printf("Byl vytvoren soubor %s s ohodnocenym grafem.\n", path);

    fclose(fw);

    return 1;
}

/*
 * Precte graf se souboru a naplni pole graph.
 * Zjisti take pocet uzlu grafu.
 */
int loadGraph(FILE *fr, int **graph, int *numberOfNodes) {
    char str[MAX_FILE_LINE];
    int lineNumber = 0; // Cislo aktualne ctene radky
    int lineLenght; // Pocet znaku na aktualne ctene radce
    int gi = -1, gj = 0; // Pomocne indexy grafu, -1 protoze prvni radek souboru je pocet uzlu


    while (fgets(str, MAX_FILE_LINE, fr) != NULL) {
        lineLenght = strlen(str);

        if (lineLenght == (MAX_FILE_LINE - 1) && str[lineLenght - 1] != '\n') {
            printf("Radka vstupniho souboru je prilis dlouha.");
            return 0;
        }

        if (str[lineLenght - 1] == '\n') {
            str[lineLenght - 1] = '\0'; // odstraneni konce radky a nahrazeni koncem retezce
        }

        if (lineNumber == 0) { // Pri cteni prvniho radku se nacte pocet uzlu
            *numberOfNodes = atoi(str);
        } else {
            // Cteni radku po znacich, dokud je znak cislo, prirazuj znaky do number, az se narazi na carku cislo se ulozi do pole graph
            char number[4];
            int ni = 0;
            for (int i = 0; i < lineLenght - 1; i++) {
                if (str[i] != ',') {
                    number[ni] = str[i];
                    ni++;
                } else {
                    //printf("%i ", atoi(number));
                    //printf("ukladam %i do [%i,%i]\n", atoi(number), gi,gj);
                    graph[gi][gj] = atoi(number);
                    gj++; // Skoncilo cislo, index sloupce grafu zvysit
                    ni = 0;
                    for (int i = 0; i < 4; i++) {
                        number[i] = 0;
                    }
                }
            }

            //printf("\n");
        }
        gj = 0;
        gi++;
        lineNumber++;
    }


    return 0;
}