A Faster Tree Control

#ifndef RGTREET_H
#define RGTREET_H

/**********************************************************************************************
 *                                                                                            *
 *  FILE: RGTreeT.h                                                                           *
 *                                                                                            *
 *  DESCRIPTION:                                                                              *
 *       Template class for implementing a tree structure like the WinAPI tree control        *
 *                                                                                            *
 *  Ren� Greiner                                                                              *
 *		eMail: rene.greiner@gmx.de                                                            *
 *                                                                                            *
 **********************************************************************************************/

// abstract iteration position
//struct __POSITION { };
//typedef __POSITION* POSITION;

typedef int (CALLBACK* CompareFunc)( LPARAM lParam1, LPARAM lParam2);
typedef void (CALLBACK* DeleteFunc)( POSITION pos, LPARAM lParam);

template<class _T> inline void swap_classes( _T& t1, _T& t2)
{
	_T temp = t1;
	t1 = t2;
	t2 = temp;
}

template<class _ITEMDATA> class CRGTreeT
{
	// lParam1 < lParam2	=>  < 0
	// lParam1 > lParam2	=>	> 0
	// lParam1 == lParam2	=>  = 0
	
#pragma pack(push,4)
	typedef struct CTreeItem
	{
		CTreeItem*		pTIParent;
		CTreeItem*		pTIPrev;
		CTreeItem*		pTINext;
		CTreeItem*		pTIChildFirst;
		CTreeItem*		pTIChildLast;
		int				nChildCount;
		_ITEMDATA		ItemData;
		CTreeItem()		
		{
			nChildCount = 0; pTIChildFirst = pTIChildLast = NULL; 
		}
	} CTreeItem;
	
#pragma pack(pop)
#define INC_ITEMS(pParent)	{pParent->nChildCount++; m_nCount++;}
#define DEC_ITEMS(pParent)	{pParent->nChildCount--; m_nCount--;}
	
public:
	// Construction / Destruction
	CRGTreeT();
	~CRGTreeT();

	// returns the count of all items
	UINT GetItemCount() const;
	// returns the count of all child items 
	UINT GetChildCount( /*[in]*/ POSITION posParent) const;

	// returns the root
	POSITION GetRootPosition() const;
	// returns the parent of an item
	POSITION GetParentPosition( /*[in]*/ POSITION pos) const;

	// adds an items at the begin of the list
	POSITION AddHead( /*[in]*/ const _ITEMDATA *pItemData, /*[in]*/ POSITION posParent=NULL);
	// adds an items at the end of the list
	POSITION AddTail( /*[in]*/ const _ITEMDATA *pItemData, /*[in]*/ POSITION posParent=NULL);
	POSITION InsertAfter( /*[in]*/ const _ITEMDATA *pItemData, POSITION posParent=NULL, /*[in]*/POSITION posAfter=NULL);

	// Remove the item at position pos including all subitems
	void RemoveAt( /*[in]*/ POSITION pos);
	// Removes all items
	void RemoveAll();

	// returns the first/last child item of the item at position posParent
	POSITION GetChildPosition( /*[in]*/ POSITION posParent, /*[in]*/ BOOL bFirst=TRUE) const;
	// returns the next list element, NULL if none
	POSITION GetNextPosition( /*[in]*/ POSITION pos) const;
	// returns the previous element, NULL if none
	POSITION GetPrevPosition( /*[in]*/ POSITION pos) const;

	// returning a copy of the ITEMDATA at position pos
	void GetAt( /*[in]*/ POSITION pos, /*[out]*/ _ITEMDATA* pItemData) const;
	// Returning a pointer to the ITEMDATA at position pos
	_ITEMDATA* GetAt( /*[in]*/ POSITION pos);
	// replace the ITEMDATA at position pos
	void SetAt( /*[in]*/ POSITION pos, /*[in]*/ const _ITEMDATA* pItemData);

	// sort childrens of the item at position posParent
	BOOL SortChildren( /*[in]*/ POSITION posParent, /*[in]*/ BOOL bAscending=TRUE);

	// search for an item based on the compare function
	POSITION Find( /*[in]*/ const _ITEMDATA *pItemData, /*[in]*/ POSITION posParent);
	// setting a callback function for sorting and finding items
	CompareFunc SetCompareFunc( /*[in]*/ CompareFunc func);
	DeleteFunc SetDeleteFunc( /*[in]*/ DeleteFunc func, LPARAM lParam);

protected:
	// remove all childs from an item
	void RemoveChilds( POSITION pos);
	// quick sort algorithms for sorting up- or downwards
	void QSortA( /*[in]*/ CTreeItem **pLow, /*[in]*/ CTreeItem **pHigh);
	void QSortD( /*[in]*/ CTreeItem **pLow, /*[in]*/ CTreeItem **pHigh);

private:
	CTreeItem			m_ItemRoot;
	UINT					m_nCount;
	CompareFunc		m_pCompareFunc;
	DeleteFunc		m_pDeleteFunc;
	LPARAM				m_lParamDeleteFunc;
};


