#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

#include "life1.h"


FILE *infile;
CellList *cells;   /* List of all living cells. */
CellList *minCell; /* One cell containing lowest x and y coordinate. */

uint64_t pos[64]; /* Contains the values where only the bit with the specified
                 position is set. (pos[0] = 1, pos[1] = 2, pos[n] = 2^n) */


/**
 * Creates a new cell.
 */
CellList *newCell(long x, long y) {
    CellList *new = (CellList *) malloc(sizeof(CellList));
    if (new == NULL) {
        fprintf(stderr, "life: couldn't allocate memory\n");
        exit(1);
    }
    
    new->x = x;
    new->y = y;
    new->xy = x + y;
    new->alive = 1;
    new->prev = new->next = NULL;
    
    return new;
}

/**
 * Adds the new cell directly previous to the other cell,
 * if they are not equal.
 * Returns a pointer to the new cell, if it was inserted,
 * or to the list, otherwise.
 */
CellList *addPrevious(CellList *new, CellList *list) {
    if ((new->xy == list->xy) && (new->x == list->x)) {
        free(new);
        return list;
    }
    
    new->next = list;
    new->prev = list->prev;
    list->prev = new;
    list = new->prev;
    if (list) {
        list->next = new;
    }
    
    return new;
}

/**
 * Adds the new cell directly next to the other cell,
 * if they are not equal.
 * Returns a pointer to the new cell, if it was inserted,
 * or to the list, otherwise.
 */
CellList *addNext(CellList *new, CellList *list) {
    if ((new->xy == list->xy) && (new->x == list->x)) {
        free(new);
        return list;
    }
    
    new->prev = list;
    new->next = list->next;
    list->next = new;
    list = new->next;
    if (list) {
        list->prev = new;
    }
    
    return new;
}

/**
 * Adds a cell into the specified cell list, if it doesn't contain it already.
 * Returns the head of the list.
 * 
 * Lists are sorted by xy value first, then by x value. There can be no two cells
 * with the same xy and x values in the list.
 */
CellList *addCell(CellList *new, CellList *list) {
    long xy = new->xy;
    long x = new->x;
    
    if (!list) {
        return new;
    }
    
    if (list->xy < xy) {
        while (list->next) {
            list = list->next;
            if (list->xy < xy) {
                continue;
            }
            if (list->xy > xy) {
                return addPrevious(new, list);
            }
            if (list->x >= x) {
                return addPrevious(new, list);
            }
        }
        /* Add to end of list. */
        list->next = new;
        new->prev = list;
        new->next = NULL;
        return new;
    }
    
    if (list->xy > xy) {
        while (list->prev) {
            list = list->prev;
            if (list->xy > xy) {
                continue;
            }
            if (list->xy < xy) {
                return addNext(new, list);
            }
            if (list->x <= x) {
                return addNext(new, list);
            }
        }
        /* Add as head of list. */
        list->prev = new;
        new->next = list;
        new->prev = NULL;
        return new;
    }
    
    if (list->x < x) {
        while (list->next) {
            list = list->next;
            if (list->xy != xy) {
                return addPrevious(new, list);
            }
            if (list->x >= x) {
                return addPrevious(new, list);
            }
        }
        /* Add to end of list. */
        list->next = new;
        new->prev = list;
        new->next = NULL;
        return new;
    }
    
    if ((list->x == x) && (list->xy == xy)) {
        return list;
    }
    
    while (list->prev) {
        list = list->prev;
        if (list->xy != xy) {
            return addNext(new, list);
        }
        if (list->x <= x) {
            return addNext(new, list);
        }
    }
    /* Add as head of list. */
    list->prev = new;
    new->next = list;
    new->prev = NULL;
    return new;
}

/**
 * Adds the cell at the specified position to the list of living cells.
 */
void setAlive(long x, long y) {
    cells = addCell(newCell(x, y), cells);
}

/**
 * Reads the current generation from the specified stream.
 */
