Who level sorting (QSort) [by Jorgen Sigvardsson]

From: Jorgen Sigvardsson <di5sig@cse.hks.se>
Subject: do_who -- Better sorting.

Ok.. I saw the sorted do_who version on the snippets site.. and it aint
pretty.. time complexity is raging wild! (O(n) = n + n2) and
spacecomplexity is n..
Not very good at all. I have a do_who that has a timecomplexity of
O(n) = n + n log n and a constant spacecomplexity. It's easy to put it
into the mud.
No changes to the Makefile is needed, just act.informative.c
Here it is...

// Jorgen

-----

/* do_who() and auxiliary functions */
/* this function uses qsort which comes with all(?) flavours of UN*X.
I'm not sure if the Windows SDK provides it. If so, you can always write
it yourself or get it off the net. It's easy to find.. after all it uses
the most known sorting algorithm around, quicksort.
*/

/* this array must be at least as big as MAX_PLAYERS or whatever the
global variable is called. I didn't use just because it's a variable and
not a #define. C can't handle array size specifiers that are variables,
and I didn't want to change the variable to a #define since it might break
other parts of the code. Anyways, 500 is a ok value.. It gives (on a PC)
an overhead of 4 * 500 bytes which is less that 2kb.. Tweak it for your
own satisfaction.
*/

struct char_data *theWhoList[500];

/* this little function will compare apples and pears and return
-1, 0 or 1 depending on which fruit weighs most
*/
int compareChars(const void *l, const void *r) {

    struct char_data **left;
    struct char_data **right;

    left = (struct char_data **)l;
    right = (struct char_data **)r;

    if(GET_LEVEL(*left) < GET_LEVEL(*right))
        return 1;
    else if(GET_LEVEL(*left) == GET_LEVEL(*right))
        return 0;
    else
        return -1;
}

#define WHO_FORMAT \
"format: who [minlev[-maxlev]] [-n name] [-c classlist] [-s] [-o] [-q]
[-r] [-z]\r\n"

ACMD(do_who)
{
    struct descriptor_data *d;
    struct char_data *tch;
    char name_search[MAX_INPUT_LENGTH];
    char mode;
    size_t i;
    int low = 0, high = LVL_IMPL, localwho = 0, questwho = 0;
    int showclass = 0, short_list = 0, outlaws = 0, num_can_see = 0;
    int who_room = 0;
    int noElements = 0;
    int curEl;
    extern char *race_abbrevs[];

    skip_spaces(&argument);
    strcpy(buf, argument);
    name_search[0] = '\0';

    while (*buf) {
        half_chop(buf, arg, buf1);
        if (isdigit(*arg)) {
            sscanf(arg, "%d-%d", &low, &high);
            strcpy(buf, buf1);
        } else if (*arg == '-') {
            mode = *(arg + 1);  /* just in case; we destroy arg in the switch *
/
            switch (mode) {
            case 'o':
            case 'k':
                outlaws = 1;
                strcpy(buf, buf1);
                break;
            case 'z':
                localwho = 1;
                strcpy(buf, buf1);
                break;
            case 's':
                short_list = 1;
                strcpy(buf, buf1);
                break;
            case 'q':
                questwho = 1;
                strcpy(buf, buf1);
                break;
            case 'l':
                half_chop(buf1, arg, buf);
                sscanf(arg, "%d-%d", &low, &high);
                break;
            case 'n':
                half_chop(buf1, name_search, buf);
                break;
            case 'r':
                who_room = 1;
                strcpy(buf, buf1);
                break;
            case 'c':
                half_chop(buf1, arg, buf);
                for (i = 0; i < strlen(arg); i++)
                    showclass |= find_class_bitvector(arg[i]);
                break;
            default:
                send_to_char(WHO_FORMAT, ch);
                return;
                break;
            }                   /* end of switch */

        } else {                /* endif */
            send_to_char(WHO_FORMAT, ch);
            return;
        }
    }                           /* end while (parser) */

    /* 'Collect' players and add them to the array */
    for(noElements = 0, d = descriptor_list; d; d = d->next) {
        if(d->connected)
            continue;

        if(d->original)
            tch = d->original;
        else if(!(tch = d->character))
            continue;

        theWhoList[noElements++] = tch;
    }

    /* Sort it using the built in libc-quicksort routine */
    qsort(theWhoList, noElements, sizeof(struct char_data  *), compareChars);

    send_to_char("Players\r\n-------\r\n", ch);

    /* Print it */
    for(curEl = 0; curEl < noElements; curEl++) {
        tch = theWhoList[curEl];
        /* put normal printing routine in this for {}
         */
    }                           /* end of for */

    if (short_list && (num_can_see % 4))
        send_to_char("\r\n", ch);
    if (num_can_see == 0)
        sprintf(buf, "\r\nNo-one at all!\r\n");
    else if (num_can_see == 1)
        sprintf(buf, "\r\nOne lonely character displayed.\r\n");
    else
        sprintf(buf, "\r\n%d characters displayed.\r\n", num_can_see);
    send_to_char(buf, ch);
}

<< Who level sorting [by George] | Reply | View as text | Threaded | Win95 Log Files (I) [by Shirak] >>