Sortable CObList class

.


// SortableObList.h
/////////////////////////////////////////////////////////////////////

class CSortableObList : public CObList
{
public:
	CSortableObList(int nBlockSize = 10) : CObList(nBlockSize) { }

	void Sort(int(*CompareFunc)(CObject* pFirstObj, CObject*pSecondObj));
	void Sort(POSITION posStart, int iElements, int (*CompareFunc)(CObject* pFirstObj, CObject* pSecondObj));
};


template< class TYPE >
class CTypedSortableObList : public CSortableObList
{
public:
// Construction
	CTypedSortableObList(int nBlockSize = 10) : CSortableObList(nBlockSize) { }

	// peek at head or tail
	TYPE& GetHead()
		{ return (TYPE&)CSortableObList::GetHead(); }
	TYPE GetHead() const
		{ return (TYPE)CSortableObList::GetHead(); }
	TYPE& GetTail()
		{ return (TYPE&)CSortableObList::GetTail(); }
	TYPE GetTail() const
		{ return (TYPE)CSortableObList::GetTail(); }

	// get head or tail (and remove it) - don't call on empty list!
	TYPE RemoveHead()
		{ return (TYPE)CSortableObList::RemoveHead(); }
	TYPE RemoveTail()
		{ return (TYPE)CSortableObList::RemoveTail(); }

	// add before head or after tail
	POSITION AddHead(TYPE newElement)
		{ return CSortableObList::AddHead(newElement); }
	POSITION AddTail(TYPE newElement)
		{ return CSortableObList::AddTail(newElement); }

	// add another list of elements before head or after tail
	void AddHead(CTypedSortableObList< TYPE >* pNewList)
		{ CSortableObList::AddHead(pNewList); }
	void AddTail(CTypedSortableObList< TYPE >* pNewList)
		{ CSortableObList::AddTail(pNewList); }

	// iteration
	TYPE& GetNext(POSITION& rPosition)
		{ return (TYPE&)CSortableObList::GetNext(rPosition); }
	TYPE GetNext(POSITION& rPosition) const
		{ return (TYPE)CSortableObList::GetNext(rPosition); }
	TYPE& GetPrev(POSITION& rPosition)
		{ return (TYPE&)CSortableObList::GetPrev(rPosition); }
	TYPE GetPrev(POSITION& rPosition) const
		{ return (TYPE)CSortableObList::GetPrev(rPosition); }

	// getting/modifying an element at a given position
	TYPE& GetAt(POSITION position)
		{ return (TYPE&)CSortableObList::GetAt(position); }
	TYPE GetAt(POSITION position) const
		{ return (TYPE)CSortableObList::GetAt(position); }
	void SetAt(POSITION pos, TYPE newElement)
		{ CSortableObList::SetAt(pos, newElement); }

	void Sort( int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
		{ CSortableObList::Sort((int(*)(CObject*,CObject*))CompareFunc); }
	void Sort( POSITION posStart, int iElements, int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
		{ CSortableObList::Sort(posStart, iElements, (int(*)(CObject*,CObject*))CompareFunc); }
};


// SortableObList.cpp
///////////////////////////////////////////////////////////////////

void CSortableObList::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 CSortableObList::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;
	}

}



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




Comments

  • Simply perfect

    Posted by ecloninger on 03/24/2006 05:42pm

    Exactly the piece of code that I needed in a pinch. Saved me a couple hours writing it and it's better than I would've done. Thanks Douglas!

    Reply
  • loop trough coblist string by string

    Posted by Legacy on 05/06/2003 12:00am

    Originally posted by: glenn

    Is it posible to loop trough the list sting by sting

    Reply
  • Very good

    Posted by Legacy on 01/21/2003 12:00am

    Originally posted by: Paul Kohut

    This was the right code at the right time.

    Thank you,
    Paul Kohut

    Reply
  • Sortable CObList Class

    Posted by Legacy on 02/16/1999 12:00am

    Originally posted by: Pete Nightingale

    Lovely little bit of code. Ta.

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Learn How A Global Entertainment Company Saw a 448% ROI Every business today uses software to manage systems, deliver products, and empower employees to do their jobs. But software inevitably breaks, and when it does, businesses lose money -- in the form of dissatisfied customers, missed SLAs or lost productivity. PagerDuty, an operations performance platform, solves this problem by helping operations engineers and developers more effectively manage and resolve incidents across a company's global operations. …

  • Live Event Date: December 18, 2014 @ 2:00 p.m. ET / 11:00 a.m. PT The Internet of Things (IoT) incorporates physical devices into business processes using predictive analytics. While it relies heavily on existing Internet technologies, it differs by including physical devices, specialized protocols, physical analytics, and a unique partner network. To capture the real business value of IoT, the industry must move beyond customized projects to general patterns and platforms. Check out this upcoming webcast …

Most Popular Programming Stories

More for Developers

RSS Feeds