void readLife(FILE *f) {
    infile = f;
    
    /* Parse the file. */
    if (yyparse() != 0) {
        fprintf(stderr, "syntax error");
        exit(1);
    }
}

/**
 * Outputs all living cells to the specified stream.
 * Return value is the total number of living cells.
 */
int writeLife(FILE *f) {
    CellList *c = cells;
    int living = 0;
    
    /* All cells after current position (and current). */
    while (c) {
        fprintf(f, "%ld %ld\n", c->x, c->y);
        c = c->next;
        ++living;
    }
    
    c = cells->prev;
    /* All cells before current position. */
    while (c != NULL) {
        fprintf(f, "%ld %ld\n", c->x, c->y);
        c = c->prev;
        ++living;
    }
    
    return living;
}

/**
 * Deletes all dead cells (alive == 0) from the list of living cells.
 */
void cleanCells() {
    CellList *curr, *tmp;
    
    if (!cells) {
        return;
    }
    
    curr = cells->prev;
    if (curr) {
        /* curr->next is never NULL */
        do {
            if (!curr->alive) {
                tmp = curr;
                curr = curr->prev;
                tmp->next->prev = curr;
                if (curr) {
                    curr->next = tmp->next;
                    free(tmp);
                }
                else {
                    free(tmp);
                    break;
                }
            }
            else {
                curr = curr->prev;
            }
        } while (curr);
        
        /* Now we have to ensure that cells points to a living cell. */
        if (cells->prev) {
            cells = cells->prev;
        }
        else {
            /* cells->prev is always NULL */
            while (cells && (!cells->alive)) {
                curr = cells->next;
                if (!curr) {
                    free(cells);
                    cells = NULL;
                    return;
                }
                curr->prev = NULL;
                free(cells);
                cells = curr;
            }
        }
    }
    else {
        /* cells->prev is always NULL */
        while (cells && (!cells->alive)) {
            curr = cells->next;
            if (!curr) {
                free(cells);
                cells = NULL;
                return;
            }
            curr->prev = NULL;
            free(cells);
            cells = curr;
        }
    }
    
    if (!cells) {
        return;
    }
    
    curr = cells->next;
    /* curr->prev is never NULL */
    do {
        if (!curr->alive) {
            tmp = curr;
            curr = curr->next;
            tmp->prev->next = curr;
            if (curr) {
                curr->prev = tmp->prev;
                free(tmp);
            }
            else {
                free(tmp);
                return;
            }
        }
        else {
            curr = curr->next;
        }
    } while (curr);
}

/**
 * Executes the next-generation-computation for one cell.
 * 
 * @param add The list of cells to be added in the next generation.
 */
