#pragma once
#include <malloc.h>
#include <string>
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <sstream>
using namespace std;
class CHuffman
{
	typedef struct{
		unsigned int weight;
		unsigned int parent,lchild,rchild;
	}HTNode,*HuffmanTree;
	typedef unsigned char** HuffmanCode;

	struct BYTE_8{
		unsigned char data;
		unsigned  operator [](int i)const{
			unsigned char tmp=data;//*(unsigned char*)this;
			if(tmp&(1<<(i-1)))
				return 1;
			return 0;
		}
	};
protected:
	//在HuffmanTree HT中選擇兩個權值最小的樹的編號
	void Select(HuffmanTree HT,int num,int &s1,int &s2);
	//根據權值構造Huffman樹HT,并進行編碼
	void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,unsigned int*weight,int n);
	//在一個字節中設置某個位的值，j介于1與8之間，c為0或1
	void setBit(BYTE_8&b,int j,unsigned char c);
	//清零
	void setByte0(BYTE_8&b);
	//利用折半查找法，在charSet中查找ch的位置
	void FindIndex(const char &ch,int &i,const unsigned char*charSet,int setNum);
	//根據Huffman編碼集HC與符號集charSet，將origbuff壓縮到destbuff中
	void Coding(const unsigned char*origbuff,unsigned char*&destbuff,int origNum,int destNum,
				const HuffmanCode &HC, const unsigned char*charSet,int setNum);
	//根據b的第j位的值（0或1），計算Huffman樹HT的第p個元素的孩子的位置
	int Child(const HuffmanTree &HT,int p,int&j,const BYTE_8 &b);
	//根據Huffman編碼集HC與符號集charSet，將origbuff解壓到destbuff中
	void UnCoding(const unsigned char*origbuff,const HuffmanTree &HT,unsigned char*&destbuff,int root,int len, const unsigned char*charSet);
public:
	//將文件sourcefile中的數據流壓縮到文件destfile中
	void compress(const char*sourcefile,const char*destfile);
	//將文件sourcefile中的數據流解壓到文件destfile中
	void uncompress(const char*sourcefile,const char*destfile);
	CHuffman(void);
	~CHuffman(void);
};