Using Templates to Create a Multiple Sort

Introduction

Windows with listboxes often allow the user to sort entries on different fields. There are number of ways to implement such sorts, but you can use template functions and functor classes to simplify the process. The Standard Template Library (STL) discused in week 12 has many template functions that implement sorts, seaches and other common algorithms for the container classes contained in the library. These sorts depend overriding the comparison operators in the classes stored in the containers. While this works well if the comparisons are based on one field, if you want to sort on different fields you will have trouble. The sort given here will work on any or all orderable data members of a class.

Basic Idea

Template functions are used to perform standard operations on object from an arbitrary class. Sorts are always based on comparing two items in a container (in this case an array) and if the two are not in the preferred order calling on a swap routine to reverse the order. The swap function demostrates how simple template functions work. Parameters of a template function may be assigned at the time the function is instantiated. So in the case of the swap function, both parameters (and a local variable) are fixed when the swap is called. In this case the parameters and the local varible must all be the same type or there will be a compiler error.

template <class Type>
void swap(Type &x, Type &y)
{
	Type temp = x;
	x = y;
	y = temp;
}

The Sort

The sort is a bit more complicated here since you will be able to use this sort no matter which class you want to sort and no matter how you will determine how two members of the class are compared. This sort also connects the original list to the sorted list. When working with data referred to by its subscript from a master list, you don't want the master list changed by the sort. You will instead have a list of subscripts which will give the ordering for a given sort.

First create the compare abstract base class. This is a functor class with an equal and greaterThan function. Other functions should be added for completeness.

template <class Type>
class Compare
{
public:
	virtual int equal(const Type &, const Type&)const=0;
	virtual int greaterThan(const Type &, const Type&)const = 0;
};

The sort has a reference parameter for the array of integers, a constant reference to the array of the user type and a RcPointer to a compare type object. While this sort is a very crude bubble sort, any of the standard sorts could used here since they all share the comparisons and swap operation. For our listbox sort, you will not notice any improvement with a sophisticated sort since you are only sorting a few items.

template <class Type>
void sort(Array< int>&sorted, const Array< Type> & values,RcPointer< Compare < Type> > c)
{
	int size = values.numberInArray();
	for(int i = 0;i < size;i++)
		sorted.insertItemAt(i,i);
	for (i = 0;i < size-1;i++)
		for(int j = 0;j < size-1;j++)
			  if (c->greaterThan(values[sorted[j]],values[sorted[j+1]]))
				swap(sorted[j],sorted[j+1]);
}

Using The Sort

Click here to see an example of the sort in action.