#include <iostream>
#include <fstream>
#include <cassert>
#include <string>
#include <string.h>
using namespace std;
struct HNode
{
    HNode *parent;
    HNode *lch, *rch;
    int weight,codelen;
    char data;  
    char *code; //������
};
//�����������ͣ�ָ�룩
typedef HNode* HTree;
typedef HNode* ElemType;
//˳���
typedef struct
{
    ElemType *elem;
    int length; //��ǰ���ݵ�ʵ�ʳ���(�ж�������)
} seqList;
//����˳���ht��������Ź��������Ľ��
seqList ht;

//��ʼ����������������Ҷ�ӽ����Ϣ���뵽˳���
//a:Ȩֵ��b��Ҷ����ַ���n��Ҷ������
void input(int a[], char b[], int n)
{
    for (int i = 0; i < n; i++)
    {
        HNode *tmp = new HNode;
        tmp->parent = NULL;
        tmp->weight = a[i];
        tmp->data = b[i];
        tmp->lch = NULL;
		tmp->rch = NULL;
        ht.elem[i]=tmp;
        ht.length++;
    }
}
// n:�±�Ϊ[0~n)��������n����˳���ht�� 0~n��ѡ��2��Ȩֵ��С�Ľ�㣬����±��ŵ�s1,s2��
void selectMin(int n, int &s1, int &s2)
{   		
    int m1 = 0x7fff;
	int m2 = 0x7fff;			// m1ȡ��СȨ�أ�m2ȡ��СȨ��
    int lnode = 0;
	int rnode = 0;     		// lnode, rnode�ֱ�ȡ������СȨ�صĽ��λ��
    for(int k=0; k<n; k++){
	    if(ht.elem[k]->parent==NULL){
			if(ht.elem[k]->weight<m1) {
	            m2 = m1;  rnode=lnode;
				m1 = ht.elem[k]->weight;  lnode=k;
			}
			else if(ht.elem[k]->weight<m2) {
				m2 =ht.elem[k]->weight;
				rnode = k;
			}
        }
	}
	s1=lnode;
	s2=rnode;
}
//����n��Ҷ�ӽ�㴴�����������������������cht��
void creatHt(HTree &cht, int n)
{
    HNode tNode;
    int m = 2 * n - 1;
    int s1, s2;
    //��ʼ0~n-1��ѡ
    for (int i = n; i < m; i++)
    {
        HNode *r = new HNode;
        r->parent = NULL;
        selectMin(i, s1, s2);
        r->weight=ht.elem[s1]->weight+ht.elem[s2]->weight;
        r->lch=ht.elem[s1];
        r->rch=ht.elem[s2];
        ht.elem[s1]->parent=r;
        ht.elem[s2]->parent=r;
        ht.elem[i]=r;
        ht.length++;
    }
    cht = ht.elem[m-1];
}
void printHfTreePre(HTree t)//��������������� 
{
    if (t != NULL)
    {
        if (t->lch == NULL && t->rch == NULL)
        {
            cout << "weight:" << t->weight << " " << t->data << ":" <<t->code <<  endl;//
        }
        printHfTreePre(t->lch);
        printHfTreePre(t->rch);
    }
}
void hufmadecode(char* filename,HTree t,char *ziped,int len){//����ѹ���ĵ� 
	ifstream infile(filename);
	if(!infile.is_open()){
		cerr<<"ifstream open file error\n";
		return;
	}
	infile.seekg(0,ios_base::end);
	int length = infile.tellg();
	infile.seekg(ios_base::beg);
	char* buff=new char[length+1]();
	infile.read(buff,length+1);
	int count =0;
	for(int i=0;i<length+1;i++){
		for(int j=0;j<len;j++){
			if(buff[i]==ht.elem[j]->data){
				strcpy(ziped+count,ht.elem[j]->code);
				count+=ht.elem[j]->codelen;
				break;
			}
		}
	}
	ziped[count+1]='\0';
	infile.close();
}

//�������±�������
void hufEncode(HTree t, int k, char *code)
{
    if (t == NULL)
        return;
    if (t->lch == NULL && t->rch == NULL)
    {
        code[k] = '\0';
        t->code = new char[k + 1];
        strncpy(t->code, code ,k + 1); 
        t->codelen=k;
    }
    if(t->lch != NULL){
    	code[k]='0';
    	hufEncode(t->lch, k+1, code);
	}
	if(t->rch != NULL){
    	code[k]='1';
    	hufEncode(t->rch, k+1, code);
	}   
}
//����: �����dec��
void hufDecode(HTree &ht, char str[], char *dec)
{

    HNode *t = ht;
    while (*(str+1))
    {
        if(*str=='0')t=t->lch;
        else t=t->rch;
        if(t->lch==NULL&&t->rch==NULL){
        	cout<<t->data;
        	t=ht;
		}
        str++;
    }
}

int Search(char *a,char ch)
{//�����������ַ�ch���ڵ�λ�ã����������±꣬���򷵻�-1
	for(int i=0;a[i]!='\0';i++){
        if(a[i]==ch)return i;
    }
    return -1;
}
/*
ͳ���ļ����ַ��ij��ִ���
freq����Ŵ���
letters������ַ�
*/

