#include "gbos.h"
/* sort [-r] [-n] [file]: sort lines, from a file or stdin.
 *
 * Everything is held in RAM, which bounds it: a task has 8 KiB, a file caps
 * at 3 KiB, so MAXBYTES/MAXLINES are set to fit with room for the stack.
 * Insertion sort - with at most 96 lines, the simple thing is fast enough and
 * costs far less ROM than anything clever.
 *
 *   ls /bin | sort | head       alphabetical
 *   uniq -c f | sort -n -r      the classic "top hits" pipeline
 *
 * The line store is static (it is far too big for the stack), so main() must
 * copy the arguments off $A000 before touching it - see usr/ping.c. */

#define MAXBYTES 2400
#define MAXLINES 96

#define KEY MAXLINES /* scratch slot: the line being inserted */

static char store[MAXBYTES];
static unsigned int off[MAXLINES + 1];
static unsigned char len[MAXLINES + 1];

/* -> 1 if line a sorts after line b */
static unsigned char gt(unsigned char a, unsigned char b, unsigned char num) {
    unsigned char i, la = len[a], lb = len[b];
    if (num) { /* leading integer, if any */
        unsigned int va = 0, vb = 0;
        for (i = 0; i < la && store[off[a] + i] >= '0' && store[off[a] + i] <= '9'; i++)
            va = va * 10 + (unsigned char)(store[off[a] + i] - '0');
        for (i = 0; i < lb && store[off[b] + i] >= '0' && store[off[b] + i] <= '9'; i++)
            vb = vb * 10 + (unsigned char)(store[off[b] + i] - '0');
        if (va != vb) return (unsigned char)(va > vb);
    }
    for (i = 0; i < la && i < lb; i++) {
        char ca = store[off[a] + i], cb = store[off[b] + i];
        if (ca != cb) return (unsigned char)(ca > cb);
    }
    return (unsigned char)(la > lb);
}

void main(void) {
    char args[24];
    char *argv[4];
    unsigned char argc, rev, num, fd = NOFD, i, j;
    unsigned int used = 0;
    unsigned char n = 0, clen = 0;
    unsigned int cstart = 0;
    char *fname = 0;
    int ch;

    { /* argv lives at $A000, and so does store[] - copy the flags out first */
        char *a = getargs();
        for (i = 0; a[i] && i < 23; i++) args[i] = a[i];
        args[i] = 0;
    }
    argc = 0;
    { /* tokenize our stack copy */
        char *p = args;
        for (;;) {
            while (*p == ' ') *p++ = 0;
            if (!*p) break;
            if (argc < 4) argv[argc] = p;
            argc++;
            while (*p && *p != ' ') p++;
        }
    }
    rev = hasflag(argv, argc, 'r');
    num = hasflag(argv, argc, 'n');
    for (i = 0; i < argc; i++)
        if (argv[i][0] != '-') {
            fname = argv[i];
            break;
        }

    if (fname) {
        fd = open(fname, O_READ);
        if (fd == EISDIR) {
            puts("sort: is a directory");
            nl();
            sexit(2);
        }
        if (fd == NOFD) {
            puts("sort: no such file");
            nl();
            sexit(2);
        }
    }
    cstart = 0;
    for (;;) {
        if (fd == NOFD) {
            char c = readc();
            ch = (c == EOF) ? -1 : c;
        } else ch = fgetc(fd);
        if (ch == '\r') continue;
        if (ch >= 0 && ch != '\n') {
            if (used < MAXBYTES) {
                store[used++] = (char)ch;
                clen++;
            }
            continue;
        }
        if (ch < 0 && clen == 0) break;
        if (n < MAXLINES) {
            off[n] = cstart;
            len[n] = clen;
            n++;
        }
        cstart = used;
        clen = 0;
        if (ch < 0) break;
    }
    if (fd != NOFD) close(fd);

    for (i = 1; i < n; i++) { /* insertion sort on the index */
        off[KEY] = off[i];
        len[KEY] = len[i];
        j = i;
        /* shift while the neighbour is on the wrong side of the key. gt()
           takes table slots, so the key needs a slot of its own - reusing
           slot i as scratch overwrites the entries being shifted into it. */
        while (j && (gt((unsigned char)(j - 1), KEY, num) ? !rev : rev)) {
            off[j] = off[j - 1];
            len[j] = len[j - 1];
            j--;
        }
        off[j] = off[KEY];
        len[j] = len[KEY];
    }
    for (i = 0; i < n; i++) {
        writes(store + off[i], len[i]);
        nl();
    }
}