// Пример использования
#include <string>
#include <iostream>

#include "HuffmanTree.cpp"

using std::string;
using std::cout;
using std::endl;

	 
int main() {
	string text = "KOL_OKOLO_KOLOKOLA";

	HuffmanTree* tree = new HuffmanTree(text);
	string compress = tree->getCompressed();

	cout << compress << endl;
	// Выведет 001101101110011011110100110111001101100
	system("pause");
}


#include <vector>
#include <map>
#include <string>

using std::string;
using std::vector;
using std::pair;
using std::map;

// Алгоритм:
// 1. Получаем все символы строки и кол-во их вхождений
// 2. Составляем поддеревья из всех символов
// 3. Составляем дерево Хаффмана из всех поддеревьев
// 4. Обходим дерево Хаффмана, создавая набор
//    какой символ на что заменить
class HuffmanTree {
private:
	 // Узел дерева
	 // Хранит вес
	 // Хранит либо указатели на поддеревья (один или два)
	 // Либо символы (один или два)
	struct Node {
		int weight; // Вес вершины

		// Первый и второй символ
		char first_symbol;
		char second_symbol;

		// Указатели на левое и правое поддеревья
		Node* left;
		Node* right;

		// Конструктор создания поддерева
		// Где будут хранится один или два символа
		// Указатели на поддеревья, соответственно равны nullptr
		Node(int weight, char first_symbol, char second_symbol = '\0')
			: left(nullptr), right(nullptr) {
			this->weight = weight;
			this->first_symbol = first_symbol;
			this->second_symbol = second_symbol;
		}

		// Конструктор для создания поддерева
		// Где будут хранится указатели на правое и левое поддерево
		// Символы, соответственно будут равны \0
		Node(int weight, Node* left, Node* right = nullptr) 
			: first_symbol('\0'), second_symbol('\0') {
			this->weight = weight;
			this->left = left;
			this->right = right;
		}

		// Функция возаращает true, если узел хранит только один символ
		// Нужно при обходе дерева Хаффмана
		bool isSingleLeaf() {
			return (first_symbol != '\0' && second_symbol == '\0') ||
				   (first_symbol == '\0' && second_symbol != '\0');
		}

		// В деструкторе удаляем поддеревья
		~Node() {
			if (left  != nullptr) delete left;
			if (right != nullptr) delete right;
		}
	};

	// Увеличиваем кол-во вхождений символа symbol в векторе frequencie на единицу
	// Для этого ищем нужный pair. Если такого не нашлось - создаем
	void increaseCount(vector<pair<char, int>> &frequencie, char symbol) {
		for (auto &pair : frequencie) {
			// Если нашли
			if (pair.first == symbol) {
				pair.second += 1;
				return;
			}
		}
		// Если не нашли - добавляем {symbol, 1} в конец вектора
		frequencie.push_back(pair<char, int>(symbol, 1));
	}

	// Возвращает неотсортированный вектор из набора 
	// символов и кол-ва их вхождений в строку string
	// Этот набор реализуется классом std::pair
	//
	// Из "AABBCA" получим {A, 3}, {B, 2}, {C, 1}
	vector<pair<char, int>> getFrequencies(string const &string) {
		vector<pair<char, int>> frequencie;
		for (auto symbol : string) {
			increaseCount(frequencie, symbol);
		}
		return frequencie;
	}

	// Функция нужна для извлечения (возврата + удаления)
	// набора {Символ => Кол-во вхождений}, с минимальным кол-вом вхождений
	pair<char, int> executeMinimalPair(vector<pair<char, int>> &frequencie) {
		pair<char, int> result = frequencie[0];
		int result_position = 0; // Позиция минимального (возаращаемого) элемента
		int i = 0;
		for (auto &pair : frequencie) {
			if (pair.second < result.second) {
				result = pair;
				result_position = i;
			}
			i += 1;
		}
		// Удаляем минимальный (возвращаемый) элемент
		frequencie.erase(frequencie.begin() + result_position); 
		return result;
	}

	// Функция нужна дли извлечения (возврата + удаления)
	// поддерева с минимальным весом
	Node* executeMinimalTree() {
		Node* result = nodes[0];
		int result_position = 0; // Позиция поддерева с минимальным весом
		int position = 0;
		for (auto &tree : nodes) {
			if (tree->weight < result->weight) {
				result = tree;
				result_position = position;
			}
			position += 1;
		}
		// Удаляем поддерево с минимальным весом из списка вершин
		nodes.erase(nodes.begin() + result_position);
		return result;
	}

