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

#include "loadsave.h"
#include "life.h"
#include "util.h"

/*** Private Prototypes ***/

static char* load_component_block(FILE* f, int32 xoffset, int32 yoffset);
static char* load_component_coordinates(FILE* f, int32 xoffset, int32 yoffset, boolean until_eof);
static void  load_component_rle(FILE* f, boolean use_glf_format);
static void  save_component_blocks(FILE* f);
static void  save_component_coordinates(FILE* f);
static void  save_component_description(FILE* f, char prefix_char);
static void  save_component_rle(FILE* f, boolean use_glf_format);

static void  get_block_text(uint16 block, char buf[8][9], int32 xoffset, int32 yoffset);
static int   rle_compare(const void* cage1, const void* cage2);
static void  rle_add_row(FILE* f, uint16 block, int32 bit_row, int32 first_bit);
static void  rle_add(FILE* f, char obj, uint32 count);
static void  rle_output(FILE* f, char obj, uint32 count);
static void  save_block_coordinates(FILE* f, uint16 block, int32 startx, int32 starty);

/* Public Constants */

loader_function loaders[NUM_FORMATS] = {
    load_pattern_glf,
    load_pattern_rle,
    load_pattern_lif_105,
    load_pattern_lif_106,
    load_pattern_xlife
};

saver_function savers[NUM_FORMATS] = {
    save_pattern_glf,
    save_pattern_rle,
    save_pattern_lif_105,
    save_pattern_lif_106,
    save_pattern_xlife
};

/*** Private Globals ***/

static char*  newline;   /* used as the newline sequence when saving */

/*** Public Functions ***/

/* Helper functions which load patterns of various formats from open files. Description loading
 * is done by load_pattern() itself, so these functions only load cell data.
 */

void load_pattern_glf(FILE* f)
{
    load_component_rle(f, TRUE);
}

void load_pattern_rle(FILE* f)
{
    load_component_rle(f, FALSE);
}

void load_pattern_lif_105(FILE* f)
{
    char*   line;
    int32   x, y;

    /* Process #P blocks, ignoring all else */
    line = dgets(f);
    while (line) {
        if (STR_STARTS_WITH(line, "#P")) {
            if (sscanf(line+2, "%d%d", &x, &y) != 2)
                x = y = 0;
            line = load_component_block(f, x, y);
        } else {
            free(line);
            line = dgets(f);
        }
    }
}

void load_pattern_lif_106(FILE* f)
{
    load_component_coordinates(f, 0, 0, TRUE);
}

void load_pattern_xlife(FILE* f)
{
    char*   line;
    int32   x, y;

    /* Our implementation processes #A, #R, and #P blocks, treating unnamed blocks as #A's.
     * We don't handle #B/#E sub-patterns or #I includes (load_pattern() errors out). */

    line = dgets(f);
    while (line) {
        if (STR_STARTS_WITH(line, "#A")) {
            /* A list of absolute coordinates */
            line = load_component_coordinates(f, 0, 0, FALSE);
        } else if (STR_STARTS_WITH(line, "#R")) {
            /* A list of relative coordinates */
            if (sscanf(line+2, "%d%d", &x, &y) != 2)
                x = y = 0;
            line = load_component_coordinates(f, x, y, FALSE);
        } else if (STR_STARTS_WITH(line, "#P")) {
            /* A "picture" block */
            if (sscanf(line+2, "%d%d", &x, &y) != 2)
                x = y = 0;
            line = load_component_block(f, x, y);
        } else if (sscanf(line, "%d%d", &x, &y) == 2) {
            /* A block with no header: treat it like an #A block */
            draw_cell(x + WORLD_SIZE/2, y + WORLD_SIZE/2, DRAW_SET);
            line = load_component_coordinates(f, 0, 0, FALSE);
        } else {
            free(line);
            line = dgets(f);
        }
    }
}

/* Helper functions which save patterns to open files using various formats. */

