/******************************************************************************
 *                                                                            *
 *   sortcomp.c  version 1.0 of  1 Januari 1989    (C) L.J.M. de Wit 1989     *
 *                                                                            *
 * This software may be used and distributed freely if not used commercially  *
 * and the originator (me) is mentioned in the source (just leave this 9 line *
 * header intact).                                                            *
 *                                                                            *
 ******************************************************************************
 *
 * sortcomp.c: comparision functions
 *
 * These functions contain the numeric comparision functions c_n and its
 * reverse, c_nr. The other 48 comparision functions are formed by combining
 * the following properties (take note of the Capitals):
 *  a) either Dictionary, Ignore non-printables or Any other        (3)
 *  b) ignore leading Blanks, versus not ignoring them              (2)
 *  c) Fold upper case to lower, versus not folding                 (2)
 *  d) Reverse the result of the comparision, versus not reversing  (2)
 *  e) Unbounded (bounded only by '\0'), versus upper limit bound   (2)
 *
 * Since comparing is done a lot it is important for the compare functions
 * to be fast. As for using the 48 functions as it stands the following
 * arguments are used:
 * One could have combined functions and used flags to discern between options.
 * This would however involve passing more parameters to the function (the
 * flags) and would require (perhaps a lot of) unwanted testing inside the
 * function.
 * Several functions call one of the other functions. This has been done in
 * such a way that duplication of code is mostly prevented, but still this call
 * is limited to only one (both in number and in level).
 * The numerical compare could have been done by a simple atoi(), but the
 * c_n function does the comparision inline, and stops comparing when the
 * bigger one has been found (while atoi needs to do calculation ala
 * 10 * num + digit, and will use all digits).
 */

#include <stdio.h>
#include <ctype.h>
#include "sortmain.h"
#include "sortcomp.h"

#define SKIPSPACE(bs,bt) while (wspace(*(bs))) (bs)++; while (wspace(*(bt))) (bt)++

#define NCHARS  256
#define NORM 0x1
#define DICT 0x2
#define isnorm(c)   (stype[(c)]&NORM)
#define isdict(c)   (stype[(c)]&DICT)

#undef  isdigit
#define isdigit(c) ((c) >= '0' && (c) <= '9')

static char fold[NCHARS];                       /* For lcase conversion     */

static char stype[NCHARS];                      /* For table lookup         */

void initlookup()                               /* Initialize lookup tables */
{
    register int i;

    for (i = 0; i < NCHARS; i++) {
        fold[i] = isupper(i) ? tolower(i) : i;  /* Init lcase convert array */
        stype[i] = 0;                           /* Not really needed ...    */
        if (i >= 040 && i <= 0176) {            /* Ascii non-control        */
            stype[i] |= NORM;
        }
        if (wspace(i) || isalnum(i)) {          /* Whitespace & alphanum    */
            stype[i] |= DICT;
        }
    }
}

int c_nr(bs,bt,es,et)                           /* Reversed Numeric         */
char *bs, *bt;
char *es, *et;
{
    return c_n(bt,bs,et,es);
}

