ch5-numcmp (Numeric comparison, lines)

Chapter_5     Exercise_5-13

Exercise_5-14

---

---

Note:  See also Exercise_5-7.

nlines.c     K&R, p. 108-110, 119-121         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);

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

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

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

while (--argc > 0 && (*++argv)[0] == '-') // optional argument
{
while (c = *++argv[0]) // -n, -n -n, -nn, etc.
{
switch(c)
{
case 'n' :
numeric = 1;
break;
default:
(*printf)("Illegal option: '%c'\n", c);
printf("Usage : ./nlines -n\n");
printf("optional argument \"-n\" - numeric sort\n");
// (*printf)(""); // alternative function call
return 1; // end program, signalling error
}
}
}

if (argc) // if (argc > 0)
{
printf("Usage : ./nlines -n\n");
printf("optional argument \"-n\" - numeric sort\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,
(numeric ? (int (*)(void*, void*))numcmp : (int (*)(void*, void*))strcmp));

writelines(lineptr, nlines, (numeric ? "numsort.txt" : "lexsort.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] lexicographically or numerically into increasing order
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++)
{ // (*comp)(v[i], v[left])
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 <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 nlines.c -o nlines
./nlines < me.txt // created file "lexsort.txt"

./nlines n
Usage : ./nlines -n
optional argument "-n" - numeric sort

./nlines -c
Illegal option: 'c'
Usage : ./nlines -n
optional argument "-n" - numeric sort

./nlines -nc
Illegal option: 'c'
Usage : ./nlines -n
optional argument "-n" - numeric sort

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

./nlines -n -n -nn < me.txt // created file "numsort.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.
getLine() should return after reading '\n' or EOF (upon reaching the end of file), otherwise it may need ungetch(), see Chapter_4, Sec. 4.3.
I changed the quotation marks in me.txt to their corresponding ASCII equivalents, ', ".

---

---

Chapter_5     Exercise_5-13

BACK_TO_TOP

Exercise_5-14