// HuffTree.cpp : 實(shí)現(xiàn)文件
//

#include "stdafx.h"
#include "huffman.h"
#include "HuffTree.h"
#include ".\hufftree.h"


// CHuffTree
IMPLEMENT_SERIAL(CHuffTree,CObject,1)
CHuffTree::CHuffTree()
{
	m_nCNum=0;
	m_pHT=NULL;
	int i;
	for(i=0;i<CHAR_NUM;i++)
	{
		m_CN[i].ch='\0';
		m_CN[i].weht=0;
	}
}

CHuffTree::~CHuffTree()
{

}


void CHuffTree::pidu(CString fn)
{
	FILE *fp;
	int i=0;
	if((fp=fopen(fn,"r"))==NULL)
	{
		printf("cannot open the file\n");
		exit(0);
	}
	char ch;
	ch=fgetc(fp);
	while(ch!=EOF)
	{
		for(i=0;i<m_nCNum;i++)
		{
			if(ch==m_CN[i].ch)
			{
				m_CN[i].weht++;	
				break;
			}
		}
		if(i==m_nCNum)
		{
			m_CN[i].ch=ch;
			m_CN[i].weht++;
			m_nCNum++;
		}
		ch=fgetc(fp);
	}
	fclose(fp);
}

void CHuffTree::piduInput(CString input)
{
	int length=input.GetLength();
	int i=0;
	for(i=0;i<length;i++)
	{
		char ch=input.GetAt(i);
		for(int j=0;j<m_nCNum;j++)
		{
			if(ch==m_CN[j].ch)
			{
				m_CN[j].weht++;
				break;
			}
		}
		if(j==m_nCNum)
		{
			m_CN[j].ch=ch;
			m_CN[j].weht++;
			m_nCNum++;
		}
	}
}

int CHuffTree::Select(int last,int *flag)
{
	unsigned int minw;
	int i;
	int temp;
	for(i=0;i<last;i++)
	{
		if(flag[i]==0)
		{
			minw=m_pHT[i+1].weight;
			temp=i+1;
			break;
		}
	}
 	for(i=1;i<=last;i++)
	{
		if(m_pHT[i].weight<minw&&flag[i-1]==0) 
		{
			minw=m_pHT[i].weight;
			temp=i;
		}
	}
	flag[temp-1]=1;
	return temp;
}

void CHuffTree::HufmanTree()
{
	if(m_nCNum<=1) return;
	int m=2*m_nCNum-1;
	int i;
	int s1,s2;
	int *sflag=(int *)malloc((2*m_nCNum-1)*sizeof(int));
	int *q=sflag;
	for(i=0;i<2*m_nCNum-1;i++,q++) *q=0;
	m_pHT=(HTNode *)malloc((m+1)*sizeof(HTNode));
	HTNode *p=m_pHT+1;
	for(i=1;i<=m_nCNum;++i)
	{
		p->weight=m_CN[i-1].weht;
		p->data=m_CN[i-1].ch;
		p->parent=p->lchild=p->rchild=0;
		p++;
	}
	for(;i<=m;++i,p++) p->parent=p->lchild=p->rchild=p->data=0;
	for(i=m_nCNum+1;i<=m;++i)
	{
		s1=Select(i-1,sflag);
		s2=Select(i-1,sflag);
		m_pHT[s1].parent=i;
		m_pHT[s2].parent=i;
		m_pHT[i].lchild=s1;
		m_pHT[i].rchild=s2;
		m_pHT[i].weight=m_pHT[s1].weight+m_pHT[s2].weight;
	}
	free(sflag);
}

char ** CHuffTree::HufmanCode()
{
	int n=m_nCNum;
	HTNode * HT=m_pHT;
	char **HC=(char **)malloc((n+1)*sizeof(char *));	
	char *cd=(char *)malloc(n*sizeof(char));
	int start,c,i,f;
	cd[n-1]='\0';
	for(i=1;i<=n;i++)
	{
		start=n-1;
		for(c=i,f=HT[c].parent;f!=0;c=f,f=HT[f].parent)
			if(HT[f].lchild==c) cd[--start]='0';
			else cd[--start]='1';
		HC[i]=(char *)malloc((n-start)*sizeof(char));
		strcpy(HC[i],&cd[start]);
	}
	free(cd);
	return HC;
}