int c_n(bs,bt,es,et)                            /* Numeric compare          */
register char *bs, *bt;
char *es, *et;
{
    register int rev, mini;

    SKIPSPACE(bs,bt);
    if (*bs == '-') {
        if (*bt == '-') {                       /* Two negatives: reverse   */
            rev = -1;
            bs++;
            bt++;
        } else {                                /* bt will be the larger one*/
            return -1;
        }
    } else {
        if (*bt == '-') {                       /* bs will be the larger one*/
            return 1;
        } else {
            rev = 1;                            /* Both positive            */
        }
    }

    while (*bs == *bt && isdigit(*bt)) {        /* Compare & skip eq. digits*/
        bs++; bt++;
    }

    if (!isdigit(*bs)) {
        if (!isdigit(*bt)) {
            if (*bs == '.' && *bt == '.') {     /* Decimal point            */
                while (*++bs == *++bt && isdigit(*bt)) ;
                while (*bs == '0') bs++;        /* Skip possibly trailing   */
                while (*bt == '0') bt++;        /*     zeroes               */
                if (!isdigit(*bs)) {
                    if (!isdigit(*bt)) {
                        return 0;               /* Tails also equal         */
                    }
                    return -rev;                /* bt has more digits       */
                }
                if (!isdigit(*bt)) {
                    return rev;                 /* bs has more digits       */
                }
                return (rev == 1)               /* Current digit decides    */
                       ? (*bs - *bt) : (*bt - *bs);
            } else {
                return 0;                       /* Equal numeric strings    */
            }
        }
        return -rev;                            /* bt has more digits       */
    }
    if (!isdigit(*bt)) {
        return rev;                             /* bs has more digits       */
    }
    mini = (rev == 1)                           /* Current digit decides:   */
           ? (*bs - *bt) : (*bt - *bs);         /* Difference into mini     */
    do {
        bs++;
        bt++;
    } while (isdigit(*bs) && isdigit(*bt));     /* Skip any more digits     */

    if (!isdigit(*bs)) {
        if (!isdigit(*bt)) {                    /* Strings equally long:    */
            return mini;                        /* then mini decides        */
        }
        return -rev;                            /* bt has more digits       */
    }
    return rev;                                 /* bs has more digits       */
}

int c_df(bs,bt,es,et)                           /* Dictionary/Fold          */
register char *bs, *bt;                         /* Strings to compare       */
register char *es, *et;
{
    --bs;   --bt;   --es;   --et;
    for ( ; bs < es && bt < et; ) {
        if (fold[*++bs] != fold[*++bt]) {       /* Increment & compare      */
            if (isdict(*bs)) {
                if (isdict(*bt)) {
                    return fold[*bs] - fold[*bt];
                } else {
                    --bs;                       /* Effectively skip *bt     */
                }
            } else if (isdict(*bt)) {
                --bt;                           /* Effectively skip *bs     */
            }                                   /* (else: skip both)        */
        }
    }
    for ( ; bs < es; ) {                        /* Skip any more            */
        if (isdict(*++bs)) {                    /* non-dict chars in bs     */
            --bs;
            break;
        }
    }
    for ( ; bt < et; ) {                        /* Skip any more            */
        if (isdict(*++bt)) {                    /* non-dict chars in bt     */
            --bt;
            break;
        }
    }

    return (et - bt) - (es - bs);
}

int c_d(bs,bt,es,et)                            /* Dictionary order         */
register char *bs, *bt;
register char *es, *et;
{
    --bs;   --bt;   --es;   --et;
    for ( ; bs < es && bt < et; ) {
        if (*++bs != *++bt) {                   /* Increment & compare      */
            if (isdict(*bs)) {
                if (isdict(*bt)) {
                    return fold[*bs] - fold[*bt];
                } else {
                    --bs;                       /* Effectively skip *bt     */
                }
            } else if (isdict(*bt)) {
                --bt;                           /* Effectively skip *bs     */
            }                                   /* (else: skip both)        */
        }
    }
    for ( ; bs < es; ) {                        /* Skip any more            */
        if (isdict(*++bs)) {                    /* non-dict chars in bs     */
            --bs;
            break;
        }
    }
    for ( ; bt < et; ) {                        /* Skip any more            */
        if (isdict(*++bt)) {                    /* non-dict chars in bt     */
            --bt;
            break;
        }
    }

    return (et - bt) - (es - bs);
}

int c_if(bs,bt,es,et)                           /* Normalized/Fold          */
register char *bs, *bt;
register char *es, *et;
{
    --bs;   --bt;   --es;   --et;
    for ( ; bs < es && bt < et; ) {
        if (fold[*++bs] != fold[*++bt]) {       /* Increment & compare      */
            if (isnorm(*bs)) {
                if (isnorm(*bt)) {
                    return fold[*bs] - fold[*bt];
                } else {
                    --bs;                       /* Effectively skip *bt     */
                }
            } else if (isnorm(*bt)) {
                --bt;                           /* Effectively skip *bs     */
            }                                   /* (else: skip both)        */
        }
    }
    for ( ; bs < es; ) {                        /* Skip any more            */
        if (isnorm(*++bs)) {                    /* non-norm chars in bs     */
            --bs;
            btˆ@pدددددددد€pدددد€pددددˆ€دأدہOŒپدءدˆ
ہOآO€Oدددددددددددددددددددددددہ@د„دژ‚O€ˆOدددددددددددہہpدددددددد‚دأ‚€€Cہہ@پآBO€OدددددددددددددددددددہB non-norm chars in bt     */
            --bt;
            break;
        }
    }

    return (et - bt) - (es - bs);
}

