#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "myUtils.h"
#include "myHT.h"

typedef struct item_t i_t;
typedef struct set_t s_t;

int comb_r(s_t *workers, s_t *firms, int current, int N);
int checkStability(s_t *w, s_t *f, int N);
void loadFile(FILE *input, s_t **workers, s_t **firms, int *n);
void printAssignments(s_t *workers, int N);
void freeSet(s_t *s, int N);
void freeItem(i_t *i, int N);
s_t *setInit(int N);
i_t *itemInit(char *name, int N);

struct item_t {
    char *name;
    s_t *preferences;
    i_t *assigned;
};

struct set_t {
    i_t **table;
    ht_t *ht;
};

int main(int argc, char **argv) {
    int N;
    s_t *workers, *firms;
    FILE *input;

    if (argc != 2) {
        printf("Expected 1 argument: prgm.exe <filename>\n");
        exit(EXIT_FAILURE);
    }

    input = fopenOrDie(argv[1], "r");
    loadFile(input, &workers, &firms, &N);
    fclose(input);

    if (comb_r(workers, firms, 0, N))printAssignments(workers, N);
    else printf("No solution found.\n");

    freeSet(workers, N);
    freeSet(firms, N);

    return 0;
}

int comb_r(s_t *workers, s_t *firms, int current, int N) {
    int i;

    if (current == N) {
        if (checkStability(workers, firms, N))return 1;
        return 0;
    }

    for (i = 0; i < N; i++) {
        if (firms->table[i]->assigned == NULL) {
            workers->table[current]->assigned = firms->table[i];
            firms->table[i]->assigned = workers->table[current];
            if (comb_r(workers, firms, current + 1, N))return 1;
            firms->table[i]->assigned = NULL;
        }
    }

    return 0;
}

int checkStability(s_t *w, s_t *f, int N) {
    int i, j, act_w, act_f;

    for (i = 0; i < N; i++) {
        act_w = HTfind(w->table[i]->preferences->ht, w->table[i]->assigned->name);
        for (j = 0; j < N; j++) {
            act_f = HTfind(f->table[j]->preferences->ht, f->table[j]->assigned->name);
            if (HTfind(w->table[i]->preferences->ht, f->table[j]->name) < act_w
                && HTfind(f->table[j]->preferences->ht, w->table[i]->name) < act_f)
                return 0;
        }
    }

    return 1;
}

void loadFile(FILE *input, s_t **workers, s_t **firms, int *n) {
    s_t *w, *f;
    int i, j, k = 0, pos, N;
    char name[20 + 1];

    fscanf(input, "%d", &N);

    w = setInit(N);
    f = setInit(N);

    for (i = 0; i < N; i++) {
        fscanf(input, "%s", name);
        w->table[i] = itemInit(name, N);
        HTinsert(w->ht, name, i);
        w->table[i]->preferences = setInit(N);
        for (j = 0; j < N; j++) {
            fscanf(input, "%s", name);
            pos = HTfind(f->ht, name);
            if (pos == -1) {
                f->table[k] = itemInit(name, N);
                HTinsert(f->ht, name, k++);
                pos = k;
            }
            w->table[i]->preferences->table[j] = f->table[pos];
            HTinsert(w->table[i]->preferences->ht, name, j);
        }
    }

    for (i = 0; i < N; i++) {
        fscanf(input, "%s", name);
        pos = HTfind(f->ht, name);
        for (j = 0; j < N; j++) {
            fscanf(input, "%s", name);
            f->table[pos]->preferences->table[j] = w->table[HTfind(w->ht, name)];
            HTinsert(f->table[pos]->preferences->ht, name, j);
        }
    }

    *n = N;
    *workers = w;
    *firms = f;
}

void printAssignments(s_t *workers, int N) {
    int i;
    for (i = 0; i < N; i++)printf("%s %s\n", workers->table[i]->name, workers->table[i]->assigned->name);
}

void freeSet(s_t *s, int N) {
    int i;
    for (i = 0; i < N; i++)freeItem(s->table[i], N);
    HTfree(s->ht);
    free(s);
}

void freeItem(i_t *i, int N) {
    free(i->name);
    free(i->preferences);
    free(i);
}

s_t *setInit(int N) {
    s_t *set;
    set = (s_t *) allocateOrDie(sizeof(s_t));
    set->table = (i_t **) allocateOrDie(sizeof(i_t *) * N);
    set->ht = HTinit(N);
    return set;
}

i_t *itemInit(char *name, int N) {
    i_t *item;
    item = (i_t *) allocateOrDie(sizeof(i_t));
    item->name = strdup(name);
    if (item->name == NULL)exit(EXIT_FAILURE);
    item->assigned = NULL;
    item->preferences = setInit(N);
    return item;
}