Sorting with Function Pointers
This is a simple application of function pointers. Here I am trying to sort an array points based on X values, Y values or the distance from the origin. I have a simple sorting algorithm and the sorting criteria can be changed by using function pointers.
Lets start with the types we need. First, I need a structure to hold the X and Y values of the point. Point2D structure takes care of that. Second, a type that will define the sorting criteria, see in line 9. It define a pointer to a function that accepts two arguments both of which are Point2D structures and returns a bool. Typically comparison operations have this format.
1: #include <iostream>
2: #include <math.h>
3: using namespace std;
4:
5: // 2D co-ordinate system
6: typedef struct _Point2D
7: { double X, Y;}Point2D;
8: // function pointer type definiton
9: typedef bool (*Compare)(Point2D&,Point2D&);
Lets define a function to create and initialize a Point2D structure. This will make it easier to control or set default values to the Point2D structure.
10: // function that returns a 2D point
11: Point2D fnCreatePoint(const double x=0.0,const double y=0.0)
12: {
13: Point2D point;
14: point.X = x;
15: point.Y = y;
16: return point;
17: }
Lets further define swap function usually used in sorting algorithms and a simple sorting function. There are fairly direct, if you need more help with this see: Swap, Bubble Sort. Note that the sorting algorithm takes a additional argument of type Compare. That is the type of the function pointer that will define the comparison criteria while sorting.
18: // swaps the two values
19: void swap(Point2D& a,Point2D& b)
20: {
21: Point2D t;
22: t.X = a.X;t.Y = a.Y;
23: a.X = b.X;a.Y = b.Y;
24: b.X = t.X;b.Y = t.Y;
25: }
26: // sorts an array of values
27: Point2D* sort(Point2D* points,const int len,Compare fnCompare)
28: {
29: for(int i = 0;i<len;i++)
30: for(int j = i+1;j<len;j++)
31: if(!fnCompare(points[i],points[j]))
32: swap(points[i],points[j]);
33: return points;
34: }
Now, that we have the framework we need, let us define a few comparing functions. These are simple functions that perform a particular type com comparison. The compare_x function compares only the X value of the Point2D structure. Similarly, compare_y function compares the Y value. The compare_distance function calculates the distance from the origin for the two points and then compares the distance. Note that each of these functions follow the argument types and return value type defined previously in line 9.
35: // comparing functions
36: bool compare_x(Point2D& a,Point2D& b)
37: { return a.X < b.X;}
38: bool compare_y(Point2D& a,Point2D& b)
39: { return a.Y < b.Y;}
40: bool compare_distance(Point2D& a,Point2D& b)
41: { return
42: sqrt(pow(a.X,2.0) + pow(a.Y,2.0)) <
43: sqrt(pow(b.X,2.0) + pow(b.Y,2.0));
44: }
We have all the components that are needed to make this work. Here, I create an array with five points in it and call the sorting algorithm with the appropriate comparison criteria. Finally, display the sorted array of points.
int main()
{
Point2D points[]={
fnCreatePoint(-1,1),
fnCreatePoint(-2,2),
fnCreatePoint(1,-1),
fnCreatePoint(2,-2),
fnCreatePoint(0,0)};
int length = 5;
cout << "Sorted by X value:" << endl;
// Sorts the points based on X
sort(points,length,compare_x);
Display(points,length);
cout << endl << "Sorted by Y value:" << endl;
// Sorts the points based on Y
sort(points,length,compare_y);
Display(points,length);
cout << endl << "Sorted by distance from the origin:" << endl;
// Sorts the points based on distance from the origin
sort(points,length,compare_distance);
Display(points,length);
return 0;
}
I hope this helps you understand function pointers. Source code: fptr_example.cpp