home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / gnustuff / tos / futils / futils~1 / src / misc1s.zoo / misc1 / combine / pass4.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-06-23  |  6.2 KB  |  228 lines
  1. #include <stdio.h>
  2. #include <ctype.h>
  3. #include "util.h"
  4. #include "combine.h"
  5. /*
  6.  * pass4: Handle non-unique record clusters.
  7.  *
  8.  * This routine tries to fix up problems which arise due to groups of
  9.  * non-unique records which are surrounded by insertions. When this
  10.  * condition arises, the group of non-unique records are treated as
  11.  * a part of the inserted text.
  12.  *
  13.  * This routine finds a pair of anchor records which have inserted lines
  14.  * between them. (See diagram below.) All inserted lines are compared
  15.  * to one another trying to find a group of non-unique lines which
  16.  * match. Such lines are considered equal and are flagged as anchor
  17.  * points.
  18.  *
  19.  *          match1                       match1
  20.  *          insert
  21.  *          non-unique1                  non-unique1
  22.  *          insert
  23.  *          match2                       match2
  24.  *
  25.  * This routine runs in M x N time where 'M' is the number of lines
  26.  * inserted at the current position in the first file and 'N' is the number
  27.  * of lines inserted at the current position in the second file.
  28.  *
  29.  * Possible design flaw: The algorithm used to match the non-unique lines
  30.  * should really be the same alogirthm used for the rest of the file.
  31.  * That algorithm runs in linear time. The main problem with doing that is
  32.  * that the other passes of this program were not designed for or optimized
  33.  * around working for a portion of a file. Also, the proposed algorithm
  34.  * relies on the fact that some of the non-unique lines will become unique
  35.  * when only this fragment of the files are compared.
  36.  *
  37.  * Return value:
  38.  *      This procedure has no return value.
  39.  */
  40.  
  41. void pass4 () {
  42.  
  43.     int     i;        /* Misc. variable */
  44.  
  45.     int     j;        /* Misc. variable */
  46.  
  47.     /*
  48.      * Scan each pair of files.
  49.      */
  50.  
  51.     for (j = 0; j < UNIQUE_MATCH_COUNT; ++j) {
  52.  
  53.         i = unique_match[j];
  54.  
  55.         if (files[curr_file[i]].record != 0 &&
  56.                 files[corres_file[i]].record != 0) {
  57.  
  58.             pass4_scan (i);
  59.  
  60.         }
  61.  
  62.     }
  63.  
  64. }
  65. /*
  66.  * pass4_scan: pass4 for two files.
  67.  *
  68.  * This routine implements the pass4 algorithm for a pair of files.
  69.  *
  70.  * Return value:
  71.  *      This procedure has no return value.
  72.  */
  73.  
  74. void pass4_scan (match_no)
  75. int     match_no;        /* input */
  76.                 /* Which relationship is being scanned */
  77.  
  78. {
  79.  
  80.     register int i;        /* Index into record array of file1 of the
  81.                    current position in the inserted records */
  82.  
  83.     register int j;        /* Index into record array of file2 of the
  84.                    current position in the inserted records */
  85.  
  86.     file_type * file1_ptr;    /* First file - current_file */
  87.  
  88.     file_type * file2_ptr;    /* Second file - corresponding file */
  89.  
  90.     int     file1_sub;    /* For each record of the first file, this is a
  91.                    subscript of the 'value' array of the
  92.                    relationship between file1 and file2 */
  93.  
  94.     int     file2_sub;    /* For each record of the second file, this is
  95.                    a subscript of the 'value' array of the
  96.                    relationship between file2 and file1 */
  97.  
  98.     register int fn_index1;    /* Index into record array of file1 of the
  99.                    position of the last inserted record */
  100.  
  101.     register int fn_index2;    /* Index into record array of file2 of the
  102.                    position of the last inserted record */
  103.  
  104.     int     index1;        /* Index into record array of file1 of the
  105.                    record currently being processed */
  106.  
  107.     record_type * record1;    /* Pointer to record array of file1 */
  108.  
  109.     record_type * record2;    /* Pointer to record array of file2 */
  110.  
  111.     register int st_index1;    /* Index into record array of file1 of the
  112.                    position of the first inserted record */
  113.  
  114.     register int st_index2;    /* Index into record array of file2 of the
  115.                    position of the first inserted record */
  116.  
  117.  
  118.     /*
  119.      * Initialize indexes to first and last record of the files.
  120.      */
  121.  
  122.     file1_ptr = &files[curr_file[match_no]];
  123.     file2_ptr = &files[corres_file[match_no]];
  124.     file1_sub = value_sub[match_no];
  125.     file2_sub = rev_value_sub[match_no];
  126.  
  127.     record1 = file1_ptr -> record;
  128.     record2 = file2_ptr -> record;
  129.  
  130.     /*
  131.      * For each record in the first file.
  132.      *
  133.      * Note: given the existence of the 'begin' and 'end' record on each
  134.      * end of the record array,
  135.      * we can convince ourselves that the tests below won't ever index
  136.      * off the end of the arrays.
  137.      */
  138.     for (index1 = BEGIN_INDEX; index1 < file1_ptr->record_array_size-1;
  139.         index1++) {
  140.  
  141.         /*
  142.          * If the current record in file1 is not an anchor point,
  143.          *     continue the big loop.
  144.          */
  145.         st_index2 = record1[index1].value[file1_sub];
  146.         if (is_hash_code (st_index2)) {
  147.             continue;
  148.         }
  149.  
  150.         /*
  151.          * Compute the index into file2 of the corresponding record.
  152.          * Compute a pointer to value field of the next record in each
  153.          *    file.
  154.          *
  155.          * If either of the next records are anchor points,
  156.          *      continue the big loop.
  157.          */
  158.         if (!is_hash_code( record1[index1 + 1].value[file1_sub]))
  159.             continue;
  160.         if (!is_hash_code( record2[st_index2 + 1].value[file2_sub]))
  161.             continue;
  162.  
  163.         /*
  164.          * We have found the point where a group of inserted records
  165.          * begins in both files.
  166.          *
  167.          * Set up indexes to the first and last inserted records in
  168.          * the group.
  169.          */
  170.         st_index1 = fn_index1 = index1 + 1;
  171.         st_index2 = st_index2 + 1;
  172.         while (is_hash_code (record1[fn_index1].value[file1_sub])) {
  173.             ++fn_index1;
  174.         }
  175.         fn_index2 = record1[fn_index1].value[file1_sub];
  176.         fn_index1--;    /* Adjust to index to last inserted record */
  177.         fn_index2--;    /* Adjust to index to last inserted record */
  178.  
  179.         /*
  180.          * If this group of inserted records is adjacent to a group of
  181.          * moved records, skip the comparison. This isn't the case
  182.          * we're interested in.
  183.          */
  184.         index1 = fn_index1;
  185.         if (st_index2 > fn_index2) {
  186.             continue;
  187.         }
  188.  
  189.         /*
  190.          * Ensure that only non-unique records exist in the range
  191.          * of the corresponding file. This catches a move in the
  192.          * other direction.
  193.          */
  194.         for ( j=st_index2; j<=fn_index2; ++ j){
  195.             if (!is_hash_code (record2[j].value[file2_sub]))
  196.                 break;
  197.         }
  198.         if ( j <= fn_index2 )
  199.             continue;
  200.  
  201.         /*
  202.          * Compare the hash codes. If two records are identical,
  203.          * consider them to be anchor points.
  204.          */
  205.         if ( p4_debug ) {
  206.             printf("pass4: match_no: %d (%d-%d) (%d-%d)\n",
  207.                 match_no, st_index1, fn_index1,
  208.                      st_index2, fn_index2);
  209.         }
  210.  
  211.         for (i = st_index1; i<=fn_index1; ++i) {
  212.             for (j=st_index2; j<=fn_index2; ++j) {
  213.  
  214.                 if (record1[i].value[file1_sub] ==
  215.                     record2[j].value[file2_sub]) {
  216.  
  217.                     link_records(match_no,i, j);
  218.                     st_index2 = j + 1;
  219.                     break;
  220.  
  221.                 }
  222.  
  223.             }
  224.         }
  225.     }
  226.  
  227. }
  228.