CSortArray updated

This is an update of the CSortArray class that I wrote few weeks ago. In this version the sort functionality is extended and search functionality is provided.

/// <summary> Extends CArray, providing search and sort functionality </summary>
template <class TYPE, class ARG_TYPE = const TYPE&> class CSortArray : public CArray<TYPE, ARG_TYPE>
{
// Public member functions
public:
 
	/// <summary> Sort's the array content </summary>
	/// <param name="compare"> User defined compare function </param>
	/// <param name="context"> Pointer to a user defined object that can be accessed in the compare function </param>
	void QuickSort( int ( __cdecl *compare )(const void*, const void*) )
	{
		qsort( m_pData, GetCount(), sizeof(TYPE), (*compare) );
	}
	void QuickSort( int ( __cdecl *compare )(void*, const void*, const void*), void* context )
	{
		qsort_s( m_pData, GetCount(), sizeof(TYPE), (*compare), context );
	}
 
	/// <summary> Searches element in the array </summary>
	/// <param name="oKey"> Key to search </param>
	/// <param name="compare"> User defined compare function </param>
	/// <param name="context"> Pointer to a user defined object that can be accessed in the compare function </param>
	TYPE* Search( const TYPE& oKey, int ( __cdecl *compare )(const void*, const void*) )
	{
		return (TYPE*)bsearch( &oKey, m_pData, GetCount(), sizeof(TYPE), (*compare) );
	}
	TYPE* Search( const TYPE& oKey, int ( __cdecl *compare )(void*, const void*, const void*), void* context )
	{
		return (TYPE*)bsearch_s( &oKey, m_pData, GetCount(), sizeof(TYPE), (*compare), context );
	}
};

The new thing about sorting is that and override of QuickSort() method is provided that accepts a sort context. Pretty useful when you want to sort an array of complex types, for example information about a locality consisting from city, county and community by city name, county name, etc.

#define SIZE_CITY_NAME 49
#define SIZE_COUNTY_NAME 49
#define SIZE_COMMUNITY_NAME 49
 
typedef struct LOCALITY
{
	int nId;
	TCHAR szCity[SIZE_CITY_NAME + 1];
	TCHAR szCommunity[SIZE_COMMUNITY_NAME + 1];
	TCHAR szCounty[SIZE_COUNTY_NAME + 1];
	int nContactsCount;
 
	LOCALITY()
	{
		::ZeroMemory(this,sizeof(*this));
	}
} LOCALITY;

Also in the QuickSort() override the pointer to a compare function now has the following form:

int ( __cdecl *compare )(void*, const void*, const void*)

where the first argument to the function is pointer to the context object provided as void *context.

The search method can use a compare function without a context or with a context. Below is an example application that sorts an array of localities first by city, then by county and community. Then searches the array for a particular locality, for example city or community:

// SortArrayApp.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include "SortArrayApp.h"
#include "SortArray.h"
 
#ifdef _DEBUG
#define new DEBUG_NEW
#endif
 
// The one and only application object
CWinApp theApp;
 
using namespace std;
 
#define CONTEXT_ID 1
#define CONTEXT_CITY 2
#define CONTEXT_COMMUNITY 3
#define CONTEXT_COUNTY 4
#define CONTEXT_CONTACTS 5
 
#define SIZE_CITY_NAME 49
#define SIZE_COUNTY_NAME 49
#define SIZE_COMMUNITY_NAME 49
 
typedef struct LOCALITY
{
	int nId;
	TCHAR szCity[SIZE_CITY_NAME + 1];
	TCHAR szCommunity[SIZE_COMMUNITY_NAME + 1];
	TCHAR szCounty[SIZE_COUNTY_NAME + 1];
	int nContactsCount;
 
	LOCALITY()
	{
		::ZeroMemory(this,sizeof(*this));
	}
} LOCALITY;
 