template<class _ITEMDATA>
inline CRGTreeT<_ITEMDATA>::CRGTreeT()
{
	m_nCount = 0;
	memset( &m_ItemRoot, 0, sizeof(CTreeItem));
	m_pCompareFunc = NULL;
	m_pDeleteFunc = NULL;
}

template<class _ITEMDATA>
inline CRGTreeT<_ITEMDATA>::~CRGTreeT()
{
	RemoveAll();
}

template<class _ITEMDATA>
inline UINT CRGTreeT<_ITEMDATA>::GetItemCount() const
{
	return m_nCount;
}

template<class _ITEMDATA>
inline UINT CRGTreeT<_ITEMDATA>::GetChildCount( POSITION posParent) const
{
	return (posParent ? (CTreeItem*)posParent : &m_ItemRoot)->nChildCount;
}

template<class _ITEMDATA>
inline POSITION CRGTreeT<_ITEMDATA>::GetRootPosition() const
{
	return (POSITION)m_ItemRoot.pTIChildFirst;
}

template<class _ITEMDATA>
inline POSITION CRGTreeT<_ITEMDATA>::GetParentPosition( POSITION pos) const
{
	ASSERT(pos);
	return ((CTreeItem*)pos)->pTIParent == &m_ItemRoot ? NULL : (POSITION)((CTreeItem*)pos)->pTIParent;
}

template<class _ITEMDATA>
inline POSITION CRGTreeT<_ITEMDATA>::AddHead( const _ITEMDATA *pItemData, POSITION posParent)
{
	CTreeItem *pParent = posParent ? (CTreeItem*)posParent : &m_ItemRoot;
	CTreeItem *pItem = new CTreeItem;
	pItem->ItemData = *pItemData;
	pItem->pTIParent = pParent;
	pItem->pTIPrev = NULL;
	if( pParent->pTIChildFirst)
	{
		pParent->pTIChildFirst->pTIPrev = pItem;
		pItem->pTINext = pParent->pTIChildFirst;
	}
	else
	{
		pItem->pTINext = NULL;
		pParent->pTIChildLast = pItem;
	}
	pParent->pTIChildFirst = pItem;

	INC_ITEMS( pParent)
	return (POSITION)pItem;
}

template<class _ITEMDATA>
inline POSITION CRGTreeT<_ITEMDATA>::AddTail( const _ITEMDATA *pItemData, POSITION posParent)
{
	register CTreeItem *pParent = posParent ? (CTreeItem*)posParent : &m_ItemRoot;
	register CTreeItem *pItem = new CTreeItem;
	pItem->ItemData = *pItemData;
	pItem->pTINext = NULL;
	pItem->pTIParent = pParent;
	if( pParent->pTIChildLast)
	{
		pParent->pTIChildLast->pTINext = pItem;
		pItem->pTIPrev = pParent->pTIChildLast;
	}
	else
	{
		pItem->pTIPrev = NULL;
		pParent->pTIChildFirst = pItem;
	}
	pParent->pTIChildLast = pItem;

	INC_ITEMS( pParent)
	return (POSITION)pItem;
}

