/* EXERCISE 5-17 */
/* NOTE: CHANGED THE NAME OF THE SORTING ROUTINE TO QKSORT IN ORDER */
/* NOT TO CONFLICT WITH <stdlib.h>. */
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAXLINES 20 /* MAX #LINES TO BE SORTED */
#define MAXBUF 2200 /* LENGTH OF LINES BUFFER */
#define MAXLVL 10 /* MAX #SORT LEVELS */
int numeric[MAXLVL]; /* 1 FOR NUMERIC SORT */
int decrease[MAXLVL]; /* 1 FOR DECREASING SORT */
int fold[MAXLVL]; /* 1 FOR ALPHA CASE INSENSITIVE */
int direct[MAXLVL]; /* 1 FOR DIRECTORY ORDER */
int start_col[MAXLVL]; /* STARTING SORT COLUMN */
int end_col[MAXLVL]; /* ENDING SORT COLUMN */
int keylen[MAXLVL]; /* KEY LENGTH */
int has_fold = 0; /* 1 FOR ALPHA CASE INSENSITIVE KEY */
int has_direct = 0; /* 1 FOR DIRECTORY ORDER KEY */
int field_sort = 0; /* 1 FOR SORT ON KEY FIELDS */
int sortlvl = 0; /* # SORT LEVELS */
int minlen = 0; /* MINIMUM REQUIRED LINE LENGTH */
int rev; /* REVERSE FACTOR */
int readlines(char *[], char *, int);
void conv_lines(char **, char ***, int, char *);
int numcmp(char *, char *);
int keycmp(char *, char *);
void writelines(char **[], int);
void qksort(void *[], int, int, int (*)(void *, void *));
int edit_args(int, char *[]);
/* SORT INPUT LINES */
main(int argc, char *argv[])
{
int nlines; /* NUMBER OF INPUT LINES READ */
char linebuf[MAXBUF]; /* PREALLOCATED STORAGE FOR LINES */
char textbuf[MAXBUF]; /* STORAGE FOR CONVERTED LINES */
char *lineptr[2 * MAXLINES]; /* POINTERS TO TEXT LINES */
char **sortptr[MAXLINES]; /* POINTERS TO LINE POINTERS */
int (*pcf)(void *, void *); /* POINTER TO COMPARISON FUNCTION */
if (edit_args(argc, argv))
return 1;
if (field_sort)
minlen += 2;
if ((nlines = readlines(lineptr, linebuf, MAXLINES)) >= 0) {
conv_lines(lineptr, sortptr, nlines, textbuf);
if (field_sort) {
rev = 1;
pcf = (int (*)(void *, void *)) keycmp;
}
else {
rev = (decrease[0] ? -1 : 1);
pcf = (int (*)(void *, void *)) (numeric[0] ? numcmp : strcmp);
}
qksort((void **) sortptr, 0, nlines-1, pcf);
printf("THE SORTED LINES ARE:\n");
writelines(sortptr, nlines);
}
else {
if (nlines == -1)
printf("ERROR: INPUT TOO BIG TO SORT\n");
else
printf("ERROR: LINE IS SHORTER THAN LAST SORT KEY POSITION\n");
return 1;
}
printf("\nEND OF PROGRAM\n");
return 0;
}
#define MAXLEN 100 /* MAX LENGTH OF ANY INPUT LINE */
int getline(char *, int);
/* READLINES: READ INPUT LINES */
int readlines(char *lineptr[], char *linebuf, int maxlines)
{
int len, nlines, bufrem = MAXBUF;
char *p, line[MAXLEN];
nlines = 0;
while ((len = getline(line, MAXLEN)) > 0) {
if (line[len-1] == '\n')
line[len-1] = '\0'; /* DELETE NEWLINE */
else
len++;
if (len < minlen)
return -2;
if (nlines >= maxlines || (bufrem -= len) < 0)
return -1;
else {
strcpy(linebuf, line);
lineptr[2 * nlines++] = linebuf;
linebuf += len;
}
}
return nlines;
}
/* GETLINE: GET LINE INTO s , RETURN LENGTH */
int getline(char *s, int lim)
{
int c;
char *s0 = s;
while (--lim > 0 && (c=getchar()) != EOF && c != '\n')
*s++ = c;
if (c == '\n')
*s++ = c;
else
if (c != EOF) /* ADVANCE TO END OF LINE */
while ((c = getchar()) != EOF && c != '\n')
;
*s = '\0';
return s - s0;
}
/* CONV_LINES: CONVERT THE INPUT LINES */
void conv_lines(char **lpp, char ***sppp, int nlines, char *tp)
{
char **lppend = lpp + 2 * nlines;
char *lp, *lpend, *tp0;
int i;
if (field_sort)
if (has_fold || has_direct)
for (; lpp < lppend; lpp += 2) {
*(lpp + 1) = tp;
*sppp++ = lpp + 1;
for (i = 0; i < sortlvl; i++) {
lp = *lpp + start_col[i];
lpend = lp + keylen[i];
tp0 = tp;
do {
if (direct[i] && !isalnum(*lp) && *lp != ' ' && *lp != '\0')
;
else
if (fold[i])
*tp++ = toupper(*lp);
else
*tp++ = *lp;
} while (++lp < lpend);
*tp = '\0';
tp = tp0 + keylen[i] + 1; /* STORE KEYS AT FIXED OFFSETS */
}
}
else /* NO CONVERSION */
for (; lpp < lppend; lpp += 2) {
*(lpp + 1) = tp;
*sppp++ = lpp + 1;
for (i = 0; i < sortlvl; i++) {
lp = *lpp + start_col[i];
lpend = lp + keylen[i];
do {
*tp++ = *lp;
} while (++lp < lpend);
*tp++ = '\0';
}
}
else
if (has_fold || has_direct)
for (; lpp < lppend; lpp += 2) {
*(lpp + 1) = tp;
*sppp++ = lpp + 1;
lp = *lpp;
do {
if (has_direct && !isalnum(*lp) && *lp != ' ' && *lp != '\0')
;
else
if (has_fold)
*tp++ = toupper(*lp);
else
*tp++ = *lp;
} while (*lp++);
}
else /* NO CONVERSION */
for (; lpp < lppend; lpp += 2) {
*(lpp + 1) = *lpp;
*sppp++ = lpp + 1;
}
}
/* WRITELINES: WRITE OUTPUT LINES */
void writelines(char **sortptr[], int nlines)
{
while (nlines-- > 0)
printf("%s\n", *(*sortptr++ - 1));
}
/* QKSORT: SORT v[left] ... v[right] INTO INCREASING ORDER */
/* THE COMPARISON MUST DEREFERENCE v[] AN EXTRA TIME */
void qksort(void *v[], int left, int right,
int (*comp)(void *, void *))
{
int i, last;
void swap(void *[], int, int);
if (left >= right) /* DO NOTHING IF ARRAY CONTAINS */
return; /* FEWER THAN TWO ELEMENTS */
swap(v, left, (left + right)/2);
last = left;
for (i = left+1; i <= right; i++) /* NOTE CAST AND EXTRA DEREF */
if (rev * (*comp)(*((char **) v[i]), *((char **) v[left])) < 0)
swap(v, ++last, i);
swap(v, left, last);
qksort(v, left, last-1, comp);
qksort(v, last+1, right, comp);
}
#include <stdlib.h>
/* 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;
}
/* KEYCMP: COMPARE s1 AND s2 BY MULTIPLE SORT KEYS */
int keycmp(char *s1, char *s2)
{
int i, val;
for (i = 0; i < sortlvl; i++) {
if (numeric[i])
val = numcmp(s1, s2);
else
val = strcmp(s1, s2);
if (val)
return (decrease[i] ? -1 * val : val);
else {
s1 += keylen[i] + 1;
s2 += keylen[i] + 1;
}
}
return 0;
}
/* SWAP: INTERCHANGE v[i] and v[j] */
void swap(void *v[], int i, int j)
{
void *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
int test_arg(char *);
/* EDIT_ARGS: EDIT THE COMMAND LINE ARGUMENTS */
int edit_args(int parms, char *argp[])
{
int i, j;
for (i = 1; i < MAXLVL; i++)
numeric[i] = decrease[i] = fold[i] = direct[i] = 0;
for (i = 1; i < parms; i++)
if (test_arg(argp[i]))
return 1;
if (sortlvl > 1) /* CHECK FOR OVERLAPPING SORT FIELDS */
for (i = 0; i < sortlvl-1; i++)
for (j = i+1; j < sortlvl; j++)
if (start_col[i] <= end_col[j]
&& end_col[i] >= start_col[j]) {
printf("SORT FIELDS MUST NOT OVERLAP\n");
return 1;
}
return 0;
}
/* TEST_ARG: TEST AN INDIVIDUAL ARGUMENT */
int test_arg(char *c)
{
static int line_sort = 0;
int num, decr, fcase, dir;
int field_parm = 0;
int start = 0, len = 0;
if (*c != '-') {
printf("ARGUMENT MUST BEGIN WITH -\n");
return 1;
}
if (*++c == '\0') {
printf("PARAMETERS MISSING\n");
return 1;
}
if (!isdigit(*c)) { /* LINE SORT */
if (sortlvl > 0) { /* PRIOR PARAM SPECIFIED FIELD SORT */
printf("LINE & FIELD PARAMETERS MUST NOT BE MIXED\n");
return 1;
}
line_sort = 1;
}
else { /* FIELD SORT */
if (line_sort) { /* PRIOR PARAM SPECIFIED LINE SORT */
printf("LINE & FIELD PARAMETERS MUST NOT BE MIXED\n");
return 1;
}
if (sortlvl > MAXLVL-1) {
printf("SORT LEVELS LIMITED TO %d\n", MAXLVL);
return 1;
}
field_parm = field_sort = 1;
for ( ; isdigit(*c); c++)
start = 10 * start + (*c - '0');
if (start < 1 || start > MAXLEN) {
printf("START POSITION OUT OF RANGE\n");
return 1;
}
start_col[sortlvl] = start - 1;
if (*c++ != ',') {
printf("PARAMETERS MUST BE SEPARATED BY ,\n");
return 1;
}
if (!isdigit(*c)) {
printf("LENGTH PARAMETER MISSING\n");
return 1;
}
else
for ( ; isdigit(*c); c++)
len = 10 * len + (*c - '0');
if (len < 1 || start + len - 1 > MAXLEN) {
printf("LENGTH OUT OF RANGE\n");
return 1;
}
keylen[sortlvl] = len;
end_col[sortlvl] = start_col[sortlvl] + len - 1;
if (*c != '\0') {
if (*c++ != ',') {
printf("PARAMETERS MUST BE SEPARATED BY ,\n");
return 1;
}
if (*c == '\0') {
printf("INVALID ARGUMENT\n");
return 1;
}
}
}
num = decr = fcase = dir = 0;
for ( ; *c; c++) {
if (*c == 'n') {
if (num) {
printf("PARAMETERS MUST NOT BE REPEATED\n");
return 1;
}
num = 1;
}
else
if (*c == 'r') {
if (decr) {
printf("PARAMETERS MUST NOT BE REPEATED\n");
return 1;
}
decr = 1;
}
else
if (*c == 'f') {
if (fcase) {
printf("PARAMETERS MUST NOT BE REPEATED\n");
return 1;
}
fcase = 1;
}
else
if (*c == 'd') {
if (dir) {
printf("PARAMETERS MUST NOT BE REPEATED\n");
return 1;
}
dir = 1;
}
else {
printf("INVALID ARGUMENT\n");
return 1;
}
}
if (!field_parm)
if ((num && numeric[sortlvl]) || (decr && decrease[sortlvl])
|| (fcase && fold[sortlvl]) || (dir && direct[sortlvl])) {
printf("PARAMETERS MUST NOT BE REPEATED\n");
return 1;
}
if (num)
numeric[sortlvl] = 1;
if (decr)
decrease[sortlvl] = 1;
if (fcase) {
fold[sortlvl] = 1;
has_fold = 1;
}
if (dir) {
direct[sortlvl] = 1;
has_direct = 1;
}
if (field_parm) {
if (end_col[sortlvl] > minlen)
minlen = end_col[sortlvl];
sortlvl++;
}
return 0;
}