void save_pattern_glf(FILE* f)
{
    newline = "\n";

    fprintf(f, "#GLF %s%s", GLF_VERSION, newline);
    save_component_description(f, 'D');
    save_component_rle(f, TRUE);
}

void save_pattern_rle(FILE* f)
{
    newline = "\n";

    save_component_description(f, 'C');
    save_component_rle(f, FALSE);
}

void save_pattern_lif_105(FILE* f)
{
    newline = "\r\n";

    fprintf(f, "#Life 1.05%s", newline);
    save_component_description(f, 'D');
    fprintf(f, "#N%s", newline);
    save_component_blocks(f);
}

void save_pattern_lif_106(FILE* f)
{
    newline = "\r\n";

    fprintf(f, "#Life 1.06%s", newline);
    save_component_description(f, 'D');
    fprintf(f, "#N%s", newline);
    save_component_coordinates(f);
}

void save_pattern_xlife(FILE* f)
{
    newline = "\n";

    save_component_description(f, 'C');
    save_component_coordinates(f);
}

/* Other Public Functions */

/* Determine whether the given line is an "x = <num>, y = <num>, width = <num>, height = <num>" GLF
 * header line, returning true if so. If startx and starty are non-NULL, the corresponding values
 * are returned in them (adjusted from signed to unsigned coordinates), likewise width and height.
 */
boolean process_glf_header(const char* line, int32* startx, int32* starty,
                           int32* width, int32* height)
{
    int32  x, y, w, h;

    /* sscanf allows arbitrary white space wherever a space appears in the format string */
    if (sscanf(line, " x = %d , y = %d, width = %d, height = %d", &x, &y, &w, &h) == 4) {
        if (startx && starty) {
            *startx = x + WORLD_SIZE/2;
            *starty = y + WORLD_SIZE/2;
        }
        if (width && height) {
            *width  = w;
            *height = h;
        }
        return TRUE;
    } else
        return FALSE;
}

/* Determine whether the given line is an "x = <num>, y = <num>" RLE header line, returning true if
 * so. If width and height are non null, the corresponding values are returned in them. If startx
 * and starty are non-NULL, starting coordinates are returned that will place the pattern at the
 * middle of the world.
 */
boolean process_rle_header(const char* line, int32* startx, int32* starty, int32* width,
                           int32* height)
{
    int32  w, h;

    /* sscanf allows arbitrary white space wherever a space appears in the format string */
    if (sscanf(line, " x = %d , y = %d", &w, &h) == 2) {
        if (width && height) {
            *width = w;
            *height = h;
        }
        if (startx && starty) {
            *startx = (WORLD_SIZE - w) / 2;
            *starty = (WORLD_SIZE - h) / 2;
        }
        return TRUE;
    } else
        return FALSE;
}

/*** Private Functions ***/

/* Load a #P-style block of cell data from the given open file, drawing it at the given x, y
 * offset. Stop reading when we hit a line starting with '#' or end of file, returning the final
 * line or NULL.
 */
static char* load_component_block(FILE* f, int32 xoffset, int32 yoffset)
{
    char*   line;
    char*   p;
    int32   y, curx;

    xoffset += WORLD_SIZE/2;
    yoffset += WORLD_SIZE/2;

    y = yoffset;
    while ((line = dgets(f)) != NULL && line[0] != '#') {
        /* Load this line of data, unless we are out of bounds or the line is empty */
        if (y < WORLD_SIZE && line[0] != '\0') {
            for (p=line, curx=xoffset; *p; p++, curx++) {
                if (curx < WORLD_SIZE && *p != '.' && !isspace(*p))
                    draw_cell(curx, y, DRAW_SET);
            }
            y++;
        }
        free(line);
    }

    return line;
}

/* Load live-cell coordinate pairs from the given open file, applying the given offsets. If
 * until_eof is true, read coordinates until end of file, otherwise stop reading when we
 * encounter a line starting with '#', and return that line.
 */
