# Need Help Passing A Sort Function Into A Method

I need a sort function that gets passed into a method, but I don't know where to start.
###### Who is Participating?

x

Commented:
That works on my system. And the compare function gets used.

template <class ET>
class Array {
ET*      pET;
int      siz;
public:
Array() { pET = NULL; siz = 0; }
ET& operator[] (int i)
{
if (i >= siz)
{
ET* p = new ET[i+1];
memset(p, 0, (i+1)*sizeof(ET));
memcpy(p, pET, sizeof(ET)*siz);
delete [] pET;
pET = p;
siz = i+1;
}
return pET[i];
}

void sort(int (*GTcompare)(const ET &a, const ET &b));
bool operator > (const ET& et) { return true; }
};

template <class ET>
int GTcompare(const ET &a, const ET &b) {
if(a > b)
return 1;
if(a == b)
return 0;
else
return -1;
}

template <class ET>
void Array<ET>::sort(int (*GTcompare)(const ET &a, const ET &b)) {
ET temp;
int minS = -1;
int maxUsed = siz-1;

for(int x=minS+1; x<=maxUsed; x++)
{
for(int y=minS; y<=maxUsed; y++)
{
if((*GTcompare)(x,y) > 0)
{
temp = pET[x];
pET[x] = pET[y];
pET[y] = temp;
}
}
}
}

void main()
{
Array<int> a;
a[0] = 1;
a[2] = 3;
a.sort(GTcompare);
}

The only difference is this:

template <class ET>
int GTcompare(const ET &a, const ET &b) {
...

The compare function returns an int type. You may not mix up that with the function pointer that is of type int*. Also the name of the function is free, you don't need to call it GTcompare:

template <class ET>
class Array {
ET*      pET;
int      siz;
public:
Array() { pET = NULL; siz = 0; }
ET& operator[] (int i)
{
if (i >= siz)
{
ET* p = new ET[i+1];
memset(p, 0, (i+1)*sizeof(ET));
memcpy(p, pET, sizeof(ET)*siz);
delete [] pET;
pET = p;
siz = i+1;
}
return pET[i];
}

void sort(int (*GTcompare)(const ET &a, const ET &b));
bool operator > (const ET& et) { return true; }

};

template <class ET>
int CompareFunc(const ET &a, const ET &b) {
if(a > b)
return 1;
if(a == b)
return 0;
else
return -1;
}

template <class ET>
void Array<ET>::sort(int (*GTcompare)(const ET &a, const ET &b)) {
ET temp;
int minS = -1;
int maxUsed = siz-1;

for(int x=minS+1; x<=maxUsed; x++)
{
for(int y=minS; y<=maxUsed; y++)
{
if((*GTcompare)(x,y) > 0)
{
temp = pET[x];
pET[x] = pET[y];
pET[y] = temp;
}
}
}
}

void main()
{
Array<int> a;
a[0] = 1;
a[2] = 3;
a.sort(CompareFunc);
}

>> May be you can make refence on how the qsort is implenemted in C run-time libraries.

I found this an easy to unterstand article: http://www.cuj.com/documents/s=7976/cujcexp2012alexandr/

Look to the code above: It's an insertion sort that does a stable sort, i. e. if there are two or more keys equal the entries have same order before and after sort.

Regards, Alex

0

Commented:
You need to pass a pointer to the function. You first create a typedef for the function, and use this to create your parameter list of the function that needs this method. When you call the sort function, you need to dereference the pointer.
0

Commented:
#include <iostream>

using namespace std;

typedef void (*sortFunc)();

void sort()
{
}

void func(sortFunc theFunc)
{
(*theFunc)();
}

int main()
{
sortFunc theSortFunc;

theSortFunc = sort;
return 0;
}
0

Commented:
void SortFunc(int a, int b)
{
// Sort code here
}

void Method(  void (*sort) (int a, int b ) )
{
int arg1 = 1;
int arg2 = 2;
sort(arg1, arg2);
}

void Caller()
{
Method( &SortFunc );
}
0

Commented:
hi,

check

http://www.function-pointer.org/

Cheers
Dennis
0

Commented:
Here is a sample used in my own array class Hat (hashed array tree)

enum ECompare { LESS = -1, EQUAL = 0, GREATER=1 };

template <class T>
class Hat
{
....

public:
// @cmember make a typedef for the compare function pointer needed to sort the hat
typedef          ECompare (*CompareFunc)(const T& value1, const T& value2);
bool         sort(CompareFunc compareFunc);

};

// And here the implementation using a binary insert sort

template <class T>
bool Hat<T>::sort(Hat<T>::CompareFunc compareFunc)
{
// check for minimal two items
if (elements() <= 1)
return false;

// create integer array for the sorted indices
int*     idxArr  = new int[elements()];
int      nn      = 0;       // nn is the number of already sorted items
int      n1      = 0;       // n1 is the lower range index when searching binary
int      n2      = 0;       // n2 is the upper range index when searching binary
int      n       = 0;       // n is the middle of the binary range
bool     newSort = false;   // indicates if any sort happens or if the hat has been already sorted
int      i;                 // loop counter
ECompare comp;              // result of comparison

// loop all items and build a sorted index array
for (i = 0; i < elements(); i++)
{
// t1 is the new item which index must be inserted to the index array
T& t1 = (*this)[i];
// init the binary range to the current size of the already sorted index array
n1    = 0;
n2    = nn-1;

// binary search
while (n1 <= n2)
{
// compute the middle of the current range for dividing the current range into two parts
n     = (n1 + n2 + 1)/2;
// get the item to compare
T& t2 = (*this)[idxArr[n]];
// compare both items
comp  = (*compareFunc)(t1, t2);
// if the left item is less we make the lower part current
if (comp == LESS)
n2   = n - 1;
// if the left item is greater or equal we make the upper part current
else
n1 = n + 1;
}

// at end of the previous loop n1 is the new position where the current item index (i)
// has to be inserted to get the index array sorted

// if this position is not outside the current size (that means we have not to change the order)
// we move all indices on the right side for one position using memmove
// In this case we hold the info that the sort order has changed
if (n1 < nn)
{
memmove(&idxArr[n1+1], &idxArr[n1], (nn-n1)*sizeof(int));
newSort = true;
}
idxArr[n1] = i;
nn++;
}

// if the sort order has not changed we are thru
if (!newSort)
{
// delete index array after use
delete []idxArr;
return false;
}

// Build a new hat where all items will be inserted in sorted order
Hat<T> hat;
// Set the hat to the best size.
hat.setMaxElements(elements());
// loop the sorted index array
for (i = 0; i < elements(); i++)
{
// get the next index in sort order
n      = idxArr[i];
// copy the item
hat[i] = (*this)[n];
}
// delete index array after use
delete []idxArr;

// assign the new (sorted)hat to ourselves
*this = hat;

// we are thru and the sort order has changed
return true;
}

Regards, Alex

0

Author Commented:
I had it working, but then I forget my disk, so now I have to redo it. The way I had it was kinda dumb anyway. I had it in the class, but I want it in main.

Here's the compare function that I want to pass into a sort function:
template <class ET>
int (*GTcompare)(const ET &a, const ET &b) {
if(a > b)
return 1;
if(a == b)
return 0;
else
return -1;
}

Here's the sort function:
template <class ET>
void Array<ET>::sort(int (*GTcompare)(const ET &a, const ET &b)) {
ET temp;

for(int x=minS+1; x<=maxUsed; x++)
{
for(int y=minS; y<=maxUsed; y++)
{
if((*GTcompare)(x,y) > 0)
{
temp = x;
x = y;
y = temp;
}
}
}
}

This is what calls the sort, which will call the GTcompare:
keys.sort(GTcompare);

I get undeclared identifier on keys.sort(GTcompare); and redefinition on int (*GTcompare)(const ET &a, const ET &b).
Do I have to declare GTcompare somewhere instead of just sticking the function at the end of my main?
0

Commented:
You can either define it before you use it (even though I don't like this), or declare it before you use it if you use it before you define it.
0

Commented:
Instead of declaring the function like this:

int (*GTcompare)(const ET &a, const ET &b) {
Declare it like this
int GTcompare(const ET &a, const ET &b) {

Then change the sort call from

keys.sort(GTcompare);
to
keys.sort(&GTcompare);

You also might want to put a function prototype before your main for the compare function if you are implementing it after the main.
0

Author Commented:
That didn't help. It made 3 errors instead of just the one.
0

Commented:
#include <iostream>

using namespace std;

int Foo( int a );
int Method( int (*fct)(int a ));
void main()
{
cout << "In main" << endl;
Method( &Foo );
}

int Method( int (*fct)(int a))
{
cout << "In Method()" << endl;
int num = 5;
fct( num );
return num;
}

int Foo( int a )
{
cout << "Foo " << a << endl;
return a;
}

This works perfectly for me.
0

Commented:
oh, if that doesn't work for you, please post the error message because something else must be wrong.
0

Commented:
Hi denago,

>> Then change the sort call from

>> keys.sort(GTcompare);
>> to
>> keys.sort(&GTcompare);

(GTcompare) and (&GTcompare) are same... both will refer to the address of the function.....

Dennis
0

Commented:

template <class ET>
class Array
{
....
public:
typedef int (*GTcompare)(const ET &a, const ET &b);
sort(GTcompare compareFunc);   // use the typedef here
};

template <class ET>
int (*GTcompare)(const ET &a, const ET &b) {
if(a > b)
return 1;
if(a == b)
return 0;
else
return -1;
}

Here's the sort function:
template <class ET>
void Array<ET>::sort(GTcompare compareFunc)         // you pass a function pointer here, that must get a variable name
{                                                                             // and not the prototype declaration of the function itself
ET temp;

for(int x=minS+1; x<=maxUsed; x++)
{
for(int y=minS; y<=maxUsed; y++)
{
if((*compareFunc)(x,y) > 0)    // Here you need the 'argument' and NOT the 'type'
{
temp = x;
x = y;
y = temp;
}
}
}
}

Regards, Alex
0

Author Commented:
That doesn't work either. Here's what I got:

in Main.cpp before int main():
template <class ET>
int (*GTcompare)(const ET &a, const ET &b) {
if(a > b)
return 1;
if(a == b)
return 0;
else
return -1;
}

in Array.h:

template <class ET>
class Array {
public:
void sort(int (*GTcompare)(const ET &a, const ET &b));
}

template <class ET>
void Array<ET>::sort(int (*GTcompare)(const ET &a, const ET &b)) {
ET temp;

for(int x=minS+1; x<=maxUsed; x++)
{
for(int y=minS; y<=maxUsed; y++)
{
if((*GTcompare)(x,y) > 0)
{
temp = theArray[x];
theArray[x] = theArray[y];
theArray[y] = temp;
}
}
}
}

In main, I call anArray.sort(GTcompare), but it doesn't like the compare. I can't figure out why, but my teacher says I don't need the typedef thing. He said all I need to do is just write a function and call a different function with that first function's name as the argument.

0

Commented:
May be you can make refence on how the qsort is implenemted in C run-time libraries.

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.