// SimpleBinaryTree.cpp: implementation of the CSimpleBinaryTree class.
//
//////////////////////////////////////////////////////////////////////
/*
*
*
* Copyright (c) 2002 DigitalConvict <ax@digitalconvict.com>
* 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: ax@digitalconvict.com
*/
#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++){
