ex_5-14.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4
   5 #define MAXLINES 5000   // max number of lines sorted
   6 #define MAXLEN 1000     // maximum length of each line
   7 #define ALLOCSIZE 10000 // size of available space
   8
   9 int readlines(char *lineprt[], int nlines);
  10 void writelines(char *lineprt[], int nlines);
  11 void new_qsort(void *lineptr[], int left, int right, int (*comp)(void *, void*));
  12 int numcmp(char *, char *);
  13 void swap(void *v[], int i, int j);
  14 int getline(char s[], int lim);
  15 char *alloc(int n);
  16
  17 char *lineptr[MAXLINES]; // pointers to next lines
  18 static char allocbuf[ALLOCSIZE];
  19 static char *allocp = allocbuf;
  20
  21 /*
  22
  23 Get chars ony by one from stdin.  Load them into array of chars within lim.
  24
  25 */
  26 int getline(char s[], int lim)
  27 {
  28         int c, i;
  29         i = 0;
  30         while(--lim > 0 && (c = getchar()) != EOF && c != '\n')
  31                 s[i++] = c;
  32         if(c == '\n')
  33                 s[i++] = c;
  34         s[i] = '\0';
  35         return i;
  36 }
  37
  38 void new_qsort(void *v[], int left, int right, int (*comp)(void *, void*))
  39 {
  40         int i, last;
  41         void swap(void *v[], int, int);
  42
  43         if(left >= right)
  44                 return;
  45         swap(v, left, (left + right)/2);
  46         last = left;
  47         for(i = left+1; i <= right; i++)
  48                 if((*comp)(v[i], v[left]) < 0)
  49                         swap(v, ++last, i);
  50         swap(v, left, last);
  51         new_qsort(v, left, last-1, comp);
  52         new_qsort(v, last+1, right, comp);
  53 }
  54
  55 void swap(void *v[], int i, int j)
  56 {
  57         void *temp;
  58         temp = v[i];
  59         v[i] = v[j];
  60         v[j] = temp;
  61 }
  62
  63 /*
  64
  65 Compare two strings numerically.
  66
  67 */
  68 int numcmp(char *s1, char *s2)
  69 {
  70         double v1, v2;
  71         v1 = atof(s1);
  72         v2 = atof(s2);
  73         if(v1 < v2)
  74                 return -1;
  75         else if (v1 > v2)
  76                 return 1;
  77         else
  78                 return 0;
  79 }
  80
  81 /*
  82
  83 read input lines
  84
  85 Use getline to obtain data from stdin.
  86
  87 Put data into array of pointers to char, as long as number of lines less than maxlines.
  88
  89 */
  90 int readlines(char *lineprt[], int maxlines)
  91 {
  92         int len, nlines;
  93         char *p, line[MAXLEN];
  94
  95         nlines = 0;
  96         while((len = getline(line, MAXLEN)) > 0)
  97         {
  98                 if(nlines >= maxlines || (p = alloc(len)) == NULL)
  99                 {
 100                         return -1;
 101                 } else {
 102                         line[len-1] = '\0'; // delete newline
 103                         strcpy(p, line);
 104                         lineptr[nlines++] = p;
 105                 }
 106         }
 107         return nlines;
 108 }
 109
 110 /*
 111 write ouput lines to stdout
 112
 113 input is an array of pointers to char and the number of lines stored
 114
 115 ouput goes to stdout
 116
 117 */
 118 void writelines(char *lineptr[], int nlines)
 119 {
 120         while(nlines-- > 0)
 121                 printf("%s\n", *lineptr++);
 122 }
 123
 124 char *alloc(int n)
 125 {
 126         if(allocbuf + ALLOCSIZE - allocp >= n)
 127         {
 128                 allocp += n;
 129                 return allocp -n; // old pointer
 130         } else {
 131                 return 0;
 132         }
 133 }
 134
 135 /*
 136
 137 Sort lines in input numerically.
 138
 139 If -n switch entered, sort lines numerically.
 140
 141 Program is limited by buffers of both maximum number of lines and maximum length of lines.
 142
 143 */
 144
 145 int main(int argc, char *argv[])
 146 {
 147         int nlines;
 148         int numeric = 0;
 149
 150         if(argc > 1 && strcmp(argv[1], "-n") == 0)
 151                 numeric = 1;
 152         if((nlines = readlines(lineptr, MAXLINES)) >= 0)
 153         {
 154                 new_qsort((void **) lineptr, 0, nlines-1, (int(*)(void *,void *))(numeric ? numcmp : strcmp));
 155                 writelines(lineptr, nlines);
 156                 return 0;
 157         } else {
 158                 printf("Input: Too many lines to sort\n");
 159                 return 1;
 160         }
 161         return 1;
 162 }