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

typedef struct counter_pair {
    char new_symb_code[30];
    char symb_code[30];//двоичный код символа
    int count;// сколько раз символ встретился
    struct counter_pair *left;
    struct counter_pair *right;
} table;

table *make_tree(table *psym[], int k)//рeкурсивная функция создания дерева Хофмана
{
    table *temp = malloc(sizeof(table));
    temp->count = psym[k - 1]->count + psym[k - 2]->count;
    temp->new_symb_code[0] = 0;
    temp->left = psym[k - 1];
    temp->right = psym[k - 2];

    if (k == 2)
        return temp;
    else //внесение в массив в нужное место элемента дерева Хофмана
    {
        for (int i = 0; i < k; i++)
            if (temp->count > psym[i]->count) {
                for (int j = k - 1; j > i; j--)
                    psym[j] = psym[j - 1];

                psym[i] = temp;
                break;
            }
    }
    return make_tree(psym, k - 1);
}

void clear(table *dictf,
                int size) { ///очистка указателей в массиве от мусора(нужна для того, чтобы в void recode не передавались
    for (int i = 0; i < size; i++) { ///указатели на несуществующие узлы(структуры))
        dictf[i].left = 0;
        dictf[i].right = 0;
        dictf[i].new_symb_code[0] = 0;
    }
}

void make_code(table *root)//Рекурсивная функция кодирования
{
    if (root->left) {
        strcpy(root->left->new_symb_code, root->new_symb_code);
        strcat(root->left->new_symb_code, "0");
        if (root->left->count > 0) make_code(root->left);
    }
    if (root->right) {
        strcpy(root->right->new_symb_code, root->new_symb_code);
        strcat(root->right->new_symb_code, "1");
        if (root->right->count > 0) make_code(root->right);
    }
}

//функция для сортировки статистики
void sort(table numbers[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (numbers[j].count < numbers[j + 1].count) {
                table temp = numbers[j];
                numbers[j] = numbers[j + 1];
                numbers[j + 1] = temp;
            }
        }
    }
}

//функция, осуществляющая перевод считанного символа в двоичный код и последующая запись в строку
int DecimalToBinary(int dec, char *s) {
    int bin[50] = {0};

    int i = 0;
    while (dec > 0) {       //перевод в двоичную СС
        bin[i] = dec % 2;
        dec = dec / 2;
        ++i;
    }

    //записываю двоичный код в строку и переворачиваю
    int bits = 8;
    if (i > 8) {
        bits = 8 * ((i + 7) / 8);
    }
    int n = 0;
    for (int j = bits - 1; j >= 0; j--) {
        n += sprintf((s + n), "%d", bin[j]);
    }
    return dec;
}

int count_comp(table *byte, int size, int len) {
    int first = 0;
    int second = 0;
    for (int i = 0; i < size; i++) {
        first += byte[i].count;
        second += (int) (byte[i].count * strlen(byte[i].new_symb_code));
    }
    first *= len;
    printf("Размер до сжатия: %d\nРазмер после сжатия: %d\n", first, second);
    return 0;
}

