// DlgShannon.cpp : implementation file
//

#include "stdafx.h"
#include "imageprocessing.h"
#include "DlgCoding.h"
#include <math.h>

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

/////////////////////////////////////////////////////////////////////////////
// CDlgShannon dialog


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


void CDlgShannon::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CDlgShannon)
	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(CDlgShannon, CDialog)
	//{{AFX_MSG_MAP(CDlgShannon)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDlgShannon message handlers

BOOL CDlgShannon::OnInitDialog() 
{
	// 調用默認得OnInitDialog()函數
	CDialog::OnInitDialog();

	// 初始化變量
	m_dEntropy = 0.0;
	m_dAvgCodeLen = 0.0;

	// 字符串變量
	CString	str;
	str = "1";
	
	// 循環變量
	LONG	i;
	LONG	j;

	// 控件ListCtrl的ITEM
	LV_ITEM lvItem;

	// 保存控件ListCtrl中添加的ITEM編號
	int		nItem2View;	
	
	// 中間變量
	double	dT;
	LONG	lTemp;
	
	// 保存計算中間結果的數組
	double * dTemp;
	dTemp = new double[m_nColorNum];
	
	// 數組用來存放灰度值和其位置之間的映射
	LONG *	l4Turn;
	l4Turn = new LONG[m_nColorNum];
	
	// 當前編碼區間的概率和
	double	dAccum;
	dAccum = 1.0;

	// 已經編碼灰度值概率的統計和
	double	dSum;
	dSum    = 0;
	
	// 已編碼灰度值
	LONG	lCount = 0;
		
	// 起始位置
	LONG	lBegin;
	
	// 指示編碼是否已經完成一段
	BOOL	* bFinished;
	bFinished = new BOOL[m_nColorNum];
	
	// 分配內存	
	m_strCode = new CString[m_nColorNum];
			
	for (i = 0; i < m_nColorNum; i ++)
	{			
		
		// 初始化為FALSE
		bFinished[i] = FALSE;

		// 將概率賦值dTemp數組
		dTemp[i] = m_dProba[i];
		
		// 按灰度值大小順序排列
		l4Turn[i] = i;
		
	}
	
	// 用冒泡法對進行灰度值出現的概率排序
	// 同時改變灰度值位置的映射關系
	for (j = 0; j < m_nColorNum - 1; j ++)
		for (i = 0; i < m_nColorNum - j - 1; i ++)
			if (dTemp[i] > dTemp[i + 1])
			{
				// 互換
				dT = dTemp[i];
				dTemp[i] = dTemp[i + 1];
				dTemp[i + 1] = dT;
				
				// 將i和i+1灰度的位置值互換
				lTemp = l4Turn[i];
				l4Turn[i] = l4Turn[i+1];
				l4Turn[i+1] = lTemp;
				
			}
		
	/*******************************************************
	計算香農－弗諾編碼表
	*******************************************************/
	
	// 從概率大于0處開始編碼
	for (lBegin = 0; lBegin < m_nColorNum - 1; lBegin ++)
		if (dTemp[lBegin] > 0)
			break;

	// 開始編碼
	while(lCount < m_nColorNum)
	{
		// 從概率大于零的灰度值開始編碼
		lCount = lBegin;
		
		// 對區間進行分割，對每個區間的灰度值編碼
		for (i = lBegin; i < m_nColorNum; i ++)
		{
			// 判斷是否編碼完成
			if (bFinished[i] == FALSE)
			{
				// 增加當前編碼區間的概率綜合
				dSum += dTemp[i];
				
				// 判斷是否超出總和的一半
				if (dSum > dAccum/2.0)
				{
					// 超出，追加的字符改為0
					str = "0";
				}
				
				// 追加字符
				m_strCode[l4Turn[i]] = m_strCode[l4Turn[i]] + str;
				
				// 判斷是否編碼完一段
				if (dSum == dAccum)
				{
					// 完成一部分編碼，重新計算dAccum
					
					// 初始化dSum為0
					dSum = 0;
					
					// 判斷是不是對所有灰度值已經編碼一遍
					if (i == m_nColorNum - 1)
						j = lBegin;
					else
						j = i + 1;
					
					// 保存j值
					lTemp = j;
					str = m_strCode[l4Turn[j]];
					
					// 計算下一編碼區間的概率總和
					dAccum = 0;
					for (; j < m_nColorNum; j++)
					{
						// 判斷是否是同一段編碼
						if ((m_strCode[l4Turn[j]].Right(1) != str.Right(1)) 
							|| (m_strCode[l4Turn[j]].GetLength() != str.GetLength()))
							break;

						// 當前區間的概率總和增加
						dAccum += dTemp[j];
					}
					
					// 碼字增加值為1
					str = "1";
					
					// 判斷該段編碼已經完成
					if (lTemp + 1 == j)
						bFinished[lTemp] = TRUE;
				}
			}
			else
			{
				//  開始下一輪編碼
				lCount ++;
				
				// 重新賦2dSum為0
				dSum = 0;
				
				// 判斷是不是對所有灰度值已經編碼一遍
				if (i == m_nColorNum - 1)
					j = lBegin;
				else
					j = i + 1;
				
				// 保存j值
				lTemp = j;
				str = m_strCode[l4Turn[j]];
				
				// 計算下一編碼區間的概率總和
				dAccum = 0;
				for (; j < m_nColorNum; j++)
				{
					// 判斷是否是同一段編碼
					if ((m_strCode[l4Turn[j]].Right(1) != str.Right(1)) 
						|| (m_strCode[l4Turn[j]].GetLength() != str.GetLength()))
					{
						// 退出循環
						break;
					}
					
					// 累加
					dAccum += dTemp[j];
				}
				
				str = "1";
				
				// 判斷該段編碼已經完成
				if (lTemp + 1 == j)
					bFinished[lTemp] = TRUE;
			}
		}
	}
	
	// 計算圖像熵
	for (i = 0; i < m_nColorNum; i ++)
	{
		// 判斷概率是否大于0
		if (m_dProba[i] > 0)
		{
			// 計算圖像熵
			m_dEntropy -= m_dProba[i] * log(m_dProba[i]) / log(2.0);
		}
	}
	
	// 計算平均碼字長度
	for (i = 0; i < m_nColorNum; i ++)
	{
		// 累加
		m_dAvgCodeLen += m_dProba[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_nColorNum; i ++)
	{
		// 第一列顯示
		lvItem.iItem = m_lstTable.GetItemCount();
		str.Format("%u",i);
		lvItem.iSubItem = 0;
		lvItem.pszText= (LPTSTR)(LPCTSTR)str;
		nItem2View = m_lstTable.InsertItem(&lvItem);
		
		// 其它列顯示
		lvItem.iItem = nItem2View;
		
		// 添加灰度值出現的頻率
		lvItem.iSubItem = 1;
		str.Format("%f",m_dProba[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);
	}
	
	//  內存釋放
	delete l4Turn;
	delete dTemp;
	delete bFinished;
	
	return TRUE;
}