demownd.cpp

哈夫曼编码解码演示程序

// DemoWnd.cpp : implementation file
//

#include "stdafx.h"
#include "Huffman.h"
#include "DemoWnd.h"
#include "HuffNode.h"
#include "HuffmanDlg.h"
#include "math.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CDemoWnd

CDemoWnd::CDemoWnd()
{
	m_pHuff=NULL;
	m_xStart=m_yStart=10;
	m_Interval=10;
	m_xInterval=100;
	m_yInterval=30;
	m_Radius=15;
	m_crNode=RGB(255,0,0);
	m_crLine=RGB(186,110,64);
	m_xScale=(float)1.8;
	m_yScale=(float)0.7;
}
CDemoWnd::~CDemoWnd()
{
	m_Font.DeleteObject();
}

BEGIN_MESSAGE_MAP(CDemoWnd, CStatic)
	//{{AFX_MSG_MAP(CDemoWnd)
	ON_WM_PAINT()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDemoWnd message handlers

void CDemoWnd::OnPaint() 
{
	CPaintDC dc(this); // device context for painting
	
	CDC memDC,tmpDC;
	CBitmap memBmp;
	CRect rcClient;
	GetClientRect(&rcClient);
	memDC.CreateCompatibleDC(&dc);
	tmpDC.CreateCompatibleDC(&dc);
	tmpDC.SelectObject(&m_bmpBK);
	memBmp.CreateCompatibleBitmap(&dc,rcClient.Width(),
		rcClient.Height());
	memDC.SelectObject(&memBmp);
	memDC.StretchBlt(0,0,rcClient.Width(),rcClient.Height(),&tmpDC,
		0,0,m_sizeBK.cx,m_sizeBK.cy,SRCCOPY);
    
	if(Calculate())
		DrawTree(&memDC);
	DrawCode(&memDC);
	dc.BitBlt(0,0,rcClient.Width(),rcClient.Height(),
		&memDC,0,0,SRCCOPY);
	memDC.DeleteDC();
	tmpDC.DeleteDC();
	memBmp.DeleteObject();
	// Do not call CStatic::OnPaint() for painting messages
}
void CDemoWnd::DrawTree(CDC*pDC)
{
	if(m_pHuff->m_arHuffman.GetLength()==0)
		return;	
	int x=m_xStart,y=m_yStart;
	for(int i=0;i<m_pHuff->m_arHuffman.GetLength();i++)
	{
		CHuffNode*pNode=m_pHuff->m_arHuffman.GetAt(i);
		if(pNode->bUse)
		{			
			DrawLine(pDC,i,pNode->x,pNode->y);
		}	
	}
	for(i=0;i<m_pHuff->m_arHuffman.GetLength();i++)
	{
		CHuffNode*pNode=m_pHuff->m_arHuffman.GetAt(i);
		if(pNode->bUse)
		{			
			DrawNode(pDC,i);
		}	
	}	
	
}
void CDemoWnd::DrawLine(CDC*pDC,int n,int x,int y/*,
						BOOL bFocus,BOOL bLeft*/)
{
	if(n==-1)
	{	
		return ;
	}
	CHuffNode*pNode=m_pHuff->m_arHuffman.GetAt(n);
    CPen pen;
	if(pNode->bIsTrace)
	{   
		pen.CreatePen(PS_SOLID,2,RGB(255,0,0));		
	}
	else 
		pen.CreatePen(PS_SOLID,2,m_crLine);
	pDC->SelectObject(&pen);
	pDC->MoveTo(x,y+m_Radius-5);
    pDC->LineTo(pNode->x,pNode->y-5);
    if((pNode->bIsTrace)&&(pNode->parent!=-1))
	{
		CRect r;
		int xx=(x+pNode->x)/2;
		int yy=(y+pNode->y)/2;
		r.left=xx;
		r.right=r.left+10;
		r.top=yy;
		r.bottom=r.top+10;
		CString s;
		CHuffNode*parent=m_pHuff->m_arHuffman.GetAt(pNode->parent);
		if(parent->lChild==n)
			s='0';
		else s='1';
		pDC->SetBkMode(TRANSPARENT);
		pDC->SetTextColor(RGB(0,255,0));
		pDC->DrawText(s,&r,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
	}
	DrawLine(pDC,pNode->lChild,pNode->x,pNode->y);	
	DrawLine(pDC,pNode->rChild,pNode->x,pNode->y);
}
void CDemoWnd::DrawNode(CDC*pDC,int n)
{
	CHuffNode*pNode=m_pHuff->m_arHuffman.GetAt(n);
	CRect rc=CRect(pNode->x-m_Radius,pNode->y-m_Radius,
		pNode->x+m_Radius,pNode->y+m_Radius);

	if((pNode->lChild==-1)&&(pNode->rChild==-1))
	{
		if(pNode->bFocus)
		{
			DrawTransparentBitmap(&m_bmpLeafF,pDC,RGB(224,220,158),
				rc,CRect(0,0,m_sizeNode.cx,m_sizeNode.cy));
		}
		else 
		{
			DrawTransparentBitmap(&m_bmpLeaf,pDC,RGB(224,220,158),
				rc,CRect(0,0,m_sizeNode.cx,m_sizeNode.cy));
		}
	}
	else 
	{
		if(pNode->bFocus)
		{
			DrawTransparentBitmap(&m_bmpNodeF,pDC,RGB(224,220,158),
				rc,CRect(0,0,m_sizeNode.cx,m_sizeNode.cy));
		}
		else 
		{
			DrawTransparentBitmap(&m_bmpNode,pDC,RGB(224,220,158),
				rc,CRect(0,0,m_sizeNode.cx,m_sizeNode.cy));
		}
	}

	pDC->SetTextColor(m_crNode);
    pDC->SetBkMode(TRANSPARENT);
	CString str;
	if(pNode->weight==-1)
		str="0";
	else str.Format("%d",pNode->weight);
	pDC->DrawText(str,rc,DT_CENTER|DT_SINGLELINE|DT_VCENTER);
	CRect rect=rc;
	rect.top=rc.bottom+2;
	rect.bottom=rect.top+10;
	pDC->SetTextColor(RGB(0,0,255));
	str.Format("HT[%d]",n+1);
	if(m_Font.m_hObject==NULL)
	{
		VERIFY(m_Font.CreateFont(
			12,                        // nHeight
			0,                         // nWidth
			0,                         // nEscapement
			0,                         // nOrientation
			FW_NORMAL,                 // nWeight
			FALSE,                     // bItalic
			FALSE,                     // bUnderline
			0,                         // cStrikeOut
			ANSI_CHARSET,              // nCharSet
			OUT_DEFAULT_PRECIS,        // nOutPrecision
			CLIP_DEFAULT_PRECIS,       // nClipPrecision
			DEFAULT_QUALITY,           // nQuality
			DEFAULT_PITCH | FF_SWISS,  // nPitchAndFamily
			"Arial"));                 // lpszFacename
	}
	CFont*oldFont=pDC->SelectObject(&m_Font);
	pDC->DrawText(str,rect,DT_CENTER|DT_SINGLELINE|DT_VCENTER);
	pDC->SelectObject(oldFont);
}
void CDemoWnd::DrawCode(CDC*pDC)
{
	if((m_pHuff==NULL)||(m_pHuff->m_bEnCode==FALSE))
		return;
	CRect rcCode;
	GetClientRect(&rcCode);
	int w=rcCode.Width();
	if(m_pHuff->m_Bits.m_Length>6)
		w=(w-40-m_pHuff->m_Bits.m_Length*20)/2;
	else w=(w-40-6*20)/2;
    rcCode.left+=w;
	rcCode.right-=w;
	rcCode.bottom-=40;
	rcCode.top=rcCode.bottom-20;	
	pDC->FillRect(rcCode,&CBrush(RGB(255,0,0)));
	
	int line=rcCode.left+40;
	CPen pen;
	pen.CreatePen(PS_SOLID,2,RGB(0,255,0));
	CPen*oldpen=pDC->SelectObject(&pen);
    while(line<rcCode.right)
	{
		pDC->MoveTo(line,rcCode.top);
		pDC->LineTo(line,rcCode.bottom);
		line+=20;
	}
    pDC->SelectObject(oldpen);

	CRect rect=rcCode;
	rect.right=rect.left+40;
	pDC->SetBkMode(TRANSPARENT);
	pDC->SetTextColor(RGB(0,0,0));
	pDC->DrawText("编码",rect,DT_CENTER|DT_SINGLELINE|DT_VCENTER);
	CString code=m_pHuff->m_Bits.GetBits();
	for(int i=m_pHuff->m_Bits.m_Length>6?m_pHuff->m_Bits.m_Length-1
		:5;i>=0;i--)
	{
		CRect r=rcCode;
		r.right-=i*20;
		r.left=r.right-20;
		//pDC->Draw3dRect(&r,RGB(255,0,0),RGB(255,0,0));
		if(i<m_pHuff->m_Bits.m_Length)
			pDC->DrawText(code.GetAt(code.GetLength()-i-1),r,DT_CENTER|DT_SINGLELINE|DT_VCENTER);
		else pDC->DrawText("--",r,DT_CENTER|DT_SINGLELINE|DT_VCENTER);
	}
	ASSERT(m_Font.m_hObject!=NULL);
	CFont*old=pDC->SelectObject(&m_Font);
	pDC->SetTextColor(RGB(255,0,0));
	for(i=0;i<m_pHuff->m_HTCode.GetLength();i++)
	{
		CHuffNode*pNode=m_pHuff->m_arHuffman.GetAt(i);
		CString bits=m_pHuff->m_HTCode.GetBits(i);	
		TRACE2("%d,%s\n",i,bits);
		CSize size=pDC->GetTextExtent(bits+'['+']');
		CRect rect=CRect(pNode->x-size.cx/2,pNode->y+m_Radius+14,
			pNode->x+size.cx/2,pNode->y+m_Radius+14+10);		
		pDC->DrawText('['+bits+']',rect,DT_CENTER|DT_SINGLELINE|DT_VCENTER);

	}
	pDC->SelectObject(old);
}
void CDemoWnd::DrawTransparentBitmap(CBitmap *pBitmap, CDC *pDC, COLORREF crTrans, const CRect &rcDest, const CRect &rcSrc)
{
	int SaveImageDC;
	// initialize image DC
	CDC imageDC;
	imageDC.CreateCompatibleDC(pDC);
	SaveImageDC = imageDC.SaveDC();
	imageDC.SelectObject(pBitmap);

	TransparentBlt(&imageDC,pDC,crTrans,rcDest,rcSrc);

	// clean up
	imageDC.RestoreDC(SaveImageDC);
}
void CDemoWnd::TransparentBlt(CDC *pSrcDC, CDC *pDestDC, COLORREF crTrans, const CRect &rcDest, const CRect &rcSrc)
{
		int SaveDestDC = pDestDC->SaveDC();
	int SaveSrcDC = pSrcDC->SaveDC();

#ifdef CCREDITCTRL_USE_TRANSPARENT_BITBLT	// use transparent BitBlts if supported?
		// Only attempt this if device supports functionality. ( untested!! )
	if(pDestDC->GetDeviceCaps(CAPS1) & C1_TRANSPARENT)
	{
		// Special transparency background mode
		pDestDC->SetBkMode(NEWTRANSPARENT);
		pDestDC->SetBkColor(crTrans);
		// Actual blt is a simple source copy; transparency is automatic.
		pDestDC->StretchBlt(rcDest.left, rcDest.top, rcDest.Width(), rcDest.Height(), pSrcDC, rcSrc.left, rcSrc.top,rcSrc.Width(),rcSrc.Height(), SRCCOPY);
		//pDestDC->BitBlt(rcDest.left, rcDest.top, rcDest.Width(), rcDest.Height(), pSrcDC, rcSrc.left, rcSrc.top, SRCCOPY);
	} 
	else	// if driver doesn't support transparent BitBlts, do it the hard way
	{
#endif
		// initialize memory DC and monochrome mask DC
		CDC tmpDC, maskDC;
		CBitmap bmpTmp, bmpMask;
		int SaveTmpDC, SaveMaskDC;
		tmpDC.CreateCompatibleDC(pDestDC);
		maskDC.CreateCompatibleDC(pDestDC);
		SaveTmpDC = tmpDC.SaveDC();
		SaveMaskDC = maskDC.SaveDC();
		bmpTmp.CreateCompatibleBitmap(pDestDC,rcDest.Width(),rcDest.Height());
		bmpMask.CreateBitmap(rcDest.Width(),rcDest.Height(),1,1,NULL);
		tmpDC.SelectObject(&bmpTmp);
		maskDC.SelectObject(&bmpMask);

		// copy existing data from destination dc to memory dc
		tmpDC.BitBlt(0,0,rcDest.Width(),rcDest.Height(),
			pDestDC,rcDest.left,rcDest.top,SRCCOPY);

		// create mask
		pSrcDC->SetBkColor(crTrans);

		maskDC.StretchBlt(0,0,rcDest.Width(),rcDest.Height(),pSrcDC,
			rcSrc.left,rcSrc.top,rcSrc.Width(),rcSrc.Height(),SRCCOPY);
		//maskDC.BitBlt(0,0,rcDest.Width(),rcDest.Height(),pSrcDC,
		//	rcSrc.left,rcSrc.top,SRCCOPY);

		// do some BitBlt magic
		tmpDC.SetBkColor(RGB(255,255,255));
		tmpDC.SetTextColor(RGB(0,0,0));
		tmpDC.StretchBlt(0,0,rcDest.Width(),rcDest.Height(),pSrcDC,
			rcSrc.left,rcSrc.top,rcSrc.Width(),rcSrc.Height(),SRCINVERT);
		tmpDC.BitBlt(0,0,rcDest.Width(),rcDest.Height(),&maskDC,0,0,SRCAND);
		tmpDC.StretchBlt(0,0,rcDest.Width(),rcDest.Height(),pSrcDC,
			rcSrc.left,rcSrc.top,rcSrc.Width(),rcSrc.Height(),SRCINVERT);
		
		// copy what we have in our memory DC to the destination DC
		pDestDC->BitBlt(rcDest.left,rcDest.top,rcDest.Width(),
			rcDest.Height(),&tmpDC,0,0,SRCCOPY);

		// clean up
		tmpDC.RestoreDC(SaveTmpDC);
		maskDC.RestoreDC(SaveMaskDC);

#ifdef CCREDITCTRL_USE_TRANSPARENT_BITBLT
	}
#endif
	pDestDC->RestoreDC(SaveDestDC);
	pSrcDC->RestoreDC(SaveSrcDC);
}
void CDemoWnd::Attach(CHuffmanCode*pHuff)
{
	ASSERT(pHuff);
	m_pHuff=pHuff;
}
void CDemoWnd::detach()
{
	m_pHuff=NULL;
}
void CDemoWnd::LoadBmp(CString szBK,CString szNode,
		CString szNodeF,CString szLeaf,CString szLeafF)
{
	CHuffmanDlg*pDlg=(CHuffmanDlg*)GetParent();
	pDlg->LoadPictureFile(szBK,&m_bmpBK,m_sizeBK);
	pDlg->LoadPictureFile(szNode,&m_bmpNode,m_sizeNode);
	pDlg->LoadPictureFile(szNodeF,&m_bmpNodeF,m_sizeNode);
	pDlg->LoadPictureFile(szLeaf,&m_bmpLeaf,m_sizeNode);
	pDlg->LoadPictureFile(szLeafF,&m_bmpLeafF,m_sizeNode);
}
BOOL CDemoWnd::Calculate()
{
	if((m_pHuff==NULL)||(m_pHuff->m_arHuffman.GetLength==0))
		return FALSE;
	GetClientRect(m_rcDraw);

	int num=0;
	m_yStart=10;
	for(int i=0;i<m_pHuff->m_arHuffman.GetLength();i++)
	{
		CHuffNode*pNode=m_pHuff->m_arHuffman.GetAt(i);
		if(pNode->bUse)
		{
			if(pNode->parent==-1)
			{
				if((pNode->lChild!=-1)||(pNode->rChild!=-1))
				{
					int left=0,right=0,dep=0;
					int level=GetLevel(i);
					int xdis=m_xInterval,ydis=m_yInterval;
					if(level==1)
					{
						xdis=m_xInterval/3;
						ydis=m_yInterval*5;
					}
					else if(level==2)
					{
						xdis=m_xInterval;///2;
						ydis=m_yInterval*4;
					}
					else if(level==3)
					{
						xdis=m_xInterval;
						ydis=m_yInterval*3;
					}
					else if(level==4)
					{
						xdis=m_xInterval*2;
						ydis=m_yInterval*2;
					}
					else if(level==5)
					{
						xdis=m_xInterval*2;
						ydis=(int)(m_yInterval*1.5);
					}
					else if(level==6)
					{
						xdis=m_xInterval*3;
						ydis=(int)(m_yInterval*1.3);
					}
					//得到树的左右下的深度
					AdjustTreePos(i,xdis,ydis,0,0,left,right,dep);
    				AdjustTreePos(i,xdis,ydis,m_rcDraw.right
						-right-2*m_Radius-20,m_yStart+m_Radius);
					/*int over=IsOverlap();
					while(over!=0)
					{
					//	if(over==1)
						m_xInterval++;
					//	else if(over==2)
					//		m_yInterval++;
					//	else if(over==3)
					//		m_xInterval--;
                        left=right=dep=0;  
						//得到树的左右下的深度                        
						AdjustTreePos(i,m_xInterval,0,0,left,right,dep);
						AdjustTreePos(i,m_xInterval,m_rcDraw.right
							-right-2*m_Radius-20,m_yStart+m_Radius);						
						over=IsOverlap();
					}//*/
					m_rcDraw.right-=(right-left)+2*m_Radius+10;//right-left为数的横向宽度
					if((m_rcDraw.right-m_rcDraw.left)<0)
						m_yStart+=dep+5;
				}
				else num++;
			}
		}
	}
	if(num==0)
		return TRUE;
	m_Interval=(m_rcDraw.Width()-2*m_Radius*num-2*m_xStart)/num;
/*	while((m_Interval<5)&&(m_Radius>=15))
	{
		m_Radius--;
		
		TRACE1("r:%d\n",m_Radius);
        m_Interval=(m_rcDraw.Width()-2*m_Radius*num-2*m_xStart)/num;
	}//*/
	int delt=m_xStart+m_Radius;
	for(i=0;i<m_pHuff->m_arHuffman.GetLength();i++)
	{
		CHuffNode*pNode=m_pHuff->m_arHuffman.GetAt(i);
		if(pNode->weight!=-1)
		{
			if((pNode->parent==-1)&&(pNode->lChild==-1)&&
				(pNode->rChild==-1))
			{
				pNode->x=delt;
				delt+=2*m_Radius+m_Interval;
				pNode->y=m_yStart+m_Radius;
			}
		}
	}
	return TRUE;
}
int CDemoWnd::GetLevel(int n)
{
	int depth,left,right;
	if(n==-1)
	{
		depth=-1;		
	}
	else 
	{
		CHuffNode*pNode=m_pHuff->m_arHuffman.GetAt(n);
		left=GetLevel(pNode->lChild);//左子树
	    right=GetLevel(pNode->rChild);//右子树
		depth=1+(left>right?left:right);
	}
	return depth;
}
//调整树的位置
//xDelt:上一级横向偏移
void CDemoWnd::AdjustTreePos(int n,int xDelt,int yDelt,
							 int x,int y)
{
	if(n==-1)
	{	
		return ;
	}
	CHuffNode*pNode=m_pHuff->m_arHuffman.GetAt(n);
	pNode->x=x;
	pNode->y=y;

	int cypos,cxpos;

	cxpos=x-(int)(xDelt/m_xScale);
	cypos=y+yDelt;//(int)(yDelt/m_yScale);
	AdjustTreePos(pNode->lChild,(int)(xDelt/m_xScale),
		yDelt/*(int)(yDelt/m_yScale)*/,cxpos,cypos);//调整左子树
	cxpos=x+(int)(xDelt/m_xScale);
	AdjustTreePos(pNode->rChild,(int)(xDelt/m_xScale),
		yDelt/*(int)(yDelt/m_yScale)*/,cxpos,cypos);//调整右子树
}
//xDelt:横向偏移，yDelt:纵向偏移
void CDemoWnd::AdjustTreePos(int n,int xDelt,int yDelt,
							 int x,int y,int &lDep,
							 int &rDep,int &Dep )
{
	if(n==-1)
	{	
		return ;
	}
	CHuffNode*pNode=m_pHuff->m_arHuffman.GetAt(n);
	pNode->x=x;
	pNode->y=y;
	if(x<lDep)
		lDep=x;
	if(x>rDep)
		rDep=x;
	if(y>Dep)
		Dep=y;

	int cypos,cxpos;
	cxpos=x-(int)(xDelt/m_xScale);
	cypos=y+yDelt/*(int)(yDelt/m_yScale)*/;
	AdjustTreePos(pNode->lChild,(int)(xDelt/m_xScale),
		yDelt/*(int)(yDelt/m_yScale)*/,cxpos,cypos,
		lDep,rDep,Dep);//调整左子树
	cxpos=x+(int)(xDelt/m_xScale);
	AdjustTreePos(pNode->rChild,(int)(xDelt/m_xScale),
		yDelt/*(int)(yDelt/m_yScale)*/,cxpos,
		cypos,lDep,rDep,Dep);//调整右子树
}
//判断是否重叠
//0：没重叠，1：横向重叠，2：纵向重叠，3：超出左边界
int  CDemoWnd::IsOverlap()
{
	for(int i=0;i<m_pHuff->m_arHuffman.GetLength();i++)
	{
		CHuffNode*p1=m_pHuff->m_arHuffman.GetAt(i);
		if(p1->bUse==FALSE)
			continue;
//		if(p1->x<m_rcDraw.left)
//			return 3;
		for(int j=0;j<m_pHuff->m_arHuffman.GetLength();j++)
		{			
			CHuffNode*p2=m_pHuff->m_arHuffman.GetAt(j);
			if(abs(p1->x-p2->x)<2*m_Radius)
				return 1;
//			if(abs(p1->y-p2->y)<2*m_Radius)
//				return 2;			
		}
	}
    return 0;
}