	// Функция нужна для создания дерева Хаффмана из поддеревьев
	// 1. Пока в nodes больше одной вершины - создается их родитель,
	//    с весом, равным их суммарному весу
	// 2. Родитель добавляется в список вершин, 
	//    а его два потомка удаляются из этого списка
	// 3. Вызываем функцию, которая обойдет дерево Хаффмана
	//    и для каждого символа создатс строку, на которую его нужно заменить
	void createHuffmanTree() {
		// Пока в nodes хранится не одна вершина - не корень дерева
		Node* first;  // Первое поддерево
		Node* second; // Второе поддерево
		while (nodes.size() != 1) {
			first  = executeMinimalTree();
			second = executeMinimalTree();
			Node* newNode = new Node(first->weight + second->weight, // Вес двух поддеревьев
									 first, second);                 // Два поддерева
			nodes.push_back(newNode); // Добавляем родителя в список вершин
		}
		// На данном этапе у нас в nodes хранится одна
		// вершина, которая является деревом Хаффмана
		// Вызываем функцию, которая обойдет все вершины
		// и для каждого символа присвоит свою замену
		parseHuffmanTree(nodes[0], "");
	}

	// Рекурсивная функция для обхода дерева Хаффмана
	// 1. Если дерево - узел, то обходим левое  поддерево, добавив 0
	//                           обходим правое поддерево, добавив 1
	// 2. Если дерево - лист, то надо ли прибавлять 0 или 1 зависит от того
	//                                  сколько символов содержит этот узел.
	//    Если дерево содержит один символ - то 0 или 1 прибавлять не нужно
	//    Если дерево содержит два символа - то нужно
	void parseHuffmanTree(Node* node, string prefix) {
		// Если дерево - лист. Т.е. содержит символ, но не содержит поддеревья
		if (node->first_symbol != '\0') {
			if (node->isSingleLeaf()) replace[node->first_symbol] = prefix;
			else replace[node->first_symbol] = prefix + "0";
		}
		if (node->second_symbol != '\0') {
			if (node->isSingleLeaf()) replace[node->second_symbol] = prefix;
			else replace[node->second_symbol] = prefix + "1";
		}
		// Если дерево - узел. Т.е. не содержит символ, а содержит поддеревья
		if (node->left != nullptr) {
			parseHuffmanTree(node->left, prefix + "0");

		}
		if (node->right != nullptr) {
			parseHuffmanTree(node->right, prefix + "1");
		}
	}
	
	string text;
	vector<Node*> nodes; // Хранится указатели на все поддеревья
	map<char, string> replace; // Хранит набор из символов и строк, на которые их заменяем

public:
	// Входные данныех: строка
	// 1. Для каждого символа вычисляем, сколько раз он встречается в тексте
	//    Получаем набор из значений {Cимвол => Кол-во вхождений}
	//    Этот набор реализуется классом std::pair
	// 2. Из этого набора получаем все поддеревья и помещаются в вектор nodes
	//    Поддеревья получаем так:
	//            I.   Выбираем два символа с наименьшими весами
	//            II.  Создаем из них поддерево, с весом, равным их суммарному весу
	//            III. Помешаем поддерево в в вектор nodes
	//    Так же нужно обработать ситуацию, когда остался только один символ.
	//    Тогда создаем поддерево только с одним символом и помещаем его в nodes
	// 3. Вызываем функцию, в которой их всех поддеревьев соберем дерево Хаффмана
	HuffmanTree(string text) {
		this->text = text;
		// Получаем набор из {Символ => Сколько раз он встречается в тексте}
		vector<pair<char, int>> frequencie = getFrequencies(text);
		pair<char, int> first;
		pair<char, int> second;

		Node* newTree = nullptr;
		// При создании поддерева у нас будет два случая
		// 1. Когда кол-во оставшихся символов больше или равно двум
		//    Тогда создается поддерево из двух символов
		while (frequencie.size() > 1) {
			first  = executeMinimalPair(frequencie);
			second = executeMinimalPair(frequencie);
			Node* newTree = new Node(first.second + second.second,   // Сумма весов
									 first.first, second.first);     // Два символа
			nodes.push_back(newTree);

		}
		// 2. Когда кол-во элементов равно единице
		//    Тогда создаем подедерво с одним символом
		if (frequencie.size() == 1) {
			first = executeMinimalPair(frequencie);
			Node* newTree = new Node(first.second, first.first); // Вес и и один символ
			nodes.push_back(newTree);
		}
		// Вызываем функцию, в которой из всех
		// поддеревьев создадим дерево Хаффмана
		createHuffmanTree();
	}

	// Пользовательская функция, возвращает
	// набор из симвов и строк, на которые из заменяем
	map<char, string> getReplacements() {
		return replace;
	}

	// Пользовательская функция, возвращает сжатую строку
	string getCompressed() {
		string result;
		for (auto symbol : text) {
			result += replace[symbol];
		}
		return result;
	}

	// В деструкторе удаляем дерево Хаффмана
	~HuffmanTree() {
		delete nodes[0];
	}
};