Sortattava CObArray

// 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:perator[](nIndex); }
TYPE& operator[](int nIndex)
{ return (TYPE&)CSortableObArray:perator[](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("%s\n",array[i]->name);
}

Varmaan kannattaa jysäyttää beautifierin läpi ennen käyttöä

--
Lars