simplebinarytree.cpp

一个简单二叉树类（非本人原创）

// SimpleBinaryTree.cpp: implementation of the CSimpleBinaryTree class.
//
//////////////////////////////////////////////////////////////////////
/*
 *
 *
 *  Copyright (c) 2002 DigitalConvict <[e-mail]>
 *  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *
 * Contact info:
 * Site: http://www.digitalconvict.com
 * Email: [e-mail]
 */

#include "stdafx.h"
#include "SimpleBinaryTree.h"

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

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

CSimpleBinaryTree::CSimpleBinaryTree()
{
	m_nLastItemIndex=0;
	m_nTotalItems=0;
	m_nArraySize=0;
	m_nSizeOfItem=0;
	m_nDoBSThreshold=10;
	m_BTree=NULL;
	m_bAllowDuplicates=TRUE;
	m_bAutoResize=TRUE;
	m_bInitialised=FALSE;
	m_bFullySorted=FALSE;
}

/**********************************************************************
	Destructor:  Calls FreeMemory method;
**********************************************************************/
CSimpleBinaryTree::~CSimpleBinaryTree()
{
	FreeMemory();
}

/**********************************************************************
	Adds a new item to the BTree by allocating space for the new item
	and adding the pointer to the BTree array. Returns negative value
	on error.
**********************************************************************/
int CSimpleBinaryTree::AddItem(const void* pNewData, void* pStoredObject)
{
	ASSERT(m_bInitialised);

	int nResult;
	int nNewItemIndex;
	pStoredObject=NULL;

	if(m_bAutoResize 
		&& (int)((m_nTotalItems*100)/m_nArraySize)>=m_nGrowTrigger)
		ReSize(m_nArraySize+((m_nArraySize*m_nGrowByValue)/100));

	if(m_nLastItemIndex<(int)(m_nArraySize)){
		if(!m_bAllowDuplicates && FindItem(pNewData)>=0)
			return DUPLICATE_FOUND;

		if((m_BTree[m_nLastItemIndex]=malloc(m_nSizeOfItem))!=NULL){
			memcpy(m_BTree[m_nLastItemIndex], pNewData, m_nSizeOfItem);
			// increment total number of items in tree before any
			// sorting might be done - Thanks Steve V
			m_nTotalItems++;
			if(!m_bAllowDuplicates && m_nTotalItems>=m_nDoBSThreshold){
				SortItems();
				// use a full search if in Binary Search mode
				// as the index will most likely not be the last one
				// since we just sorted the tree - Thanks Steve V
				nNewItemIndex=FindItem(pNewData);
				pStoredObject=m_BTree[nNewItemIndex];
				nResult=nNewItemIndex;			
			} else {
				m_bFullySorted=FALSE;
				pStoredObject=m_BTree[m_nLastItemIndex];
				nResult=m_nLastItemIndex;
			}
			m_nLastItemIndex++;
		} else
			nResult=OUT_OF_MEMORY;
	} else
		nResult=TREE_IS_FULL;

	return nResult;
}

/**********************************************************************
	Decides which search method to use to find an item.  If the Array
	size is below the Binary Search Threshold then a linear search is
	performed instead of a Binary Search.
**********************************************************************/
int CSimpleBinaryTree::FindItem(const void* pvItemToFind, void* pvItemFound)
{
	ASSERT(m_bInitialised);

	int nResult;
	void **ptpItem=(void **)&pvItemToFind;
	pvItemFound=NULL;

	if(m_nTotalItems>m_nDoBSThreshold)
		nResult=BinarySearch(ptpItem);
	else
		nResult=LinearSearch(ptpItem);

	if(nResult!=ITEM_NOT_PRESENT)
		pvItemFound=m_BTree[nResult];

	return nResult;
}

/**********************************************************************
	Initialisation function MUST be called after object is created.
	Sets internal member variables and allocates memory for BTree array.
**********************************************************************/
BOOL CSimpleBinaryTree::Initialise(size_t nNumItems, size_t nItemSize,
									int (*compar)(const void *, 
										const void *),
									int nGrowTrigger,
									int nGrowByValue,
									int nShrinkTrigger,
									int nShrinkByValue)

