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

#define MAXVAL 256

typedef struct list {
    long int data;
    int symbol;
    struct list *next;
    struct list *left;
    struct list *right;
} list;

/* reverse:  переворачиваем строку s на месте */
void reverse(unsigned char s[])
{
    size_t i, j;
    unsigned char c;

    for (i = 0, j = strlen((const char *) s) - 1; i < j; i++, j--) {
        c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}

/* itoa:  конвертируем n в символы в s */
void itoa(long int n,unsigned char s[])
{
    long int sign;
    int i;

    if ((sign = n) < 0)  /* записываем знак */
        n = -n;          /* делаем n положительным числом */
    i = 0;
    do {       /* генерируем цифры в обратном порядке */
        s[i++] = (unsigned char) (n % 10 + '0');   /* берем следующую цифру */
    } while ((n /= 10) > 0);     /* удаляем */
    if (sign < 0)
        s[i++] = '-';
    s[i] = '\0';
    reverse(s);
}

long int separate(long int a, long int *b) {
    *b = a % MAXVAL;
    return (a / MAXVAL);
}

void push(list **head, long int data, int symbol) {
    list *tmp = (list *) malloc(sizeof(list));
    tmp->data = data;
    tmp->symbol = symbol;
    tmp->right = NULL;
    tmp->left = NULL;
    tmp->next = (*head);
    (*head) = tmp;

}


void create_list(list **head, long int *array) {
    int i;
    for (i = 0; i < MAXVAL; i++) {
        if (array[i] != 0)
            push(head, array[i], i);
    }
}

void create_table(unsigned char *array, long int *table, long int size) {
    for (long int i = 0; i < size; i++) {
        table[(int) array[i]]++;
    }
}

list *getNth(list *head, int n) {
    int counter = 0;
    while (counter < n && head) {
        head = head->next;
        counter++;
    }
    return head;
}

void deleteNth(list **head, int n) {
    if (n != 0) {
        list *prev = getNth(*head, n - 1);
        list *elm = prev->next;
        prev->next = elm->next;
        //free(elm);
    }
    else{
        (*head)=(*head)->next;
    }
}

list *find_min(list *head, long int *count, int *position) {
    list *tmp = malloc(sizeof(list));
    if (tmp==NULL){
        exit(1);
    }
    int i = 0;
    tmp = head;
    long int min = head->data;
    *position = 0;
    head = head->next;
    while (head != NULL) {
        i++;
        if (head->data < min) {
            min = head->data;
            tmp = head;
            (*position) = i;
        }
        head = head->next;
    }
    //int ERR = deleteNth(&head,position);
    *count = min;
    return tmp;
}

char code[9] = {"1"};
int count_stack = 1;

void preOrderTravers(list *root, long int *array) {
    if (root->left != NULL) {
        strcpy(&code[count_stack++], "0");
        preOrderTravers(root->left, array);
    }
    if (root->right != NULL) {
        strcpy(&code[count_stack++], "1");
        preOrderTravers(root->right, array);
    }
    if (root->symbol >= 0) {
        array[root->symbol] = atoi(code);
    }
    count_stack = (count_stack == 0) ? 1 : count_stack;
    strcpy(&code[--count_stack], "\0");
}

void create_tree(list **head) {
    long int q, e;
    int position;
    while ((*head)->next != NULL) {
        list *tmp = malloc(sizeof(list));
        q = 0;
        e = 0;

        list *first = malloc(sizeof(list));
        if (first==NULL){
            exit(1);
        }
        first = find_min(*head, &q, &position);
        deleteNth(head, position);
        first->next = NULL;

        list *second = malloc(sizeof(list));
        if (second==NULL){
            exit(1);
        }
        second = find_min(*head, &e, &position);
        deleteNth(head, position);
        second->next = NULL;

        tmp->data = q + e;
        tmp->left = first;
        tmp->symbol=-1;
        tmp->right = second;
        tmp->next = (*head);//////////
        (*head) = tmp;
    }
}

int read_input(FILE *INPUT, long int *array) {
    unsigned char buffer[MAXVAL];
    long int b;
    int i = 0;
    fseek(INPUT, 0, SEEK_END);
    long int size = ftell(INPUT);
    fseek(INPUT, 0, SEEK_SET);
    long int count = separate(size, &b);
    if (count == 0) {
        fread(buffer, sizeof(unsigned char), (size_t) b, INPUT);
        create_table(buffer, array, b);
    } else {
        for (i = 0; i < count; i++) {
            fread(buffer, sizeof(unsigned char), MAXVAL, INPUT);
            create_table(buffer, array, MAXVAL);
        }
        fread(buffer, sizeof(unsigned char), (size_t) b, INPUT);
        create_table(buffer, array, b);
    }
    fseek(INPUT, 0, SEEK_SET);
    return 0;
}

int to_dec(unsigned char *array) {
    int a = 0;
    for (int i = 0; i < 8; i++) {
        a =  a+(array[i] - '0') *(int)pow(2, 8 - i - 1);
        array[i] = array[8 + i];
    }
    return a;
}

void together(unsigned char *a, unsigned char *b, size_t size_a) {
    int j = 0;
    size_t size_b = strlen((const char *) b);
    for (size_t i = size_a; i < (size_a + size_b); i++) {
        a[i] = b[j++];
    }
}

int encryption(FILE *INPUT, FILE *OUTPUT, long int *array, unsigned char *CodeOfSymbol, size_t *size_source, int *kol) {

    unsigned char tmp[17];

    unsigned char buffer[1];
    fread(buffer, sizeof(unsigned char), 1, INPUT);
    itoa(array[(int) buffer[0]], tmp);
    size_t size = strlen((const char *) tmp);
    for (size_t j = 0; j < size; j++) {
        tmp[j] = tmp[j + 1];
    }
    together(CodeOfSymbol, tmp, *size_source);
    *size_source = (size_t)(*size_source + size - 1);
    if (*size_source >= 8) {
        buffer[0] = (unsigned char) to_dec(CodeOfSymbol);
        *size_source = *size_source - 8;
        fwrite(buffer, sizeof(unsigned char), 1, OUTPUT);
        (*kol)++;
    }
    return 0;
}

int create_out(FILE *INPUT, FILE *OUTPUT, long int *array) {
    long int b = 0, i = 0;
    int kol = 0;
    unsigned char buffer[2];
    unsigned char CodeOfSymbol[17];
    size_t size_source = 0;
    fseek(INPUT, 0, SEEK_END);
    long size = ftell(INPUT);
    fseek(INPUT, 0, SEEK_SET);
    long int count = separate(size, &b);

    if (count != 0) {
        for (int j = 0; j < count; j++) {
            for (i = 0; i < MAXVAL; i++) {
                encryption(INPUT, OUTPUT, array, CodeOfSymbol, &size_source, &kol);
            }
        }
    }
    for (int l = 0; l < b; l++) {
        encryption(INPUT, OUTPUT, array, CodeOfSymbol, &size_source, &kol);
    }
    if (size_source > 0) {
        for (i = size_source; i < 8; i++) {
            CodeOfSymbol[i] = '0';
        }
        buffer[0] = (unsigned char) to_dec(CodeOfSymbol);
        strcpy((char *) &buffer[1], "\0");
        fwrite(buffer, sizeof(unsigned char), 1, OUTPUT);
        kol++;
    }
    fseek(OUTPUT, 0, SEEK_SET);
    printf("%d", kol);
    fwrite(&kol, sizeof(int), 1, OUTPUT);
    return 0;
}


char description[100];
int count_des = 0;

void push_element(void) {
    strcpy(&description[count_des++], "1");
}

void push_symbol(int a) {
    char array[8];
    int i = 0;
    int j = 0;
    while (a > 0) {
        array[i++] = (char) (a % 2 + '0');
        a = a / 2;
    }
    for (j = 0; j < 8 - i; j++) {
        description[count_des++] = '0';
    }
    i--;
    for (j = 0; j < i+1; j++) {
        description[count_des++] = array[i - j];
    }
}

void shift(FILE *OUTPUT) {
    int i;
    unsigned char buffer[8];
    unsigned char symbol[1];
    while (count_des >= 8) {
        strncpy((char *) buffer, description, 8);
        for (i = 0; i < count_des - 8; i++) {
            description[i] = description[i + 8];
        }
        count_des = count_des - 8;
        symbol[0] = (unsigned char) to_dec(buffer);
        fwrite(symbol, sizeof(char), 1, OUTPUT);
    }
}

void create_descript(FILE *OUTPUT, list *root) {
    if (root->left != NULL) {
        push_element();
        create_descript(OUTPUT, root->left);
    }
    if (root->right != NULL) {
        push_element();
        create_descript(OUTPUT, root->right);
    }
    if (root->symbol >= 0) {
        strcpy(&description[count_des++], "0");
        push_symbol(root->symbol);
        if (count_des >= 8) {
            shift(OUTPUT);
        }
    }
}

void tail(FILE *OUTPUT) {
    unsigned char buffer[8];
    char symbol[1];
    if (count_des != 0) {
        for (int i = count_des; i < 8; i++) {
            description[i] = '0';
        }
        strncpy((char *) buffer, description, 8);
        symbol[0] = (unsigned char) to_dec(buffer);
        fwrite(symbol, sizeof(char), 1, OUTPUT);
    }
}


//////////////////////////////////////////////////////////////////////////////////
unsigned char buffer = 0;
size_t count = 0;
size_t ask=0;

int readBit(FILE *in) {
    int res;
    size_t readed;
    if (count == 0) {
        readed = fread(&buffer, sizeof(unsigned char), 1, in);
        count = readed * 8;
        ask++;
    }
    res = buffer & 0x80; // 0x80 == _1_0000000
    buffer = buffer << 1;
    count--;
    return res;
}

int readByte(FILE *in) {
    int i, res = 0;
    for (i = 0; i < 8; i++) {
        res = res << 1;
        if (readBit(in)) {
            res |= 1;
        }
    }
    return res;
}

list *readHuffmansTree(FILE *file) {
    list *node = malloc(sizeof(list));

    if (readBit(file)==0) {
        node->symbol = readByte(file);
        node->data = 0;
        node->left = NULL;
        node->right = NULL;
    } else {
        node->symbol = -1;
        node->data = 0;
        node->left = readHuffmansTree(file);
        readBit(file);
        node->right = readHuffmansTree(file);
    }
    return node;
}


void readHeader(FILE *file, list **ppTree, unsigned int *length, long int *alphavite) {
    fread(length, sizeof(unsigned int), 1, file);
    printf("%d", *length);
    *ppTree = readHuffmansTree(file);
    preOrderTravers(*ppTree, alphavite);
}

int decodeByte(FILE *in, list *tree) {
    if (tree->symbol != -1) {
        return tree->symbol;
    } else if (readBit(in)) {
        return decodeByte(in, tree->right);
    } else {
        return decodeByte(in, tree->left);
    }
}

void decode(FILE *infile, FILE *outfile, long int *alphavite) {
    int  ch;
    unsigned int length = 0;
    list *pTree;

    readHeader(infile, &pTree, &length, alphavite);
    count=0;
    ask=0;
    while(ask!=length) {
        ch = decodeByte(infile, pTree);
        fputc(ch, outfile);
    }
}

int main(void) {
    list *head = malloc(sizeof(list));
    if (head==NULL){
        return 1;
    }
    head = NULL;
    FILE *INPUT;
    FILE *OUTPUT;
    long int alphavite[MAXVAL] = {0};
        INPUT = fopen("S1.txt", "rb");
        if (!INPUT)
            return 1;

        if (read_input(INPUT, alphavite)) {        //подсчитываем количество вхождений символов в файле
            return 1;
        }
        create_list(&head, alphavite);            //создаём список встречающихся символов
        create_tree(&head);                        //создаём бинарное дерево
        preOrderTravers(head, alphavite);        //обходим дерево
        OUTPUT = fopen("new.txt", "wb+");
        if (!OUTPUT)
            return 1;
        fseek(OUTPUT,sizeof(int), SEEK_SET);
        create_descript(OUTPUT, head);        //записываем дерево
        tail(OUTPUT);                        //
        create_out(INPUT, OUTPUT, alphavite);        //создание шифрованного файла
        fclose(OUTPUT);
        fclose(INPUT);

        INPUT = fopen("new.txt", "rb");
        if (!INPUT)
            return 1;

        OUTPUT = fopen("old.txt", "wb+");
        if (!OUTPUT)
            return 1;

        decode(INPUT, OUTPUT, alphavite);
        fclose(OUTPUT);
        fclose(INPUT);
    free(head);
    return 0;
}