int c_i(bs,bt,es,et)                            /* Normalized order         */
register char *bs, *bt;
register char *es, *et;
{
    --bs;   --bt;   --es;   --et;
    for ( ; bs < es && bt < et; ) {
        if (*++bs != *++bt) {                   /* Increment & compare      */
            if (isnorm(*bs)) {
                if (isnor€CہŒپآBO€pدددددددددددددددددددد„ˆ
€€دˆ€
‰€@Œ„OہOˆ€
‰€@Œپ€@pدددددددددددددددد€Oˆ
„O€pددددددددددددددددددددہ@„@Oددددددددددددددددددددددہ@دکˆˆ
‚ˆ
‚O„دہŒپدددددہہpدددددددددددددددد€pدددددددددددد€Oˆ
„O‚دأ‚€€CہŒپآBO€pدددددددددددددد does the comparision inline, and stops comparing when the
 * bigger one has been found (while atoi needs to do calculation ala
 * 10 * num + digit, and will use all digits).
 */

#include <stdio.h>
#include <ctype.h>
#include "sortmain.h"
#include "sortcomp.h"

#define SKIPSPACE(bs,bt) while (wspace(*(bs))) (bs)++; while (wspace(*(bt))) (bt)++

#define NCHARS  256
#define NORM 0x1
#define DICT 0x2
#define isnorm(c)   (stype[(c)]&NORM)
#define isdict(c)   (stype[(c)]&DICT)

#undef  isdigit
#define isdigit(c) ((c) >= '0' && (c) <= '9')

static char fold[NCHARS];                       /* For lcase conversion     */

static char stype[NCHARS];                      /* For table lookup         */

void initlookup()                               /* Initialize lookup tables */
{
    register int i;

    for (i = 0; i < NCHARS; i++) {
        fold[i] = isupper(i) ? tolower(i) : i;  /* Init lcase convert array */
        stype[i] = 0;                           /* Not really needed ...    */
        if (i >= 040 && i <= 0176) {            /* Ascii non-control        */
            stype[i] |= NORM;
        }
        if (wspace(i) || isalnum(i)) {          /* Whitespace & alphanum    */
            stype[i] |= DICT;
        }
    }
}

int c_nr(bs,bt,es,et)                           /* Reversed Numeric         */
char *bs, *bt;
char *es, *et;
{
    return c_n(bt,bs,et,es);
}

int c_n(bs,bt,es,et)                            /* Numeric compare          */
register char *bs, *bt;
char *es, *et;
{
    register int rev, mini;

    SKIPSPACE(bs,bt);
    if (*bs == '-') {
        if (*bt == '-') {                       /* Two negatives: reverse   */
            rev = -1;
            bs++;
            bt++;
        } else {                                /* bt will be the larger one*/
            return -1;
        }
    } else {
        if (*bt == '-') {                       /* bs will be the larger one*/
            return 1;
        } else {
            rev = 1;                            /* Both positive            */
        }
    }

    while (*bs == *bt && isdigit(*bt)) {        /* Compare & skip eq. digits*/
        bs++; bt++;
    }

    if (!isdigit(*bs)) {
        if (!isdigit(*bt)) {
            if (*bs == '.' && *bt == '.') {     /* Decimal point            */
                while (*++bs == *++bt && isdigit(*bt)) ;
                while (*bs == '0') bs++;        /* Skip possibly trailing   */
                while (*bt == '0') bt++;        /*     zeroes               */
                if (!isdigit(*bs)) {
                    if (!isdigit(*bt)) {
                        return 0;               /* Tails also equal         */
                    }
                    return -rev;                /* bt has more digits       */
                }
                if (!isdigit(*bt)) {
                    return rev;                 /* bs has more digits       */
                }
                return (rev == 1)               /* Current digit decides    */
                       ? (*bs - *bt) : (*bt - *bs);
            } else {
                return 0;                       /* Equal numeric strings    */
            }
        }
        return -rev;                            /* bt has more digits       */
    }
    if (!isdigit(*bt)) {
        return rev;                             /* bs has more digits       */
    }
    mini = (rev == 1)                           /* Current digit decides:   */
           ? (*bs - *bt) : (*bt - *bs);         /* Difference into mini     */
    do {
        bs++;
        bt++;
    } while (isdigit(*bs) && isdigit(*bt));     /* Skip any more digits     */

    if (!isdigit(*bs)) {
        if (!isdigit(*bt)) {                    /* Strings equally long:    */
            return mini;                        /* then mini decides        */
        }
        return -rev;                            /* bt has more digits       */
    }
    return rev;                                 /* bs has more digits       */
}

int c_df(bs,bt,es,et)                           /* Dictionary/Fold          */
register char *bs, *bt;                         /* Strings to compare       */
register char *es, *et;
{
    --bs;   --bt;   --es;   --et;
    for ( ; bs < es && bt < et; ) {
        if (fold[*++bs] != fold[*++bt]) {       /* Increment & compare      */
            if (isdict(*bs)) {
                if (isdict(*bt)) {
                    return fold[*bs] - fold[*bt];
                } else {
                    --bs;                       /* Effectively skip *bt     */
                }
            } else if (isdict(*bt)) {
                --bt;                           /* Effectively skip *bs     */
            }                                   /* (else: skip both)        */
        }
    }
    for ( ; bs < es; ) {                        /* Skip any more            */
        if (isdict(*++bs)) {                    /* non-dict chars in bs     */
            --bs;
            break;
        }
    }
    for ( ; bt < et; ) {                        /* Skip any more            */
        if (isdict(*++bt)) {                    /* non-dict chars in bt     */
            --bt;
            break;
        }
    }

    return (et - bt) - (es - bs);
}

int c_d(bs,bt,es,et)                            /* Dictionary order         */
register char *bs, *bt;
register char *es, *et;
{
    --bs;   --bt;   --es;   --et;
    for ( ; bs < es && bt < et; ) {
        if (*++bs != *++bt) {                   /* Increment & compare      */
            if (isdict(*bs)) {
                if (isdict(*bt)) {
                    return fold[*bs] - fold[*bt];
                } else {
                    --bs;                       /* Effectively skip *bt     */
                }
            } else if (isdict(*bt)) {
                --bt;                           /* Effectively skip *bs     */
            }                                   /* (else: skip both)        */
        }
    }
    for ( ; bs < es; ) {                        /* Skip any more            */
        if (isdict(*++bs)) {                    /* non-dict chars in bs     */
           *es, *et;
{
    SKIPSPACE(bs,bt);
    return c_i(bt,bs,et,es);
}

int c_ib(bs,bt,es,et)                           /* Normalized/Blank         */
register char *bs, *bt;
char *es, *et;
{
    SKIPSPACE(bs,bt);
    return c_i(bs,bt,es,et);
}

int c_ifr(bs,bt,es,et)                          /* Normalized/Fold/Reverse  */
char *bs, *bt;
char *es, *et;
{
    return c_if(bt,bs,et,es);
}

int c_ir(bs,bt,es,et)                           /* Normalized/Reversed      */
char *bs, *bt;
char *es, *et;
{
    return c_i(bt,bs,et,es);
}

int c_abfr(bs,bt,es,et)                         /* Blank/Fold/Reverse       */
register char *bs, *bt;
char *es, *et;
{
    SKIPSPACE(bs,bt);
    return c_af(bt,bs,et,es);
}

int c_abf(bs,bt,es,et)                          /* Blank/Fold               */
register char *bs, *bt;
char *es, *et;
{
    SKIPSPACE(bs,bt);
    return c_af(bs,bt,es,et);
}

int c_abr(bs,bt,es,et)                          /* Blank/Reverse            */
register char *bs, *bt;
char *es, *et;
{
    SKIPSPACE(bs,bt);
    return c_a(bt,bs,et,es);
}

int c_ab(bs,bt,es,et)                           /* Blank                    */
register char *bs, *bt;
char *es, *et;
{
    SKIPSPACE(bs,bt);
    return c_a(bs,bt,es,et);
}

int c_afr(bs,bt,es,et)                          /* Fold/Reverse             */
char *bs, *bt;
char *es, *et;
{
    return c_af(bt,bs,et,es);
}

int c_ar(bs,bt,es,et)                           /* Reverse                  */
char *bs, *bt;
char *es, *et;
{
    return c_a(bt,bs,et,es);
}

/* Unbounded comparisions start here */

int c_dbfru(bs,bt)                              /* Dict/Blank/Fold/Reverse  */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_dfu(bt,bs);
}

int c_dbfu(bs,bt)                               /* Dictionary/Blank/Fold    */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_dfu(bs,bt);
}

int c_dbru(bs,bt)                               /* Dictionary/Blank/Reverse */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_du(bt,bs);
}

int c_dbu(bs,bt)                                /* Dictionary/Blank         */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_du(bs,bt);
}

int c_dfru(bs,bt)                               /* Dictionary/Fold/Reverse  */
char *bs, *bt;
{
    return c_dfu(bt,bs);
}

int c_dru(bs,bt)                                /* Dictionary/Reverse       */
char *bs, *bt;
{
    return c_du(bt,bs);
}

int c_ibfru(bs,bt)                              /* Norm/Blank/Fold/Reverse  */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_ifu(bt,bs);
}

int c_ibfu(bs,bt)                               /* Normalized/Blank/Fold    */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_ifu(bs,bt);
}

int c_ibru(bs,bt)                               /* Normalized/Blank/Reverse */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_iu(bt,bs);
}

int c_ibu(bs,bt)                                /* Normalized/Blank         */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_iu(bs,bt);
}

