Exercise 5-15 (flines - Case insensitive sort)

Chapter_5     Exercise_5-14

Exercise_5-16

---

---

Exercise 5-15     K&R, p. 121

Exercise 5-15. Add the option -f to fold upper and lower case together, so that case distinctions are not made during sorting; for example, a and A compare equal.

flines.c         download

#include <stdio.h> // for getchar(), printf(), EOF, NULL, FILE, fopen(), fclose()
#include <string.h> // for strcpy(), strcmp()

#define MAXLINES 20000 // max no of lines to be sorted
#define MAXLEN 100 // max line length

int readlines (char *lineptr[], int nlines);
void writelines (char *lineptr[], int nlines, char *filename);

void qSort(void *lineptr[], int left, int right, // qsort() is declared in stdlib.h
int (*comp)(void*, void*)); // comparison function, strcmp() or strfcmp()

int strfcmp(char*, char*); // case insensitive comparison (fold upper and lowercase)

int main(int argc, char *argv[])
{
int ci = 0; // 1 if case insensitive sort
int c;

while (--argc > 0 && (*++argv)[0] == '-') // optional argument
{
while (c = *++argv[0]) // -f, -f -f, -ff, etc.
{
switch(c)
{
case 'f' :
ci = 1;
break;
default:
printf("Illegal option: '%c'\n", c);
printf("Usage : ./flines -f\n");
printf("optional argument \"-f\" - case insensitive sort\n");
printf("(fold uppercase and lowercase together)\n");

return 1; // end program, signalling error
}
}
}

if (argc) // if (argc > 0)
{
printf("Usage : ./flines -f\n");
printf("optional argument \"-f\" - case insensitive sort\n");
printf("(fold uppercase and lowercase together)\n");

return 1; // end program, signalling error
}

char *lineptr[MAXLINES];
int nlines; // no of input lines read

if ((nlines = readlines(lineptr, MAXLINES)) >= 0)
{// casts are necessary to avoid error or warning of pointer type mismatch:
qSort((void**)lineptr, 0, nlines-1,
(ci ? (int (*)(void*, void*))strfcmp : (int (*)(void*, void*))strcmp));

writelines(lineptr, nlines, (ci ? "fsorted.txt" : "sorted.txt"));
}
else
{
printf("Error: input too big to sort\n");
return 1; // exit program, signalling error
}

return 0;
}

int getLine(char *, int); // getline() is declared in stdio.h
char* alloc(int); // allocate storage

int readlines (char *lineptr[], int maxlines) // read input lines
{
int len; // length of line
int nlines; // no of input lines read

char *p, line[MAXLEN];

nlines = 0;
while ((len = getLine(line, MAXLEN)) > 0)
{
if(nlines >= maxlines || (p = alloc(len+1)) == NULL)
{return -1;} // len+1 for ending '\0'
else
{
strcpy(p, line);
lineptr[nlines++] = p;
}
}

return nlines;
}

int getLine(char *s, int lim)
{
int c = EOF; // initialize
char *p;
// getchar() is only executed if ((p-s) < (lim-1)):
for (p = s; (p-s) < (lim-1) && (c = getchar()) != EOF && c != '\n'; p++)
{ // from 0 to lim-2; s[lim-2]='\n', s[lim-1]='\0'
*p = c;
}
if (c == '\n')
{*p++ = c;}

*p = '\0'; // the null character ends a string

return p-s; // max(p-s) == (lim-1)
}

#define ALLOCSIZE (MAXLINES * MAXLEN)

static char allocbuf[ALLOCSIZE]; // storage for alloc()
static char *allocp = allocbuf; // next free position

char* alloc(int n) // return pointer to n chars
{
if (allocbuf + ALLOCSIZE - allocp >= n) // it fits
{
allocp += n;
return allocp-n; // old pointer
}
else {return 0;} // null pointer
}
void afree(char *p) // free storage pointed to by p
{
if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
{allocp = p;}
}

void writelines (char *lineptr[], int nlines, char *filename) // write output lines
{
FILE *f = fopen(filename, "w"); // open for writing

while (nlines-- > 0)
{fprintf(f, "%s", *lineptr++);}

fclose(f);
}

void swap(void *v[], int i, int j); // interchange v[i], v[j]

// sort v[left] ... v[right]
void qSort(void *v[], int left, int right, // qsort() is declared in stdlib.h
int (*comp)(void*, void*)) // comparison function,
{ // lexicographic or numeric
int i, last;

if (left >= right) // do nothing if array contains fewer than 2 elements
{return;} // stopping condition for recursion

swap(v, left, (left + right) / 2); // move partition element to v[left]
last = left; // start moving elements to last position
for (i = left + 1; i <= right; i++)
{
if (comp(v[i], v[left]) < 0) // v[i] < v[left]
{swap(v, ++last, i);} // smaller to the left, bigger to the right
}

swap(v, left, last); // return partition element to the middle position
qSort(v, left, last-1, comp); // sort smaller elements
qSort(v, last+1, right, comp); // sort bigger elements
}

#include <ctype.h> // for isalpha(), isupper(), islower()

int strfcmp(char *s1, char *s2) // case insensitive comparison
{ // (fold uppercase and lowercase together)
int i1, i2;
for ( ; *s1 && *s2; s1++, s2++) // (*s1 != '\0') && (*s2 != '\0')
{
if (*s1 != *s2)
{
if (isalpha(*s1) && isalpha(*s2))
{
if (isupper(*s1) && isupper(*s2) || islower(*s1) && islower(*s2))
{return *s1 - *s2;}
i1 = *s1 - (isupper(*s1) ? 'A' : 'a'); // here one of *s1, *s2 is upper,
i2 = *s2 - (isupper(*s2) ? 'A' : 'a'); // the other is lower
if (i1 != i2) {return i1 - i2;} // else continue;
}
else {return *s1 - *s2;}
} // else continue;
} // *s1 == '\0', *s2 == '\0', or both
return *s1 - *s2;
}

void swap(void *v[], int i, int j) // interchange v[i], v[j]
{
void *temp;

temp = v[i]; // swap pointers
v[i] = v[j];
v[j] = temp;
}

/*
gcc flines.c -o flines
./flines < me.txt // created file "lexsort.txt"

./flines f
Usage : ./flines -f
optional argument "-f" - case insensitive sort
(fold uppercase and lowercase together)

./flines -c
Illegal option: 'c'
Usage : ./flines -f
optional argument "-f" - case insensitive sort
(fold uppercase and lowercase together)

./flines -fc
Illegal option: 'c'
Usage : ./flines -f
optional argument "-f" - case insensitive sort
(fold uppercase and lowercase together)

./flines -f < me.txt // created file "fsorted.txt"

./flines -f -f -ff < me.txt // created file "fsorted.txt"

rm sorted.txt fsorted.txt // clean
*/

Notes:

For the contents of text file me.txt see Martin_Eden on Project_Gutenberg.
Redefine MAXLINES and MAXLEN if you use other input file.

---

---

Chapter_5     Exercise_5-14

BACK_TO_TOP

Exercise_5-16