The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 5.16 on page 121
Add the -d ("directory order") option, which makes comparisons only on letters, numbers
and blanks. Make sure it works in conjunction with -f .
Solution by Barrett Drawdy
/* * Solution to K&R exercise 5-16 * This solution uses a slightly modified version of the readline function * that allows it to read very long lines. However, it can be used with * with the original readline. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> int getline(char*, int); char *alloc(int); int readlines(char**, int); void writelines(char**, int); void quicksort(void**, int, int, int (*)(void*, void*)); int numcmp(char*, char*); int mystrcmp(char*, char*); #define MAXLINES 10000 #define MAXLEN 1000 char *lineptr[MAXLINES]; /* pointers to text lines */ int decreasing = 0; /* 0 if increasing, 1 if decreasing -r flag */ int numeric = 0; /* 1 if numeric sort -n flag */ int fold = 0; /* 1 if not case-sensitive -f flag */ int directory = 0; /* 1 if directory sort -d flag */ int main(int argc, char* argv[]) { int nlines, i; while(--argc > 0) { ++argv; if((*argv)[0] == '-') for(i = 1; (*argv)[i]; ++i) switch((*argv)[i]) { case 'n': numeric = 1; break; case 'f': fold = 1; break; case 'r': decreasing = 1; break; case 'd': directory = 1; break; default: printf("usage: sort -dfnr\n"); return 1; } else { printf("usage: sort -dfnr\n"); return 1; } } if((nlines = readlines(lineptr, MAXLINES)) >= 0) { if(numeric) quicksort((void**) lineptr, 0, nlines - 1, (int (*)(void*, void*))numcmp); else quicksort((void**) lineptr, 0, nlines - 1, (int (*)(void*, void*))mystrcmp); writelines(lineptr, nlines); return 0; } else { printf("input too big to sort\n"); return 1; } } /* quicksort: sort v[left]...v[right] into increasing or decreasing order */ void quicksort(void *v[], int left, int right, int (*comp)(void*, void*)) { int i, last; void swap(void *v[], int, int); if(left >= right) /* do nothing if array contains */ return; /* fewer than two elements */ swap(v, left, (left + right) / 2); /* move element to sort left */ last = left; for(i = left + 1; i <= right; ++i) { /* move all elements < or > sort */ if(!decreasing) { /* element to the left according */ if((*comp)(v[i], v[left]) < 0) /* to order */ swap(v, ++last, i); } else if((*comp)(v[i], v[left]) > 0) swap(v, ++last, i); } swap(v, left, last); /* move sort element to its final position */ quicksort(v, left, last - 1, comp); /* sort left subarray */ quicksort(v, last + 1, right, comp); /* sort right subarray */ } /* * mystrcmp: Compares s1 and s2 lexicographically. Ignores characters that * are not letters, numbers, or whitespace if directory flag is set. If the * fold flag is set, it isn't case sensitive. */ int mystrcmp(char *s1, char *s2) { if(directory) { while(!isdigit(*s1) && !isalpha(*s1) && !isspace(*s1) && *s1) ++s1; /* ignore bad characters */ while(!isdigit(*s2) && !isalpha(*s2) && !isspace(*s2) && *s2) ++s2; /* ignore bad characters */ } while(fold ? (tolower(*s1) == tolower(*s2)) : (*s1 == *s2)) { if(*s1 == '\0') return 0; ++s1; ++s2; if(directory) { while(!isdigit(*s1) && !isalpha(*s1) && !isspace(*s1) && *s1) ++s1; /* ignore bad characters */ while(!isdigit(*s2) && !isalpha(*s2) && !isspace(*s2) && *s2) ++s2; /* ignore bad characters */ } } return fold ? (tolower(*s1) - tolower(*s2)) : (*s1 - *s2); } /*numcmp: compare s1 and s2 numerically */ int numcmp(char *s1, char *s2) { double v1, v2; v1 = atof(s1); v2 = atof(s2); if(v1 < v2) return -1; else if(v1 > v2) return 1; else return 0; } void swap(void *v[], int i, int j) { void *temp; temp = v[i]; v[i] = v[j]; v[j] = temp; } /*readlines: read input lines. This version is slightly modified to read longer lines than the limit set by MAXLEN. */ int readlines(char *lineptr[], int maxlines) { int len, nlines = 0; char *p, line[MAXLEN]; int longline = 0; while((len = getline(line, MAXLEN)) > 0) { if(nlines >= maxlines || (p = alloc(len)) == NULL) return -1; else { if(line[len - 1] == '\n') { line[len - 1] = '\0'; /* delete newline */ strcpy(p, line); if(!longline) lineptr[nlines++] = p; else longline = 0; } else { strcpy(p, line); if(!longline) { lineptr[nlines++] = p; longline = 1; } } } } return nlines; } /* writelines: write output lines */ void writelines(char *lineptr[], int nlines) { while(nlines-- > 0) printf("%s\n", *lineptr++); return; } int getline(char *s, int max) { int c; char *ps = s; while(--max && (c=getchar()) != EOF && c != '\n') *s++ = c; if(c == '\n') *s++ = '\n'; *s = '\0'; return s - ps; } #define ALLOCSIZE 2000000 static char allocbuf[ALLOCSIZE]; /* storage for alloc */ static char *allocp = allocbuf; /* next free position */ char *alloc(int n) { if(allocbuf + ALLOCSIZE - allocp >= n) { /* it fits */ allocp += n; return allocp - n; /* old p */ } else /* not enough room */ return 0; }
Solution by Codybartfast
(cat 0) -
Key based solution:
void dirvalue(char *value); void fold(char *value); char *makekey(char *value, int dofold, int dodirsort); char **keyvaluepair(char *key, char *value); char *key(char *pair[]); char *value(char *pair[]); int keycompare(void *a, void *b); int reverse(void *a, void *b); int (*basecompare)(void *, void *); int (*compare)(void *, void *); int main(int argc, char *argv[]) { int i, nlines; int numeric = 0; int doreverse = 0; int dofold = 0; int dodirsort = 0; char *buff, **lines, ***kvps; for (i = 1; i < argc; i++) { if (strcmp(argv[i], "-n") == 0) numeric = 1; else if (strcmp(argv[i], "-r") == 0) doreverse = 1; else if (strcmp(argv[i], "-f") == 0) dofold = 1; else if (strcmp(argv[i], "-d") == 0) dodirsort = 1; } basecompare = numeric ? ((int (*)(void *, void *))numcmp) : ((int (*)(void *, void *))strcmp); compare = doreverse ? reverse : basecompare; if ((nlines = readlines(&buff, &lines)) == LNS_ERROR) { printf("input too big to sort\n"); return 0; } kvps = malloc(nlines * sizeof(char **)); for (i = 0; i < nlines; i++) { char *key = makekey(lines[i], dofold, dodirsort); kvps[i] = keyvaluepair(key, lines[i]); } quicksort((void **)kvps, 0, nlines - 1, keycompare); for (i = 0; i < nlines; i++) lines[i] = value(kvps[i]); writelines(lines, nlines); freelines(buff, lines); freestuff(kvps, nlines); return 0; } void fold(char *value) { while ((*value = toupper(*value))) value++; } void dirvalue(char *value) { char c, *write; write = value; while ((c = *value++)) { if (isalnum(c) || c == ' ' || c == '\n') *write++ = c; } *write = '\0'; } char *makekey(char *value, int dofold, int dodirsort) { char *key = malloc((strlen(value) + 1) * sizeof(char)); strcpy(key, value); if (dofold) fold(key); if (dodirsort) dirvalue(key); return key; } char **keyvaluepair(char key[], char value[]) { char **pair = malloc(2 * sizeof(char *)); pair[0] = key; pair[1] = value; return pair; } char *key(char *pair[]) { return pair[0]; } char *value(char *pair[]) { return pair[1]; } int keycompare(void *a, void *b) { char *v1 = key(a); char *v2 = key(b); return (*compare)(v1, v2); } int reverse(void *a, void *b) { return (*basecompare)(b, a); }
Full code on github
Solution by anonymous
This is an extension from my exercise 5.15 solution. I added dircmp, referenced it in the pointer functions part of the code, and added -d to the arguments code.
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <ctype.h> /* Exercise 5-16. Add the -d ("directory order") option, which makes comparisons only on letters, numbers and blanks. Make sure it works in conjunction with -f. */ #define MAXLINES 5000 // max #lines to be sorted #define MAXLEN 1000 // max length of any input line #define ALLOCSIZE 10000 // size of available space char *lineptr[MAXLINES]; // pointers to text lines static char allocbuf[ALLOCSIZE]; // storage for alloc static char *allocp = allocbuf; // next free position int readlines(char *lineptr[], int nlines); void writelines(char *lineptr[], int nlines); void swap(void *v[], int, int); int readlines(char *lineptr[], int maxlines); void writelines(char *lineptr[], int nlines); int getline(char *s, int lim); char *alloc(int n); void myqsort(void *lineptr[], int left, int right, int (*comp)(void *, void *)); // qsort had to be renamed to myqsort since stdlib.h is included. int reverseCompare(void *, void *); // used to call baseCompare with the arguments in reverse order int numcmp(const char *, const char *); int dircmp(const char *, const char *); enum booelan { FALSE, TRUE }; // FALSE == 0, TRUE == 1, this creates booleans in a language that that doesn't natively support them unless you import stdbool.h in c99 or newer int (*baseCompare)(void *, void *); // function pointer called baseCompare which points to either numcmp or cmpstr depending on the sorting type int (*compare)(void *, void *); // function pointer called compare that will either point to the regular compare function baseCompare, or a new function called reverseCompare int caseInsensitive = FALSE; // sort input lines int main(int argc, char *argv[]) { // nlines = number of input lines read, numeric, reverse, and dirOrder are flags for features turned on in the arguments int nlines, numeric = FALSE, reverse = FALSE, dirOrder = FALSE; while (--argc > 0) if (strcmp(*++argv, "-n") == 0) numeric = TRUE; else if (strcmp(*argv, "-r") == 0) reverse = TRUE; else if (strcmp(*argv, "-f") == 0) caseInsensitive = TRUE; else if (strcmp(*argv, "-d") == 0) dirOrder = TRUE; else { printf("Usage: sort [-n] [-r] [-f] [-d]\n"); return 1; } baseCompare = (int (*)(void *, void *))(numeric ? numcmp : dirOrder ? dircmp : caseInsensitive ? strcmpi : strcmp); // chooses comparison function based on flags compare = reverse ? reverseCompare : baseCompare; // if reverse, use reverseCompare, otherwise use baseCompare if ((nlines = readlines(lineptr, MAXLINES)) >= 0) { myqsort((void **) lineptr, 0, nlines - 1, compare); writelines(lineptr, nlines); return 0; } else { printf("input too big to sort\n"); return 1; } } // sort v[left]...v[right] into increasing order void myqsort(void *v[], int left, int right, int (*comp)(void *, void *)) { int i, last; if (left >= right) // do nothing if array contains fewer than two elements return; swap(v, left, (left + right) / 2); last = left; for (i = left + 1; i <= right; i++) if ((*comp)(v[i], v[left]) < 0) swap(v, ++last, i); swap(v, left, last); myqsort(v, left, last - 1, comp); myqsort(v, last + 1, right, comp); } // compare s1 and s2 numerically int numcmp(const char *s1, const char *s2) { double v1 = atof(s1), v2 = atof(s2); if (v1 < v2) return -1; else if (v1 > v2) return 1; return 0; } // swaps int i and j void swap(void *v[], int i, int j) { void *temp = v[i]; v[i] = v[j]; v[j] = temp; } // read input lines int readlines(char *lineptr[], int maxlines) { int len, nlines; char *p, line[MAXLEN]; nlines = 0; while ((len = getline(line, MAXLEN)) > 0) if (nlines >= maxlines || (p = alloc(len)) == NULL) return -1; else { line[len - 1] = '\0'; // delete newline strcpy(p, line); lineptr[nlines++] = p; } return nlines; } // write output lines void writelines(char *lineptr[], int nlines) { while (nlines-- > 0) printf("%s\n", *lineptr++); } // get line into s, return length int getline(char *s, int lim) { int c; char *original = s; while (--lim > 0 && (c = getchar()) != EOF && c != '\n') *s++ = c; if (c == '\n') *s++ = c; *s = '\0'; return s - original; // returns length } // return pointer to n characters char *alloc(int n) { if (allocbuf + ALLOCSIZE - allocp >= n) // it fits { allocp += n; // update marker to note where the next unallocated memory starts return allocp - n; // old pointer address } else return 0; // not enough room } int reverseCompare(void *left, void *right) { return (*baseCompare)(right, left); // reverses the order that items are compared and which causes it to be sorted in reverse (descending) order } // compare s1 and s2 via directory order (compares only on letters, numbers, and blanks) int dircmp(const char *s1, const char *s2) { int i = 0, j = 0; while (s1[i] || s2[i]) if (isalnum(s1[i]) || isspace(s1[i])) if (isalnum(s2[j]) || isspace(s2[j])) if (caseInsensitive ? tolower(s1[i]) < tolower(s2[j]) : s1[i] < s2[j]) return -1; else if (caseInsensitive ? tolower(s1[i]) > tolower(s2[j]) : s1[i] > s2[j]) return 1; else i++, j++; else j++; else i++; return 0; }