int countLetter(char* filename, int *freq, char *letters)
{
    ifstream infile(filename);
	if(!infile.is_open()){
		cerr<<"ifstream open file error\n";
		return 0;
	}
	infile.seekg(0,ios_base::end);
	int length = infile.tellg();
	infile.seekg(ios_base::beg);
	char* buff=new char[length+1]();
	infile.read(buff,length+1);
	int count=0;
	for(int i=0;i<length+1;i++){
	//	cout<<buff[i];
        int x=Search(letters,buff[i]);
        if(x==-1){
            letters[count++]=buff[i];
            letters[count]='\0';
        }
        x=Search(letters,buff[i]);
        freq[x]++;
    }
	infile.close();
	return count-1;
}
int main()
{
    HTree htt=NULL;
    int freq[128] = {0};
    char letters[128] = {'\0'};
    int len;
    char dec[10000],code[100],zipped[100000];
    const char *choe="end",*chob="begin",*choz="zipped",*choc="checktree",*chod="decode",*choo="help";
    char s[100];//="C:\\Users\\��а\\Desktop\\����vc2019\\dev\\hhh.txt";
    cout<<"-----------------------------------------"<<endl;
    cout<<"    ������ʾ"<<endl; 
    cout<<"����begin��ʼ"<<endl; 
    cout<<"����end����"<<endl; 
    cout<<"����zippedչʾѹ�����ļ�"<<endl; 
    cout<<"����checktree�鿴��Ҷ�ӽ��Ȩ�غͱ���"<<endl; 
    cout<<"����decode�鿴�����ļ�"<<endl; 
    cout<<"����help�鿴����"<<endl;
    cout<<"-----------------------------------------"<<endl;
    cin>>s;
    while(strcmp(s,choe)){
    	if(strcmp(s,chob)==0){
            cout<<"������txt�ļ�·����"; 
		    cin>>s;
            len = countLetter(s, freq, letters);
            cout<<"-----------------------------------------"<<endl;
            cout<<"�ַ�ͳ����ϣ�����"<<len<<"���ַ�"<<endl;
            ht.elem=new ElemType[len*2-1];
            ht.length=0;
			input(freq,letters,len);
            cout<<"˳�����ʼ����ɣ�"<<endl;
			creatHt(htt, len);
			cout<<"��������������ɣ�"<<endl;
			hufEncode(htt, 0, code);
			cout<<"���������봴�����"<<endl; 
			hufmadecode(s,htt,zipped,len);
			cout<<"�ļ�ѹ�����"<<endl; 
			cout<<"-----------------------------------------"<<endl;
		}
  //  seqListInit(ht,len*2-1);
        else if(strcmp(s,choz)==0){
		    cout<<"-----------------------------------------"<<endl;
        	if(*zipped){
        	    cout<<"ѹ������ļ����£�"<<endl;
		        cout<<zipped<<endl;
		    }
		    else{
		    	cout<<"��û��ѹ���ļ�������ʹ��begin����"<<endl;
			} 
			cout<<"-----------------------------------------"<<endl;
		}
        else if(strcmp(s,choc)==0){
        	cout<<"-----------------------------------------"<<endl;
        	if(htt!=NULL){
        	    cout<<"���ڵ����£�"<<endl;
		        printHfTreePre(htt);
		    }
		    else{
		    	cout<<"δ�ҵ���������ʹ��begin����"<<endl; 
			}
		    cout<<"-----------------------------------------"<<endl; 
		}
        else if(strcmp(s,chod)==0){
        	if(*zipped){
        	    cout<<"-----------------------------------------"<<endl; 
        	    cout<<"�������ļ����£�"<<endl;
		        hufDecode(htt, zipped, dec);
		        cout<<endl<<"-----------------------------------------"<<endl; 
			}
			else{
				cout<<"-----------------------------------------"<<endl;
				cout<<"��û��ѹ���ļ����޷����룡����ʹ��begin����"<<endl;
				cout<<"-----------------------------------------"<<endl;
			} 
		}
        else if(strcmp(s,choo)==0){
        	cout<<"-----------------------------------------"<<endl;
        	cout<<"����begin��ʼ"<<endl; 
            cout<<"����end����"<<endl; 
            cout<<"����zippedչʾѹ�����ļ�"<<endl; 
            cout<<"����checktree�鿴��Ҷ�ӽ��Ȩ�غͱ���"<<endl; 
            cout<<"����decode�鿴�����ļ�"<<endl; 
            cout<<"����help�鿴����"<<endl;
            cout<<"-----------------------------------------"<<endl;
		}
	    else {
	    	cout<<"-------------------------------------------------"<<endl;
	    	cout<<"�����������������������룡(����help�鿴����)"<<endl;
	    	cout<<"-------------------------------------------------"<<endl;
		}
		cout<<"��������һ��ָ�"; 
	    cin>>s;
	}
	return 0;
}