static char* load_component_coordinates(FILE* f, int32 xoffset, int32 yoffset, boolean until_eof)
{
    char*  line;
    int32  x, y;

    xoffset += WORLD_SIZE/2;
    yoffset += WORLD_SIZE/2;

    while ((line = dgets(f)) != NULL) {
        if (line[0] == '#') {
            if (!until_eof)
                break;
        } else if (sscanf(line, "%d%d", &x, &y) == 2)
            draw_cell(x + xoffset, y + yoffset, DRAW_SET);
        free(line);
    }

    return line;
}

/* Load pattern data from an RLE-type file, stopping when we hit a '!' character. If use_glf_format
 * is true, expect GLF-style header info.
 */
static void load_component_rle(FILE* f, boolean use_glf_format)
{
    char*    line;
    char*    pos;
    char*    endptr;
    int32    startx, starty;
    int32    x, y;
    int32    endx;
    int32    count;
    boolean  end_of_pattern = FALSE;
    boolean  success;

    line = dgets(f);
    while (line[0] == '#') {
        free(line);
        line = dgets(f);
    }
    success = (use_glf_format ? process_glf_header(line, &startx, &starty, NULL, NULL) :
                                process_rle_header(line, &startx, &starty, NULL, NULL));
    if (!success)
        startx = starty = WORLD_SIZE/2;
    free(line);

    x = startx;
    y = starty;
    count = 1;
    while (!end_of_pattern && (line = dgets(f)) != NULL) {
        for (pos=line; *pos; pos++) {
            if (isdigit(*pos)) {
                count = strtol(pos, &endptr, 10);
                pos = endptr-1;
            } else if (*pos == 'b') {
                x += count;
                count = 1;
            } else if (*pos == '$') {
                y += count;
                x = startx;
                count = 1;
            } else if (*pos == '!') {
                end_of_pattern = TRUE;
                break;
            } else {    /* the character for live cells is 'o', but accept other characters too */
                endx = x + count;
                while (x < endx)
                    draw_cell(x++, y, DRAW_SET);
                count = 1;
            }
        }
        free(line);
    }
}

/* Output pattern data in #P blocks to the given open file.
 */
static void save_component_blocks(FILE* f)
{
    cage_type*  c;
    char        chunk[8][9];
    int32       startx, starty;
    int32       first_row, last_row, first_col;
    int32       x, y;

    for (y=0; y < 8; y++)
        chunk[y][8] = '\0';

    while ((c = loop_cages()) != NULL) {
        if (IS_EMPTY(c))
            continue;

        /* Get the starting coords for the cage, relative to center of world */
        startx = (c->x * CAGE_SIZE) - WORLD_SIZE/2;
        starty = (c->y * CAGE_SIZE) - WORLD_SIZE/2;

        /* Fill the chunk with the data from the four 4x4 blocks */
        get_block_text(c->bnw[parity], chunk, 0, 0);
        get_block_text(c->bne[parity], chunk, 4, 0);
        get_block_text(c->bsw[parity], chunk, 0, 4);
        get_block_text(c->bse[parity], chunk, 4, 4);

        /* Trim off empty rows, empty columns, and trailing empty cells */
        for (y=0; y < 8 && STR_EQUAL(chunk[y], "........"); y++, starty++) {}
        first_row = y;
        for (y=7; y > first_row && STR_EQUAL(chunk[y], "........"); y--) {}
        last_row = y;
        for (x=0; x < 8; x++, startx++) {
            for (y=0; y < 8 && chunk[y][x] == '.'; y++) {}
            if (y < 8)
                break;
        }
        first_col = x;
        for (y=0; y < 8; y++) {
            for (x=7; x > first_col && chunk[y][x] == '.'; x--) { }
            chunk[y][x+1] = '\0';
        }

        /* Output chunk header and data */
        fprintf(f, "#P %d %d%s", startx, starty, newline);
        for (y=first_row; y <= last_row; y++)
            fprintf(f, "%s%s", chunk[y] + first_col, newline);
    }
}

/* Output pattern data in x/y coordinate pairs to the given open file.
 */
