From: Jorgen Sigvardsson 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); }