#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <errno.h>
#include <stdbool.h>
#include <string.h>

#include "evil.h"

typedef struct numbers {
        /* Linked list */
        int32_t value;
        struct numbers* next;
} numbers_t;

typedef struct queue {
        /* Circular buffer */
        int head;
        int tail;
        uint32_t *data;
} queue_t;

/* Add an entry to evilDB for value:
 *      ref <operator> parent = value
 */
static bool addEntry(uint32_t value, uint32_t ref, uint32_t parent, operator_t operator, uint64_t *db) {
        if (((value & INDEXMASK) != value)
                        || ((parent & INDEXMASK) != parent)) {
                return false;
        }
        if (0 == db[value]) {
                db[value] = (((uint64_t) parent) << 32) + ref + (operator << INDEXBITS);
                return true;
        }
        else {
                return false;
        }
}

/* Try to add a new combination of numbers to the database.
 * Do nothing if the result is already in the database.
 * 
 * returns true if it encounters an error it can't recover from.
 */
static bool queueOperation(uint32_t a, uint32_t b, uint32_t op, uint64_t *db, queue_t *q, int max) {
        uint32_t result;
        switch (op) {
                case ADD:
                        result = b + a;
                        break;
                case SUB:
                        if (a >= b) {
                                return false;
                        }
                        result = b - a;
                        break;
                case MUL:
                        result = b * a;
                        break;
                case DIV:
                        if ((0 == a) || ((b%a) > 0)) {
                                return false;
                        }
                        result = b / a;
                        break;
                case PAL:
                        if (0 == b%10) {
                                return false;
                        }
                        result = 0;
                        uint32_t tmp = b;
                        while (b > 0) {
                                result *= 10;
                                result += b%10;
                                b /= 10;
                        }
                        b = tmp;
                        break;
                default:
                        printf("Invalid operation\n");
                        return true;
                        break;
        }
        if (result > max){
                return false;
        }
        if (addEntry(result, a, b, op, db)) {
                /* Operation created new entry in DB */
                q->data[q->tail] = result;
                q->tail += 1;
                q->tail %= max;
                if (q->tail == q->head) {
                        printf("Queue overflow at number %d!\n", result);
                        return true;
                }
        }
        return false;
}

static void cleanup(uint64_t *db, queue_t *queue, numbers_t *numbers) {
        /* Clean up */
        if (NULL != db) free(db);
        if (NULL != queue->data) free(queue->data);
        while (NULL != numbers) {
                numbers_t *next = numbers->next;
                free(numbers);
                numbers = next;
        }
}

int main(int argc, char *argv[]) {
        /* Parse input parameters */
        char line[256] = {0};
        char *dbfile = NULL;
        char *txtfile = NULL;
        int size = 0;
        for (int i = 1; i<argc; i++) {
                int len = strlen(argv[i]);
                if ((len > 4) && (strcmp(argv[i] + len - 4, ".txt") == 0)) {
                        txtfile = argv[i];
                        printf("Using %s for reference.\n", txtfile);
                } else if ((len > 3) && (strcmp(argv[i] + len - 3, ".db") == 0)) {
                        dbfile = argv[i];
                        printf("Using %s as database.\n", dbfile);
                } else {
                        size = atoi(argv[i]);
                }
        }
        if (0 == size) {
                size = 1000*1000;
        }

        /* Load evil numbers */
        numbers_t *evil = NULL;
        FILE *fp = NULL;
        if (NULL != txtfile) {
                fp = fopen(txtfile, "r");
        } else {
                fp = fopen("evil.txt", "r");
        }
        if (NULL == fp) {
                perror("fopen");
                exit(5);
        } else {
                int count = 0;
                while (fgets(line, sizeof(line), fp)) {
                        numbers_t *head = (numbers_t *) malloc(sizeof(numbers_t));
                        if (NULL == head) {
                                printf("malloc error: %d\n", errno);
                                cleanup(NULL, NULL, evil);
                                exit(2);
                        }
                        head->value = atoi(line);
                        head->next = evil;
                        evil = head;
                        count++;
                }
                fclose(fp);
                printf("Using %d evil numbers to map the world...\n", count);
        }

        /* Initialize breath-first search with 0 */
        queue_t queue;
        queue.head = 0;
        queue.data = malloc(size * sizeof(uint32_t));
        queue.data[0] = 0;
        queue.tail = 1;

        /* Fill DB */
        uint64_t *db = calloc(size, sizeof(uint64_t));
        while (queue.tail != queue.head) {
                uint32_t parent = queue.data[queue.head];
                queue.head += 1;
                queue.head %= size;
                numbers_t *candidate = evil;
                bool error = false;
                error |= queueOperation(0, parent, PAL, db, &queue, size);
                while (NULL != candidate) {
                        error |= queueOperation(candidate->value, parent, ADD, db, &queue, size);
                        error |= queueOperation(candidate->value, parent, SUB, db, &queue, size);
                        error |= queueOperation(candidate->value, parent, MUL, db, &queue, size);
                        error |= queueOperation(candidate->value, parent, DIV, db, &queue, size);
                        candidate = candidate->next;
                        if (error) {
                                cleanup(db, &queue, evil);
                                exit(1);
                        }
                }
        }

        /* Persist DB */
        FILE *out = NULL;
        if (NULL != dbfile) {
                out = fopen(dbfile, "wb");
        } else {
                out = fopen("evil.db", "wb");
        }
        if (NULL == out) {
                perror("fopen");
        } else {
                fwrite(db, sizeof(uint64_t), size, out);
                fclose(out);
        }
        cleanup(db, &queue, evil);
        exit(0);
}