static void save_component_coordinates(FILE* f)
{
    cage_type*  c;
    int32       startx, starty;

    while ((c = loop_cages()) != NULL) {
        startx = (c->x * CAGE_SIZE) - WORLD_SIZE/2;
        starty = (c->y * CAGE_SIZE) - WORLD_SIZE/2;
        save_block_coordinates(f, c->bnw[parity], startx, starty);
        save_block_coordinates(f, c->bne[parity], startx + 4, starty);
        save_block_coordinates(f, c->bsw[parity], startx, starty + 4);
        save_block_coordinates(f, c->bse[parity], startx + 4, starty + 4);
    }
}

/* Output the pattern description to the given open file, using the specified prefix character.
 */
static void save_component_description(FILE* f, char prefix_char)
{
    int32  i;

    for (i=0; i < desc_num_lines; i++) {
        if (IS_EMPTY_STRING(pattern_description[i]))
            fprintf(f, "#%c%s", prefix_char, newline);
        else
            fprintf(f, "#%c %s%s", prefix_char, pattern_description[i], newline);
    }
}

/* Output pattern data in run-length-encoded format (including dimensions header) to the given
 * open file. If use_glf_format is true, output GLF-style header info.
 */
static void save_component_rle(FILE* f, boolean use_glf_format)
{
    cage_type*  c;
    rle_cage*   cages;
    int32       minx = 0xFFFF, miny = 0xFFFF;
    int32       maxx = 0, maxy = 0;
    int32       top_bits, bottom_bits, left_bits, right_bits;
    int32       min_bit;
    int32       prevy;
    int32       width, height;
    int32       xpad;
    int32       jstart, jend, bstart;
    int32       i, j, b, x, y, nc;
    uint16      mask;

    /* Special case if the world is empty */
    if (num_cages == 0) {
        if (use_glf_format)
            fprintf(f, "x = 0, y = 0, width = 0, height = 0%s", newline);
        else
            fprintf(f, "x = 0, y = 0, rule = S23/B3%s", newline);
        return;
    }

    /* Copy cages into an array sorted by row, then by column */
    cages = safe_malloc(num_cages * sizeof(rle_cage));
    i = 0;
    while ((c = loop_cages()) != NULL) {
        if (IS_EMPTY(c))
            continue;
        cages[i].nw = c->bnw[parity];
        cages[i].ne = c->bne[parity];
        cages[i].sw = c->bsw[parity];
        cages[i].se = c->bse[parity];
        cages[i].x  = c->x;
        cages[i].y  = c->y;
        if (c->x < minx)
            minx = c->x;
        if (c->x > maxx)
            maxx = c->x;
        if (c->y < miny)
            miny = c->y;
        if (c->y > maxy)
            maxy = c->y;
        i++;
    }
    nc = i;
    qsort(cages, nc, sizeof(rle_cage), rle_compare);

    /* Find the topmost live cells */
    top_bits = 7;
    for (i=0; i < nc && cages[i].y == cages[0].y; i++) {
        for (j=0, mask=0x000F; j < MIN(4, top_bits); j++, mask <<= 4) {
            if ((cages[i].nw & mask) || (cages[i].ne & mask)) {
                top_bits = j;
                break;
            }
        }
        if (j == 4) {
            for (j=4, mask=0x000F; j < MIN(7, top_bits); j++, mask <<= 4) {
                if ((cages[i].sw & mask) || (cages[i].se & mask)) {
                    top_bits = j;
                    break;
                }
            }
        }
    }

    /* Find the bottommost live cells */
    bottom_bits = 0;
    for (i=nc-1; i >= 0 && cages[i].y == cages[nc-1].y; i--) {
        for (j=7, mask=0xF000; j > MAX(3, bottom_bits); j--, mask >>= 4) {
            if ((cages[i].sw & mask) || (cages[i].se & mask)) {
                bottom_bits = j;
                break;
            }
        }
        if (j == 3) {
            for (j=3, mask=0xF000; j > MAX(0, bottom_bits); j--, mask >>= 4) {
                if ((cages[i].nw & mask) || (cages[i].ne & mask)) {
                    bottom_bits = j;
                    break;
                }
            }
        }
    }

    /* Find the leftmost and rightmost live cells */
    left_bits = 7;
    right_bits = 0;
    for (i=0; i < nc; i++) {
        if (cages[i].x == minx) {
            for (j=0, mask=0x1111; j < MIN(4, left_bits); j++, mask <<= 1) {
                if ((cages[i].nw & mask) || (cages[i].sw & mask)) {
                    left_bits = j;
                    break;
                }
            }
            if (j == 4) {
                for (j=4, mask=0x1111; j < MIN(7, left_bits); j++, mask <<= 1) {
                    if ((cages[i].ne & mask) || (cages[i].se & mask)) {
                        left_bits = j;
                        break;
                    }
                }
            }
        } else if (cages[i].x == maxx) {
            for (j=7, mask=0x8888; j > MAX(3, right_bits); j--, mask >>= 1) {
                if ((cages[i].ne & mask) || (cages[i].se & mask)) {
                    right_bits = j;
                    break;
                }
            }
            if (j == 3) {
                for (j=3, mask=0x8888; j > MAX(0, right_bits); j--, mask >>= 1) {
                    if ((cages[i].nw & mask) || (cages[i].sw & mask)) {
                        right_bits = j;
                        break;
                    }
                }
            }
        }
    }

    /* Determine and output the location and dimensions of the pattern */
    x      = (minx*CAGE_SIZE - WORLD_SIZE/2) + left_bits;
    y      = (miny*CAGE_SIZE - WORLD_SIZE/2) + top_bits;
    width  = (CAGE_SIZE * (maxx-minx+1)) - (left_bits - 0) - (7 - right_bits);
    height = (CAGE_SIZE * (maxy-miny+1)) - (top_bits - 0)  - (7 - bottom_bits);
    if (use_glf_format)
        fprintf(f, "x = %d, y = %d, width = %d, height = %d%s", x, y, width, height, newline);
    else
        fprintf(f, "x = %d, y = %d, rule = S23/B3%s", width, height, newline);

    /* Output cell data */
    prevy = -1;
    for (i=0; i < nc; i = jend) {
        y = cages[i].y;
        if (prevy > -1)
            rle_add(f, '$', ((y == prevy+1) ? 1 : CAGE_SIZE * (y-prevy-1) + 1));
        prevy = y;
        xpad = (CAGE_SIZE * (cages[i].x - minx)) - left_bits;
        for (j=i; j < nc && cages[j].y == y; j++) {}
        jstart = i;
        jend = j;
        bstart = ((y == miny) ? top_bits : 0);
        for (b=bstart; b < CAGE_SIZE; b++) {
            if (b > bstart)
                rle_add(f, '$', 1);
            if (xpad > 0)
                rle_add(f, 'b', xpad);
            for (j=jstart; j < jend; j++) {
                if (j == jstart)
                    min_bit = ((cages[j].x == minx) ? left_bits: 0);
                else {
                    min_bit = 0;
                    if (cages[j].x > cages[j-1].x + 1)
                        rle_add(f, 'b', CAGE_SIZE * (cages[j].x - cages[j-1].x - 1));
                }
                if (b < BLOCK_SIZE) {
                    rle_add_row(f, cages[j].nw, b, min_bit);
                    rle_add_row(f, cages[j].ne, b, min_bit - BLOCK_SIZE);
                } else {
                    rle_add_row(f, cages[j].sw, b - BLOCK_SIZE, min_bit);
                    rle_add_row(f, cages[j].se, b - BLOCK_SIZE, min_bit - BLOCK_SIZE);
                }
            }
        }
    }

    /* End file */
    rle_add(f, '!', 1);
    free(cages);
}

