//лабараторная работа №2

#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

struct KeyValue//хранит пару значение после кодирования и символ
{
	string value_;
	char symbol_;
	KeyValue(string a, char b) :value_(a), symbol_(b)
	{}

};


class AlgoritmShenona_Phano //класс хранит алгоритм Шенона-Фано
{
	string firstWords_;//слово
	vector <double> value_;//вектор хранит значиния частоты символов
	vector <char> symbols_;//вектор храни символы
	vector <KeyValue> keySymbol_;//вектор  пар значение - символ
	int size_;//размер
public:

	AlgoritmShenona_Phano(vector <double> &value, vector <char> &symbols,const string &word) :value_(value), symbols_(symbols),firstWords_(word)//конструктор
	{
		size_ = value_.size();
	}

	void execute(ostream &os)//расчеты алгоритма и запись результата
	{
		splitUP(value_, symbols_, "");
		int wordSize = firstWords_.size();
		os << "\n\nwords: ";

		for (int i = 0; i < wordSize; i++)
		{
			os<< searchsymbol (firstWords_[i]) <<" ";
		}

		os << "\n";
	}

	int someCount(const vector <double> &allValue)//находим среднии значения для расчетов
	{
		int count = 0;
		int fullvalue = 0;
		double someValue = 0;
		double a = 0;

		for (int i = 0; i < allValue.size(); i++)
		{
			fullvalue += allValue[i];
		}

		while (a < 0.45)
		{
			someValue += allValue[count];
			count++;
			a = someValue / fullvalue;
		}
		return(count);
	}

	string searchsymbol(char a)//сопостовляем символ с кодом
	{
		for (int i = 0; i < size_; i++)
		{
			if (a == keySymbol_[i].symbol_)
			{
				return(keySymbol_[i].value_);
			}
		}

	}

	void splitUP( vector <double> fullValue,vector <char> fullSymbols, const string &code)//делим массив значений на два массива (рекурсия)
	{
		int size = fullValue.size();
		vector <double> value1;
		vector <char> symbols1;
		vector <double> value2;
		vector <char> symbols2;
		if (size < 0)
		{
			cerr << "\n\nerror!!\n\n";
		}

		if (size == 1)//если массив из одного значения присваиваем значение кодов к символам т.е. базовый случай
		{
			string code1 = code;
			code1 += "0";
			KeyValue key(code1, fullSymbols[0]);
			keySymbol_.push_back(key);
		}

		if (size == 2)//если массив из двух значений присваиваем значения кодов к символов т.е. базовый случай
		{
			string code1 = code;
			code1 += "0";
			string code2 = code;
			code2 += "1";

			KeyValue key(code1, fullSymbols[0]);
			keySymbol_.push_back(key);

			KeyValue key1(code2, fullSymbols[1]);
			keySymbol_.push_back(key1);
		}

		if (size >2)//делим алгоритм на две части
		{

			int halfSize = someCount(fullValue);
			for (int i = 0; i < halfSize; i++)
			{
				value1.push_back(fullValue[i]);
				symbols1.push_back(fullSymbols[i]);
			}

			for (int i = halfSize; i < size; i++)
			{
				value2.push_back(fullValue[i]);
				symbols2.push_back(fullSymbols[i]);
			}

			string code1 = code;
			code1 += "0";
			string code2 = code;
			code2 += "1";
			splitUP(value1, symbols1, code1);
			splitUP(value2, symbols2, code2);
		}
	}



};

int main()
{
	unordered_map<char, int> myMap;//пара символ значение
	string world;//наше слово
	cout << "write world: ";
	cin >> world;
	for (const auto symbol : world)
	{
		myMap[symbol]++;
	}

	string str("abcdefghijklmnopqrstuvwxyz");
	vector <double> value;// массив цифр хранит кол-во повторений цифры
	vector<char> symbol;//массив символов


	int buffQty;//промежуточные значения
	char buffSymbol;//промежуточные значения
	for (size_t j = 0; j < world.size(); j++)
	{
		buffQty = 1;
		buffSymbol = '1';
		for (size_t i = 0; i < str.size(); i++)
		{
			if (buffQty <= myMap[str[i]])//находим наиболее часто повторяющийся символ
			{
				cout << "\n" <<str[i]<<" "<<myMap[str[i]];
				buffQty=myMap[str[i]];//записываем его в промежуточные значения
				buffSymbol = str[i];
			}

		}
		if (buffSymbol != '1')
		{
			unordered_map<char, int>::iterator it;
			for (it = myMap.begin(); it != myMap.end(); it++)//удаляем этот символ myMap.erase(it);
			{

				if ((it->first) == buffSymbol)
				{
					myMap.erase(it);
					break;
				}
			}

			value.push_back(buffQty);//добавляем символ в массив символов и количество его повторения в аналогичный массив
			symbol.push_back(buffSymbol);
		}
	}

	cout << "\nsecondMap " << myMap['a']<<"\n";


	AlgoritmShenona_Phano algo(value,symbol,world );//создаем класс реализующий алгоритм


	algo.execute(cout);//метод execute принимаем метод для вывода

	cout <<"\n\n";
	system("pause");//ожидание нажатия в консоли
	return 0;
}