Sortable CObArray class

.



// 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);
}


More by Author

Must Read