/*
  Name:    pmsort.c
  Purpose: "Poor man's" sort utility
  Author:  Bill Slough

  Usage:   pmsort filename

  Notes:
    1. Sorts a file of strings into lexicographical order, using C's strcmp().

    2. The sorting algorithm used is selection sort:  easy to understand, but
       not efficient.

    3. Strings are limited to a fixed length, controlled by MAX_WORD_LENGTH.
       Input strings longer than this will simply be truncated.

    4. The number of strings pmsort can handle is controlled by MAX_LINES.
*/

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

#define MAX_WORD_LENGTH 8    /* Adjust as necessary       */
#define MAX_LINES 15         /* Kept small for testing... */

char *readLine(char *s, int n, FILE *fp, bool *overflow);
void *safe_malloc(size_t size);
void display(char *v[ ]);
void sort(char *v[ ], int n);
void swap(char **p, char **q);

int main(int argc, char *argv[ ]) {
    FILE *fp;             /* file pointer for an input stream */
    int lineCount;        /* number of lines processed */
    bool lineOverflow;    /* not enough room in char array? */
    int  nrTruncations;   /* number of input lines which overflow char array */

    char line[MAX_WORD_LENGTH + 1];  /* string to hold one line of input */
    char *lines[MAX_LINES + 1];      /* stores the lines read from the file */
    int nrLines;                     /* number of lines in the lines array */

    /* Check for proper usage */
    if (argc != 2) {
        fprintf(stderr, "Usage: pmsort filename\n");
        exit(EXIT_FAILURE);
    }

    /* Try to open the input stream for reading */
    fp = fopen(argv[1], "r");
    if (fp == NULL) {
        fprintf(stderr, "Error: can't open \"%s\" for reading.\n", argv[1]);
        exit(EXIT_FAILURE);
    }

    /* Read the file, line by line */
    nrTruncations = 0;
    lineCount = 0;
    nrLines = 0;
    while (readLine(line, sizeof(line), fp, &lineOverflow) != NULL) {
        /* Did this line get truncated? */
        if (lineOverflow)
            nrTruncations++;

        /* Add this line to the array of lines if there is room */
        if (lineCount < MAX_LINES) {
            lines[nrLines] = safe_malloc(strlen(line) + 1);  /* +1 for '\0' */
            strcpy(lines[nrLines], line);
            nrLines++;
        }
        lineCount++;
    }
    lines[nrLines] = NULL;    /* deposit a sentinel value to mark the end */

    /* Give warnings as necessary */
    if (lineCount > nrLines)
        fprintf(stderr, "pmsort: warning - too many lines to sort.\n");
    if (nrTruncations > 0)
        fprintf(stderr, "pmsort: warning - some lines were truncated.\n");

    /* Process */
    sort(lines, nrLines);
    display(lines);

    /* Close the stream */
    fclose(fp);

    return 0;
}

/* Read and store one line of input

   return NULL if stream is at eof or there was a read error
   otherwise returns the pointer s to the char array

   reads and stores up to n characters in the char array, stopping at newline
   if there isn't space to hold the entire line, overflow is set to true
   and any trailing characters on that line are discarded
*/
char *readLine(char *s, int n, FILE *fp, bool *overflow) {
    int i;       /* number of characters stored in the string */
    int ch;      /* most recent character read from the file */
    int count;   /* number of characters read */

    i = 0;
    count = 0;
    /* read characters on the current line, storing as many as will fit */
    while (((ch = getc(fp)) != '\n') && (ch != EOF)) {
        count++;
        /* safely deposit this character */
        if (i < n - 1)    /* hold one slot back for '\0' */
            s[i++] = ch;
    }
    if ((count == 0) && (ch == EOF))    /* no characters read: at eof */
        return NULL;

    /* stream was not at eof, so a line has been read */
    s[i] = '\0';   /* properly terminate the string */

    /* Too many characters on this line? */
    if (count > i)
        *overflow = true;
    else
        *overflow = false;

    return s;
}

/* safely allocate a block of storage, aborting program if not possible */
void *safe_malloc(size_t size) {
    void *p;
    p = malloc(size);
    if (p == NULL) {
        fprintf(stderr, "pmsort: error - out of space!");
        exit(EXIT_FAILURE);
    } else
        return p;
}

/* display the contents of a NULL-terminated array of strings */
void display(char *v[ ]) {
    int i;
    i = 0;
    while (v[i] != NULL) {
        printf("%s\n", v[i]);
        i++;
    }
}

/* sort an array of n strings into lexicographical order */
void sort(char *v[ ], int n) {
    int i;
    int j;
    int k;

    /* use selection sort to rearrange the strings in sorted order */
    i = 0;
    while (i < n - 1) {
        /* v[0], v[1], v[2], ..., v[i - 1] are in sorted order and they
           are the smallest among all the elements in v.

           To make progress, locate the smallest value in the tail end
           of v and place it at v[i]
        */
        j = i;    /* index of smallest known element among v[i] ... v[n - 1] */
        for (k = i + 1; k < n; k++) {
            /* is there a smaller value somewhere? */
            if (strcmp(v[k], v[j]) < 0)
                j = k;
        }
        swap(&v[i], &v[j]);
        i++;
    }
}

/* swap two strings in an array of strings */
void swap(char **p, char **q) {
    char *temp;
    temp = *p;
    *p = *q;
    *q = temp;
}