#include <stdio.h>
#include <stdlib.h>

#define ARR_LEN(a) (sizeof(a) / sizeof(*a))

enum symbol {
    PLUS = 0,
    MINUS,
    LPAREN,
    RPAREN,
    N0, N1,
    END_INPUT,
    
    EP, E, T, N,
    SYMBOL_COUNT,
};

static inline int is_terminal(enum symbol s)    { return s < E; }
static inline int is_nonterminal(enum symbol s) { return s >= E; }

struct production {
    enum symbol LHS;
    enum symbol *RHS;
    size_t nRHS;
};

#define PROD(LHS, _, ...) {LHS, (enum symbol[]){__VA_ARGS__}, sizeof((enum symbol[]){__VA_ARGS__})/sizeof(enum symbol)}

static struct production grammar[] = {
    PROD(EP, ->, E, END_INPUT),
    PROD(E, -->, E, PLUS, T),
    PROD(E, -->, E, MINUS, T),
    PROD(E, -->, T),
    PROD(T, -->, T, LPAREN, E, RPAREN),
    PROD(T, -->, N),
    PROD(N, -->, N0),
    PROD(N, -->, N1),
};

static int follow[SYMBOL_COUNT][SYMBOL_COUNT];
void fill_follow_table();

void print_grammar()
{
    for(size_t i = 0; i < ARR_LEN(grammar); i++)
    {
        printf("%d --> ", grammar[i].LHS);
        for(size_t j = 0; j < grammar[i].nRHS; j++)
            printf("%d ", grammar[i].RHS[j]);
        printf("\n");
    }
}


struct action {
    enum action_type {
        ACTION_NOT_SET = 0, ACTION_SHIFT,
        ACTION_GOTO, ACTION_REDUCE,
        ACTION_ACCEPT
    } type;
    size_t arg;
};

static struct action *(table[SYMBOL_COUNT]);
static size_t states;


struct item {
    size_t prod_idx;
    size_t dot;
};

int items_eq(struct item *i1, struct item *i2)
{
    if(i1->dot == i2->dot && i1->prod_idx == i2->prod_idx) return 1;
}

// TODO: check bounds
static struct {
    struct item *items;
    size_t nitems;
    size_t state;
} seen_sets[100];
static size_t nseen_sets;

size_t handle_set(struct item *set, size_t nset);
int fill_table(size_t state, struct item *initial_set, size_t ninitial);
void closure(struct item *in_set, size_t nin, struct item *out_set, size_t *nout);
    
#define DIE(...) (printf("ERROR %s:%d\n", __FILE__, __LINE__), __VA_OPT__(exit(__VA_ARGS__),) exit(1), 1)

int main(void)
{
    struct item i[] = {{1, 2}};
    struct item o[16];
    size_t no = ARR_LEN(o);
    
    closure(i, ARR_LEN(i), o, &no);
    (no > ARR_LEN(o)) && DIE();

    for(int i = 0; i < no; i++) {
        printf("%d %d\n", o[i].prod_idx, o[i].dot);
    }
}

size_t handle_set(struct item *set, size_t nset)
{
    // is set in seen_sets
    for(size_t i = 0; i < nseen_sets; i++) {
        if(seen_sets[i].nitems != nset) continue;
        
        int _seen = 0;
        for(size_t j = 0; j < nset; j++) {
            _seen = 0;
            for(size_t k = 0; k < nset; k++)
                if(items_eq(&seen_sets[i].items[j], &set[k])) _seen = 1;
            if(!_seen) break;
        }
        if(_seen) return seen_sets[i].state;
    }

    // add set to seen_sets
    // TODO: check calloc
    seen_sets[nseen_sets].items = calloc(nset, sizeof(*set));
    seen_sets[nseen_sets].nitems = nset;
    for(size_t i = 0; i < nset; i++)
        seen_sets[nseen_sets].items[i] = set[i];

    size_t new_state = seen_sets[nseen_sets++].state = states++;
    
    fill_table(new_state, set, nset) && DIE();
    return new_state;
}

int fill_table(size_t state, struct item *initial_set, size_t ninitial)
{    
    struct item closure_set[100];
    size_t nclosure = 100;
    
    closure(initial_set, ninitial, closure_set, &nclosure);
    if(nclosure > 100) return 1;

    for(size_t sym = 0; sym < SYMBOL_COUNT; sym++) {
        // TOOD: check goto bounds
        struct item goto_set[100];
        size_t ngoto = 0; 
        
        for(size_t j = 0; j < nclosure; j++) {
            struct production *p = &grammar[closure_set[j].prod_idx];
            size_t dot = closure_set[j].dot;
            
            if(dot == p->nRHS) {
                // if(follow[p->LHS][sym]) {
                //     //add reduction
                // }
                continue;
            }
            
            if(p->RHS[dot] == sym) {
                goto_set[ngoto] = closure_set[j];
                goto_set[ngoto++].dot++;
            }
        }

        size_t new_state = handle_set(goto_set, ngoto);

        // TODO: check table bounds
        // TODO: check if table state is already set
        table[state][sym] = (struct action){
            is_terminal(sym) ? ACTION_SHIFT : ACTION_GOTO,
            new_state};
    }
}

void closure(struct item *in_set, size_t nin, struct item *out_set, size_t *nout)
{
    size_t nout_max = *nout;
    *nout = nin;
    
    if(*nout > nout_max) return;
    for(size_t i = 0; i < nin; i++) out_set[i] = in_set[i];

    int *is_in_closure = calloc(ARR_LEN(grammar), sizeof(int));
    for(size_t i = 0; i < *nout; i++)
    {
        struct production *p = &grammar[out_set[i].prod_idx];
        if(out_set[i].dot == p->nRHS) continue;
        enum symbol sym = p->RHS[out_set[i].dot];
        
        for(size_t j = 0; j < ARR_LEN(grammar); j++)
            if(grammar[j].LHS == sym) {
                if(is_in_closure[j]) continue;
                is_in_closure[j] = 1;

                if(*nout >= nout_max) goto cleanup;
                out_set[(*nout)++] = (struct item){j, 0};
            }
    }

cleanup:
    free(is_in_closure);
}

void fill_follow_table()
{
    1 && DIE();
}