home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Guide / c-cplusplus-interactive-guide.iso / c_ref / csource3 / 195_01 / sort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-05  |  7.6 KB  |  412 lines
  1. /* [SORT.C of JUGPDS Vol.18]
  2. *****************************************************************
  3. *                                *
  4. *    Written by  Hakuo Katayose (JUG-CP/M No.179)        *
  5. *            49-114 Kawauchi-Sanjuunin-machi        *
  6. *            Sendai, Miyagi 980                          *
  7. *            Phone: 0222-61-3219                *
  8. *                                *
  9. *    Edited & tested by Y. Monma (JUG-C/M Disk Editor)       * 
  10. *                                *
  11. *****************************************************************
  12. */
  13.  
  14. /* sort - sort and merge */
  15.  
  16. #include "stdio.h"
  17. #include "def.h"
  18. #include <dio.h>
  19.  
  20. #define LINES    2000
  21. #define MAXLEN    128
  22. #define MAXBUF    16
  23. #define MERGEORDER    7
  24.  
  25. char    allocbuf[1024][MAXBUF], *alloc_bp, *alloc_ep;
  26. char    opt_d;        /* dictionary order */
  27. char    opt_f;        /* fold order        */
  28. char    opt_n;        /* numeric order   */
  29. char    opt_l;        /* line_no listing  */
  30. char    opt_r;        /* reverse order    */
  31.  
  32.  
  33. main(argc, argv)
  34. int argc;
  35. char *argv[];
  36.  
  37. {
  38.     char    *ap;
  39.     int    i;
  40.  
  41.     dioinit(&argc, argv);
  42.     if (argc <3) {
  43.         error("Usage: sort -{dfnlr} file1 file2 ... >outfile");
  44.         exit();
  45.         }
  46.     else
  47.     opt_d = opt_f = opt_n = opt_l = opt_r = OFF;
  48.     i = 0;
  49.     while (--argc > 0 && (*++argv)[0] == '-')
  50.         for (ap = argv[0]+1; *ap != '\0'; ap++)
  51.             switch (tolower(*ap)) {
  52.             case 'd':
  53.                 opt_d = ON;
  54.                 break;
  55.             case 'f':
  56.                 opt_f = ON;
  57.                 break;
  58.             case 'n':
  59.                 opt_n = ON;
  60.                 break;
  61.             case 'l' :
  62.                 opt_l = ON;
  63.                 break;
  64.             case 'r':
  65.                 opt_r = ON;
  66.                 break;
  67.             }
  68.     FileSort();
  69.     dioflush();
  70. }
  71.  
  72.  
  73. FileSort()
  74. {
  75.     char    fname[15], *lineptr[LINES], opt_ll;
  76.     int    nlines, t, high, low, lim;
  77.     FILE    infp[MERGEORDER], outfp;
  78.  
  79.     high = 0;
  80.     t = Gtext(lineptr, &nlines, LINES, STDIN);
  81.     Sort(lineptr, nlines);
  82.     if (t == EOF) {
  83.         Ptext(lineptr, nlines, STDOUT);
  84.         return;
  85.     }
  86.     opt_ll = opt_l;
  87.     opt_l  = OFF;
  88.     MakeFile(high, &outfp);
  89.     Ptext(lineptr, nlines, &outfp);
  90.     putc(CPMEOF, &outfp);
  91.     fclose(&outfp);
  92.     while (t != EOF) {
  93.         t = Gtext(lineptr, &nlines, LINES, STDIN);
  94.         Sort(lineptr, nlines);
  95.         MakeFile(++high, &outfp);
  96.         Ptext(lineptr, nlines, &outfp);
  97.         putc(CPMEOF, &outfp);
  98.         fclose(&outfp);
  99.         }
  100.     opt_l = opt_ll;
  101.     for (low = 0; low <= high; low += MERGEORDER) {
  102.         lim = min(low + MERGEORDER - 1, high);
  103.         Gopen(infp, low, lim);
  104.         MakeFile(++high, &outfp);
  105.         Merge(infp, lim-low+1, &outfp);
  106.         putc(CPMEOF, &outfp);
  107.         fclose(&outfp);
  108.         Gremove(infp, low, lim);
  109.     }
  110.  
  111.     sprintf(fname, "stemp.%d", high);
  112.     if (fopen(fname, infp) == ERROR) {
  113.         fprintf(STDERR, "file not open: %s\n", fname);
  114.         exit();
  115.         }
  116.     Fcopy(infp, STDOUT);
  117.     fclose(infp);
  118.     unlink(fname);
  119. }
  120.  
  121.  
  122. MakeFile(fno, fp)
  123. FILE    *fp;
  124. {
  125.     char    fname[15];
  126.  
  127.     sprintf(fname, "stemp.%d", fno);
  128.     if (fcreat(fname, fp) == ERROR) {
  129.         fprintf(STDERR, "file not creat: %s\n", fname);
  130.         exit();
  131.         }
  132. }
  133.  
  134.  
  135. Fcopy(inbuf, outbuf)
  136. FILE *inbuf, *outbuf;
  137. {
  138.     int c, lno;
  139.  
  140.     lno = 1;
  141.     while (fgetlin(inbuf, allocbuf, MAXLEN) > 0) {
  142.         if( opt_l == ON )
  143.             fputdec(outbuf, lno++, 6);
  144.         fputlin(outbuf, allocbuf);
  145.         if (outbuf != STDOUT)
  146.             putch(NEWLINE, outbuf);
  147.     }
  148. }
  149.  
  150.  
  151. Gopen(fp, low, lim)
  152. FILE    fp[];
  153. {
  154.     int    i;
  155.     char    fname[15];
  156.  
  157.     for (i = 0; i < lim - low + 1; i++) {
  158.         sprintf(fname, "stemp.%d", low + i);
  159.         if (fopen(fname, fp[i]) == ERROR) {
  160.             fprintf(STDERR, "file not open: %s\n", fname);
  161.             exit();
  162.         }
  163.     }
  164. }
  165.  
  166.  
  167. Gremove(fp, low, lim)
  168. FILE    fp[];
  169. {
  170.     char    fname[15];
  171.     int    i;
  172.  
  173.     for (i = 0; i < lim - low + 1; i++) {
  174.         putc(CPMEOF, fp[i]);
  175.         fclose(fp[i]);
  176.         sprintf(fname, "stemp.%d", low + i);
  177.         unlink(fname);
  178.     }
  179. }
  180.  
  181. /* merge - merge infile(1)...infile(nfiles) onto outfile */
  182. Merge(infile, nfiles, outfile)
  183. FILE infile[], *outfile;
  184. {
  185.     char    *lineptr[MERGEORDER], *p;
  186.     int    i, nl, inf, len;
  187.     int    strdfcmp(), strfcmp(), strcmp(), strdcmp(), numcmp(), swap();
  188.  
  189.     p = alloc_bp = allocbuf;
  190.     for (nl = 0, i = 0; i < nfiles; i++)
  191.         if ((len = fgetlin(infile[i], alloc_bp, MAXLEN)) > 0) {
  192.             *(alloc_bp + len - 1) = '\0';
  193.             lineptr[nl++] = alloc_bp;
  194.             alloc_bp += MAXLINE;
  195.         }
  196.     Sort(lineptr, nl--);
  197.     while (nl >= 0) {
  198.         fputlin(outfile, lineptr[0]);
  199.         putch(NEWLINE, outfile);
  200.         inf = (lineptr[0] - p) / MAXLINE;
  201.         if ((len =fgetlin(infile[inf], lineptr[0], MAXLEN)) <= 0)
  202.             lineptr[0] = lineptr[nl--];
  203.         else
  204.             *(lineptr[0] + len - 1) = '\0';
  205.         if (opt_n == ON)
  206.             reheap(lineptr, nl, numcmp, swap);
  207.         else if (opt_d == ON && opt_f == ON)
  208.             reheap(lineptr, nl, strdfcmp, swap);
  209.         else if (opt_d == ON)
  210.             reheap(lineptr, nl, strdcmp, swap);
  211.         else if (opt_f == ON)
  212.             reheap(lineptr, nl, strfcmp, swap);
  213.         else
  214.             reheap(lineptr, nl, strcmp, swap);
  215.         }
  216. }
  217.  
  218. /* reheap - propagat inbuf(lineptr(1)) to proper place in heap */
  219. reheap(lineptr, nl, comp, exch)
  220. char    *lineptr[];
  221. int    (*comp)(), (*exch)();
  222. {
  223.     int    i, f;
  224.     char    *p;
  225.  
  226.     for (i = 1; i <= nl; i++) {
  227.         f = (*comp)(lineptr[i-1], lineptr[i]);
  228.         if (opt_r == ON && f >= 0)
  229.             break;
  230.         else if (opt_r==OFF && f <= 0)
  231.             break;
  232.         (*exch)(&lineptr[i-1], &lineptr[i]);
  233.     }
  234. }
  235.  
  236.  
  237. Sort(lineptr, nlines)
  238. char *lineptr[];
  239. {
  240.     int    strdfcmp(), strfcmp(), strcmp(), strdcmp(), numcmp(), swap();
  241.  
  242.     if (opt_n == ON)
  243.         quick(lineptr, 0, nlines-1, numcmp, swap);
  244.     else if (opt_d == ON && opt_f == ON)
  245.         quick(lineptr, 0, nlines-1, strdfcmp, swap);
  246.     else if (opt_d == ON)
  247.         quick(lineptr, 0, nlines-1, strdcmp, swap);
  248.     else if (opt_f == ON)
  249.         quick(lineptr, 0, nlines-1, strfcmp, swap);
  250.     else
  251.         quick(lineptr, 0, nlines-1, strcmp, swap);
  252. }
  253.  
  254. /* quick - quicksort for character lines */ 
  255. quick(v, l, r, comp, exch)
  256. char    *v[];
  257. int    l, r;
  258. int    (*comp)(), (*exch)();
  259.  
  260. {
  261.     int    vx, i, j;
  262.  
  263.     i = l;  j = r;
  264.     vx = v[ (l+r)/2 ];
  265.     while(i <= j) {
  266.         while( (*comp)(v[i], vx) < 0 )
  267.             i++;
  268.         while( (*comp)(vx, v[j]) < 0 )
  269.             j--;
  270.         if(i <= j) {
  271.             (*exch)(&v[j], &v[i]);
  272.             i++;
  273.             j--;
  274.             }
  275.         }
  276.     if(l < j) quick(v, l, j, comp, exch);
  277.     if(i < r) quick(v, i, r, comp, exch);
  278. }
  279.  
  280.  
  281. numcmp(s1, s2)
  282. char *s1, *s2;
  283.  
  284. {
  285.     int    atoi(), v1, v2;
  286.  
  287.     v1 = atoi(s1);
  288.     v2 = atoi(s2);
  289.     if (v1 < v2)
  290.         return(-1);
  291.     else if (v1 > v2)
  292.         return(1);
  293.     else
  294.         return(0);
  295. }
  296.  
  297.  
  298. Gtext(lineptr, nlines, maxlines, fp)
  299. char    *lineptr[];
  300. int    *nlines;
  301. FILE    *fp;
  302.  
  303. {
  304.     int    len;
  305.  
  306.     *nlines = 0;
  307.     alloc_bp = allocbuf;
  308.     alloc_ep = &allocbuf[1023][(MAXBUF-1)];
  309.     do {
  310.         if ((len = fgetlin(fp, alloc_bp, MAXLEN)) <= 0)
  311.             return EOF;
  312.         lineptr[(*nlines)++] = alloc_bp;
  313.         alloc_bp += len;
  314.         *(alloc_bp - 1) = '\0';
  315.         } while (alloc_bp + MAXLEN <= alloc_ep && *nlines < maxlines);
  316.     return(len);
  317. }
  318.  
  319.  
  320. Ptext(lineptr, nlines, fp)
  321. char    *lineptr[];
  322. int    nlines;
  323. FILE    *fp;
  324.  
  325. {
  326.     int    lno;
  327.  
  328.     lno = 1;
  329.     if (opt_r == ON) lineptr += nlines;
  330.     while (nlines--) {
  331.         if (opt_l == ON)
  332.             fputdec(fp, lno++, 6);
  333.         fputlin(fp, (opt_r == ON ? *--lineptr : *lineptr++));
  334.         putch(NEWLINE, fp);
  335.         }
  336. }
  337.  
  338.  
  339. /* fputdec - put decimal integer in field width >= w for FILE *fp */
  340. fputdec(fp, n, w)
  341. FILE *fp;
  342.  
  343. {
  344.     char    s[64], itoa();
  345.     int    len;
  346.  
  347.     len = strlen(itoa(s,n));
  348.     if ((len = w - len) > 0)
  349.         while (len--)
  350.             putch(BLANK, fp);
  351.     fputlin(fp, s);
  352.     putch(':', fp);
  353. }
  354.  
  355.  
  356. fputlin(fp, s)
  357. char *s;
  358. FILE *fp;
  359. {
  360.     while (*s)
  361.         putch(*s++, fp);
  362. }
  363.  
  364.  
  365. putch(c,fp)
  366. FILE *fp;
  367. {
  368.     if (fp == STDOUT)
  369.         putchar(c);
  370.     else {
  371.         if (c == NEWLINE)
  372.             putc(CRETURN, fp);
  373.         putc(c, fp);
  374.     }
  375. }
  376.  
  377.  
  378. fgetlin(fp, s, lim)
  379. char    *s;
  380. int    lim;
  381.  
  382. {
  383.     char    *p;
  384.     int    c;
  385.  
  386.     p = s;
  387.     while (--lim > 0 && (c = getch(fp)) != EOF && c != NEWLINE)
  388.         *s++ = c;
  389.     if(c == NEWLINE)
  390.         *s++ = c;
  391.     *s = '\0';
  392.     return(s-p);
  393. }
  394.  
  395.  
  396. getch(fp)
  397. FILE *fp;
  398.  
  399. {
  400.     int    c;
  401.  
  402.     if (fp == STDIN)
  403.         return getchar();
  404.     else {
  405.         if ((c = getc(fp)) == CRETURN)
  406.             return getch(fp);
  407.         if (c == CPMEOF || c == EOF)
  408.             c = EOF;
  409.         return c;
  410.     }
  411. }
  412.