home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_100 / 189_01 / fcomp.c < prev    next >
Text File  |  1985-08-21  |  4KB  |  211 lines
  1. /* fcomp.c:     file comparator that beats DIFF! */
  2.  
  3. #include <stdio.h>
  4.  
  5. #define MAXLINES 1000
  6. #define ORIGIN MAXLINES
  7. #define INSERT 1
  8. #define DELETE 2
  9.  
  10. struct edit {
  11.    struct edit *link;
  12.    int op;
  13.    int line1;
  14.    int line2;
  15. };
  16.  
  17. char *A[MAXLINES], *B[MAXLINES];
  18.  
  19. main(argc,argv)
  20. int argc;
  21. char *argv[];
  22. {
  23.    int   max_d,
  24.          m,
  25.          n,
  26.          lower,
  27.          upper,
  28.          d,
  29.          k,
  30.          row,
  31.          col;
  32.  
  33.    int last_d[2*MAXLINES+1];
  34.    struct edit *script[2*MAXLINES+1];
  35.  
  36.    struct edit *new;
  37.    char *malloc();
  38.  
  39.    if (argc > 1 && argv[1][0] == '-')
  40.    {
  41.       max_d = atoi(&argv[1][1]);
  42.       ++argv;
  43.       --argc;
  44.    }
  45.    else
  46.       max_d = 2*MAXLINES;
  47.  
  48.    if(argc != 3)
  49.       fatal("diff requires two file names.");
  50.  
  51.    m = in_file(argv[1],A);
  52.    n = in_file(argv[2],B);
  53.  
  54.    for (row=0 ; row<m && row < n && strcmp(A[row],B[row]) == 0 ; ++row)
  55.       ;
  56.    last_d[ORIGIN] = row;
  57.    script[ORIGIN] = NULL;
  58.    lower = (row == m) ? ORIGIN + 1 : ORIGIN - 1;
  59.    upper = (row == n) ? ORIGIN - 1 : ORIGIN + 1;
  60.    if (lower > upper) 
  61.    {
  62.       puts("The files are identical.");
  63.       exit();
  64.    }
  65.  
  66.    for (d = 1 ; d <= max_d ; ++d) 
  67.    {
  68.       for ( k = lower ; k <= upper ; k +=2) 
  69.       {
  70.          new = (struct edit *) malloc(sizeof(struct edit));
  71.          if (new == NULL)
  72.             exceed(d);
  73.  
  74.          if (k == ORIGIN-d || k != ORIGIN+d && last_d[k+1] >= last_d[k-1]) 
  75.          {
  76.             row = last_d[k+1]+1;
  77.             new->link = script[k+1];
  78.             new->op = DELETE;
  79.          } 
  80.          else 
  81.          {
  82.             row = last_d[k-1];
  83.             new->link = script[k-1];
  84.             new->op = INSERT;
  85.          }
  86.          new->line1 = row;
  87.          new->line2 = col = row + k - ORIGIN;
  88.          script[k] = new;
  89.  
  90.          while(row < m && col < n && strcmp(A[row],B[col]) == 0) 
  91.          {
  92.             ++row;
  93.             ++col;
  94.          }
  95.          last_d[k] = row;
  96.  
  97.          if (row == m && col == n)
  98.          {
  99.             put_scr(script[k]);
  100.             exit();
  101.          }
  102.          if (row == m)
  103.             lower = k+2;
  104.  
  105.          if (col == n)
  106.             upper = k-2;
  107.       }
  108.       --lower;
  109.       ++upper;
  110.    }
  111.    exceed(d);
  112. }
  113.  
  114. in_file(filename,P)
  115. char *filename, *P[];
  116. {
  117.    char buf[100], *malloc(), *fgets(), *save, *b;
  118.    FILE *fp, *fopen();
  119.    int lines = 0;
  120.  
  121.    if ((fp = fopen(filename,"r")) == NULL) 
  122.    {
  123.       fprintf(stderr, "Cannot open file %s.\n",filename);
  124.       exit();
  125.    }
  126.  
  127.    while(fgets(buf,100,fp) != NULL) 
  128.    {
  129.       if (lines >= MAXLINES)
  130.          fatal("File is to large for diff.");
  131.       if ((save = malloc(strlen(buf)+1)) == NULL)
  132.          fatal("Not enough room to save the files.");
  133.       P[lines++] = save;
  134.       for (b = buf ; *save++ = *b++ ; )
  135.          ;
  136.    }
  137.    fclose(fp);
  138.    return(lines);
  139. }
  140.  
  141. put_scr(start)
  142. struct edit *start;
  143. {
  144.    struct edit *ep, *behind, *ahead, *a, *b;
  145.    int change;
  146.  
  147.    ahead = start;
  148.    ep = NULL;
  149.    while (ahead != NULL) 
  150.    {
  151.       behind = ep;
  152.       ep = ahead;
  153.       ahead = ahead->link;
  154.       ep->link = behind;
  155.    }
  156.  
  157.    while( ep != NULL) 
  158.    {
  159.       b = ep;
  160.       if (ep->op == INSERT)
  161.          printf("Inserted after line %d:\n",ep->line1);
  162.       else 
  163.       {
  164.          do 
  165.          {
  166.             a = b;
  167.             b = b->link;
  168.          } while (b!=NULL && b->op == DELETE && b->line1 == a->line1+1);
  169.  
  170.          change = (b!=NULL && b->op == INSERT && b->line1 == a->line1);
  171.          if (change)
  172.             printf("\nChanged ");
  173.          else
  174.             printf("\nDeleted ");
  175.          if (a == ep)
  176.             printf("line %d\n",ep->line1);
  177.          else
  178.             printf("lines %d-%d:\n",ep->line1,a->line1);
  179.  
  180.          do 
  181.          {
  182.             printf(" %s",A[ep->line1-1]);
  183.             ep = ep->link;
  184.          } while (ep != b);
  185.  
  186.          if (!change)
  187.             continue;
  188.          printf("To:\n");
  189.       }
  190.       do 
  191.       {
  192.          printf(" %s",B[ep->line2-1]);
  193.          ep = ep->link;
  194.       } while (ep != NULL && ep->op == INSERT && ep->line1 == b->line1);
  195.    }
  196. }
  197.  
  198. fatal(msg)
  199. char *msg;
  200. {
  201.    fprintf(stderr,"%s\n",msg);
  202.    exit();
  203. }
  204.  
  205. exceed(d)
  206. int d;
  207. {
  208.    fprintf(stderr,"The files differ in at least %d lines. \n",d);
  209.    exit();
  210. }
  211.  yd$SUBST   C   E~     PAGE    EXE Bö} U0READ    ME  ¢>ü $≡