Haffman Algorithm.h


/*!
	\file
	\brief Заголовочный файл с описанием функций и структур
	Данный файл содержит в себе определение структуры Node, и определения функций, используемых в программе.
*/

#ifndef HAFFMAN_ALGORITHM_H
#define HAFFMAN_ALGORITHM_H

#include <string>
#include <unordered_map>

/*!
	\brief Структура узла дерева Хаффмана
	Узел дерева Хаффмана содержит символ, частоту его появления, а также указатель на сопряжённые ветви.
*/
struct Node {
	char ch = 0;
	int freq = 0;
	Node* left = nullptr, * right = nullptr;

	Node() {}
	Node(char val) {
		ch = val;
	}

	Node(char character, Node* left, Node* right) {
		Node* node = new Node();

		ch = character;
		freq = 0;
		left = left;
		right = right;
	}
};

//! \brief Структура, описывающая операцию сравнения элементов для приоритетной очереди
struct comp {
	bool operator()(Node* l, Node* r) {
		return l->freq > r->freq;
	}
};


/*!	\defgroup main_functions
	\brief Функции, основного файла программы (main.cpp)
	@{
*/
/*!
		\brief Функция для определения задачи (сжатие / разархивация)
		\param[in] argv[] Переданные в командную строку аргументы
		\return При ключе -en | -encode возвращает 1. При -de | -decode возвращает -1
*/
int check_task(char* argv[]);
/*! @} */


/*!	\defgroup fstream_functions
	\brief Функции, имеющие отношение к работе с файлами (fstream.cpp)
	@{
*/
/*!
		\brief Функция для генерации имени сжатого файла
		\param[in] original Название исходного файла
		\return Строка с названием для сжатых файлов
*/
std::string gen_en_filename(std::string original);

/*!
		\brief Функция для генерации имени разархивированного файла
		\param[in] original Название исходного файла
		\return Строка с названием для разархивиронных файлов
*/
std::string gen_de_filename(std::string original);

/*!
		\brief Функция для записи кол-ва дополнительных нулей в бинарный файл
		\param[in] outfile файл, открытый в бинарном режиме
		\param[in] bits Кол-во дополнительных нулей (0 <= bits < 8)
*/
void insert_zeros_counter(std::ofstream& outfile, int bits);

/*!
		\brief Функция для записи битовой строки в бинарный файл
		\details Эта функция упаковывает восемь битов в байт,
		затем записывает его в бинарный файл. Последний байт
		при необходимости заполняется дополнительными нулями
		\param[in] outfile файл, открытый в бинарном режиме 
		\param[in] str битовая строка
*/
void writeBinaryString(std::ofstream& outfile, std::string& str);

/*!
		\brief Функция для генерации строковой репрезентации бинарного дерева Хаффмана
		\details Для генерации строковой репрезентации дерева используется
		прямой обход (NLR). Если текущий узел является листом (не имеет потомков)
		, то в строку добавляется единица и символ этого узла. Если текущий узел
		не является листом, в строку записывается ноль и происходит рекурсивный вызов функции
		\param[in] node Указатель на корень дерева
		\param[in] result Ссылка на строку, в которой будет сохранён результат
*/
void writeBinaryTree(Node* node, std::string& result);

/*!
		\brief Функция для генерации бинарного дерева Хаффмана на основе его строковой репрезентации
		\details Если текущий символ равен единице, это значит, что следующий за ней символ является листом
		\param[in] str Ссылка на строку, в которой содержится строковая репрезентация дерева Хаффмана
		\param[in] index Ссылка на индекс
		\return Указатель на корень дерева
*/
Node* readBinaryTree(std::string& str, int& index);

/*!
		\brief Функция для считывания исходного текста
		\param[in] name Ссылка на имя файла
		\param[in] text Ссылка на строку, в которую будет сохранён результат
		\return При успешном считывании - 1, иначе - 0
*/
int parse_file(std::string& name, std::string& text);

/*!
		\brief Функция для считывания строковой репрезентации дерева из бинарного файла
		\param[in] infile Ссылка на файл, открытый в двоичном режиме
		\param[in] text Ссылка на строку, в которую будет сохранён результат
		\return Длина строковой репрезентации дерева
*/
int parse_tree(std::ifstream& infile, std::string& text);

