#include "stdafx.h"

class CBits : public CObject
{
	CByteArray m_arrData;
	int  m_iCurByte;
	char m_iCurBit;
public:
	CBits()
	{
		m_iCurByte = -1;
		m_iCurBit = 7;
	}

	BYTE GetAt(int i) const
	{
		ASSERT(i < GetSize());
		int idxByte = i >> 3;//i/8;
		int idxBit  = i & 7;//i%8;
		return (m_arrData[idxByte] >> (7-idxBit)) & 1;
	}

	int GetSize(void) const
	{
		return m_iCurByte < 0 ? 0 : m_iCurByte * 8 + m_iCurBit + 1;
	}

	void Serialize(CArchive &ar)
	{
		if(ar.IsStoring()) {
			ASSERT(m_iCurByte >= -1);
			ar << m_iCurByte << m_iCurBit;
			for(int i = 0; i <= m_iCurByte; ++i)
				ar << m_arrData[i];
		} else {
			ar >> m_iCurByte >> m_iCurBit;
			ASSERT(m_iCurByte >= -1);
			m_arrData.SetSize(m_iCurByte+1);
			for(int i = 0; i <= m_iCurByte; ++i)
				ar >> m_arrData[i];
		}
	}
};

struct Sym { BYTE byte, nLen; };
struct Tree { Tree *l,*r; Sym sym; };
typedef Tree * PTREE;

static void DecodingTree(CBits & treeCode,int & idx, PTREE p);
static void DestroyTree(PTREE p);
void Decoding(CFile & desFile, CFile & srcFile);

void Decoding(CFile & desFile, CFile & srcFile)
{
	//打開輸入輸出文件
	CArchive ar(&srcFile,CArchive::load);

	CBits codes;
	codes.Serialize(ar);//1.讀出壓縮文件

	Tree tree;
	int i = 0;
	DecodingTree(codes,i,&tree);//2.還原編碼樹

	//3.取出編碼并解碼還原成超符號后寫入文件
	PTREE p = &tree;
	for(int codesLen = codes.GetSize(); i < codesLen; ++i) {
		//search the symbol in huffman tree with code 
		p = codes.GetAt(i) == 0 ? p->l : p->r;
		if(p->l) continue;
		ASSERT(!p->r);
		//found the symbol at leaf of tree
		for(int n = 0; n < p->sym.nLen; ++n) {
			desFile.Write(&p->sym.byte,1);
		}
		p = &tree;
	}
	DestroyTree(tree.l);
	DestroyTree(tree.r);
}

//從treeCode的第i位開始由其后續位串構建一個huffman樹,葉子上存放了超符號
void DecodingTree(CBits & treeCode,int & idx, PTREE p)
{
	ASSERT(treeCode.GetSize() > 0);

	if(treeCode.GetAt(idx++) == 1) { //為節點創建子樹
		DecodingTree(treeCode,idx,p->l = new Tree);
		DecodingTree(treeCode,idx,p->r = new Tree);
	} else { //葉子上存放超符號
		p->l = p->r = NULL;
		for(int i = 0; i < 8; ++i) {
			p->sym.byte <<= 1;
			p->sym.byte |= treeCode.GetAt(idx++);
		}
		for(i = 0; i < 8; ++i) {
			p->sym.nLen <<= 1;
			p->sym.nLen |= treeCode.GetAt(idx++);
		}
	}
}

void DestroyTree(PTREE p) {
	if(p->l) {
		ASSERT(p->r);
		DestroyTree(p->l); p->l = NULL;
		DestroyTree(p->r); p->r = NULL;
	}
	delete p;
}