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 );
}
}; |
/// <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; |
#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*) |
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;
} |
// 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.