int c_ifru(bs,bt)                               /* Normalized/Fold/Reverse  */
char *bs, *bt;
{
    return c_ifu(bt,bs);
}

int c_iru(bs,bt)                                /* Normalized/Reverse       */
char *bs, *bt;
{
    return c_iu(bt,bs);
}

int c_abfru(bs,bt)                              /* Blank/Fold/Reverse       */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_afu(bt,bs);
}

int c_abfu(bs,bt)                               /* Blank/Fold               */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_afu(bs,bt);
}

int c_abru(bs,bt)                               /* Blank/Reverse            */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_au(bt,bs);
}

int c_abu(bs,bt)                                /* Blank                    */
register char *bs, *bt;
{
    SKIPSPACE(bs,bt);
    return c_au(bs,bt);
}

int c_afru(bs,bt)                               /* Fold/Reverse             */
register char *bs, *bt;
{
    register char *fld = fold;

    if (fld[*bs] == fld[*bt] && *bt) {
        for ( ; fld[*++bs] == fld[*++bt] && *bt; ) ;
    }

    return fld[*bt] - fld[*bs];
}

int c_aru(bs,bt)                                /* Reverse                  */
register char *bs, *bt;
{
    if (*bs == *bt && *bt) {
        for ( ; *++bs == *++bt && *bt; ) ;
    }

    return *bt - *bs;
}

int c_au(bs,bt)                                 /* Ordinary sort            */
register char *bs, *bt;
{
    if (*bs == *bt && *bs) {                    /* Compare & skip eq. chars */
        while (*++bs == *++bt && *bs) ;         /* Compare & skip eq. chars */
    }

    return *bs - *bt;
}

int c_a(bs,bt,es,et)                            /* Ordinary sort            */
register char *bs, *bt;
register char *es, *et;
{
    register short minlen;

    minlen = ((es - bs) <= (et - bt)) ? (es - bs) : (et - bt);
    if (minlen == 0) {
        return (es - bs) - (et - bt);
    }

    if (*bs == *bt) {
        for ( ; --minlen != 0 && *++bs == *++bt; ) ;
        if (minlen == 0) {
            return 0;
        }
    }

    return *bs - *bt;
}
#endif not MC68000