/*  a-wada/qsortlib/ccg/qsortd.c                                Feb. 17, 2000 */
/*  Copyright (c) 2000    Akira Wada <a-wada@mars.dti.ne.jp>                  */

/*      <<< Example of QSORTBASE to generate sort subroutine >>>              */
/*          A template of the tailor-made quick sort for an application       */
/*            . using pointer sort to be efficient for large elements         */
/*            . stability to preserve the initial order for equal sort keys   */
/*            . prevention from the degeneration caused by peculiar input     */

/** define the object to be sorted **/
typedef struct {
    int nmb; char *grp; double sum; int klg; char text[108];} typeA;

/** specify the sorting parameters **/
#include <string.h>
#define QSNAME      qsortd
#define ARGSP       typeA  A[], int N
#define KLG1        16
#define PT(i)       a ## i
#define KF(i, mmb) (PT(i) = *i)->mmb
#define KY(i, mmb)  PT(i)->mmb
#define COMPP(i, j) (                                                          \
      (c = strncmp (KF(i, grp),  KF(j, grp), KLG1)) != 0 ?  c : (              \
                    KY(i, sum) > KY(j, sum)              ? -1 : (              \
                    KY(i, sum) < KY(j, sum)              ?  1 : (              \
                    PT(i)      - PT(j)))))    /* <- uniquekey for stability */
#define SWAPP(i, j) PT(i) = *i,  PT(j) = *j,  *i = PT(j),  *j = PT(i)
#define ROTATEP(i, j, k)                                                       \
                    PT(i) = *i, PT(j) = *j, *i = PT(j),                        \
                    PT(j) = *k, *j = PT(j), *k = PT(i)

/** call the sorting algorithm (QSORTBASE) **/
typedef typeA **    PTRTYP;
#define ARGS        ARGSP
#define DFWRK       STACK;  UNQKEY
#define VALID       N > 1
#define HSKP        UKYINI
#define ESZ         1
#define COMP(i, j)  COMPP (i, j)
#define SWAP(i, j)  SWAPP (i, j)
#define ROTATE(i, j, k)  ROTATEP (i, j, k)
#define CLNUP       UKYEND

#define STACK       PTRTYP s[STKSZ], *p = s
#define STKSZ       sizeof (int) * 8 * 2
#define PUSH(x, y)  *(p++) = x, *(p++) = y
#define EMPTY       (s >= p)
#define POP(y, x)   y = *(--p), x = *(--p)

#define UNQKEY      typeA *ai, *aj, *ak, *am, *an, **ll, **rr; int c
#define UL          sizeof (typeA)
#define UKYINI      l = ll = (typeA **) malloc (sizeof (typeA *) * N);         \
                    r = rr = ll + (N - 1); ai = A;                             \
                    for (i = l; i <= r; i++, ai++) *i = ai
#define UARNGELM    ai = ak = A; an = (typeA *) malloc (UL);                   \
                    for (i = ll; i <= rr; i++, ai++)                           \
                        if ((aj = *i) != ai) {                                 \
                            memcpy (an, ai, UL); am = ai, m = i; do            \
                                *m = memcpy (am, aj, UL),                      \
                                am = aj, m = ll + (aj - ak);                   \
                                while ((aj = *m) != ai);                       \
                            *m = memcpy (am, an, UL);}
#define UKYEND      UARNGELM; free (an); free (ll)

#include "qsortbase.h"

    QSORTBASE  (QSNAME)

/*  a-wada/qsortlib/ccg/qsortd.c end  */