#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
*/
Redefine MAXLINES and MAXLEN if you use other input file.
getLine() should return after reading '\n' or EOF, otherwise it may need ungetch(), see Section ch4-Calculator in Chapter_4.
I changed the quotation marks in me.txt to their corresponding ASCII equivalents, ', ".
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
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.
#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
*/
Redefine MAXLINES and MAXLEN if you use other input file.
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
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.
#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
*/
Redefine MAXLINES and MAXLEN if you use other input file.
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
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.
#include <stdio.h> // for getchar(), printf(), EOF, NULL, FILE, fopen(), fclose()
#include <string.h> // for strcat(), 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);
void qSort(void *lineptr[], int left, int right, // qsort() is declared in stdlib.h
int (*comp)(void*, void*)); // comparison function,
// strcmp(), strfcmp(), strdcmp(), or strfdcmp()
int strfcmp(char*, char*); // case insensitive comparison (fold upper and lowercase)
int strdcmp(char*, char*); // directory order comparison
int strfdcmp(char*, char*); // case insensitive, directory order
int main(int argc, char *argv[])
{
int ci = 0; // 1 if case insensitive sort
int dirord = 0; // 1 if directory order sort
int c;
while (--argc > 0 && (*++argv)[0] == '-') // optional arguments
{
while (c = *++argv[0]) // -f, -d, -f -d, -df, -fdf, etc.
{
switch(c)
{
case 'f' :
ci = 1;
break;
case 'd' :
dirord = 1;
break;
default:
printf("Illegal option: '%c'\n", c);
printf("Usage : ./dlines -f -d\n");
printf("Optional arguments:\n");
printf("\"-f\" - case insensitive sort (fold upper and lowercase)\n");
printf("\"-d\" - directory order sort (letters, numbers, blanks)\n");
return 1; // end program, signalling error
}
}
}
if (argc) // if (argc > 0)
{
printf("Usage : ./dlines -f -d\n");
printf("Optional arguments:\n");
printf("\"-f\" - case insensitive sort (fold upper and lowercase)\n");
printf("\"-d\" - directory order sort (letters, numbers, blanks)\n");
return 1; // end program, signalling error
}
char *lineptr[MAXLINES];
int nlines; // no of input lines read
char filename[MAXFNLEN];
int i = 0;
if (ci) // case insensitive sort
{filename[i++] = 'f';}
if (dirord) // directory order sort
{filename[i++] = 'd';}
filename[i] = '\0';
strcat(filename, "sort.txt");
int (*comp)(void*, void*);
if ((nlines = readlines(lineptr, MAXLINES)) >= 0)
{// casts are necessary to avoid error or warning of pointer type mismatch:
if (ci && dirord) // case insensitive, directory order
{comp = (int (*)(void*, void*))strfdcmp;}
else if (ci)
{comp = (int (*)(void*, void*))strfcmp;}
else if (dirord)
{comp = (int (*)(void*, void*))strdcmp;}
else {comp = (int (*)(void*, void*))strcmp;}
{qSort((void**)lineptr, 0, nlines-1, comp);}
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]
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(), isalnum(), isdigit()
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;
}
int strdcmp(char *s1, char *s2) // directory order comparison
{
for ( ; *s1 && *s2; s1++, s2++) // (*s1 != '\0') && (*s2 != '\0')
{ // compare only letters, numbers, blanks
while (*s1 && *s1 != ' ' && !isalnum(*s1)) {s1++;}
while (*s2 && *s2 != ' ' && !isalnum(*s2)) {s2++;}
if (*s1 != *s2)
{ // space is ASCII 32 < digits, letters (alphanumeric)
return *s1 - *s2;
} // else continue;
}
return *s1 - *s2; // *s1 == '\0', *s2 == '\0', or both
}
int strfdcmp(char *s1, char *s2) // case insensitive, directory order
{
int i1, i2;
for ( ; *s1 && *s2; s1++, s2++) // (*s1 != '\0') && (*s2 != '\0')
{ // compare only letters, numbers, blanks
while (*s1 && *s1 != ' ' && !isalnum(*s1)) {s1++;}
while (*s2 && *s2 != ' ' && !isalnum(*s2)) {s2++;}
if (*s1 != *s2)
{ // space is ASCII 32 < digits, letters (alphanumeric)
if (!isalpha(*s1) || !isalpha(*s2) ||
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 continue;
}
return *s1 - *s2; // *s1 == '\0', *s2 == '\0', or both
}
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 dlines.c -o dlines
./dlines < me.txt // created file "sort.txt"
./dlines f
Usage : ./dlines -f -d
Optional arguments:
"-f" - case insensitive sort (fold upper and lowercase)
"-d" - directory order sort (letters, numbers, blanks)
./dlines -c
Illegal option: 'c'
Usage : ./dlines -f -d
Optional arguments:
"-f" - case insensitive sort (fold upper and lowercase)
"-d" - directory order sort (letters, numbers, blanks)
./dlines -fdc
Illegal option: 'c'
Usage : ./dlines -f -d
Optional arguments:
"-f" - case insensitive sort (fold upper and lowercase)
"-d" - directory order sort (letters, numbers, blanks)
./dlines -f < me.txt // created file "fsort.txt"
./dlines -d < me.txt // created file "dsort.txt"
./dlines -f -d -df < me.txt // created file "fdsort.txt"
rm *sort.txt // clean
*/
Redefine MAXLINES and MAXLEN if you use other input file.
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
Exercise 5-17. Add a field-handling capability, so sorting may be done on fields within lines, each field sorted according to an independent set of options. (The index for this book was sorted with -df for the index category and -n for the page numbers.)
call by value 95
command-line arguments 116
<< left shift operator 206
a.out 6
< less than operator 41
alloc function 101
a.out 70
<< left shift operator 49
call by reference 27
command-line arguments 118
<ctype.h> header 248
temperature conversion program 12
command-line arguments 114
<= less or equal operator 206
increment operator, ++ 203
temperature conversion program 9
default label 222
definition, function 69
pointer to function 201
#define, multi-line 89
call by value 202
++ increment operator 18
command-line arguments 115
call by value 27
\t tab character 193
++ increment operator 46
UNIX file system 169
++ increment operator 203
definition, function 25
< less than operator 206
#define with arguments 89
<ctype.h> header 43
increment operator, ++ 106
pointer, null 102
temperature conversion program 13
definition, function 225
pointer to function 118
increment operator, ++ 18
\t tab character 11
default label 58
increment operator, ++ 46
less than operator, < 206
pointer initialization 102
left shift operator, << 206
temperature conversion program 8
less than operator, < 41
pointer initialization 138
command-line arguments 117
++ increment operator 106
pointer to function 147
pointer, null 198
\t tab character 38
temperature conversion program 15
UNIX file system 179
\t tab character 8
<= less or equal operator 41
left shift operator, << 49
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for getchar(), printf(), EOF, NULL, FILE, fopen(), fclose()
#include <string.h> // for strcat(), strcpy(), strcmp()
#include <ctype.h> // for isdigit(), isalpha(), isupper(), islower(), isalnum()
#define MAXLINES 5000 // max no of lines to be sorted
#define MAXLEN 1000 // max line length
#define MAXFNLEN 100 // max file name length
void initField(int *field, int c, char **s);
void printUsage(void);
int readlines (char *lineptr[], int nlines);
void writelines (char *lineptr[], int nlines, char *filename);
int strfcmp(char*, char*); // case insensitive (fold upper and lowercase)
int strdcmp(char*, char*); // directory order comparison
int strfdcmp(char*, char*); // case insensitive, directory order
int numcmp(char*, char*); // numeric comparison
void qSort1(void *lineptr[], int left, int right, // qsort() is declared in stdlib.h
int (*comp)(void*, void*)); // comparison function,
// strcmp(), strfcmp(), strdcmp(), strfdcmp(), or numcmp()
void qSort2(void *lineptr[], int left, int right, int *fields,
int (*lexComp)(void*, void*), int (*numComp)(void*, void*));
// lexComp() can be strcmp(), strfcmp(), strdcmp(), or strfdcmp()
// numComp() can be numcmp() or NULL
// first do lexicographic sort, then numeric sort on 'equal' lex compared lines
// if (strcmp(line1) == strcmp(line2)), perform numeric sort on a field
int main(int argc, char *argv[])
{ // sorting can be generalized to n fields
int fields[] = {0, 0}; // fields has size 2 (lexicographic and numeric)
// lexicographic sort: strcmp(), strfcmp(), strdcmp(), strfdcmp()
// fields within each line, delimited by ' ' and '\t',
// null fields means regular sort
int orders[3] = {0}; // alternative initialization
// orders: fold (case insensitive), directory, numeric
int c;
while (--argc > 0 && (*++argv)[0] == '-') // optional arguments
{
while (c = *++argv[0]) // -f -d1 -n-1, -f+0 -d -n-1, -fd1, -n2, etc.
{
switch(c)
{
case 'f' :
orders[0] = 1; // case insensitive (fold) order
initField(fields, c, argv); // &fields[0]
break;
case 'd' :
orders[1] = 1; // directory order
initField(fields, c, argv); // &fields[0]
break;
case 'n' :
orders[2] = 1; // numeric order
initField(fields+1, c, argv); // &fields[1]
break;
default:
printf("Illegal option: '%c'\n", c);
printUsage();
return 1; // end program, signalling error
}
}
}
if (argc) // if (argc > 0)
{
printUsage();
return 1; // end program, signalling error
}
if (orders[2] && !fields[1] && // numeric for the entire line
(orders[0] || orders[1]) && !fields[0]) // fold or dir or both for the entire line
{
printf("\"-f\", \"-d\" work together, but not with \"-n\"\n");
printUsage();
return 1; // end program, signalling error
}
if (fields[1] && (fields[0] == fields[1])) // fields[0] == fields[1] > 0
{ // fields[1] > 0 implies orders[2] >0,
// fields[0] > 0 implies (orders[0] || orders[1]) > 0
printf("\"-f\", \"-d\" cannot overlap with \"-n\" over the same field\n");
printUsage();
return 1; // end program, signalling error
}
char *lineptr[MAXLINES];
int nlines; // no of input lines read
char filename[MAXFNLEN];
int i = 0;
if (orders[0]) // case insensitive sort
{filename[i++] = 'f';}
if (orders[1]) // directory order sort
{filename[i++] = 'd';}
if (orders[2]) // numeric sort
{filename[i++] = 'n';}
filename[i] = '\0';
strcat(filename, "sort.txt");
int (*comp)(void*, void*);
int (*lexComp)(void*, void*), (*numComp)(void*, void*) = NULL;
if ((nlines = readlines(lineptr, MAXLINES)) >= 0)
{
if (fields[0] == 0 && fields[1] == 0) // regular sort:
{ // lexicographic or numeric sort for the entire line
if (orders[0] && orders[1]) // case insensitive, directory order
{comp = (int (*)(void*, void*))strfdcmp;}
else if (orders[0]) // case insensitive (fold)
{comp = (int (*)(void*, void*))strfcmp;}
else if (orders[1]) // directory order
{comp = (int (*)(void*, void*))strdcmp;}
else if (orders[2]) // numeric order
{comp = (int (*)(void*, void*))numcmp;}
else {comp = (int (*)(void*, void*))strcmp;}
qSort1((void**)lineptr, 0, nlines-1, comp);
}
else
{
if (orders[0] && orders[1]) // case insensitive, directory order
{lexComp = (int (*)(void*, void*))strfdcmp;}
else if (orders[0]) // case insensitive (fold)
{lexComp = (int (*)(void*, void*))strfcmp;}
else if (orders[1]) // directory order
{lexComp = (int (*)(void*, void*))strdcmp;}
else {lexComp = (int (*)(void*, void*))strcmp;}
if (orders[2]) // numeric order
{numComp = (int (*)(void*, void*))numcmp;}
qSort2((void**)lineptr, 0, nlines-1, fields, lexComp, numComp);
}
writelines(lineptr, nlines, filename);
}
else
{
printf("Error: input too big to sort\n");
return 1; // exit program, signalling error
}
return 0;
}
void initField(int *field, int c, char **s)
{
c = *++s[0];
if (c == '\0')
{
--s[0]; // ungetch()
return;
}
if (c != '+' && c != '-' && !isdigit(c))
{
--s[0]; // ungetch()
return;
}
int sign = 1;
if (c == '-') {sign = -1; c = *++s[0];}
else if (c == '+') {c = *++s[0];} // move past sign
if (!isdigit(c))
{
--s[0]; // ungetch()
return;
}
*field = 0; // *field may have been set before
while (isdigit(c))
{
*field = *field * 10 + (c - '0');
c = *++s[0];
}
*field *= sign;
--s[0]; // ungetch()
}
void printUsage(void)
{
printf("Usage : ./lines [-f field1] [-d field1] [-n field2]\n");
printf("Examples: ./lines -f+0 -d -n-1, ./lines -fd1 -n2\n");
printf("Optional arguments (field1 != field2):\n");
printf("\"-f\" - case insensitive sort (fold upper and lowercase)\n");
printf("\"-d\" - directory order sort (letters, numbers, blanks)\n");
printf("\"-n\" - numeric sort for lines or numbers within lines\n");
printf("field - integer, sort by a field (word) within each line\n");
printf("field > 0 - from the beginning of each line\n");
printf("field < 0 - from the end of each line\n");
printf("field = 0 or missing - sort (the rest of) each line\n");
}
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] in increasing order
void qSort1(void *v[], int left, int right, int (*comp)(void*, void*))
{// qsort() is declared in stdlib.h
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
qSort1(v, left, last-1, comp); // sort smaller elements
qSort1(v, last+1, right, comp); // sort bigger elements
}
// extract substrings from str based on fields
void subStr(char *str, char *substr1, char *substr2, int *fields);
// sort v[left] ... v[right] in increasing order
void qSort2(void *v[], int left, int right, int *fields,
int (*lexComp)(void*, void*), int (*numComp)(void*, void*))
{ // lexComp() can be strcmp(), strfcmp(), strdcmp(), or strfdcmp()
int i, last; // numComp() can be numcmp() or NULL
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
int c; // comparison result
char sub1[MAXLEN], sub2[MAXLEN]; // allocate space for substrings
char subL1[MAXLEN], subL2[MAXLEN]; // substrings of v[i], v[left]
for (i = left + 1; i <= right; i++)
{
subStr(v[i], sub1, sub2, fields);
subStr(v[left], subL1, subL2, fields);
c = lexComp(sub1, subL1);
if (c < 0) // sub1 < subL1
{swap(v, ++last, i);} // smaller to the left, bigger to the right
else if (c == 0 && numComp != NULL) // sub1 == subL1, numcmp
{
c = numComp(sub2, subL2); // numcmp(sub2, subL2)
if (c < 0) // sub2 < subL2
{swap(v, ++last, i);} // smaller to the left, bigger to the right
}
}
swap(v, left, last); // return partition element to the middle position
qSort2(v, left, last-1, fields, lexComp, numComp); // sort smaller elements
qSort2(v, last+1, right, fields, lexComp, numComp); // sort bigger elements
}
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;
}
#include <stdlib.h> // for abs(), atof()
// extract substrings from str based on fields
void subStr(char *str, char *substr1, char *substr2, int *fields)
{ // fields[0] != fields[1] >= 0, words separated by ' ', '\t'
char copy[MAXLEN]; // used by strtok()
strcpy(copy, str); // save str, strtok() destroys copy[]
char sep[] = " \t"; // {' ', '\t', '\0'} // separators
char *token = strtok(copy, sep);
if (token == NULL) // empty line
{
substr1[0] = '\0';
substr2[0] = '\0';
return;
}
// here token != NULL
char *tokens[MAXLEN];
int i = 0;
while (token != NULL)
{
tokens[i++] = token;
token = strtok(NULL, sep);
}
// i holds the length of tokens[] (no of tokens)
if (abs(fields[0]) > i) // field[0] greater than no of words
{
substr1[0] = '\0';
if (abs(fields[1]) > i) // field[1] greater than no of words
{
substr2[0] = '\0';
return;
} // here abs(fields[1]) <= i
if (fields[1] == 0) // hold the (rest of the) line
{
strcpy(substr2, str);
} // here fields[1] != 0
else if (fields[1] > 0)
{strcpy(substr2, tokens[fields[1]-1]);}
else // fields[1] < 0
{strcpy(substr2, tokens[i+fields[1]]);} // i-abs(fields[1])
return;
} // here abs(fields[0]) <= i
if (abs(fields[1]) > i) // field[1] greater than no of words
{
substr2[0] = '\0';
if (fields[0] == 0) // hold the (rest of the) line
{
strcpy(substr1, str);
} // here fields[0] != 0
else if (fields[0] > 0)
{strcpy(substr1, tokens[fields[0]-1]);}
else // fields[0] < 0
{strcpy(substr1, tokens[i+fields[0]]);} // i-abs(fields[0])
return;
}
// here abs(fields[0]) <= i, abs(fields[1]) <= i
int j, index;
if (fields[0] == 0) // fields[1] != 0
{ // numeric sort for one part, lexicographic for the rest of string
if (fields[1] > 0)
{index = fields[1]-1;}
else // fields[1] < 0
{index = i+fields[1];} // i-abs(fields[1])
strcpy(substr2, tokens[index]);
substr1[0] = '\0';
for (j = 0; j < i; j++)
{
if (j != index)
{
strcat(substr1, tokens[j]); // tokens do not contain delimiters ' ', '\t'
if (j < i-1) {strcat(substr1," ");} // space necessary for directory order
}
}
}
else if (fields[1] == 0) // fields[0] != 0
{ // lexicographic sort for one part, numeric for the rest of string
if (fields[0] > 0)
{index = fields[0]-1;}
else // fields[0] < 0
{index = i+fields[0];} // i-abs(fields[0])
strcpy(substr1, tokens[index]);
substr2[0] = '\0';
for (j = 0; j < i; j++)
{
if (j != index)
{
strcat(substr2, tokens[j]); // tokens do not contain delimiters ' ', '\t'
if (j < i-1) {strcat(substr2," ");} // space necessary for directory order
}
}
}
else // (fields[0] != 0) != (fields[1] != 0)
{ // lexicographic and numeric sort each for one part of the string
if (fields[0] > 0)
{strcpy(substr1, tokens[fields[0]-1]);}
else // fields[0] < 0
{strcpy(substr1, tokens[i+fields[0]]);} // i-abs(fields[0])
if (fields[1] > 0)
{strcpy(substr2, tokens[fields[1]-1]);}
else // fields[1] < 0
{strcpy(substr2, tokens[i+fields[1]]);} // i-abs(fields[1])
}
}
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;
}
return *s1 - *s2; // *s1 == '\0', *s2 == '\0', or both
}
int strdcmp(char *s1, char *s2) // directory order comparison
{
for ( ; *s1 && *s2; s1++, s2++) // (*s1 != '\0') && (*s2 != '\0')
{ // compare only letters, numbers, blanks
while (*s1 && *s1 != ' ' && !isalnum(*s1)) {s1++;}
while (*s2 && *s2 != ' ' && !isalnum(*s2)) {s2++;}
if (*s1 != *s2)
{ // space is ASCII 32 < digits, letters (alphanumeric)
return *s1 - *s2;
} // else continue;
}
return *s1 - *s2; // *s1 == '\0', *s2 == '\0', or both
}
int strfdcmp(char *s1, char *s2) // case insensitive, directory order
{
int i1, i2;
for ( ; *s1 && *s2; s1++, s2++) // (*s1 != '\0') && (*s2 != '\0')
{ // compare only letters, numbers, blanks
while (*s1 && *s1 != ' ' && !isalnum(*s1)) {s1++;}
while (*s2 && *s2 != ' ' && !isalnum(*s2)) {s2++;}
if (*s1 != *s2)
{ // space is ASCII 32 < digits, letters (alphanumeric)
if (!isalpha(*s1) || !isalpha(*s2) ||
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 continue;
}
return *s1 - *s2; // *s1 == '\0', *s2 == '\0', or both
}
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
}
/*
gcc lines.c -o lines
./lines < unsorted.txt // created file "sort.txt"
./lines f
Usage : ./lines [-f field1] [-d field1] [-n field2]
Examples: ./lines -f+0 -d -n-1, ./lines -fd1 -n2
Optional arguments (field1 != field2):
"-f" - case insensitive sort (fold upper and lowercase)
"-d" - directory order sort (letters, numbers, blanks)
"-n" - numeric sort for lines or numbers within lines
field - integer, sort by a field (word) within each line
field > 0 - from the beginning of each line
field < 0 - from the end of each line
field = 0 or missing - sort (the rest of) each line
./lines -c
Illegal option: 'c'
Usage : ./lines [-f field1] [-d field1] [-n field2]
...
./lines -fdc
Illegal option: 'c'
Usage : ./lines [-f field1] [-d field1] [-n field2]
...
./lines -f < unsorted.txt // created file "fsort.txt"
./lines -d < unsorted.txt // created file "dsort.txt"
./lines -f -d -df < unsorted.txt // created file "fdsort.txt"
./lines -n < unsorted.txt // created file "nsort.txt"
./lines -f -d -n
"-f", "-d" work together, but not with "-n"
Usage : ./lines [-f field1] [-d field1] [-n field2]
...
./lines -fd1 -n1
"-f", "-d" cannot overlap with "-n" over the same field
Usage : ./lines [-f field1] [-d field1] [-n field2]
...
./lines -n-1 < unsorted.txt // created file "nsort.txt"
// strings are sorted lexicographically, numbers are sorted numerically
./lines -f -n-1 < unsorted.txt // created file "fnsort.txt"
// case insensitive sort for strings
./lines -d -n-1 < unsorted.txt // created file "dnsort.txt"
// directory order sort for strings
./lines -df -n-1 < unsorted.txt // created file "fdnsort.txt"
./lines -fd0 -n-1 < unsorted.txt // created file "fdnsort.txt"
// case insensitive, directory order sort for strings
rm *sort.txt // clean
*/
File fdnsort.txt looks almost like an index.
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
++ increment operator 18
++ increment operator 46
++ increment operator 106
++ increment operator 203
<< left shift operator 49
<< left shift operator 206
<= less or equal operator 41
<= less or equal operator 206
< less than operator 41
< less than operator 206
alloc function 101
a.out 6
a.out 70
call by reference 27
call by value 27
call by value 95
call by value 202
command-line arguments 114
command-line arguments 115
command-line arguments 116
command-line arguments 117
command-line arguments 118
<ctype.h> header 43
<ctype.h> header 248
default label 58
default label 222
#define, multi-line 89
#define with arguments 89
definition, function 25
definition, function 69
definition, function 225
increment operator, ++ 18
increment operator, ++ 46
increment operator, ++ 106
increment operator, ++ 203
left shift operator, << 49
left shift operator, << 206
less than operator, < 41
less than operator, < 206
pointer initialization 102
pointer initialization 138
pointer, null 102
pointer, null 198
pointer to function 118
pointer to function 147
pointer to function 201
\t tab character 8
\t tab character 11
\t tab character 38
\t tab character 193
temperature conversion program 8
temperature conversion program 9
temperature conversion program 12
temperature conversion program 13
temperature conversion program 15
UNIX file system 169
UNIX file system 179
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for getchar(), printf(), EOF, NULL, FILE, fopen(), fclose()
#include <string.h> // for strcmp(), strcat(), strcpy(), strlen()
#define MAXLINES 5000 // max no of lines to be sorted
#define MAXLEN 1000 // max line length
#define MAXFNLEN 100 // max file name length
#define MAXNODIG 15 // max no of digits of a page number
#define MAXPGNOS 1000 // max no of page numbers for an index entry
int readlines (char *lineptr[], int nlines);
unsigned getPgNo(char *); // read a line, return page number
int utoa (unsigned , char *); // unsigned to string, return length
void writelines (char lines[][MAXLEN], int nlines, char *filename);
int main()
{
char *lineptr[MAXLINES];
int nlines; // no of input lines read
char indexLines[MAXLINES][MAXLEN];
char number[MAXNODIG];
int i, j, k, pgnos; // no of page numbers read from lines
unsigned numbers[MAXPGNOS];
int indLines; // index lines
if ((nlines = readlines(lineptr, MAXLINES)) >= 0)
{
i = 0;
indLines = 0; // index of the first index line
// if nlines == 1, there is only one line, which needs no processing
while (i < nlines-1)
{ // there are at least two lines left
if (i > 0) // not the first iteration
{ // ungetch()
numbers[0] = numbers[pgnos];
pgnos = 1, i++;
numbers[pgnos] = getPgNo(lineptr[i]);
}
else // first iteration, i == 0
{
pgnos = 0;
numbers[pgnos] = getPgNo(lineptr[i]);
strcpy(indexLines[indLines], lineptr[i]); // first index line
pgnos++, i++;
numbers[pgnos] = getPgNo(lineptr[i]);
}
while (i < nlines && strcmp(lineptr[i], indexLines[indLines]) == 0)
{
++pgnos, ++i;
if (i < nlines)
{numbers[pgnos] = getPgNo(lineptr[i]);}
}
// pgnos holds no of 'equal' lines
for (j = 0; j < pgnos; j++)
{
if (j == pgnos-1) // last page number
{
if (pgnos > 1)
{strcat(indexLines[indLines], ", ");}
else {strcat(indexLines[indLines], " ");} // 2 spaces after string
utoa(numbers[j], number);
strcat(indexLines[indLines], number);
break; // out of for()
}
k = j;
while (numbers[j+1]-numbers[j] == 1)
{
j++;
if (j == pgnos-1)
{break;} // out of while()
}
if (k > 0)
{strcat(indexLines[indLines], ", ");}
else {strcat(indexLines[indLines], " ");} // 2 spaces after string
utoa(numbers[k], number);
strcat(indexLines[indLines], number);
if (j > k) // at least two consecutive numbers
{
strcat(indexLines[indLines], "-"); // or dash
utoa(numbers[j], number);
strcat(indexLines[indLines], number);
}
}
strcat(indexLines[indLines], "\n");
indLines++; // no of index lines 'read' so far
if (i < nlines) // there are unprocessed lines
{
strcpy(indexLines[indLines], lineptr[i]); // last processed line
if (i == nlines - 1) // last line
{ // rebuild processed line
strcat(indexLines[indLines], " "); // 2 spaces after string
utoa(numbers[pgnos], number);
strcat(indexLines[indLines], number);
strcat(indexLines[indLines], "\n");
indLines++; // no of index lines
i++; // end while()
}
}
}
writelines(indexLines, indLines, "index.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*2]; // index entry,
// substring followed by a sequence of page numbers
nlines = 0;
while ((len = getLine(line, MAXLEN)) > 0)
{ // allocate enough space for an index entry
if (line[0] == '\n') // do not add empty lines
{continue;} // go to the next iteration of while()
if(nlines >= maxlines || (p = alloc(len + 1)) == NULL)
{return -1;} // (+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;}
}
#include <ctype.h> // for isdigit()
void reverse(char *s, int len); // reverse string s, knowing its length
unsigned atou(char *s);// string to unsigned
unsigned getPgNo(char *str) // read a line, return page number
{
int len = 0;
char pgno[MAXNODIG];
char *p = str+strlen(str)-1; // last char of str before '\0'
if (*p == '\n') {p--;} // last char of str before '\n'
while (isdigit(*p))
{
pgno[len++] = *p;
p--;
}
pgno[len] = '\0'; // end string
*p = '\0'; // shrink str to contain only a string
reverse(pgno, len); // page number
return atou(pgno);
}
void reverse(char *s, int len) // reverse string s, knowing its length
{
char *start = s, *end = s+len-1;
char temp;
while (start < end)
{
temp = *start;
*start++ = *end;
*end-- = temp;
}
}
// string to unsigned
unsigned atou(char *s)
{
unsigned n = 0; // number
while (*s != '\0' && isdigit(*s))
{
n = n * 10 + (*s - '0');
s++;
}
return n;
}
int utoa (unsigned n, char *s) // unsigned to string
{
char *p = s;
do
{ // get the digits in reverse order:
*p++ = n % 10 + '0'; // get next (last read) digit
} while (n /= 10); // while ((n /= 10) != 0); // delete last digit
*p = '\0'; // end the string
reverse(s, p-s);
return p-s;
}
// write output lines
void writelines (char lines[][MAXLEN], int nlines, char *filename)
{
FILE *f = fopen(filename, "w"); // open for writing
while (nlines-- > 0)
{fprintf(f, "%s", *lines++);}
fclose(f);
}
/*
gcc index.c -o index
./index < fdnsort.txt // created file "index.txt"
meld fdnsort.txt index.txt // compare files
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
++ increment operator 18, 46, 106, 203
<< left shift operator 49, 206
<= less or equal operator 41, 206
< less than operator 41, 206
alloc function 101
a.out 6, 70
call by reference 27
call by value 27, 95, 202
command-line arguments 114-118
<ctype.h> header 43, 248
default label 58, 222
#define, multi-line 89
#define with arguments 89
definition, function 25, 69, 225
increment operator, ++ 18, 46, 106, 203
left shift operator, << 49, 206
less than operator, < 41, 206
pointer initialization 102, 138
pointer, null 102, 198
pointer to function 118, 147, 201
\t tab character 8, 11, 38, 193
temperature conversion program 8-9, 12-13, 15
UNIX file system 169, 179