home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume16 / spiff / part01 / miller.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-11-10  |  2.6 KB  |  128 lines
  1. /*                        Copyright (c) 1988 Bellcore
  2. **                            All Rights Reserved
  3. **       Permission is granted to copy or use this program, EXCEPT that it
  4. **       may not be sold for profit, the copyright notice must be reproduced
  5. **       on copies, and credit should be given to Bellcore where it is due.
  6. **       BELLCORE MAKES NO WARRANTY AND ACCEPTS NO LIABILITY FOR THIS PROGRAM.
  7. */
  8.  
  9.  
  10. #ifndef lint
  11. static char rcsid[]= "$Header: miller.c,v 1.1 88/09/15 11:33:56 daniel Rel $";
  12. #endif
  13.  
  14. #include "misc.h"
  15. #include "token.h"
  16. #include "edit.h"
  17.  
  18. #define MAXT    K_MAXTOKENS
  19. #define ORIGIN (max_obj/2)
  20.  
  21. #define MILLER_CHATTER    100
  22.  
  23. /*
  24. **    totally opaque miller/myers code
  25. **        hacked from a version provided by the author
  26. */
  27.  
  28.  
  29. E_edit
  30. G_do_miller(m,n,max_d,comflags)
  31. int m;
  32. int n;
  33. int max_d;
  34. int comflags;
  35. {
  36.     int    max_obj = m + n;
  37.     int
  38.     lower,
  39.     upper,
  40.     d,
  41.     k,
  42.     row,
  43.     col;
  44.     E_edit new;
  45.  
  46. #ifdef STATIC_MEM
  47.     static E_edit script[MAXT+1];
  48.     static int last_d[MAXT+1];
  49. #else
  50.     E_edit *script;
  51.     int *last_d;
  52.     /*
  53.     **    make space for the two big arrays
  54.     **        these could probably be smaller if I
  55.     **        understood this algorithm at all
  56.     **        as is, i just shoe horned it into my program.
  57.     **    be sure to allocate max_obj + 1 objects as was done
  58.     **        in original miller/myers code
  59.     */
  60.     script = Z_ALLOC(max_obj+1,E_edit);
  61.     last_d = Z_ALLOC(max_obj+1,int);
  62.  
  63. #endif
  64.     for (row=0;row < m && row < n && X_com(row,row,comflags) == 0; ++row)
  65.         ;
  66.     last_d[ORIGIN] = row;
  67.     script[ORIGIN] = E_NULL;
  68.     lower = (row == m) ? ORIGIN+1 : ORIGIN - 1;
  69.     upper = (row == n) ? ORIGIN-1 : ORIGIN + 1;
  70.     if (lower > upper)
  71.     {
  72.         /*
  73.         **    the files are identical
  74.         */
  75.         return(E_NULL);
  76.     }
  77.     for (d = 1; d <= max_d; ++d) {
  78.         for (k = lower; k<= upper; k+= 2) {
  79.             new = E_edit_alloc();
  80.  
  81.             if (k == ORIGIN-d || k!= ORIGIN+d && last_d[k+1] >= last_d[k-1]) {
  82.                 row = last_d[k+1]+1;
  83.                 E_setnext(new,script[k+1]);
  84.                 E_setop(new,E_DELETE);
  85.             } else {
  86.                 row = last_d[k-1];
  87.                 E_setnext(new,script[k-1]);
  88.                 E_setop(new,E_INSERT);
  89.             }
  90.  
  91.             E_setl1(new,row);
  92.             col = row + k - ORIGIN;
  93.             E_setl2(new,col);
  94.             script[k] = new;
  95.  
  96.             while (row < m && col < n && X_com(row,col,comflags) == 0) {
  97.                 ++row;
  98.                 ++col;
  99.             }
  100.             last_d[k] = row;
  101.             if (row == m && col == n) {
  102.                 return(script[k]);
  103.             }
  104.             if (row == m)
  105.                 lower = k+2;
  106.             if (col == n)
  107.                 upper = k-2;
  108.         }
  109.         --lower;
  110.         ++upper;
  111. #ifndef NOCHATTER
  112.         if ((d > 0) && (0 == (d % MILLER_CHATTER)))
  113.         {
  114.             (void) sprintf(Z_err_buf,
  115.                 "found %d differences\n",
  116.                 d);
  117.             Z_chatter(Z_err_buf);
  118.         }
  119. #endif
  120.     }
  121.     Z_exceed(max_d);
  122.     /*
  123.     **    dummy lines to shut up lint
  124.     */
  125.     Z_fatal("fell off end of do_miller\n");
  126.     return(E_NULL);
  127. }
  128.