|
// NGSortableObList.cpp
///////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "NGSortableObList.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
void CNGSortableObList::Sort(int (*CompareFunc)(CObject* pFirstObj, CObject* pSecondObj))
{
// CompareFunc is expected to return a positive integer if pFirstObj
// should follow pSecondObj (is greater than)
// Uses Insertion Sort
// The Shell Sort is much faster than a straight insertion sort, however, it cannot
// be performed on a linked list (it COULD, but the resulting code would probably be
// much slower as a Shell Sort jumps all around the reletive positions of elements).
// An Insertion Sort works by evaluating an item, if that item should
// precede the item in front of it, than it shifts all the items that
// should follow that item up one place until it finds the correct position
// for the item, whereby it then 'inserts' that item.
ASSERT_VALID(this);
// If the list contains no items, the HEAD position will be NULL
if (m_pNodeHead == NULL)
return;
CObject *pOtemp;
CObList::CNode *pNi,*pNj;
// Walk the list
for (pNi = m_pNodeHead->pNext; pNi != NULL; pNi = pNi->pNext)
{
// Save data pointer
pOtemp = pNi->data;
// Walk the list backwards from pNi to the beginning of the list or until
// the CompareFunc() determines that this item is in it's correct position
// shifting all items upwards as it goes
for (pNj = pNi; pNj->pPrev != NULL && CompareFunc(pNj->pPrev->data,pOtemp) > 0; pNj = pNj->pPrev)
pNj->data = pNj->pPrev->data;
// Insert data pointer into it's proper position
pNj->data = pOtemp;
}
}
void CNGSortableObList::Sort(POSITION posStart, int iElements, int (*CompareFunc)(CObject* pFirstObj, CObject* pSecondObj))
{
// This variation allows you to sort only a portion of the list
// iElements can be larger than the number of remaining elements without harm
// iElements can be -1 which will always sort to the end of the list
ASSERT_VALID(this);
ASSERT( AfxIsValidAddress((CObList::CNode*)posStart, sizeof(CObList::CNode)) );
// Make certain posStart is a position value obtained by a GetHeadPosition or Find member function call
// as there is no way to test whether or not posStart is a valid CNode pointer from this list.
// Ok, there is one way, we could walk the entire list and verify that posStart is in the chain, but even
// for debug builds that's a bit much.
// If the list contains no items, the HEAD position will be NULL
if (m_pNodeHead == NULL)
return;
CObject *pOtemp;
CObList::CNode *pNi,*pNj;
// Walk the list
for (pNi = (CObList::CNode*)posStart; pNi != NULL && iElements != 0; pNi = pNi->pNext, iElements--)
{
// Save data pointer
pOtemp = pNi->data;
// Walk the list backwards from pNi to the beginning of the sort or until
// the CompareFunc() determines that this item is in it's correct position
// shifting all items upwards as it goes
for (pNj = pNi; pNj->pPrev != NULL && pNj->pPrev != ((CObList::CNode*)posStart)->pPrev && CompareFunc(pNj->pPrev->data,pOtemp) > 0; pNj = pNj->pPrev)
pNj->data = pNj->pPrev->data;
// Insert data pointer into it's proper position
pNj->data = pOtemp;
}
}
#if 0
// Usage
//////////////////////////////////////////////////////////
// Create a CObject based class
// 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 a list object
CTypedNGSortableObList< CMyObject* > list;
// Fill the list with a bunch of objects
for (int i=0; i < 10; i++)
{
CMyObject * pObj = new CMyObject;
pObj->name.Format("Object #%d",i);
list.AddTail(pObj);
}
// Sort the list
list.Sort(CMyObject::CompBackward);
// Display the contents of the now sorted list
for (POSITION pos = list.GetHeadPosition(); pos != NULL; )
{
CMyObject* pObj = list.GetNext(pos);
TRACE1("%s\n",pObj->name);
}
#endif
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
I haven't always written software for a living. When I graduated from Surrey University in 1989, it was with an Electronic Engineering degree, but unfortunately that never really gave me the opportunity to do anything particularly interesting (with the possible exception of designing
Darth Vader's Codpiece * for the UK Army in 1990).
* Also known as the Standard Army Bootswitch. But that's another story...
Since the opportunity arose to lead a software team developing C++ software for
Avionic Test Systems in 1996, I've not looked back. More recently I've been involved in the development of subsea acoustic navigation systems, digital TV broadcast systems, port security/tracking systems, and most recently software development tools with my own company,
Riverblade Ltd.
One of my personal specialities is IDE plug-in development.
ResOrg was my first attempt at a plug-in, but my day to day work is with
Visual Lint, an interactive code analysis tool environment with works within the Visual Studio and Eclipse IDEs or on build servers.
I love lots of things, but particularly music, photography and anything connected with history or engineering. I
despise ignorant, intolerant and obstructive people - and it shows...I can be a bolshy cow if you wind me up the wrong way...
I'm currently based 15 minutes walk from the beach in Bournemouth on the south coast of England. Since I moved here I've grown to love the place - even if it is full of grockles in Summer!