template<class _ITEMDATA>
inline POSITION CRGTreeT<_ITEMDATA>::InsertAfter( const _ITEMDATA *pItemData, POSITION posParent, POSITION posAfter)
{
	if( posAfter == NULL
		|| posAfter == (POSITION)TVI_ROOT)
		return AddTail( pItemData, posParent);

	CTreeItem *pParent = posParent ? (CTreeItem*)posParent : &m_ItemRoot;
	CTreeItem *pAfter = (CTreeItem*)posAfter;
	if( pAfter->pTIParent != pParent)
		return NULL;
	if( pParent->pTIChildLast == pAfter)
		return AddTail( pItemData, posParent);

	CTreeItem *pItem = new CTreeItem;
	ASSERT(pItem);
	pItem->ItemData = *pItemData;
	pItem->pTIParent = pParent;

	pItem->pTIPrev = pAfter;
	pItem->pTINext = pAfter->pTINext;
	pAfter->pTINext = pItem;
	pItem->pTINext->pTIPrev = pItem;

	INC_ITEMS( pParent)
	return (POSITION)pItem;
}

template<class _ITEMDATA>
inline void CRGTreeT<_ITEMDATA>::RemoveAt( POSITION pos)
{
	RemoveChilds( GetChildPosition( pos));
	CTreeItem *pNext = ((CTreeItem*)pos)->pTINext;
	CTreeItem *pPrev = ((CTreeItem*)pos)->pTIPrev;
	CTreeItem *pParent = ((CTreeItem*)pos)->pTIParent;
	if( pPrev)
		pPrev->pTINext = pNext;
	else
		pParent->pTIChildFirst = pNext;

	if( pNext)
		pNext->pTIPrev = pPrev;
	else
		pParent->pTIChildLast = pPrev;

	if( m_pDeleteFunc)
		(*m_pDeleteFunc)( pos, m_lParamDeleteFunc);
	delete (CTreeItem*)pos;
	DEC_ITEMS( pParent)
}

template<class _ITEMDATA>
inline void CRGTreeT<_ITEMDATA>::RemoveAll()
{
	RemoveChilds( (POSITION)m_ItemRoot.pTIChildFirst);
	m_ItemRoot.pTIChildFirst = m_ItemRoot.pTIChildLast = NULL;
}

template<class _ITEMDATA>
inline POSITION CRGTreeT<_ITEMDATA>::GetChildPosition( POSITION posParent, BOOL bFirst) const
{
	if( !posParent)
		return GetRootPosition();
	return (POSITION)(bFirst ? ((CTreeItem*)posParent)->pTIChildFirst : ((CTreeItem*)posParent)->pTIChildLast);
}

template<class _ITEMDATA>
inline POSITION CRGTreeT<_ITEMDATA>::GetNextPosition( POSITION pos) const
{
	return (POSITION)((CTreeItem*)pos)->pTINext;
}

template<class _ITEMDATA>
inline POSITION CRGTreeT<_ITEMDATA>::GetPrevPosition( POSITION pos) const
{
	return (POSITION)((CTreeItem*)pos)->pTIPrev;
}

template<class _ITEMDATA>
inline void CRGTreeT<_ITEMDATA>::GetAt( POSITION pos, _ITEMDATA* pItemData) const
{
	*pItemData = ((CTreeItem*)pos)->ItemData;
}

template<class _ITEMDATA>
inline _ITEMDATA* CRGTreeT<_ITEMDATA>::GetAt( POSITION pos)
{
	return &((CTreeItem*)pos)->ItemData;
}

template<class _ITEMDATA>
inline void CRGTreeT<_ITEMDATA>::SetAt( POSITION pos, const _ITEMDATA* pItemData)
{
	((CTreeItem*)pos)->ItemData = *pItemData;
}

template<class _ITEMDATA>
inline CompareFunc CRGTreeT<_ITEMDATA>::SetCompareFunc( CompareFunc func)
{
	swap_classes( func, m_pCompareFunc);
	return func;
}

template<class _ITEMDATA>
inline DeleteFunc CRGTreeT<_ITEMDATA>::SetDeleteFunc( DeleteFunc func, LPARAM lParam)
{
	swap_classes( func, m_pDeleteFunc);
	m_lParamDeleteFunc = lParam;
	return func;
}

