/*******************************************************************************
 * K&R 5-7
 *
 * Line sorting program using pointers
 *
 * program: linesort
 *
 * 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. 
 * ~yetimach
 ******************************************************************************/

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

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

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

void writelines(char *lineptr[], int nlines){
    while (nlines-- > 0)
        printf("%s\n", *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 nlines;
    if ((nlines = readlines(lineptr, MAXLINES)) >= 0){
        my_qsort(lineptr, 0, nlines-1);
        writelines(lineptr, nlines);
    } else {
        printf("error: input too big to sort\n");
        return 1;
    }
    return 0;
}