|
|
UCanCode
Software focuses on general application software development. We provide complete solution for developers. No matter you want to develop a simple database
workflow application, or an large flow/diagram based system, our product will provide a complete solution for you. Our product had been used by hundreds of top companies around the world!
"100% source code provided! Free you from not daring to use components because of unable to master the key technology of components!"
|
|
VC++
Example: Sort CObList class
|
| |
Douglas
Peterson.
// 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);
}
|
|
|
|
|
E-XD++Visual
C++/ MFC Products 
