// DlgHuffman.cpp : implementation file
//

#include "stdafx.h"
#include "ch1_1.h"
#include "DlgHuffman.h"
#include "DIBAPI.h"
#include <math.h>

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

/////////////////////////////////////////////////////////////////////////////
// CDlgHuffman dialog


CDlgHuffman::CDlgHuffman(CWnd* pParent /*=NULL*/)
	: CDialog(CDlgHuffman::IDD, pParent)
{
	//{{AFX_DATA_INIT(CDlgHuffman)
	m_dEntropy = 0.0;
	m_dAvgCodeLen = 0.0;
	m_dEfficiency = 0.0;
	//}}AFX_DATA_INIT
}


void CDlgHuffman::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CDlgHuffman)
	DDX_Control(pDX, IDC_LST_Table, m_lstTable);
	DDX_Text(pDX, IDC_EDIT1, m_dEntropy);
	DDX_Text(pDX, IDC_EDIT2, m_dAvgCodeLen);
	DDX_Text(pDX, IDC_EDIT3, m_dEfficiency);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CDlgHuffman, CDialog)
	//{{AFX_MSG_MAP(CDlgHuffman)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDlgHuffman message handlers

BOOL CDlgHuffman::OnInitDialog() 
{
	
	// 字符串變量
	CString	str;
	
	// 循環變量
	LONG	i;
	LONG	j;
	LONG	k;
	
	// 中間變量
	FLOAT	fT;
	
	// ListCtrl的ITEM
	LV_ITEM lvitem;
	
	// 中間變量，保存ListCtrl中添加的ITEM編號
	int		iActualItem;
	
	// 調用默認得OnInitDialog()函數
	CDialog::OnInitDialog();
	
	// 初始化變量
	m_dEntropy = 0.0;
	m_dAvgCodeLen = 0.0;
	
	// 計算圖像熵
	for (i = 0; i < m_iColorNum; i ++)
	{
		// 判斷概率是否大于0
		if (m_fFreq[i] > 0)
		{
			// 計算圖像熵
			m_dEntropy -= m_fFreq[i] * log(m_fFreq[i]) / log(2.0);
		}
	}
	
	// 保存計算中間結果的數組
	FLOAT *	fTemp;
	
	// 保存映射關系的數組
	int	*	iMap;
	
	// 分配內存
	fTemp = new FLOAT[m_iColorNum];
	iMap  = new int[m_iColorNum];
	m_strCode = new CString[m_iColorNum];
	
	// 初始化fTemp為m_fFreq
	for (i = 0; i < m_iColorNum; i ++)
	{
		// 賦值
		fTemp[i] = m_fFreq[i];
		iMap[i] = i;
	}
	
	// 用冒泡法對進行灰度值出現的概率排序，結果保存在數組fTemp中
	for (j = 0; j < m_iColorNum - 1; j ++)
	{
		for (i = 0; i < m_iColorNum - j - 1; i ++)
		{
			if (fTemp[i] > fTemp[i + 1])
			{
				// 互換
				fT = fTemp[i];
				fTemp[i] = fTemp[i + 1];
				fTemp[i + 1] = fT;
				
				// 更新映射關系
				for (k = 0; k < m_iColorNum; k ++)
				{
					// 判斷是否是fTemp[i]的子節點
					if (iMap[k] == i)
					{
						// 改變映射到節點i+1
						iMap[k] = i + 1;
					}
					else if (iMap[k] == i + 1)
					{
						// 改變映射到節點i
						iMap[k] = i;
					}
				}
			}
		}
	}
	
	//////////////////////////////////////////////////////////
	// 計算哈夫曼編碼表
	
	// 找到概率大于0處才開始編碼
	for (i = 0; i < m_iColorNum - 1; i ++)
	{
		// 判斷概率是否大于0
		if (fTemp[i] > 0)
		{
			break;
		}
	}
	
	// 開始編碼
	for (; i < m_iColorNum - 1; i ++)
	{
		// 更新m_strCode
		for (k = 0; k < m_iColorNum; k ++)
		{
			// 判斷是否是fTemp[i]的子節點
			if (iMap[k] == i)
			{
				// 改變編碼字符串
				m_strCode[k] = "1" + m_strCode[k];
			}
			else if (iMap[k] == i + 1)
			{
				// 改變編碼字符串
				m_strCode[k] = "0" + m_strCode[k];
			}
		}
		
		// 概率最小的兩個概率相加，保存在fTemp[i + 1]中
		fTemp[i + 1] += fTemp[i];
		
		// 改變映射關系
		for (k = 0; k < m_iColorNum; k ++)
		{
			// 判斷是否是fTemp[i]的子節點
			if (iMap[k] == i)
			{
				// 改變映射到節點i+1
				iMap[k] = i + 1;
			}
		}
		
		// 重新排序
		for (j = i + 1; j < m_iColorNum - 1; j ++)
		{
			if (fTemp[j] > fTemp[j + 1])
			{
				// 互換
				fT = fTemp[j];
				fTemp[j] = fTemp[j + 1];
				fTemp[j + 1] = fT;
				
				// 更新映射關系
				for (k = 0; k < m_iColorNum; k ++)
				{
					// 判斷是否是fTemp[i]的子節點
					if (iMap[k] == j)
					{
						// 改變映射到節點j+1
						iMap[k] = j + 1;
					}
					else if (iMap[k] == j + 1)
					{
						// 改變映射到節點j
						iMap[k] = j;
					}
				}
			}
			else
			{
				// 退出循環
				break;
			}
		}
	}
	
	// 計算平均碼字長度
	for (i = 0; i < m_iColorNum; i ++)
	{
		// 累加
		m_dAvgCodeLen += m_fFreq[i] * m_strCode[i].GetLength();
	}
	
	// 計算編碼效率
	m_dEfficiency = m_dEntropy / m_dAvgCodeLen;
	
	// 保存變動
	UpdateData(FALSE);
	
	//////////////////////////////////////////////////////////
	// 輸出計算結果
	
	// 設置List控件樣式
	m_lstTable.ModifyStyle(LVS_TYPEMASK, LVS_REPORT);
	
	// 給List控件添加Header
	m_lstTable.InsertColumn(0, "灰度值", LVCFMT_LEFT, 60, 0);
	m_lstTable.InsertColumn(1, "出現頻率", LVCFMT_LEFT, 78, 0);
	m_lstTable.InsertColumn(2, "哈夫曼編碼", LVCFMT_LEFT, 110, 1);
	m_lstTable.InsertColumn(3, "碼字長度", LVCFMT_LEFT, 78, 2);
	
	// 設置樣式為文本
	lvitem.mask = LVIF_TEXT;
	
	// 計算平均碼字長度
	for (i = 0; i < m_iColorNum; i ++)
	{
		// 添加一項
		lvitem.iItem = m_lstTable.GetItemCount();
		str.Format("%u",i);
		lvitem.iSubItem = 0;
		lvitem.pszText= (LPTSTR)(LPCTSTR)str;
		iActualItem = m_lstTable.InsertItem(&lvitem);
		
		// 添加其它列
		lvitem.iItem = iActualItem;
		
		// 添加灰度值出現的頻率
		lvitem.iSubItem = 1;
		str.Format("%f",m_fFreq[i]);
		lvitem.pszText = (LPTSTR)(LPCTSTR)str;
		m_lstTable.SetItem(&lvitem);
		
		// 添加哈夫曼編碼
		lvitem.iSubItem = 2;
		lvitem.pszText = (LPTSTR)(LPCTSTR)m_strCode[i];
		m_lstTable.SetItem(&lvitem);
		
		// 添加碼字長度
		lvitem.iSubItem = 3;
		str.Format("%u",m_strCode[i].GetLength());
		lvitem.pszText = (LPTSTR)(LPCTSTR)str;
		m_lstTable.SetItem(&lvitem);
	}	
	
	// 返回TRUE
	return TRUE;
}