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

#define POOL_CAP 512

typedef struct node {
    bool is_char;
    char ch;

    size_t references;
    int direction; // 0 - left; 1 - right

    struct node *parent;
} node_t;

// void liner_insert(void base[.size * .nmemb + 1],
//                  size_t nmemb, size_t size, void *el,
//                  int (*compar)(const void [.size], const void [.size]));
void liner_insert(void *base, size_t nmemb, size_t size, void *el, int (*compar)(const void *, const void *));

int compare_nodes(const void *p1, const void *p2);

void node_char_init(node_t *node, size_t ref, char ch);
void node_link_init(node_t *node, node_t* left, node_t* right);
void node_print(node_t *node, int indent);

node_t pool[POOL_CAP];
size_t pool_sz;

node_t *encoding_table[256];

int main(int argc, char **argv)
{
    if(argc != 2) {
        fprintf(stderr, "ERROR: Not enough command line arguments\n");
        exit(1);
    }

    //-------------------------------------------------//

    pool_sz = 0;

    for(int i = 0; i < 256; i++)
        encoding_table[i] = NULL;

    //-------------------------------------------------//
    // Load the file data
    int times_seen[256] = {0};

    FILE *fp = fopen(argv[1], "rb");
    if(!fp) {
        fprintf(stderr, "ERROR: Could not open file %s\n", argv[1]);
        exit(1);
    }

    char mem[1024];
    size_t sz;
    while((sz = fread(mem, sizeof(char), 1024, fp)) != 0)
    {
        for(size_t i = 0; i < sz; i++) {
            times_seen[(size_t)mem[i]]++;
        }
        memset(mem, '\0', sizeof(char) * 1024);
    }
    rewind(fp);

    //-------------------------------------------------//
    // Load everything into nodes array and sort

    node_t *nodes[256];
    size_t nodes_sz = 0;

    for(int i = 0; i < 256; i++) {
        if(times_seen[i] <= 0) {
            continue;
        }

        nodes[nodes_sz] = malloc(sizeof(node_t));
        node_char_init(nodes[nodes_sz], times_seen[i], (char)i);
        encoding_table[i] = nodes[nodes_sz];
        nodes_sz++;
    }

    qsort(nodes, nodes_sz, sizeof(node_t *), compare_nodes);

    //-------------------------------------------------//
    // Continuously sort and build the tree

    while(nodes_sz != 1)
    {
        nodes_sz--;
        node_link_init(&pool[pool_sz], nodes[nodes_sz], nodes[nodes_sz-1]);

        liner_insert(nodes, nodes_sz-1, sizeof(node_t *), &pool[pool_sz++], compare_nodes);

        for(size_t i = 0; i < nodes_sz; i++)
            node_print(nodes[i], 0);
    }


    //-------------------------------------------------//

    for(int i = 0; i < 256; i++)
        if(encoding_table[i] != NULL) free(encoding_table[i]);
    fclose(fp);
    return 0;
}

void liner_insert(void *base, size_t nmemb, size_t size, void *el, int (*compar)(const void *, const void *))
{
    for(size_t i = 0; i < nmemb; i++)
    {
        void *cur = base + (i * size);
        if(compar(cur, &el) < 0) continue;

        for(size_t j = nmemb; j >= i; j--) {
            void *src = base + (j * size);
            void *dest = src + size;
            memcpy(dest, src, size);
        }

        memcpy(cur, &el, size);
        break;
    }
}

int compare_nodes(const void *p1, const void *p2)
{
    // printf("ff\t%d %d\n", (*(node_t **)p2)->references, (*(node_t **)p1)->references);
    return (*(node_t **)p2)->references - (*(node_t **)p1)->references;
}

void node_char_init(node_t *node, size_t ref, char ch)
{
    node->is_char = true;
    node->ch = ch;
    node->references = ref;
    node->parent = NULL;
}

void node_link_init(node_t *node, node_t* left, node_t* right)
{
    node->is_char = false;
    node->references = left->references + right->references;
    node->parent = NULL;

    left->parent = node;
    right->parent = node;
    left->direction = 0;
    right->direction = 1;
}

void node_print(node_t *node, int indent)
{
    for(int i = 0; i < indent; i++) printf(" ");
    printf("ref: %ld\n", node->references);


    if(node->is_char) {
        for(int i = 0; i < indent; i++) printf(" ");
        printf("char: %c\n", node->ch);
    } else {
        for(int i = 0; i < indent; i++) printf(" ");
        printf("link thing\n");
    }

    if(node->parent != NULL) {
        for(int i = 0; i < indent; i++) printf(" ");
        printf("dir: %d\n", node->direction);        node_print(node->parent, indent + 4);
    }
}