/*******************************************************************************
 * K&R 5-14
 *
 * Line sorting program using pointers
 * with option to sort numerically or
 * lexicographically, normal or reverse 
 * order. 
 *
 * program: linesort
 * ops: 
 * -n sort numerically
 * -r reverse order
 * -f ignore case
 *
 * This is just copied and ordered from the book. But I found that the 
 * version in the book "ate" the last char of each line. This was solved
 * by giving len+1 to alloc() and then placing the '\0' at len and not 
 * len-1. I'm not totally sure why this was the case--a typo in the version 
 * of K&R used? The version of getline() used? Anyhow, as is it seems to work
 * well. 
 * 
 * I was lucky to stumble on the solution of declaring numcmp with const 
 * paramaters so it matches strcmp. Otherwise, there was an error of mismatched
 * pointers in the condition statement. 
 * ~yetimach
 ******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

void my_swap(void *v[], int i, int j){
    void *temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

int numcmp(const char *s1, const char *s2){
    double v1, v2;
    v1 = atof(s1);
    v2 = atof(s2);
    if (v1 < v2)
        return -1;
    if (v1 > v2)
        return 1;
    else
        return 0;
}

void my_qsort(void *v[], int left, int right, 
        int (*comp) (void *, void *)){
    int i, last;
    if (left >= right)
        return;
    my_swap(v, left, (left + right)/2);
    last = left;
    for (i = left+1; i <= right; i++)
        if ((*comp)(v[i], v[left]) < 0)
            my_swap(v, ++last, i);
    my_swap(v, left, last);
    my_qsort(v, left, last-1, comp);
    my_qsort(v, last+1, right, comp);
}

void writelines(char *lineptr[], int nlines, int rev){
        while (nlines-- > 0)
            printf("%s\n", rev ? lineptr[nlines] : *lineptr++);
    }

int my_getline(char *s, int max){
    int c, i;
    for (i = 0; i < max-1 && (c = getchar()) != '\n' && c != EOF; *s++ = c, i++)
        ;
    *s = '\0'; 
    if (i >= max-1)
        return -1;
    else
        return i;
}

#define ALLOCSIZE 1000
static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf;

char *alloc(int n){
    if (allocbuf + ALLOCSIZE - allocp >= n){
        allocp += n;
        return allocp - n;
    }else
        return NULL;
}

void afree(char *p){
    if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
        allocp = p;
}

#define MAXLEN 1000
int readlines(char *lineptr[], int maxlines){
    int len, nlines;
    char *p, line[MAXLEN];
    nlines = 0;
    while ((len = my_getline(line, MAXLEN)) > 0)
        if (nlines >= maxlines || (p = alloc(len+1)) == NULL)
            return -1;
        else {
            line[len] = '\0'; 
            strcpy(p, line);
            lineptr[nlines++] = p;
        }
    return nlines;
}

#define MAXLINES 5000

char *lineptr[MAXLINES];

int main(int argc, char *argv[])
{
    int nlines, numeric = 0, reverse = 0, fold = 0, c;
    while (--argc > 0 && (*++argv)[0] == '-')
        while ((c = *++argv[0]))
            switch (c) {
                case 'n':
                    numeric = 1;
                    break;
                case 'r':
                    reverse = 1;
                    break;
                case 'f':
                    fold = 1;
                    break;
                default:
                    printf("unknown option: '%c'\n", c);
                    return -1;
                    break;
            }
    if ((nlines = readlines(lineptr, MAXLINES)) >= 0){
            my_qsort((void**) lineptr, 0, nlines-1, 
                (int (*) (void*, void*)) (numeric ? numcmp : 
                    (fold ? strcasecmp : strcmp)));
        writelines(lineptr, nlines, reverse);
    } else {
        printf("error: input too big to sort\n");
        return 1;
    }
    return 0;
}