/* Fill a quarter of the buffer buf with text representing the given 4x4 cell block, using the
 * given x/y offsets into the buffer.
 */
static void get_block_text(uint16 block, char buf[8][9], int32 xoffset, int32 yoffset)
{
    int32  x, y;
    int32  bit;

    for (y=yoffset, bit=0; y < yoffset+4; y++) {
        for (x=xoffset; x < xoffset+4; x++, bit++)
            buf[y][x] = ((block & (1 << bit)) ? '*' : '.');
    }
}

/* Sort cages in ascending order by y-coordinate first, then by x-coordinate.
 */
static int rle_compare(const void* cage1, const void* cage2)
{
    const rle_cage*  c1;
    const rle_cage*  c2;

    c1 = (const rle_cage*)cage1;
    c2 = (const rle_cage*)cage2;

    if (c1->y < c2->y)
        return -1;
    else if (c1->y > c2->y)
        return 1;
    else if (c1->x < c2->x)
        return -1;
    else if (c1->x > c2->x)
        return 1;
    else
        return 0;
}

/* Process the specified row of four bits in block and add the appropriate characters/counts to
 * the RLE stream using rle_add. If first_bit > 0, only start outputting the row at that bit.
 */
static void rle_add_row(FILE* f, uint16 block, int32 bit_row, int32 first_bit)
{
    int32  bit;

    bit = bit_row * 4;
    if (first_bit < 1)
        rle_add(f, ((block & (1 << bit)) ? 'o' : 'b'), 1);
    bit++;
    if (first_bit < 2)
        rle_add(f, ((block & (1 << bit)) ? 'o' : 'b'), 1);
    bit++;
    if (first_bit < 3)
        rle_add(f, ((block & (1 << bit)) ? 'o' : 'b'), 1);
    bit++;
    if (first_bit < 4)
        rle_add(f, ((block & (1 << bit))   ? 'o' : 'b'), 1);
}

