views:

1347

answers:

3

I have a structure:

struct pkt_
{
  double x;
  double y;
  double alfa;
  double r_kw;
};

typedef struct pkt_ pkt;

A table of these structures:

pkt *tab_pkt;

tab_pkt = malloc(ilosc_pkt * sizeof(pkt));

What I want to do is to sort tab_pkt by tab_pkt.alfa and tab_pkt.r:

qsort(tab_pkt, ilosc_pkt, sizeof(pkt), porownaj);

Where porownaj is a compare function, but how to write it? Here is my "sketch" of it:

int porownaj(const void *pkt_a, const void *pkt_b)
{
  if (pkt_a.alfa > pkt_b.alfa && pkt_a.r_kw > pkt_b.r_kw) return 1;
  if (pkt_a.alfa == pkt_b.alfa && pkt_a.r_kw == pkt_b.r_kw) return 0;
  if (pkt_a.alfa < pkt_b.alfa && pkt_a.r_kw < pkt_b.r_kw) return -1;
}
+1  A: 

There are two parts to the problem - how to write the code, and how to compare the packet types. You must ensure you always return a value. Your code should also always be such that:

porownaj(&pkt_a, &pkt_b) == -porownaj(&pkt_b, &pkt_a)

Your outline comparison does not handle cases such as:

pkt_a->alfa >  pkt_b->alfa && pkt_a->r_kw <= pkt_b->r_kw
pkt_a->alfa <  pkt_b->alfa && pkt_a->r_kw >= pkt_b->r_kw
pkt_a->alfa == pkt_b->alfa && pkt_a->r_kw != pkt_b->r_kw

There is one more problem - is it appropriate to compare floating point values for exact equality? That will depend on your application.

Mechanically, you have to convert the const void pointers to const structure pointers. I use the explicit cast - C++ requires it, and I try to make my code acceptable to a C++ compiler even when it is really C code.

int porownaj(const void *vp1, const void *vp2)
{
     const pkt *pkt_a = (const pkt *)vp1;
     const pkt *pkt_b = (const pkt *)vp2;

     if (pkt_a->alfa >  pkt_b->alfa && pkt_a->r_kw >  pkt_b->r_kw) return 1;
     if (pkt_a->alfa == pkt_b->alfa && pkt_a->r_kw == pkt_b->r_kw) return 0;
     if (pkt_a->alfa <  pkt_b->alfa && pkt_a->r_kw <  pkt_b->r_kw) return -1;
     return 0;
 }

This does not deal with the bits that I cannot resolve since I am not party to the necessary information. Note that, in general, multi-dimensional objects (such as complex numbers, or (x,y) or (x,y,z) coordinates) cannot simply be compared for greater than or less than or equal to.

Jonathan Leffler
+7  A: 

Something like this should work:

int porownaj(const void *p_a, const void *p_b)
{
  /* Need to store arguments in appropriate type before using */
  const pkt *pkt_a = p_a;
  const pkt *pkt_b = p_b;

  /* Return 1 or -1 if alfa members are not equal */
  if (pkt_a->alfa > pkt_b->alfa) return 1;
  if (pkt_a->alfa < pkt_b->alfa) return -1;

  /* If alfa members are equal return 1 or -1 if r_kw members not equal */
  if (pkt_a->r_kw > pkt_b->r_kw) return 1;
  if (pkt_a->r_kw < pkt_b->r_kw) return -1;

  /* Return 0 if both members are equal in both structures */
  return 0;
}

Stay away from silly tricks like:

return pkt_a->r_kw - pkt_b->r_kw;

which return un-normalized values, are confusing to read, won't work properly for floating point numbers, and sometimes have tricky corner cases that don't work properly even for integer values.

Robert Gamble
arg. i knew void* doesn't need a cast in C when assigned to something T* . but wasn't sure whether it also applies to const void* :D i'll memorize that it's also possible then :)
Johannes Schaub - litb
I was going to comment in favor of the "silly trick" you mentioned, but then I came to my senses :b +1
efotinis
Yeah; I made several mistakes in my solution. I completely forgot we're dealing with doubles here, not integers. An integer subtraction is much faster than three extra if's, which is why I used that method.
strager
@strager: I benchmarked this a long time ago and found there was very little, if any, performance difference. The main problem is that the method doesn't handle integer overflow, i.e. if a-b > INT_MAX the behavior is undefined, the method also gives the wrong answer in certain corner cases.
Robert Gamble
And the 'corner cases' don't have to be all that extreme. if a > (INT_MAX/2 + 1) and b < -(INT_MAX/2 + 1), then (a - b) is a guranteed overflow, and hence undefined behaviour.
Jonathan Leffler
A: 

Yes, I am sorting by alfa and r_kw decides if pkt is first (first value will have the biggest (or smallest) alfa and r_kw I think). That's how I understand the problem, I am not 100% sure.

diminish