void oneGenerationCell(CellList *curr, CellList *add) {
    CellList *tmp;
    uint64_t area;
    long xy;
    long x, y;
    long tx, ty;
    int livnbs;
    char nbs[8];
    
    /* area is a 64 bit number, in which the 5x5 grid surrounding the current
       cell is encoded. For each living cell in that grid, except curr, the
       bit on position [tx * 8 + ty] is set. */
    area = 0L;
    
    /* Read all cells of 5x5 neighbourhood into area. */
    /* 1) Neighbours with xy < curr.xy */
    /* Optimization: Cell (x-1, y-1) is not checked, therefore cell (x-2, y-2)
       has not got to be read. The same applys for cells (x+1/2, y+1/2).
       A bit complicated train of thought, but if you can't understand it, just believe me. */
    
    xy = curr->xy - 4;
    x = curr->x - 2;
    y = curr->y - 2;
    
    tmp = curr->prev;
    while (tmp && tmp->xy > xy) {
        tx = tmp->x - x;
        ty = tmp->y - y;
        
        if ((tx >= 0) && (ty >= 0)) {
            area |= pos[tx * 8 + ty];
        }
        tmp = tmp->prev;
    }
    
    /* 2) Neighbours with xy >= curr.xy */
    
    /*xy = curr->xy + 4;*/
    xy += 8;
    
    tmp = curr->next;
    while (tmp && tmp->xy < xy) {
        tx = tmp->x - x;
        ty = tmp->y - y;
        
        if ((tx < 5) && (ty < 5)) {
            area |= pos[tx * 8 + ty];
        }
        tmp = tmp->next;
    }
    
    
    /* Check, wether there are any neighbours at all. */
    if ((area) == 0L) {
        curr->alive = 0;
        return;
    }
    
    livnbs = 0; /* Number of living neighbours of current cell. */
    *((uint64_t *) nbs) = 0L; /* Numbers of living neighbours of the
                             other cells in a 3x3 grid. */
    
    /* Set x and y. */
    x += 2;
    y += 2;
    
    /*    nbs:        area (bit at pos.):
     *    . . . . .   -  5 10 15 20      
     *    . 0 3 5 .   1  6 11 16 21      
     *    . 1 X 6 .   2  7 >< 17 22      
     *    . 2 4 7 .   3  8 13 18 23      
     *    . . . . .   4  9 14 19 --      
     */                                  
    
    /*
     * COUNT NEIGHBOURS:
     */
    
    /* (-2, -1) */
    if (area & 2L) {
        /*++nbs[0];*/ /* Commented out, because (-1, -1) and (+1, +1) are not checked. */
        ++nbs[1];
    }
    /* (-2, 0) */
    if (area & 4L) {
        /*++nbs[0];*/
        ++nbs[1];
        ++nbs[2];
    }
    /* (-2, 1) */
    if (area & 8L) {
        ++nbs[1];
        ++nbs[2];
    }
    /* (-2, 2) */
    if (area & 16L) {
        ++nbs[2];
    }
    /* (-1, -2) */
    if (area & 256L) {
        /*++nbs[0];*/
        ++nbs[3];
    }
    /* (-1, -1) */
    if (area & 512L) {
        /*nbs[0] = 8;*/
        ++nbs[1];
        ++nbs[3];
        
        ++livnbs;
    }
    /* (-1, 0) */
    if (area & 1024L) {
        /*++nbs[0];*/
        nbs[1] = 8; /* If a cell is already living, it will later
                       become curr itself, so we don't have to
                       check for its survival now. */
        ++nbs[2];
        ++nbs[3];
        ++nbs[4];
        
        ++livnbs;
    }
    /* (-1, 1) */
    if (area & 2048L) {
        ++nbs[1];
        nbs[2] = 8;
        ++nbs[4];
        
        ++livnbs;
    }
    /* (-1, 2) */
    if (area & 4096L) {
        ++nbs[2];
        ++nbs[4];
    }
    /* (0, -2) */
    if (area & 65536L) {
        /*++nbs[0];*/
        ++nbs[3];
        ++nbs[5];
    }
    /* (0, -1) */
    if (area & 131072L) {
        /*++nbs[0];*/
        ++nbs[1];
        nbs[3] = 8;
        ++nbs[5];
        ++nbs[6];
        
        ++livnbs;
    }
    /* (0, 1) */
    if (area & 524288L) {
        ++nbs[1];
        ++nbs[2];
        nbs[4] = 8;
        ++nbs[6];
        /*++nbs[7];*/
        
        ++livnbs;
    }
    /* (0, 2) */
    if (area & 1048576L) {
        ++nbs[2];
        ++nbs[4];
        /*++nbs[7];*/
    }
    /* (1, -2) */
    if (area & 16777216L) {
        ++nbs[3];
        ++nbs[5];
    }
    /* (1, -1) */
    if (area & 33554432L) {
        ++nbs[3];
        nbs[5] = 8;
        ++nbs[6];
        
        ++livnbs;
    }
    /* (1, 0) */
    if (area & 67108864L) {
        ++nbs[3];
        ++nbs[4];
        ++nbs[5];
        nbs[6] = 8;
        /*++nbs[7];*/
        
        ++livnbs;
    }
    /* (1, 1) */
    if (area & 134217728L) {
        ++nbs[4];
        ++nbs[6];
        /*nbs[7] = 8;*/
        
        ++livnbs;
    }
    /* (1, 2) */
    if (area & 268435456L) {
        ++nbs[4];
        /*++nbs[7];*/
    }
    /* (2, -2) */
    if (area & 4294967296L) {
        ++nbs[5];
    }
    /* (2, -1) */
    if (area & 8589934592L) {
        ++nbs[5];
        ++nbs[6];
    }
    /* (2, 0) */
    if (area & 17179869184L) {
        ++nbs[5];
        ++nbs[6];
        /*++nbs[7];*/
    }
    /* (2, 1) */
    if (area & 34359738368L) {
        ++nbs[6];
        /*++nbs[7];*/
    }
    
    /*
     * COMPUTE RESURRECTED CELLS:
     */
    
    /* (-1, 0) */
    if (nbs[1] == 2) {
        add = addCell(newCell(x - 1, y), add);
    }
    /* (-1, 1) */
    if (nbs[2] == 2) {
        add = addCell(newCell(x - 1, y + 1), add);
    }
    /* (0, -1) */
    if (nbs[3] == 2) {
        add = addCell(newCell(x, y - 1), add);
    }
    /* (0, 1) */
    if (nbs[4] == 2) {
        add = addCell(newCell(x, y + 1), add);
    }
    /* (1, -1) */
    if (nbs[5] == 2) {
        add = addCell(newCell(x + 1, y - 1), add);
    }
    /* (1, 0) */
    if (nbs[6] == 2) {
        add = addCell(newCell(x + 1, y), add);
    }
    
    /* Does curr survive? */
    if ((livnbs != 2) && (livnbs != 3)) {
        curr->alive = 0;
    }
    
}

