#include <iostream>
#include <vector>
#include <string>
#include <math.h>
using namespace std;

const int char_l = 8;  //CII碼表示范圍,8位二元碼

class CodeResult
{
private:
	int dict_l;
	string result;
public:
	CodeResult(string result, int dict_l)
	{
		this->dict_l = dict_l;
		this->result = result;
	}
	string getResult()
	{
		return result;
	}
	int getDict_l()
	{
		return dict_l;
	}
};

int getCodeLen(const int totalChars)  //totalChars個不同字符需要的二元碼個數
{
	int temp = log(totalChars + 1) / log(2);
	int char_l = (int)temp;
	
	if (temp != char_l)
	{
		char_l += 1;
	}

	char_l += 1;

	return char_l;
}

int toDec(string c)
{
	int result = 0;
	int i;
	for (i = 0; i < c.length(); i++)
	{
		char temp = c.at(i);
		if (temp == '1')
		{
			result += pow(2, c.length() - i - 1);
		}
	}

	return result;
}

string toBinary(int num, int len)
{
	int i, rest;
	char a[1];
	vector<int> v;
	string result = "";
	string temp = "";
	
	if (num == 0)
	{
		v.push_back(0);
	}
	while (num != 0)
	{
		v.push_back(num % 2);
		num = num / 2;
	}
	for (i = v.size() - 1; i >= 0; i--)
	{
		result += temp.assign(itoa(v[i], a, 10));
	}

	temp.assign("");
	rest = len - result.length();
	if (rest > 0)
	{
		for (i = 0; i < rest; i++)
		{
			temp += "0";
		}
	}

	result = temp + result;
	return result;
}

CodeResult code(const string text)
{
	int i = 0, j = 0;
	int count = -1;
	string str;
	string result;
	string zero;
	vector<string> dict;  //字典
	vector<int> index;
	double temp = 0;
	int dict_l;  //字典需要dict_l位二位碼元表示
	
	cout << "字典:" << endl;

	for (i = 0; i < text.length(); i++)
	{
		str = text.substr(i, 1);

		for (j = 0; j < dict.size(); j++)
		{
			if (i + 1 < text.length())
			{
				if (str.compare(dict[j]) == 0)
				{
					count = j;
					str += text.substr(i + 1, 1);
					i++;
					j = 0;
				}
			}
			else
				break;
		}

		if (count != -1) 
		{
			index.push_back(count);
		}
		dict.push_back(str);
		cout << str << endl;
		count = -1;
	}
	
	dict_l = getCodeLen(dict.size());
	zero = toBinary(0, dict_l);
	count = 0;
	for (i = 0; i < dict.size(); i++)
	{
		if (dict[i].length() == 1)
		{
			result += zero + toBinary(dict[i].at(0), char_l);
		}
		else
		{
			result += toBinary(index[count++]+1, dict_l) + 
				toBinary(dict[i].at(dict[i].length() - 1), char_l);
		}
	}

	return CodeResult(result, dict_l);
}

string decode(const string c, const int dict_l)
{
	int i, j;
	char a[2];
	string result;
	string temp;
	string dictGroup, charGroup;
	string zero = toBinary(0, dict_l);
	vector<string> dict;
	int groupLen = dict_l + char_l;
	int groupCount = c.length() / groupLen;
	
	a[1] = '\0';
	for (i = 0; i < groupCount; i++)
	{
		temp.assign("");
		dictGroup = c.substr(i * groupLen, dict_l);
		charGroup = c.substr(i * groupLen + dict_l, char_l);
		if (dictGroup.compare(zero) != 0)
		{
			temp += dict[toDec(dictGroup)-1];
		}

		a[0] = toDec(charGroup);
		
		temp += a;
		result += temp;
	//	cout << temp << endl;
		dict.push_back(temp);
	}
	
	return result;
}

int main()   
{

	char * text = "The sky is so clean I like it The sky is so clean I like it The sky is so clean I like it."; 
	CodeResult c = code(text);
	cout << "編碼序列:" << endl;
	cout << c.getResult() << endl;
	string d = decode(c.getResult(), c.getDict_l());
	cout << "解碼序列:" << endl;
	cout << d << endl;
	system("pause");
	return 0;
}