Exercise 5-14 (rlines - Sort in reverse order)

Chapter_5     Exercise_5-13     numcmp

Exercise_5-15

---

---

Exercise 5-14     K&R, p. 121

Exercise 5-14. Modify the sort program to handle a -r flag, which indicates sorting in reverse (decreasing) order. Be sure that -r works with -n.

rlines.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
#define MAXFNLEN 100 // max file name length

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

// sort lines lexicographically or numerically, increasingly or decreasingly
void qSort(void *lineptr[], int left, int right, // qsort is declared in stdlib.h
int (*comp)(void*, void*), int reverse); // comparison function,
// lexicographic or numeric, reverse - sort order

int numcmp(char*, char*); // numeric comparison

int main(int argc, char *argv[])
{
int numeric = 0; // 1 if numeric sort
int reverse = 0; // 1 if reverse order
int c;

while (--argc > 0 && (*++argv)[0] == '-') // optional arguments
{
while (c = *++argv[0]) // -n -r -nr -rn
{
switch(c)
{
case 'n' :
numeric = 1;
break;
case 'r' :
reverse = 1;
break;
default:
printf("Illegal option: '%c'\n", c);
printf("Usage : ./nlines -n -r\n");
printf("Optional arguments:\n");
printf("\"-n\" - numeric sort\n");
printf("\"-r\" - reverse order\n");

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

if (argc) // if (argc > 0)
{
printf("Usage : ./nlines -n -r\n");
printf("Optional arguments:\n");
printf("\"-n\" - numeric sort\n");
printf("\"-r\" - reverse order\n");

return 1; // end program, signalling error
}

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

char filename[100];
if (numeric && reverse)
{strcpy(filename,"numrevsort.txt");}
else if (numeric)
{strcpy(filename,"numsort.txt");}
else if (reverse)
{strcpy(filename,"revsort.txt");}
else {strcpy(filename,"lexsort.txt");}

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

writelines(lineptr, nlines, filename);
}
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] lexicographically or numerically, increasingly or decreasingly
void qSort(void *v[], int left, int right, // qsort() is declared in stdlib.h
int (*comp)(void*, void*), int reverse) // comparison function,
{ // lexicographic or numeric, reverse - sort order
int i, last;
int cmp; // comparison result

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++)
{
cmp = comp(v[i], v[left]);
if ((cmp < 0 && !reverse) || (cmp > 0 && reverse)) // v[i] < v[left], v[i] > v[left]
{swap(v, ++last, i);} // smaller (bigger) to the left, bigger (smaller) to the right
}

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

#include <stdlib.h> // for atof()

int numcmp(char *s1, char *s2) // numeric comparison
{
double v1, v2;

v1 = atof(s1);
v2 = atof(s2);

if (v1 < v2) {return -1;}
if (v1 > v2) {return 1;}
return 0;
// return (int)(v1-v2); may not work because of truncation
}

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 rlines.c -o rlines
./rlines < me.txt // created file "lexsort.txt"

./rlines n
Usage : ./nlines -n -r
Optional arguments:
"-n" - numeric sort
"-r" - reverse order

./rlines -c
Illegal option: 'c'
Usage : ./nlines -n -r
Optional arguments:
"-n" - numeric sort
"-r" - reverse order

./rlines -nrc
Illegal option: 'c'
Usage : ./nlines -n -r
Optional arguments:
"-n" - numeric sort
"-r" - reverse order

./rlines -n < me.txt // created file "numsort.txt"

./rlines -r < me.txt // created file "revsort.txt"

./rlines -nr < me.txt // created file "numrevsort.txt"

./rlines -n -r -nr < me.txt // created file "numrevsort.txt"

rm *sort.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-13     numcmp

BACK_TO_TOP

Exercise_5-15