#define _CRT_SECURE_NO_WARNINGS
#include <io.h>
#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;

long 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;
	}
	*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 = find_min(*head, &q, &position);
		deleteNth(head, position);
		first->next = NULL;

		list *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) - 3;
	if (size == 0)
		return 1;
	fseek(INPUT, 3, 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, 3, 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) {

	unsigned char tmp[17];

	unsigned char buffer[1];
	fread(buffer, sizeof(unsigned char), 1, INPUT);
	_itoa(array[(int)buffer[0]], tmp, 10);
	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);
	while (*size_source >= 8) {
		buffer[0] = (unsigned char)to_dec(CodeOfSymbol);
		*size_source = *size_source - 8;
		fwrite(buffer, sizeof(unsigned char), 1, OUTPUT);
	}
	return 0;
}

int create_out(FILE *INPUT, FILE *OUTPUT, long int *array) {
	long int b = 0, i = 0;
	unsigned char buffer[2];
	unsigned char CodeOfSymbol[17];
	size_t size_source = 0;
	fseek(INPUT, 0, SEEK_END);
	long int size = ftell(INPUT) - 3;
	fseek(INPUT, 3, 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);
			}
		}
	}
	for (int l = 0; l < b; l++) {
		encryption(INPUT, OUTPUT, array, CodeOfSymbol, &size_source);
	}
	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);
	}
	fseek(OUTPUT, 0, SEEK_SET);
	fwrite(&size, sizeof(long 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(unsigned 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];
	unsigned 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(unsigned char), 1, OUTPUT);
	}
}


//////////////////////////////////////////////////////////////////////////////////
//раскодировка файла
unsigned char buffer = 0;
size_t count = 0;

int readBit(FILE *in) {
	int res;
	size_t readed;
	if (count == 0) {
		readed = fread(&buffer, sizeof(unsigned char), 1, in);
		count = readed * 8;
	}
	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, long int *length, long int *alphavite) {
	fread(length, sizeof(long int), 1, file);
	*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;
	long int i, length = 0;
	list *pTree;

	readHeader(infile, &pTree, &length, alphavite);
	count = 0;
	for (i = 0; i<length; i++) {
		ch = decodeByte(infile, pTree);
		fputc(ch, outfile);
	}
}


int main(void) {
	list *head = malloc(sizeof(list));
	char buffer[4];
	if (head == NULL) {
		return 1;
	}
	head = NULL;
	FILE *INPUT;
	FILE *OUTPUT;
	long int alphavite[MAXVAL] = { 0 };
	INPUT = fopen("in.txt", "rb");
	if (!INPUT)
		return 2;
	_setmode(_fileno(INPUT), _O_BINARY);
	fgets(buffer, 4, INPUT);
	if (buffer[0] == 'c') {
		if (read_input(INPUT, alphavite)) {        //подсчитываем количество вхождений символов в файле
			return 0;
		}
		create_list(&head, alphavite);            //создаём список встречающихся символов
		create_tree(&head);                        //создаём бинарное дерево
		preOrderTravers(head, alphavite);        //обходим дерево
		OUTPUT = fopen("out.txt", "wb");
		_setmode(_fileno(OUTPUT), _O_BINARY);
		if (!OUTPUT) {
			return 4;
		}
		fseek(OUTPUT, sizeof(long int), SEEK_SET);
		create_descript(OUTPUT, head);        //записываем дерево
		tail(OUTPUT);                        //
		create_out(INPUT, OUTPUT, alphavite);        //создание шифрованного файла
		fclose(OUTPUT);
		fclose(INPUT);
	}
	else {
		if (buffer[0] == 'd') {
			OUTPUT = fopen("out.txt", "wb");
			_setmode(_fileno(OUTPUT), _O_BINARY);
			if (!OUTPUT)
				return 6;
			decode(INPUT, OUTPUT, alphavite);
			fclose(OUTPUT);
			fclose(INPUT);
		}
	}
	free(head);
	return 0;
}