#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Tree_t {//дерево
    char data;
    int weight;
    char str[256];
    struct Tree_t *left;
    struct Tree_t *right;
}tree;

typedef struct code_t { //структура для вывода дерева.
    unsigned long long code;
    int len;
}code_s;

unsigned char codes[256]; //для составления кода, во время обхода
int all_len;//не используется
unsigned char last_code; //сам код
int len_last_code; //длина последнего кода (для write_bit)
FILE *fout = fopen("out.txt", "wb");
int global;//для отладки

typedef struct queue_t { //Эта структура для слияния
    tree *tree;
    struct queue_t *next;
}queue;

tree *merge(tree *l, tree *r) { //слияние деревьев
    tree *new_tr = (tree*)calloc(1, sizeof(tree));
    new_tr->weight = l->weight + r->weight;
    new_tr->left = l;
    new_tr->right = r;
    return new_tr;
}

queue *enqueue(queue *head, tree *tree_t) { //добавление элемента в очередь с приоритетом
    queue *first, *second;
    queue *new_el = (queue*)calloc(1, sizeof(queue));
    new_el->tree = tree_t;
    new_el->next = NULL;

    if (head == NULL)
        return new_el;
    first = head;
    second = head->next;

    if (new_el->tree->weight <= first->tree->weight) {
        new_el->next = first;
        return new_el;
    }
    else {
        while (second) {
            if (new_el->tree->weight <= second->tree->weight)
                break;
            first = second;
            second = first->next;
        }
        first->next = new_el;
        new_el->next = second;
        return head;
    }
}

queue *build_haff_tree(queue *head) { //Строим дерево Хаффмана. Голову возвращаем, т.к. она может меняться в процессе
    queue *first = NULL, *second = NULL, *new_head = NULL;
    queue *tmp = head;
    tree *buf;

    first = tmp;
    second = tmp->next;
    new_head = second->next;

    buf = merge(first->tree, second->tree);
    head = enqueue(new_head, buf);
    free(first); free(second); //Удаляем элементы, которые уже вхоядт в новое дерево
    return head;
}

queue *create_start_tree(int *ascii, queue *head) { //создаем начальное дерево
    int i = 0;
    for (i = 0; i <= 255; i++) {
        if (ascii[i] != 0) {
                tree *new_tr = (tree*)calloc(1, sizeof(tree));
                new_tr->data = i;
                new_tr->weight = ascii[i];
                head = enqueue(head, new_tr);
        }
    }
    return head;
}

void clear_tree(tree *tree) {//удаление дерева
    if (tree == NULL) { return; }

    clear_tree(tree->left);
    clear_tree(tree->right);
    free(tree);
}

void input_ascii(FILE *fin, int *ascii) { //заполняем таблицу частоты
    while (!feof(fin)) {
        ascii[fgetc(fin)]++;
    }
}
void input_code_len(char **ascii, char *ascii_len) { //заполняем таблицу длины кодов
    for (int i = 0; i < 256; i++) {
        if (ascii[i] != NULL)
            ascii_len[i] = strlen(ascii[i]);
    }
}

void write_bit(code_s code, unsigned char sumbol) {//записываем дерево
    int i = 0;
    unsigned char out_bit = 0;
    unsigned char out_sumbol = 0;
    if (len_last_code != 0)
        i = len_last_code;
    out_bit = (128 >> (code.len + len_last_code));
    while (i <= code.len + len_last_code) {
        i++;
        if (i == 8) {
            out_sumbol = out_bit | last_code;
            fprintf(fout, "%c", out_sumbol);
            code.len = code.len - (8 - len_last_code);
            len_last_code = 0;
            i = 0;
            out_bit = 0;
            out_bit = (128 >> (code.len + len_last_code));
            global++;
        }
    }

    out_sumbol = out_bit | (sumbol >> i);
    fprintf(fout, "%c", out_sumbol);
    last_code = (sumbol << (8 - i));
    len_last_code = i;
    global++;
    return;
}

void write_tree_haffman(tree *tree, FILE *tree_out, char **ascii, code_s code) { //Составляем таблицу и записываем дерево в файл
    if ((tree->left == NULL) && (tree->right == NULL)) {
        tree->weight = strlen(tree->str);
        codes[tree->data] = code.code;
        if (codes[tree->data] != codes[0])
            write_bit(code, tree->data);
        return;
    }
    else {
        code_s c = code;
        c.code = (1 << c.len);
        c.len++;
        all_len++;
        strcpy(tree->left->str, tree->str);
        ascii[tree->left->data] = tree->left->str;
        tree->weight = strlen(tree->str);
        tree->left->str[tree->weight] = '0';
        write_tree_haffman(tree->left, tree_out, ascii, c);
        strcpy(tree->right->str, tree->str);
        ascii[tree->right->data] = tree->right->str;
        tree->right->str[tree->weight] = '1';
        write_tree_haffman(tree->right, tree_out, ascii, c);
    }
}

void print_text(FILE *fin, FILE *fout, char **ascii, char *ascii_len) { //переводим текст в код хаффмана
    char c;
    int last_len = 0;
    unsigned char out = 0;
    char *tmp;
    while (fscanf(fin, "%c", &c) != -1) {
        tmp = ascii[c];
        for (int j = 0; j < ascii_len[c]; j++) {
            last_len++;
            if (tmp[j] == '1')
                out = out | (1 << (8 - last_len));
            if (last_len == 8) {
                fprintf(fout, "%c", out);
                out = 0;
                last_len = 0;
            }
        }
    }
}

int main() {
    int ascii[260] = { 0 };
    char *ascii_code[260] = { NULL };
    char len_code[260] = { 0 };
    char c = 0;
    queue *head = NULL;
    queue *tmp_head = NULL;
    tree *tree_h = NULL;
    code_s code;
    code.code = 0;
    code.len = 0;
    global = 0;

    FILE *fin = fopen("in.txt", "rb");
    fscanf(fin, "%c", &c);

    input_ascii(fin, ascii); //заполняем массив частоты элементов
    head = create_start_tree(ascii, head); //создаем первые узлы и кидаем их в очередь с их приоритетом
    tmp_head = head;

    while (head->next != NULL)
        head = build_haff_tree(head); //создаем дерево Хаффмана

    tree_h = head->tree;
    tree_h->str[0] = 0;
    fseek(fin, 2, SEEK_SET);
    write_tree_haffman(tree_h, fout, ascii_code, code);
    if (len_last_code != 0)
        fprintf(fout, "%c", last_code);
    input_code_len(ascii_code, len_code);
    //print_text(fin, fout, ascii_code, len_code);
    fclose(fin); fclose(fout);
    return 0;
}