/*!
		\brief Функция для считывания байтов текста из бинарного файла
		\details В заархивированном файле первый символ означает кол-во
		дополнительных нулей вставленных функцией Flush_Bits(). Следующее за ним
		число - длина строковой репрезентации дерева. Затем следует разделительный
		символ, непосредственно строковая репрезентация дерева, и сжатый текст.
		\param[in] infile Ссылка на файл, открытый в двоичном режиме
		\param[in] text Ссылка на строку, в которую будет сохранён результат
		\param[in] tree_size Длина строковой репрезентации дерева
		\param[in] zeros Кол-во дополнительных нулей
*/
void parse_binary_text(std::ifstream& infile, std::string& text, int tree_size, int zeros);
/*! @} */


/*!	\defgroup encode_functions
	\brief Функции, имеющие отношение к кодированию (encode.cpp)
	@{
*/
/*!
		\brief Функция для создания узла
		\param[in] ch Символ узла
		\param[in] freq Частота употребления символа в исходном тексте
		\param[in] left Указатель на левую ветвь
		\param[in] right Указатель на правую ветвь
*/
Node* addNode(char ch, int freq, Node* left, Node* right);

/*!
		\brief Функция для архивации текста
		\details Алгоритм Хаффмана кодирует наиболее часто встречаемые символы
		бинарными кодами меньшей длины, а редко встречаемые символы бинарными 
		кодами большей длины. Таким образом, заменяя символы на их соответствующие
		коды, полученные в ходе обхода дерева Хаффмана можно сжать файл
		\param[in] name Имя файла
		\return При успешном считывании - 1, иначе - 0
*/
int pack(std::string& name);

/*!
		\brief Функция для определения кодов символов
		\details Рекурсивный прямой обход дерева (NLR). При переходе к левой ветви,
		на следующий уровень рекурсии копируется строка с добавленной к ней нулём,
		к правой - с единицей. Если текущий узел является листом (не имеет потомков)
		- сопоставить символу этого узла полученную в ходе рекурсии строку.
		\param[in] root Указатель на корень дерева
		\param[in] str Строка, необходимая для работы рекурсии
		\param[in] huffmanCode Пустой список пар символ-строка для записи кодов
*/
void encode(Node* root, std::string str, std::unordered_map<char, std::string>& huffmanCode);

/*!
		\brief Функция для определения частоты употребления символов в исходном тексте
		\param[in] text Ссылка на текст
		\return Список пар символ-частота
*/
std::unordered_map<char, int> find_frequency(std::string& text);

/*!
		\brief Функция для генерации дерева Хаффмана
		\details Создаётся приоритетная очередь, которая в последствии заполняется
		 узлами (символ-частота). Затем создаётся новый узел двоичного дерева, 
		 частота которого равна	сумме частот двух символов с наивысшей частотой, 
		 которые затем становятся его листьями и удаляются из приоритетной очереди.
		 Процесс повторяется до	тех пор, пока все вершины не станут листьями дерева
		\param[in] freq Список пар символ-частота
		\return Указатель на корень бинарного дерева Хаффмана
*/
Node* build_tree(std::unordered_map<char, int> freq);
/*! @} */


/*!	\defgroup decode_functions
	\brief Функции, имеющие отношение к разархивации (decode.cpp)
	@{
*/
/*!
		\brief Функция для разархивации текста
		\details Считывается кол-во дополнительных нулей, на основании строковой
		репрезентации генерируется бинарное дерево Хаффмана, после чего считанный
		закодированный текст декодируется с помощью обхода дерева Хаффмана
		\param[in] name Имя файла
		\return При успешном считывании - 1, иначе - 0 
*/
int unpack(std::string& name);

/*!
		\brief Функция для декодирования битовой последовательности
		\details Эта фунцкия использует нерекурсивный обход бинарного дерева для
		идентификации закодированного символа.
		\param[in] root Указатель на корень дерева Хаффмана
		\param[in] index Ссылка на текущий индекс элементов массива символов
		\param[in] str Последовательность битов (закодированный текст)
		\param[in] outfile Ссылка на файл для сохранения результата
*/
void decode(Node* root, std::string& str, std::ofstream& outfile);
/*! @} */


#endif