/**
 * Calculates the changes for a progress of one generation.
 */
void oneGeneration() {
    CellList *curr;
    CellList *tmp;
    CellList *add = minCell;
    add->next = NULL;
    
    if (!cells) {
        return;
    }
    
    for (curr = cells; curr; curr = curr->next) {
        oneGenerationCell(curr, add);
    }
    for (curr = cells->prev; curr; curr = curr->prev) {
        oneGenerationCell(curr, add);
    }
    
    /*
     * Deletes all dead cells in cells.
     */
    cleanCells();
    
    /* Now add all cells from add to cells, at their correct positions. */
    add = minCell->next;
    if (!add) {
        return;
    }
    add->prev = NULL;
    
    if (!cells) {
        cells = add;
        return;
    }
    
    curr = add;
    while (curr) {
        tmp = curr->next;
        cells = addCell(curr, cells);
        curr = tmp;
    }
}

/**
 * The main method, which receives the arguments and starts the processing.
 * 
 * @param argc The number of arguments. Must be 2 (command name and number of generations).
 * @param argc The arguments.
 */
int main(int argc, char **argv) {
    long generations;
    long i;
    long j;
    char *endptr;
    int living;

    if (argc!=2) {
        fprintf(stderr, "Usage: %s #generations < startfile | sort > endfile\n", argv[0]);
        exit(1);
    }
    
    generations = strtol(argv[1], &endptr, 10);
    if (*endptr != '\0') {
        fprintf(stderr, "\"%s\" not a valid generation count\n", argv[1]);
        exit(1);
    }
    
    j = 1L;
    for (i = 0L; i < 64L; ++i) {
        pos[i] = j;
        j <<= 1;
    }
    
    minCell = newCell(LONG_MIN / 2, LONG_MIN / 2);
    cells = minCell;
    readLife(stdin);
    cells = minCell->next;
    if (!cells) {
        return 0;
    }
    cells->prev = NULL;
    
    for (i = 0L; i < generations; i++) {
        oneGeneration();
    }
    
    living = writeLife(stdout);
    
    fprintf(stderr,"%d cells alive\n", living);
    
    free(minCell);
    while (cells->prev) {
        cells = cells->prev;
    }
    while (cells->next != NULL) {
        cells = cells->next;
        free(cells->prev);
    }
    free(cells);
    
    return 0;
}