int main() {
    int input;
    printf("Какую статистику хотите получить?(для 8 бит введите 1, для 12 бит введите 2, для 16 бит введите 3, для 20 бит введите 4)\n");
    scanf("%d", &input);
    FILE *text = fopen("text.txt", "r");
    if (!text) {
        printf("Error of file opening.\n");
        return 1;
    }
    //на данном этапе высчитавю количество символов в текстовом файле и задаю количетсво символов при 8 12 16 20 битах соответственно
    fseek(text, 0, SEEK_END);
    int text_lenght = ftell(text);
    int text_lenght1 = (text_lenght * 8) / 12;
    int text_lenght2 = (text_lenght * 8) / 16;
    int text_lenght3 = (text_lenght * 8) / 20;
    fseek(text, 0, SEEK_SET);
    //записываю в структуру коды символов по 8 бит, обнуля счетчик повтора
    if (input == 1) {
        table byte8[256];
        for (int i = 0; i < 256; i++) {
            byte8[i].count = 0;
        }
        table *psym[256];
        int j = 0;
        int flag = 0;
        while (!feof(text)) {
            int k = getc(text);
            char *byte1 = calloc(8, sizeof(char) + 1);
            DecimalToBinary(k, byte1);
            flag = 0;
            for (int i = 0; i < 256; i++) {
                if (strcmp(byte8[i].symb_code, byte1) == 0) {
                    flag = 1;
                    byte8[i].count += 1;
                }

            }
            if (flag == 0) {
                strcpy(byte8[j].symb_code, byte1);
                j++;
            }
        }
        for (int i = 0; i < j; i++) {
            if (byte8[i].count == 0)
                byte8[i].count += 1;
        }
        for (int i = 0; i < j; i++) //в массив указателей заносим адреса записей
            psym[i] = &byte8[i];

        sort(byte8, j);
        clear(byte8, j);
        table *root = make_tree(psym, j);
        make_code(root);
        for (int i = 0; i < j; i++) {

            printf("%s - %d   %s\n", byte8[i].symb_code, byte8[i].count, byte8[i].new_symb_code);
        }
        printf("количество символов: %d\n", text_lenght);
        count_comp(byte8, j, 8);
        //записываю в структуру коды символов по 12 бит, обнуля счетчик повтора
    } else if (input == 2) {
        table byte12[4096];
        for (int i = 0; i < 4096; i++) {
            byte12[i].count = 0;
        }
        table *psym[4096];
        int j = 0;
        int flag = 0;
        while (!feof(text)) {
            int b1 = getc(text);
            int b2 = getc(text);
            int b3 = getc(text);
            //сдвигаю первый байт на 4 сдвигаю второй байт на 4 и соединяю их логическим или
            int k = (b1 << 4) | (b2 >> 4);
            //к 3 байту логическим или добавляю последние 4 бита 2 байта
            int k1 = (b3) | ((b2 & 15) << 8);
            char *byte1 = calloc(12, sizeof(char) + 1);
            DecimalToBinary(k, byte1);
            flag = 0;
            for (int i = 0; i < 4096; i++) {
                if (strcmp(byte12[i].symb_code, byte1) == 0) {
                    flag = 1;
                    byte12[i].count += 1;
                }
            }
            if (flag == 0) {
                strcpy(byte12[j].symb_code, byte1);
                j++;
            }
            byte1 = calloc(12, sizeof(char) + 1);
            DecimalToBinary(k1, byte1);
            flag = 0;
            for (int i = 0; i < 4096; i++) {
                if (strcmp(byte12[i].symb_code, byte1) == 0) {
                    flag = 1;
                    byte12[i].count += 1;
                }
            }
            if (flag == 0) {
                strcpy(byte12[j].symb_code, byte1);
                j++;
            }
        }
        for (int i = 0; i < j; i++) {
            if (byte12[i].count == 0)
                byte12[i].count += 1;
        }
        for (int i = 0; i < j; i++) //в массив указателей заносим адреса записей
            psym[i] = &byte12[i];
        sort(byte12, j);
        clear(byte12, j);
        table *root = make_tree(psym, j);
        make_code(root);
        for (int i = 0; i < j; i++) {

            printf("%016s - %d   %s\n", byte12[i].symb_code, byte12[i].count, byte12[i].new_symb_code);
        }
        printf("количество символов: %d\n", text_lenght1);
        count_comp(byte12, j, 12);


        //записываю в структуру коды символов по 16 бит, обнуля счетчик повтора
    } else if (input == 3) {
        table byte16[65536];
        for (int i = 0; i < 65536; i++) {
            byte16[i].count = 0;
        }
        table *psym[65536];
        int j = 0;
        int flag = 0;
        while (!feof(text)) {
            int b1 = getc(text);
            int b2 = getc(text);
            //сдвигаю первый байт на 8 и логическим или добавляю второй байт
            int k = ((b1 << 8) | (b2));
            char *byte1 = calloc(16, sizeof(char) + 1);
            DecimalToBinary(k, byte1);
            flag = 0;
            for (int i = 0; i < 65536; i++) {
                if (strcmp(byte16[i].symb_code, byte1) == 0) {
                    flag = 1;
                    byte16[i].count += 1;
                }
            }
            if (flag == 0) {
                strcpy(byte16[j].symb_code, byte1);
                j++;
            }

        }
        for (int i = 0; i < j; i++) {
            if (byte16[i].count == 0)
                byte16[i].count += 1;
        }

        for (int i = 0; i < j; i++) //в массив указателей заносим адреса записей
            psym[i] = &byte16[i];
        sort(byte16, j);
        clear(byte16, j);
        table *root = make_tree(psym, j);
        make_code(root);
        for (int i = 0; i < j; i++) {

            printf("%016s - %d   %s\n", byte16[i].symb_code, byte16[i].count, byte16[i].new_symb_code);
        }
        printf("количество символов: %d\n", text_lenght2);
        count_comp(byte16, j, 16);

        //записываю в структуру коды символов по 20 бит, обнуля счетчик повтора
    } else if (input == 4) {
        table byte20[10485];
        for (int i = 0; i < 10485; i++) {
            byte20[i].count = 0;
        }
        table *psym[10485];
        int j = 0;
        int flag = 0;
        while (!feof(text)) {
            int b1 = getc(text);
            int b2 = getc(text);
            int b3 = getc(text);
            int b4 = getc(text);
            int b5 = getc(text);
            // сдвигаю первый байт на 12 бит и второй байт на 4 бита  а третий на 4 бита и соездиняю их логическим или
            int k = ((b1 << 12) | ((b2 << 4) | (b3 >> 4)));
            //сдвигаю 4 байт на 8 бит а оставшуюся часть 3 байта сдвигаю на 16 бит и соединяю логическим или с 4 и 5 байтом
            int k1 = ((b4 << 8) | (b5) | (b3 & 15) << 16);
            char *byte1 = calloc(20, sizeof(char) + 1);
            DecimalToBinary(k, byte1);
            flag = 0;
            for (int i = 0; i < 10485; i++) {
                if (strcmp(byte20[i].symb_code, byte1) == 0) {
                    flag = 1;
                    byte20[i].count += 1;
                }
            }
            if (flag == 0) {
                strcpy(byte20[j].symb_code, byte1);
                j++;
            }
            byte1 = calloc(20, sizeof(char) + 1);
            DecimalToBinary(k1, byte1);
            flag = 0;
            for (int i = 0; i < 10485; i++) {
                if (strcmp(byte20[i].symb_code, byte1) == 0) {
                    flag = 1;
                    byte20[i].count += 1;
                }
            }
            if (flag == 0) {
                strcpy(byte20[j].symb_code, byte1);
                j++;
            }
        }

        for (int i = 0; i < j; i++) {
            if (byte20[i].count == 0)
                byte20[i].count += 1;
        }

        for (int i = 0; i < j; i++) //в массив указателей заносим адреса записей
            psym[i] = &byte20[i];
        sort(byte20, j);
        clear(byte20, j);
        table *root = make_tree(psym, j);
        make_code(root);
        for (int i = 0; i < j; i++) {

            printf("%024s - %d   %s\n", byte20[i].symb_code, byte20[i].count, byte20[i].new_symb_code);
        }
        printf("количество символов: %d\n", text_lenght3);
        count_comp(byte20, j, 20);
    }

    return 0;
}