/* Example of function pointers and qsort

  qsort(3C) - quick sort array 
  #include <stdlib.h>
  void qsort(void *base, size_t numel, size_t width,
                          int (*pcompare) (const void *, const void *));
     base:     base of array of:  data or pointers to data
     numel:    number of elements in array
     width:    sizeof(element of array)
     pcompare: pointer to comparison function:  
               function is given two pointers to:  data or pointers to data.
               It must return  < 0, = 0 or > 0 depending if first argument 
               pointed to is before, equal or after second argument.

     qsort compares i-th and j-th element using returned value of call:
       (*pcompare) ( (char *) base + width * i, (char *) base + width * j) 

  Although it is easier to understand qsort when just straight data is used,
  usually pointers to data are used instead.  This is because it is usually 
  more efficient to swap two pointers than to swap two data items.

In the following example, the data structures are as follows:
  As straight data:                   As pointers to data:
   arraydata[4]                arraypointers[4]         arraystruct[4]
  Before:   After:            Before:    After:       .data  .otherjunk
   3.1      -1.4               & 3.1     &-1.4          3.1    "one"
   2.2       2.2               & 2.2     & 2.2          2.2    "two" 
   5.3       3.1               & 5.3     & 3.1          5.3    "three"
  -1.4       5.3               &-1.4     & 5.3         -1.4    "four"
               ... here & means the address in arraystruct[] of that number.
*/

#include <stdio.h>
#include <stdlib.h>
#define NUMEL 4

/* structure for data when using pointers to data */
typedef struct 
{
    double data;
    char *otherjunk;
} 
DATANODE, *PDATANODE;

int comp_data(const double *p1, const double *p2);     /* straight data */
int comp_pointers(const PDATANODE *p1, const PDATANODE *p2); /* point. data */

int main()
{
    int i;

    double arraydata[NUMEL] =                     /* straight data */
       {3.1, 2.2, 5.3, -1.4};

    DATANODE arraystruct[NUMEL] =                 /* pointers to data */
       { {3.1,"one"},{2.2,"two"},{5.3,"three"},{-1.4,"four"} }; 
    PDATANODE arraypointers[NUMEL];

    /* initialize array of pointers                  pointers to data */
    for (i=0; i<NUMEL; i++) 
	arraypointers[i] = arraystruct + i;

    /* sort as straight data                 NOTE cast                */
    qsort(arraydata, NUMEL, sizeof(double), (int (*)()) &comp_data);   

    /* sort as pointers to data                     NOTE cast         */
    qsort(arraypointers, NUMEL, sizeof(PDATANODE), (int (*)()) &comp_pointers);
    /* Note abbreviation:  In above function pointers the '&' can be dropped
       since the only possible interpretation is as a pointer.
    */

    printf("Results:\n");                       /* as straight data */
      for (i=0; i<NUMEL; i++) printf("%4.1lf\n",arraydata[i]);
    printf("and:\n");                           /* as pointers to data */
      for (i=0; i<NUMEL; i++) printf("%4.1lf\n",arraypointers[i]->data);
    return 0;
}


/* comparison function for straight data */
int comp_data(const double *p1, const double *p2)
{
    if      (*p1 < *p2) return -1;
    else if (*p1 > *p2) return  1;
    else                return  0;
}

/* comparision function for pointers to data */
int comp_pointers(const PDATANODE *p1, const PDATANODE *p2)
{
    /* We received a pointer p1 to an entry in the array of pointers.
       To get the value in array:  (*p1)     This is now a pointer
       to DATANODE.  Access member via ->
    */
    if      ((*p1)->data < (*p2)->data) return -1;
    else if ((*p1)->data > (*p2)->data) return  1;
    else                                return 0;
}

/* end of code */

#if 1 == 0              /*  Makes cc skip over the rest. 

 Note that there are problems with rounding errors when comparing
 doubles that arise from computations, although here we can ignore
 the problem.  Two "equal" doubles can differ by a small amount.
 Equality tests on doubles are dubious.  A possible solution:
 Replace x < y by x + ep < y ,  
         x > y by x - ep > y  and 
         x = y by fabs(x - y) < ep   
  where ep is a suitable small positive value.

 The cast in the qsort() calls can be avoided by using prototypes: 

	int comp_data(void *p1, void *p2);
	int comp_pointers(void *p1, void *p2);

 and replacing the beginning of comp_data() by:

        int comp_data(const void *q1, const void *q2)
        {   
            const double *p1 = q1; 
            const double *p2 = q2; 

 Similarly for comp_pointers().

*/
#endif