void CHuffTree::CodeFile(char **HC,CString filename)
{
	int n=m_nCNum;
	CodeNode * cn=m_CN;
	FILE *fr,*fw;
	char ch;
	int i;
	if((fr=fopen(filename,"r"))==NULL)
	{
		printf("cannot open the file!");
		exit(0);
	}
	if((fw=fopen("hufcode.txt","w+"))==NULL)
	{
		printf("cannot open the file!");
		exit(0);
	}
	ch=fgetc(fr);
	while(ch!=EOF)
	{
		for(i=0;i<n;i++)
		{
			if(cn[i].ch==ch)
			{
				fputs(HC[i+1],fw);
				break;
			}
		}
		ch=fgetc(fr);
	}
	FILE *fc=fopen("bincoded.huf","wb");
	rewind(fw);
	char cd[9];
	cd[8]='\0';
	int w,j,end;
	unsigned int c;
	ch=fgetc(fw);
	while(ch!=EOF)
	{	
		c=0;
		end=7;
		for(i=0;i<8&&ch!=EOF;i++)
		{
			cd[i]=ch;
			ch=fgetc(fw);
		}
		if(ch==EOF)
		{
			for(;i<8;i++) cd[i]='0';
		}
		printf("\n%s",cd);
		for(i=0;i<8;i++)
		{
			w=1;
			for(j=0;j<i;j++) w*=2;
			c=(cd[end--]-48)*w+c;
		}
		printf("\n%d",c);
		fputc(c,fc);
	}	
	fclose(fc);
	fclose(fr);
	fclose(fw);
}	

void CHuffTree::decode(HTNode *HT,int n)
{
	FILE *fenc=fopen("hufdecode.txt","wb+");
	FILE *fd=fopen("decodefile.txt","w");
	FILE *fc=fopen("bincoded.huf","rb");
	HTNode *p=HT+2*n-1;
	int end,i;
	char ch,cd[9];
	cd[8]='\0';
	unsigned int enc;
	rewind(fc);
	enc=fgetc(fc);
	while(enc!=EOF)
	{
		printf("\n%d",enc);
		end=7;
		for(i=0;i<8;i++)
		{
			cd[end--]=enc%2+48;
			enc=enc/2;
		}
		fputs(cd,fenc);
		enc=fgetc(fc);
	}
	rewind(fenc);
	ch=fgetc(fenc);
	while(ch!=EOF)
	{
		if(ch=='0'&&p->lchild!=0)
		{
			p=&HT[p->lchild];
			ch=fgetc(fenc);
			if(ch==EOF) fputc(p->data,fd);
		}
		else if(ch=='1'&&p->rchild!=0) 
		{
			p=&HT[p->rchild];
			ch=fgetc(fenc);
			if(ch==EOF) fputc(p->data,fd);
		}
		else if(p->lchild==0||p->rchild==0)
		{
			fputc(p->data,fd);
			p=&HT[2*n-1];
		}
	}
	fclose(fc);
	fclose(fd);
	fclose(fenc);
}

int CHuffTree::getLayerNum()
{
	if(m_nCNum<=1) return 1;
	int m=2*m_nCNum-1;
	int layer=1;
	int s,p;
	int *sflag=(int *)malloc((2*m_nCNum-1)*sizeof(int));
	int *q=sflag;
	for(int i=0;i<2*m_nCNum-1;i++,q++) *q=0;
	s=Select(m_nCNum,sflag);
	p=m_pHT[s].parent;
	while(p!=0)
	{
		layer++;
		s=p;
		p=m_pHT[s].parent;
	}
	return layer;
}

int CHuffTree::toArray(int ta[])
{
	int head=0;
	int rear=0;
	int layer=getLayerNum();
	int maxnum=power2(layer)-1;
	int m=2*m_nCNum-1;
	ta[head]=m;
	rear++;
	while(rear<maxnum)
	{
		if(ta[head]!=0)
		{
			ta[rear]=m_pHT[ta[head]].lchild;
			rear++;
			ta[rear]=m_pHT[ta[head]].rchild;
			rear++;
		}
		else
		{
			ta[rear]=0;
			rear++;
			ta[rear]=0;
			rear++;
		}
		head++;
	}
	return rear;
}

int CHuffTree::power2(int n)
{
	int result=1;
	if(n==0) return result;
	for(int i=1;i<=n;i++)
	{
		result=result*2;
	}
	return result;
}
void CHuffTree::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{	
		ar<<m_nCNum;
		for(int i=1;i<=(2*m_nCNum-1);i++)
		{
			ar<<m_pHT[i].data<<m_pHT[i].parent<<m_pHT[i].lchild<<m_pHT[i].rchild<<m_pHT[i].weight;
		}
	}
	else
	{
		ar>>m_nCNum;
		int m=2*m_nCNum-1;
		m_pHT=(HTNode *)malloc((m+1)*sizeof(HTNode));
		for(int i=1;i<=(2*m_nCNum-1);i++)
		{
			ar>>m_pHT[i].data>>m_pHT[i].parent>>m_pHT[i].lchild>>m_pHT[i].rchild>>m_pHT[i].weight;
		}
   	}
}