Exercise 5.16

Page 121

Add the -d ("directory order") option, which makes comparisons only on letters, numbers

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

#define MAXLINES 5000
#define MAXCHARS 500000
char *lineptr[MAXLINES];

int readlines(char *lineptr[], int maxlines, char storage[], int maxchars);
void writelines(char *lineptr[], int nlines);

void q_sort(void *lineptr[], int left, int right,
	    int (*comp)(const char *, const char *, const unsigned),
	    unsigned opts);
int numcmp(const char *, const char *, unsigned);
int str_cmp(const char *, const char *, unsigned);

enum opt {
	opt_numeric = 0b0001,
	opt_reverse = 0b0010,
	opt_fold = 0b0100,
	opt_directory_order = 0b1000
};
int main(int argc, char *argv[])
{
	int nlines;
	unsigned opts = 0;
	char storage[MAXCHARS];

	while (--argc > 0) {
		if (strcmp(argv[argc], "-n") == 0) {
			opts |= opt_numeric;
		} else if (strcmp(argv[argc], "-r") == 0) {
			opts |= opt_reverse;
		} else if (strcmp(argv[argc], "-f") == 0) {
			opts |= opt_fold;
		} else if (strcmp(argv[argc], "-d") == 0) {
			opts |= opt_directory_order;
		}
	}

	if ((nlines = readlines(lineptr, MAXLINES, storage, MAXCHARS)) >= 0) {
		q_sort((void **)lineptr, 0, nlines - 1,
		       (int (*)(const char *, const char *, unsigned))(
			       opts & opt_numeric ? numcmp : str_cmp),
		       opts);
		writelines(lineptr, nlines);
		return 0;
	} else {
		printf("input too big to sort \n");
		return 1;
	}
}

void q_sort(void *v[], int left, int right,
	    int (*comp)(const char *, const char *, unsigned), unsigned opts)
{
	int i, last, comp_result;
	void swap(void *v[], int, int);

	if (left >= right) {
		return;
	}
	swap(v, left, (left + right) / 2);
	last = left;
	for (i = left + 1; i <= right; i++) {
		comp_result = (*comp)(v[i], v[left], opts);
		if (opts & opt_reverse && comp_result >= 0) {
			swap(v, ++last, i);
		} else if (!(opts & opt_reverse) && comp_result < 0) {
			swap(v, ++last, i);
		}
	}
	swap(v, left, last);
	q_sort(v, left, last - 1, comp, opts);
	q_sort(v, last + 1, right, comp, opts);
}

int numcmp(const char *s1, const char *s2, unsigned opts)
{
	double v1, v2;

	v1 = atof(s1);
	v2 = atof(s2);
	if (v1 < v2) {
		return -1;
	} else if (v1 > v2) {
		return 1;
	} else {
		return 0;
	}
}

void to_lower(const char *src, char *dst);
void filter_directory_characters(const char *src, char *dst);
int str_cmp(const char *s1, const char *s2, unsigned opts)
{
	/* Yes I know this function isn't great but I am aiming to use primarily only what I 
	 * have been taught by the book so far. I'm sure it could still be better but oh 
	 * well. */

	const char *s1_comp = s1;
	const char *s2_comp = s2;

	if (opts & opt_fold) {
		char s1_lower[strlen(s1)];
		char s2_lower[strlen(s2)];
		to_lower(s1_comp, s1_lower);
		to_lower(s2_comp, s2_lower);

		s1_comp = s1_lower;
		s2_comp = s2_lower;
	}

	if (opts & opt_directory_order) {
		char s1_filtered[strlen(s1)];
		char s2_filtered[strlen(s2)];
		filter_directory_characters(s1_comp, s1_filtered);
		filter_directory_characters(s2_comp, s2_filtered);

		s1_comp = s1_filtered;
		s2_comp = s2_filtered;
	}

	return strcmp(s1_comp, s2_comp);
}

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

#define MAXLEN 1000
int get_line(char s[], int lim);
int readlines(char *lineptr[], int maxlines, char storage[], int maxchars)
{
	int len, nlines;
	char line[MAXLEN];
	int i;

	i = 0;
	nlines = 0;
	while ((len = get_line(line, MAXLEN)) > 0) {
		if (nlines >= maxlines || (i + len) >= maxchars) {
			return -1;
		} else {
			line[len - 1] = '\0';
			strcpy(storage + i, line);
			lineptr[nlines++] = storage + i;
			i += len;
		}
	}
	return nlines;
}

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

int get_line(char s[], int lim)
{
	int c, i;

	i = 0;
	while (--lim > 0 && (c = getchar()) != EOF && c != '\n') {
		s[i++] = c;
	}
	if (c == '\n') {
		s[i++] = c;
	}
	s[i] = '\0';
	return i;
}

#include <ctype.h>
void to_lower(const char *src, char *dst)
{
	while ((*dst++ = tolower(*src++)) != '\0')
		;
}

void filter_directory_characters(const char *src, char *dst)
{
	while (*src != '\0') {
		if (*src < '0' || (*src > 9 && *src < 'A') ||
		    (*src > 'Z' && *src < 'a') || *src > 'z') {
			*dst = ' ';
		} else {
			*dst = *src;
		}
		dst++;
		src++;
	}
}