{
	if(m_bInitialised)
		FreeMemory();

	if((m_BTree=new void*[nNumItems])==NULL)
		return FALSE;

	m_pfuncCompare=compar;
	m_nSizeOfItem=nItemSize;
	m_nArraySize=nNumItems;
	m_nGrowTrigger=nGrowTrigger;
	m_nGrowByValue=nGrowByValue;
	m_nShrinkTrigger=nShrinkTrigger;
	m_nShrinkByValue=nShrinkByValue;

	m_bInitialised=TRUE;

	return TRUE;
}

/**********************************************************************
	Simply sorts the elements in the array using C's quick sort function
**********************************************************************/
void CSimpleBinaryTree::SortItems()
{
	qsort(m_BTree, m_nTotalItems, sizeof(void *), m_pfuncCompare);
	m_bFullySorted=TRUE;
}

/**********************************************************************
	Shrinks or Grows the BTree according to the new Size indicated by
	nNewSize.  If nNewSize equals the current size or no more memory can
	be allocated the function returns FALSE otherwise returns TRUE.

	Elements of the array are copied to a new array and then deleted from
	the original array m_BTree;  m_BTree is then assigned the pointer to
	the	newly allocated array.
**********************************************************************/
BOOL CSimpleBinaryTree::ReSize(size_t nNewSize)
{
	ASSERT(m_bInitialised);

	BOOL bRetval=FALSE;
	void** pTempTree;
	pTempTree=new void*[nNewSize];

	if(pTempTree==NULL || nNewSize==m_nArraySize)
		return FALSE;

	int nLimit = (m_nTotalItems<(int)nNewSize ? m_nTotalItems : (int)nNewSize);

	memcpy(pTempTree, m_BTree, sizeof(void*)*nLimit);
	
	if((int)nNewSize<m_nTotalItems){
		for(int i=nLimit;i<m_nTotalItems;i++){
			delete m_BTree[i];
		}
	}

	delete[] m_BTree;
	m_BTree=pTempTree;
	m_nArraySize=nNewSize;

	if((int)nNewSize<m_nTotalItems)
		m_nTotalItems=nNewSize;

	return TRUE;
}

/**********************************************************************
	Returns a void* which points to the data item of the BTree indexed by
	nItem.  Returns NULL if nItem index is outside the valid range
**********************************************************************/
void* CSimpleBinaryTree::GetItemPtr(int nItem)
{
	ASSERT(m_bInitialised);

	if(nItem>=0 && nItem<m_nTotalItems)
		return m_BTree[nItem];
	else
		return NULL;
}

/**********************************************************************
	Frees up any heap memory allocated for the BTree array and items
	contained there within.  User should never have to call this unless
	they need memory in a hurry and are willing to destroy the BTree.

	Better to let the BTree go out of scope and have the default
	destructor call FreeMemory() automatically.
**********************************************************************/
void CSimpleBinaryTree::FreeMemory()
{
	ASSERT(m_bInitialised);

	for(int i=0;i<m_nTotalItems;i++){
		delete m_BTree[i];
	}
	if(m_BTree!=NULL){
		delete[] m_BTree;
		m_BTree=NULL;
		m_nLastItemIndex=0;
		m_nTotalItems=0;
	}
}

/**********************************************************************
	Removes an Item from the BTree. Item is deleted and all pointers 
	above this position in the array are shifted left 1 place. Item count
	member variable is updated accordingly. Returns TRUE if nItem is in
	the range of valid indexes.
**********************************************************************/
BOOL CSimpleBinaryTree::RemoveItem(int nItem)
{
	ASSERT(m_bInitialised);

	if(nItem>=0 && nItem<m_nTotalItems){
		delete m_BTree[nItem];
		for(int i=nItem+1;i<m_nTotalItems;i++){
			m_BTree[i-1]=m_BTree[i];
		}
		m_BTree[--m_nTotalItems]=NULL;
		m_nLastItemIndex--;

		if(m_bAutoResize 
			&& (int)((m_nTotalItems*100)/m_nArraySize)<=m_nShrinkTrigger)
			ReSize(m_nArraySize-((m_nArraySize*m_nShrinkByValue)/100));

		return TRUE;
	}

	return FALSE;
}

/**********************************************************************
	Performs a linear search on the elements of the m_BTree array.
	Returns the index of the element if the item is found or -1 otherwise
**********************************************************************/
int CSimpleBinaryTree::LinearSearch(const void* pvItemToFind)
{
	int nRetval=ITEM_NOT_PRESENT;

	for(int i=0;i<m_nTotalItems;i++){