#include "huffman_base.h"int huffman_base::get_code_len(int index){	check();	if (index < 0 || index >= (int)code_lens.size())		throw new huffman_exception("參數(shù)非法");	return code_lens[index];}vector<int> huffman_base::get_all_code_lens(void){	check();	return code_lens;}unsigned long huffman_base::get_code(int index){	check();	if (index < 0 || index >= (int)codes.size())		throw new huffman_exception("參數(shù)非法");	return codes[index];}vector<unsigned long> huffman_base::get_all_codes(void){	check();	return codes;}string huffman_base::get_code_str(int index){	check();	if (index < 0 || index >= (int)codes.size())		throw new huffman_exception("參數(shù)非法");	return long_to_string(codes[index], code_lens[index]);}vector<string> huffman_base::get_all_code_strs(void){	check();	vector<string> v;	for(int i = 0; i < (int)codes.size(); i++)		v.push_back(long_to_string(codes[i], code_lens[i]));	return v;}int huffman_base::find(unsigned long code){	check();	for(int i = 0; i < (int)codes.size(); i++)		if (codes[i] == code)			return i;	return -1;}int huffman_base::find(const string& code){	return find(string_to_long(code.c_str()));}inline void huffman_base::check(){	if (codes.size() <= 0)		throw new huffman_exception("尚未調(diào)用過generate_codes()");}unsigned long huffman_base::string_to_long(const char* code){	unsigned long ret = 0;	int len = (int)strlen(code);	for(int i = len - 1; i >= 0; i--)		if (code[i] == '1')			ret |= (1ul << (len - i - 1));	return ret;}string huffman_base::long_to_string(unsigned long code, int code_len){	char* buf = new char[code_len + 1];	if (buf == NULL)		throw new huffman_exception("no enough memory.");	memset(buf, 0, code_len + 1);	unsigned long bit = 1 << (code_len - 1);	for(int i = 0; i < code_len; i++)	{		if (code & bit)			buf[i] = '1';		else			buf[i] = '0';		bit >>= 1;	}	string ret(buf); delete buf;	return ret;}void huffman_base::generate_canonical_codes(){	if (code_lens.size() <= 0)		throw new huffman_exception("生成Canonical Huffman編碼前，應(yīng)已知所有元素碼長");	int max_code_len = 0;	int min_code_len = 1000;	const int tmp = sizeof(unsigned long) * 8 + 1;	int len_count[tmp];	unsigned long min_code[tmp];	memset(len_count, 0, tmp * sizeof(int));	memset(min_code, 0, tmp * sizeof(unsigned long));	int num = (int)code_lens.size();	// 統(tǒng)計(jì)碼長信息	for (int i = 0; i < num; i++)	{		int codelen = code_lens[i];		// huffman_base用unsigned long存儲(chǔ)編碼，因此		// 碼長要限制在sizeof(unsigned long)*8以內(nèi)		// 這里對(duì)超長的編碼都簡單忽略掉了		if ((unsigned long)codelen > sizeof(unsigned long)*8)			continue;		if (codelen > max_code_len)			max_code_len = codelen;		if (codelen < min_code_len)			min_code_len = codelen;		len_count[codelen]++;	}		// 計(jì)算特定碼長的所有元素中最小的編碼,這里使用的是	// Canonical Huffman編碼規(guī)則,請(qǐng)參見相關(guān)文獻(xiàn)	for (int i = max_code_len - 1; i >= 0; i--)		min_code[i]	= (min_code[i +	1] + len_count[i + 1]) >> 1;	// 已知特定碼長的所有元素中最小的編碼,同樣碼長的元素,	// 編碼逐個(gè)加1就可以了	codes.clear();	for (int i = 0; i < num; i++)		if (code_lens[i] > 0 && (unsigned long)code_lens[i] <= sizeof(unsigned long)*8)			codes.push_back(min_code[code_lens[i]]++);		else			codes.push_back(0);}bool huffman_base::verify(){	check();		int max = 0;	const int code_len_limit = 100; // 這里能檢驗(yàn)的最大碼長是100	int len_count[code_len_limit + 1];	memset(len_count, 0, sizeof(int)*(code_len_limit+1));	for(int i = 0; i < (int)code_lens.size(); i++)	{		if (code_lens[i] > code_len_limit)			return true; // 如果有超長碼，就不檢驗(yàn)了		len_count[code_lens[i]]++;		if (code_lens[i] > max) max = code_lens[i];	}	// 從根開始，算每層分支結(jié)點(diǎn)數(shù)目，如果最后一層不為0，就表明Huffman樹有錯(cuò)誤	int nonleaf = 1;	for(int i = 1; i <= max; i++)		nonleaf = nonleaf * 2 - len_count[i];	return (nonleaf == 0);}