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

  • Live Event Date: October 29, 2014 @ 11:00 a.m. ET / 8:00 a.m. PT Are you interested in building a cognitive application using the power of IBM Watson? Need a platform that provides speed and ease for rapidly deploying this application? Join Chris Madison, Watson Solution Architect, as he walks through the process of building a Watson powered application on IBM Bluemix. Chris will talk about the new Watson Services just released on IBM bluemix, but more importantly he will do a step by step cognitive …

  • Live Event Date: November 13, 2014 @ 2:00 p.m. ET / 11:00 a.m. PT APIs can be a great source of competitive advantage. The practice of exposing backend services as APIs has become pervasive, however their use varies widely across companies and industries. Some companies leverage APIs to create internal, operational and development efficiencies, while others use them to drive ancillary revenue channels. Many companies successfully support both public and private programs from the same API by varying levels …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds