dictionary.cpp

自己编写的一个采用LZW压缩算法对文件进行压缩的程序；

// Dictionary.cpp: implementation of the CDictionary class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Dictionary.h"
#include <stdio.h>
#include <memory.h>
#include <string.h>
#include "ByteString.h"

////////////////////////////////////////////////////////
static void DestroyDictTree(DictTree* tree)
{
	DictTree* p=tree->sub;
	while( p!=NULL )
	{		
		DestroyDictTree(p);
		p = p->next;
	}

	tree->sub = NULL;
}


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CDictionary::CDictionary()
{
	m_pDictItem = NULL;
	m_pDictTree = NULL;
	m_nRootNum  = 0;
	m_nItemMax  = 0;
	m_nCurCode  = 0;
}

CDictionary::~CDictionary()
{
	Destroy();
}

int CDictionary::Init(unsigned int type)
{
	if( m_pDictItem!=NULL )Destroy();

	switch( type )
	{
	case CDictionary::typeASCII:
		m_nRootNum = 256;
		m_nItemMax = 0xfffe;
		break;
	default:
		m_nRootNum = 0;
		m_nItemMax = 0;
		break;
	}
	if( m_nRootNum==0 )return DICTERR_INVALIDPARAM;

	// init the dictionary tree
	m_pDictTree = new DictTree [m_nRootNum];
	if( m_pDictTree==NULL )return DICTERR_MEMORY;
	for(int i=0; i<m_nRootNum; i++)
	{		
		m_pDictTree[i].code = i;		
		m_pDictTree[i].ch = i;
		m_pDictTree[i].next = NULL;	
		m_pDictTree[i].sub  = NULL;	
	}

	// init the dictionary item table
	m_pDictItem = new DictItem[m_nItemMax+1];
	if( m_pDictItem==NULL )
	{
		delete[] m_pDictTree;
		return DICTERR_MEMORY;
	}

	memset(m_pDictItem,0,sizeof(*m_pDictItem)*(m_nItemMax+1));
	for(i=0; i<m_nRootNum; i++)
	{		
		m_pDictItem[i].code = i;
		m_pDictItem[i].parent = -1;	
		m_pDictItem[i].ch = i;
		m_pDictItem[i].tree = m_pDictTree+i;
	}

	m_nCurCode = m_nRootNum;

	return DICTERR_SUCCESS;
}

void CDictionary::Destroy()
{	
	// destroy the dictionary item table
	if( m_pDictItem )delete[] m_pDictItem;

	// destroy the dictionary tree
	for(int i=0; i<m_nRootNum; i++)DestroyDictTree(m_pDictTree+i);
	delete[] m_pDictTree;

	m_pDictItem = NULL;
	m_pDictTree = NULL;
	m_nRootNum  = 0;
	m_nItemMax  = 0;
	m_nCurCode  = 0;
}

int CDictionary::FindString(CByteString& str, int parent)
{
	int len = str.GetLength();
	if( len<=0 )return DICTERR_INVALIDPARAM;
	//find str along the dictionary tree
	DictTree* tree=m_pDictTree+str[0];	
	BYTE ch;
	if( parent==-1 )
	{
		for(int i=1; i<len; i++)
		{			
			tree = tree->sub;
			if( tree==NULL )return DICTERR_NOTFOUND;

			ch = str[i];
			while( tree!=NULL && tree->ch!=ch )tree = tree->next;
			if( tree==NULL )return DICTERR_NOTFOUND;
		}
	}
	else
	{
		tree = m_pDictItem[parent].tree->sub;
		if( tree==NULL )return DICTERR_NOTFOUND;
	
		ch = str[len-1];
		while( tree!=NULL && tree->ch!=ch )tree = tree->next;
		if( tree==NULL )return DICTERR_NOTFOUND;
	}

	return tree->code;
}

int CDictionary::AddString(CByteString& str, int parent)
{
	int len = str.GetLength();
	if( len<=1 )return DICTERR_INVALIDPARAM;
	if( m_nCurCode>=m_nItemMax )return DICTERR_DICTFULL;

	int parentCode=-1;
	//-------------add str to the dictionary tree
	// get the parent item
	DictTree* cur;
	DictTree* tree=m_pDictTree+str[0];	
	BYTE ch;
	if( parent==-1 )	
	{
		for(int i=1; i<len-1; i++)
		{
			tree = tree->sub;
			if( tree==NULL )return DICTERR_INVALIDPARAM;					
			
			ch = str[i];
			while( tree!=NULL && tree->ch!=ch )tree = tree->next;
			if( tree==NULL )return DICTERR_INVALIDPARAM;
		}

	}
	else
	{
		tree = m_pDictItem[parent].tree;				
	}

	// at this time, tree contains the parent of the item that is about to be inserted
	ch = str[len-1];
	if( tree->sub==NULL )
	{
		parentCode = tree->code;

		cur = new DictTree;
		if( cur==NULL )return DICTERR_MEMORY;	
		cur->ch = ch;
		cur->code = m_nCurCode;
		cur->sub = NULL;
		cur->next = NULL;
		tree->sub = cur;		
	}
	else
	{
		parentCode = tree->code;

		DictTree *last=NULL;
		tree = tree->sub;		
		while( tree!=NULL && tree->ch!=ch )
		{
			last = tree;
			tree = tree->next;			
		}
		if( tree!=NULL )return DICTERR_INVALIDPARAM;
		cur = new DictTree;
		if( cur==NULL )return DICTERR_MEMORY;		
		cur->ch = ch;
		cur->code = m_nCurCode;
		cur->sub = NULL;
		cur->next = NULL;
		last->next = cur;		
	}

	//add str to the dictionary item table
	m_pDictItem[m_nCurCode].code = m_nCurCode;
	m_pDictItem[m_nCurCode].parent = parentCode;
	m_pDictItem[m_nCurCode].ch = ch;
	m_pDictItem[m_nCurCode].tree = cur;

	m_nCurCode++;
	return DICTERR_SUCCESS;
}

bool CDictionary::GetString(unsigned int code, CByteString& str)
{
	if( code>=(unsigned)m_nCurCode||code<0 )return false;
	
	//it take less time to find str along the dictionary item table
	str.Empty();
	while(code!=-1)
	{ 	
		str.Append(m_pDictItem[code].ch); 
		code = m_pDictItem[code].parent; 
	}

	int len = str.GetLength();
	BYTE *buf = str.GetBuffer();
	BYTE ch=0;
	for(int i=0; i<len/2; i++)
	{
		ch = buf[i];
		buf[i] = buf[len-1-i];	
		buf[len-1-i] = ch;			
	}
	
	return true;
}


int CDictionary::FindCode(unsigned int code)
{	
	if( code>=(unsigned)m_nCurCode||code<0 )return DICTERR_NOTFOUND;
	return DICTERR_SUCCESS;
}