template<class _ITEMDATA>
BOOL CRGTreeT<_ITEMDATA>::SortChildren( POSITION posParent, BOOL bAscending)
{
	if( !m_pCompareFunc)
		return FALSE;
	CTreeItem *pParent = posParent ? (CTreeItem*)posParent : &m_ItemRoot;
	if( !pParent->nChildCount)
		return FALSE;

	CTreeItem **pItemArray = (CTreeItem**)malloc( pParent->nChildCount*sizeof(CTreeItem*));
	register CTreeItem **pArItem = pItemArray;
	for( CTreeItem *pItem=pParent->pTIChildFirst; pItem; pItem=pItem->pTINext)
		*pArItem++ = pItem;

	CTreeItem **pEnde = pItemArray+pParent->nChildCount-1;
	pArItem = pItemArray;
	if( bAscending)
		QSortA( pArItem, pEnde);
	else
		QSortD( pArItem, pEnde);

	CTreeItem *pTIPrev = NULL;
	pParent->pTIChildFirst = *pArItem;
	for( ; pArItem != pEnde; )
	{
		(*pArItem)->pTIPrev = pTIPrev;
		pTIPrev->pTINext = (pTIPrev = *pArItem++, *pArItem);
	}
	(*pArItem)->pTIPrev = pTIPrev;
	(*pArItem)->pTINext = NULL;
	pParent->pTIChildLast = *pArItem;

	free( pItemArray);
	return TRUE;
}

template<class _ITEMDATA>
POSITION CRGTreeT<_ITEMDATA>::Find( const _ITEMDATA *pItemData, POSITION posParent)
{
	if( !m_pCompareFunc)
		return NULL;
	CTreeItem *pParent = posParent ? (CTreeItem*)posParent : &m_ItemRoot;
	for( CTreeItem *pItem=pParent->pTIChildFirst; pItem; pItem=pItem->pTINext)
		if( !(*m_pCompareFunc)( (LPARAM)pItemData, (LPARAM)&pItem->ItemData))
			return (POSITION)pItem;
	return NULL;
}


// protected functions

template<class _ITEMDATA>
void CRGTreeT<_ITEMDATA>::RemoveChilds( POSITION pos)
{
	if( m_pDeleteFunc)
		for( POSITION posNext; pos; pos=posNext)
		{
			RemoveChilds( GetChildPosition( pos));
			posNext = GetNextPosition( pos);
			DEC_ITEMS( ((CTreeItem*)pos)->pTIParent)
			(*m_pDeleteFunc)( pos, m_lParamDeleteFunc);
			delete (CTreeItem*)pos;
		}
	else
		for( POSITION posNext; pos; pos=posNext)
		{
			RemoveChilds( GetChildPosition( pos));
			posNext = GetNextPosition( pos);
			DEC_ITEMS( ((CTreeItem*)pos)->pTIParent)
			delete (CTreeItem*)pos;
		}
}

template<class _ITEMDATA>
void CRGTreeT<_ITEMDATA>::QSortA( CTreeItem **pLow, CTreeItem **pHigh)
{
	if( pLow >= pHigh)
		return;
	const LPARAM lMedian = (LPARAM)&(*(pLow+(pHigh-pLow+1)/2))->ItemData;
	CTreeItem **p1 = pLow, **p2 = pHigh;
	do
	{
		for( ; (*m_pCompareFunc)( (LPARAM)&(*p1)->ItemData, lMedian) < 0; p1++);
		for( ; (*m_pCompareFunc)( lMedian, (LPARAM)&(*p2)->ItemData) < 0; p2--);
		if( p1 <= p2)
			swap_classes( *p1++, *p2--);
	}
	while( p1 < p2);
	QSortA( pLow, p2);
	QSortA( p1, pHigh);
}

template<class _ITEMDATA>
void CRGTreeT<_ITEMDATA>::QSortD( CTreeItem **pLow, CTreeItem **pHigh)
{
	if( pLow >= pHigh)
		return;
	const LPARAM lMedian = (LPARAM)&(*(pLow+(pHigh-pLow+1)/2))->ItemData;
	CTreeItem **p1 = pLow, **p2 = pHigh;
	do
	{
		for( ; (*m_pCompareFunc)( (LPARAM)&(*p1)->ItemData, lMedian) > 0; p1++);
		for( ; (*m_pCompareFunc)( lMedian, (LPARAM)&(*p2)->ItemData) > 0;	p2--);
		if( p1 <= p2)
			swap_classes( *p1++, *p2--);
	}
	while( p1 < p2);
	QSortD( pLow, p2);
	QSortD( p1, pHigh);
}

#endif //RGTREET_H