/* Add count items of the given type ('o', 'b', '$') to the RLE file stream, ending the stream if
 * obj is '!'.
 */
static void rle_add(FILE* f, char obj, uint32 count)
{
    static char    prev_obj       = '!';
    static uint32  prev_count     = 0;
    static uint32  saved_newlines = 0;

    if (!count)
        return;
    if (obj == prev_obj && obj != '!') {
        prev_count += count;
        return;
    }

    if (prev_obj != '!') {
        if (prev_obj == 'o' || obj == 'o') {
            if (saved_newlines) {
                rle_output(f, '$', saved_newlines);
                saved_newlines = 0;
            }
            rle_output(f, prev_obj, prev_count);
        } else if (obj == '$') {
            count += saved_newlines;
            saved_newlines = 0;
        } else if (prev_obj == '$')
            saved_newlines = prev_count;
    }

    if (obj == '!') {
        rle_output(f, '!', 1);
        saved_newlines = 0;
    }

    prev_obj = obj;
    prev_count = count;
}

/* Output the given object ('o', 'b', '$', or '!') to an RLE file, with the given count. If object
 * is '!', assume this is end of file.
 */
static void rle_output(FILE* f, char obj, uint32 count)
{
    static int32  line_len = 0;
    int32  nchars;

    nchars = ((count < 3) ? count : num_digits(count) + 1);
    if (line_len > RLE_MAX_COLS - nchars) {
        fprintf(f, newline);
        line_len = 0;
    }

    if (count == 1)
        putc(obj, f);
    else if (count == 2)
        fprintf(f, "%c%c", obj, obj);
    else
        fprintf(f, "%u%c", count, obj);

    if (obj == '!') {
        fprintf(f, newline);
        line_len = 0;
    } else
        line_len += nchars;
}

/* Print a list of x/y coordinate pairs to the given file for all live cells in the given block,
 * which begins at (startx,starty). The coordinates will be relative to a (0,0) middle-of-world.
 */
static void save_block_coordinates(FILE* f, uint16 block, int32 startx, int32 starty)
{
    int32  b;

    for (b=0; b < 16; b++) {
        if (block & (1 << b))
            fprintf(f, "%d %d%s", startx + b%4, starty + b/4, newline);
    }
}