Sortable CObArray class

CodeGuru content and product recommendations are editorially independent. We may make money when you click on links to our partners. Learn More.

.

// SortableObArray.h

/////////////////////////////////////////////////////////////////////

class CSortableObArray : public CObArray

{

public:

	void Sort(int(*CompareFunc)(CObject* pFirst, CObject* pSecond));

	void Sort(int iStartPos, int iElements, int(*CompareFunc)(CObject* pFirst, CObject* pSecond));

};
template< class TYPE >

class CTypedSortableObArray : public CSortableObArray

{

public:

	// Accessing elements

	TYPE GetAt(int nIndex) const

	{ return (TYPE)CSortableObArray::GetAt(nIndex); }

	TYPE& ElementAt(int nIndex)

	{ return (TYPE&)CSortableObArray::ElementAt(nIndex); }

	void SetAt(int nIndex, TYPE ptr)

	{ CSortableObArray::SetAt(nIndex, ptr); }
	// Potentially growing the array

	void SetAtGrow(int nIndex, TYPE newElement)

	{ CSortableObArray::SetAtGrow(nIndex, newElement); }

	int Add(TYPE newElement)

	{ return CSortableObArray::Add(newElement); }

	int Append(const CTypedPtrArray< CSortableObArray, TYPE >& src)

	{ return CSortableObArray::Append(src); }

	void Copy(const CTypedPtrArray< CSortableObArray, TYPE >& src)

	{ CSortableObArray::Copy(src); }
	// Operations that move elements around

	void InsertAt(int nIndex, TYPE newElement, int nCount = 1)

	{ CSortableObArray::InsertAt(nIndex, newElement, nCount); }

	void InsertAt(int nStartIndex, CTypedSortableObArray< TYPE >* pNewArray)

	{ CSortableObArray::InsertAt(nStartIndex, pNewArray); }
	// overloaded operator helpers

	TYPE operator[](int nIndex) const

	{ return (TYPE)CSortableObArray::operator[](nIndex); }

	TYPE& operator[](int nIndex)

	{ return (TYPE&)CSortableObArray::operator[](nIndex); }
	void Sort( int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )

	{ CSortableObArray::Sort((int(*)(CObject*,CObject*))CompareFunc); }

	void Sort( int iStartPos, int iElements, int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )

	{ CSortableObArray::Sort(iStartPos, iElements, (int(*)(CObject*,CObject*))CompareFunc); }

};
// SortableObArray.cpp

///////////////////////////////////////////////////////////////////
#define STRIDE_FACTOR 3
void CSortableObArray::Sort(int(*CompareFunc)(CObject* pFirst, CObject* pSecond))

{

	// CompareFunc is expected to return a positive integer if pFirstObj

	// should follow pSecondObj (is greater than)
	// Uses Shell Sort
	// Basically it does a bunch of smaller insertion sorts than insertion sorts the

	//  whole thing.  Insertion sorting is much faster on a list that is already

	//  mostly sorted.
	// ** NOTE:  Because GetSize() is called to retrieve the number of elements, you should

	//            call SetSize() with the number of valid elements.  An alternative is

	//            shown in the sort function below.
	ASSERT_VALID(this);
	BOOL bFound;

	int iElements = GetSize();

	int iInner,iOuter,iStride = 1;

	CObject *pTmp;
	while (iStride <= iElements)
		iStride = iStride * STRIDE_FACTOR + 1;

	while (iStride > (STRIDE_FACTOR – 1))

	{

		iStride = iStride / STRIDE_FACTOR;

		for (iOuter = iStride; iOuter < iElements; iOuter++)
		{
			bFound = 0;
			iInner = iOuter - iStride;
			while ((iInner >= 0) && !bFound)

			{

				if (CompareFunc(m_pData[iInner+iStride],m_pData[iInner]) < 0)
				{
					pTmp = m_pData[iInner+iStride];
					m_pData[iInner+iStride] = m_pData[iInner];
					m_pData[iInner] = pTmp;
					iInner -= iStride;
				}
				else
					bFound = 1;
			}
		}
	}
}

void CSortableObArray::Sort(int iStartPos, int iElements, int(*CompareFunc)(CObject* pFirst, CObject* pSecond))
{
	// This variation allows you to sort only a portion of the array

	ASSERT_VALID(this);
	ASSERT( iStartPos >= 0 && iStartPos <= GetUpperBound() );
	ASSERT( GetSize() - iStartPos >= iElements );
	BOOL bFound;

	int iInner,iOuter,iStride = 1;

	CObject *pTmp;

	CObject **pData = &m_pData[iStartPos];
	while (iStride <= iElements)
		iStride = iStride * STRIDE_FACTOR + 1;

	while (iStride > (STRIDE_FACTOR – 1))

	{

		iStride = iStride / STRIDE_FACTOR;

		for (iOuter = iStride; iOuter < iElements; iOuter++)
		{
			bFound = 0;
			iInner = iOuter - iStride;
			while ((iInner >= 0) && !bFound)

			{

				if (CompareFunc(pData[iInner+iStride],pData[iInner]) < 0)
				{
					pTmp = pData[iInner+iStride];
					pData[iInner+iStride] = pData[iInner];
					pData[iInner] = pTmp;
					iInner -= iStride;
				}
				else
					bFound = 1;
			}
		}
	}
}

// Usage

//////////////////////////////////////////////////////////
// Create a CObject based class

class CMyObject : public CObject

{

public:

    CString name;

    static int CompBackward(CMyObject* pFirstObj, CMyObject* pSecondObj)

    {

        return -lstrcmp((LPCTSTR)pFirstObj->name,(LPCTSTR)pSecondObj->name);

    }

};
// Create an array object

CTypedSortableObArray< CMyObject* > array;
array.SetSize(10);
// Fill the array with a bunch of objects

for (int i=0; i < 10; i++)
{
	CMyObject * pObj = new CMyObject;
	pObj->name.Format(“Object #%d”,i);

	array[i] = pObj;

}
// Sort the array

array.Sort(CMyObject::CompBackward);
// Display the contents of the now sorted array

for (int i=0; i < 10; i++)
{
	TRACE1("%sn",array[i]->name);

}