20180129

20180129.c

#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);
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);
    freeSet(firms);

    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){
    //TODO!!!!!!!!!!!!
}

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;
}