/*  a-wada/qsortlib/ccn/qsortpntr.c                             Feb.  7, 1999 */
/*  Copyright (c) 1999    Akira Wada <a-wada@mars.dti.ne.jp>                  */

/* *using "system qsort ()"  with                                             */
/*     (1) stability, to preserve initial order of elements with same sortkey */
/*     (2) efficiency for long objects                                        */
/*     (3) prevention from degeneration by low variety of key value           */
/*         even if sys-qsort not implemented for that                         */
/* *but for a little more efficiency etc, refer the following examples        */
/* *for the data set with many equal keys and not requiring stability         */
/*      use qsorts.c without unique key                                       */

#include <stdlib.h>
typedef int (*ftp) (const void *, const void *);
void rarng (void *, size_t, size_t, void *);
int cmppntr (const void *, const void *);
static ftp sqcmp;

void qsortpntr (void *av, size_t rn, size_t rl, ftp qcmp) {
    char **pv; int i, j; sqcmp = qcmp;
    pv = (char **) malloc (sizeof (char *) * rn);
    for (i = j = 0; i < (int) rn; i++, j += rl) pv[i] = (char *) av + j;
    qsort (pv, rn, sizeof (char *), cmppntr);       /* sort array of pointers */
    rarng (av, rn, rl, pv);}                  /* rearrange by sorted pointers */

int cmppntr (const void *p, const void *q) {
    char *a = *((char **) p), *b = *((char **) q); int c;
    if ((c = (*sqcmp) (a, b)) != 0) return c;
    return (a - b);}

#include "rarng.c"

/*  a-wada/qsortlib/ccn/qsortpntr.c end */
/*----------------------------------------------------------------------------**
    * Source code of rarng.c, qsorts.c
        http://www.mars.dti.ne.jp/~a-wada/qsortlib/ccn/rarng.c
        http://www.mars.dti.ne.jp/~a-wada/qsortlib/ccn/qsorts.c
    * Example of bench-mark :
        http://www.mars.dti.ne.jp/~a-wada/qsortlib/ccn/qspt0209.txt
**----------------------------------------------------------------------------*/
/*============================================================================*/
/*  examples of using system qsort () with stability in caller programs */
/*   ** read below replacing "?" by "/" for comments  **  */

/*  for long objects by sorting array of pointers *?
#include <stdlib.h>
typedef struct {                     ?* object to be sorted *?
    int w; char *x; double y; int z; char filler[108];} typeA;
void rarng (void *, size_t, size_t, void *);
int cmpptr (const void *, const void *);

void main () {
    typeA A[maxN], *P[maxN]; int N, i; .....

    for (i = 0; i < N; i++) P[i] = &A[i];
    qsort (P, N, sizeof (typeA *), cmpptr);   ?* sort array of pointers *?
    rarng (A, N, sizeof (typeA), P);    ?* rearrange by sorted pointers *?
                  ?* in many case, rearrangement might not be necessary *?
    .......................}

int cmpptr (const void *p, const void *q)  {
    typeA *a = *((typeA **) p), *b = *((typeA **) q); int c;
    if ((c = strncmp (
        a->x,  b->x, KLG1)) != 0) return  c;        ?*  x :  key-1  *?
    if (a->y > b->y)              return -1;        ?*  y :  key-2  *?
    if (a->y < b->y)              return  1;
                                  return (a - b);}  ?* <- uniquekey *?
#include "rarng.c"
?* example-1 end */

/*  for short object using unique key *?
#include <stdlib.h>
typedef struct {                    ?* object to be sorted *?
    int w; char *x; double y; int z; char filler[12];} typeA;
int cmpdrc (const void *, const void *);

void main () {
    typeA A[maxN]; int N, i; .......

    for (i = 0; i < N; i++) A[i].w = i;  ?* numbering for stability *?
    qsort (A, N, sizeof (typeA), cmpdrc);

    ..........}

int cmpdrc (const void *p, const void *q) {
    typeA *a = (typeA *) p, *b = (typeA *) q; int c;
    if ((c = strncmp (
        a->x,  b->x, KLG1)) != 0) return  c;        ?*  x :  key-1  *?
    if (a->y > b->y)              return -1;        ?*  y :  key-2  *?
    if (a->y < b->y)              return  1;
                       return (a->w - b->w);}       ?* <- uniquekey *?

?*  example-2 end  */
/*============================================================================*/