int Compare( void* context, const void* element1, const void* element2 )
{
	LOCALITY *pLocality1 = (LOCALITY*) element1;
	LOCALITY *pLocality2 = (LOCALITY*) element2;
	int *pContext = (int*) context;
 
	switch( *pContext )
	{
	case CONTEXT_ID:
		{
			if( pLocality1->nId > pLocality2->nId )
			{
				return 1;
			} else if ( pLocality1->nId < pLocality2->nId ) {
				return -1;
			} else if ( pLocality1->nId == pLocality2->nId ) {
				return 0;
			}
			break;
		}
	case CONTEXT_COMMUNITY:
		{
			return _tcscmp( pLocality1->szCommunity, pLocality2->szCommunity );
		}
	case CONTEXT_COUNTY:
		{
			return _tcscmp( pLocality1->szCounty, pLocality2->szCounty );
		}
	case CONTEXT_CITY:
		{
			return _tcscmp( pLocality1->szCity, pLocality2->szCity );
		}
	case CONTEXT_CONTACTS:
		{
			if( pLocality1->nContactsCount > pLocality2->nContactsCount )
			{
				return 1;
			} else if ( pLocality1->nContactsCount < pLocality2->nContactsCount ) {
				return -1;
			} else if ( pLocality1->nContactsCount == pLocality2->nContactsCount ) {
				return 0;
			}
			break;
		}
	}
 
	return 0;
}
 
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
	int nRetCode = 0;
 
	HMODULE hModule = ::GetModuleHandle(NULL);
 
	if (hModule != NULL)
	{
		// initialize MFC and print and error on failure
		if (!AfxWinInit(hModule, NULL, ::GetCommandLine(), 0))
		{
			// TODO: change error code to suit your needs
			_tprintf(_T("Fatal Error: MFC initialization failed\n"));
			nRetCode = 1;
		}
		else
		{
			// SortArray usage
			CSortArray<LOCALITY> arrToSort;
 
			// Add locality information in the array
			LOCALITY recLocality;
 
			recLocality.nId = 2;
			_tcscpy_s( recLocality.szCity, ( SIZE_CITY_NAME + 1 ), _T("Varna") );
			_tcscpy_s( recLocality.szCommunity, ( SIZE_COMMUNITY_NAME + 1 ), _T("Varna") );
			_tcscpy_s( recLocality.szCounty, ( SIZE_COUNTY_NAME + 1 ), _T("Varna") );
			recLocality.nContactsCount = 10;
			arrToSort.Add( recLocality );
 
			recLocality.nId = 1;
			_tcscpy_s( recLocality.szCity, ( SIZE_CITY_NAME + 1 ), _T("Balgarene") );
			_tcscpy_s( recLocality.szCommunity, ( SIZE_COMMUNITY_NAME + 1 ), _T("Lovech") );
			_tcscpy_s( recLocality.szCounty, ( SIZE_COUNTY_NAME + 1 ), _T("Lovech") );
			recLocality.nContactsCount = 3;
			arrToSort.Add( recLocality );
 
			recLocality.nId = 4;
			_tcscpy_s( recLocality.szCity, ( SIZE_CITY_NAME + 1 ), _T("Veliko Turnovo") );
			_tcscpy_s( recLocality.szCommunity, ( SIZE_COMMUNITY_NAME + 1 ), _T("Turnovo") );
			_tcscpy_s( recLocality.szCounty, ( SIZE_COUNTY_NAME + 1 ), _T("Turnovo") );
			recLocality.nContactsCount = 8;
			arrToSort.Add( recLocality );
 
			recLocality.nId = 3;
			_tcscpy_s( recLocality.szCity, ( SIZE_CITY_NAME + 1 ), _T("Sofia") );
			_tcscpy_s( recLocality.szCommunity, ( SIZE_COMMUNITY_NAME + 1 ), _T("Sofia Grad") );
			_tcscpy_s( recLocality.szCounty, ( SIZE_COUNTY_NAME + 1 ), _T("Sofia") );
			recLocality.nContactsCount = 8;
			arrToSort.Add( recLocality );
 
			// Display the unsorted elements
			cout << "Unsorted elements:" << endl;
			cout << "ID\tCity\tCommunity\tCounty\tContacts" << endl;
			for( int i = 0; i < arrToSort.GetCount(); i++ )
			{
				LOCALITY& currLocality = arrToSort[i];
				wcout << currLocality.nId << ".\t";
				wcout << currLocality.szCity << "\t";
				wcout << currLocality.szCommunity << "\t";
				wcout << currLocality.szCounty << "\t";
				wcout << currLocality.nContactsCount << endl;
			}
			wcout << endl;
 
			int context = CONTEXT_ID;
 
			// Sort the array by ID
			arrToSort.QuickSort( Compare, &context );
 
			cout << "Elements sorted by locality ID:" << endl;
			cout << "ID\tCity\tCommunity\tCounty\tContacts" << endl;
			for( int i = 0; i < arrToSort.GetCount(); i++ )
			{
				LOCALITY& currLocality = arrToSort[i];
				wcout << currLocality.nId << ".\t";
				wcout << currLocality.szCity << "\t";
				wcout << currLocality.szCommunity << "\t";
				wcout << currLocality.szCounty << "\t";
				wcout << currLocality.nContactsCount << endl;
			}
			wcout << endl;
 
			// Sort the array by contacts count
			context = CONTEXT_CONTACTS;
			arrToSort.QuickSort( Compare, &context );
 
			cout << "Elements sorted by contacts count:" << endl;
			cout << "ID\tCity\tCommunity\tCounty\tContacts" << endl;
			for( int i = 0; i < arrToSort.GetCount(); i++ )
			{
				LOCALITY& currLocality = arrToSort[i];
				wcout << currLocality.nId << ".\t";
				wcout << currLocality.szCity << "\t";
				wcout << currLocality.szCommunity << "\t";
				wcout << currLocality.szCounty << "\t";
				wcout << currLocality.nContactsCount << endl;
			}
			wcout << endl;
 
			// Sort the array by City name
			context = CONTEXT_CITY;
			arrToSort.QuickSort( Compare, &context );
 
			cout << "Elements sorted by City name:" << endl;
			cout << "ID\tCity\tCommunity\tCounty\tContacts" << endl;
			for( int i = 0; i < arrToSort.GetCount(); i++ )
			{
				LOCALITY& currLocality = arrToSort[i];
				wcout << currLocality.nId << ".\t";
				wcout << currLocality.szCity << "\t";
				wcout << currLocality.szCommunity << "\t";
				wcout << currLocality.szCounty << "\t";
				wcout << currLocality.nContactsCount << endl;
			}
			wcout << endl;
 
			// Searching by city name
			context = CONTEXT_CITY;
			LOCALITY recSearch;
			wcout << "Enter city name: ";
			wcin >> recSearch.szCity;
 
			LOCALITY *pResult = arrToSort.Search( recSearch, Compare, &context );
			if( pResult )
			{
				wcout << pResult->nId << ".\t";
				wcout << pResult->szCity << "\t";
				wcout << pResult->szCommunity << "\t";
				wcout << pResult->szCounty << "\t";
				wcout << pResult->nContactsCount << endl;
			}
			else
			{
				wcout << recSearch.szCity << " not found!" << endl;
			}
		}
	}
	else
	{
		// TODO: change error code to suit your needs
		_tprintf(_T("Fatal Error: GetModuleHandle failed\n"));
		nRetCode = 1;
	}
 
	return nRetCode;
}

NOTE: CSortArray uses the bsearch function to preform the search and expects a sorted array on which to preform the search. We can further implement a member of CSortArray that indicates if array is sorted or not.

If you liked this article and think it is useful use the buttons below.

Leave a Reply

Your email address will not be published. Required fields are marked *

*