ed-trans.c.tmpl

#linein
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <stdint.h>

#include "config.h"
#include "text-fuzzy.h"
#include "ed-trans-[% ed_type %].h"

int [% function %] (text_fuzzy_t * tf)
{
    /* "tf->text" is the studied string, so we need it to be word1. */
    const [% type %] * word1 = (const [% type %] *) tf->text.[% value %];
    int len1 = tf->text.[% length %];
    const [% type %] * word2 = (const [% type %] *) tf->b.[% value %];
    int len2 = tf->b.[% length %];

    /* Return value. */
    int d;
    /* X and Y coordinates in the matrix of strings. */
    int i;
    int j;
    /* Unfeasible value; indicates no match. */
    int large_value;
    /* Maximum distance we are interested in. */
    int max;
    int size1 = len1 + 2;
    int size2 = len2 + 2;
    /* This dictionary tracks the locations of characters from word1
       we have seen, for the sake of transpositions. */
    [% dic %]_t * dic;
#ifdef STACKALLOCOK
    unsigned int matrix[size1][size2];
#else
    unsigned int ** matrix;
#endif

    /* First handle the two extreme cases of one or the other strings
       being empty. */

    if (len1 == 0) {
	return len2;
    }
    if (len2 == 0) {
	return len1;
    }

#ifndef STACKALLOCOK
    CALLOC (matrix, size1, unsigned int *);
    for (i = 0; i < size1; i++) {
	CALLOC (matrix[i], size2, unsigned int);
    }
#endif /* STACKALLOCOK */

    dic = & tf->[% dic %];
    max = tf->max_distance;
    large_value = len1 + len2;
 
    /* Initialize the dynamic programming matrix's values. */

    matrix[0][0] = large_value;  
    matrix[1][0] = large_value;

    for (j = 0; j <= len2; j++) {
	matrix[1][j + 1] = j;
	matrix[0][j + 1] = large_value;
    }

    for (i = 1; i <= len1; i++) { 
	/* Last matching column. */
	int lmc;
	/* Minimum value on the row. */
	int row_min;
	[% type %] ic;

	ic = word1[i - 1];

	matrix[i + 1][1] = i;
	matrix[i + 1][0] = large_value;
	
	lmc = 0;
	row_min = INT_MAX;

	for (j = 1; j <= len2; j++) {
	    /* Last matching row */
	    unsigned int lmr;
	    /* Swap score */
	    unsigned int ss;
	    [% type %] jc;

	    jc = word2[j - 1];
	    /* See if we can find jc somewhere in "word1". */
	    lmr = [% dic %]_find (dic, jc);
	    if (lmr > 0) {
		/* We have found "jc" at some offset into "word1", so
		   work out the cost of swapping. */
		ss = matrix[lmr][lmc] + i + j - 1 - lmr - lmc;
	    }
	    else {
		/* Have not found "jc" in "word1", so there is no
		   possibility of transposition, don't bother
		   calculating any more. See comment about i > 0
		   below. */
		ss = large_value;
	    }
	    if (ic != jc) {
		int x;
		int y;
		/* Insertion, deletion, or replacement. */
		x = minimum (matrix[i + 1][j], matrix[i][j + 1]);
		y = minimum (matrix[i][j], x);
		/* Swapping or one of the above. */
		matrix[i + 1][j + 1] = minimum (ss, y + 1);
	    }
	    else { 
		/* Exact match, mark this as the last matching
		   column. */
		lmc = j;
		/* Copy the character. */
		matrix[i + 1][j + 1] = matrix[i][j];
	    }
	    row_min = minimum (row_min, matrix[i + 1][j + 1]);
	}
	if (max > 0 && row_min > max) {
	    d = max + 1;
	    goto cleanup;
	}

	/* Change the location of ic in the dictionary to be "i" since
	   that is now the most recent example of it. Notice this sets
	   i > 0 always, even for the first character. */
	[% dic %]_set (dic, ic, i);
    }

    d = matrix[len1 + 1][len2 + 1];

    cleanup:

#ifndef STACKALLOCOK
    for (i = 0; i < size1; i++) {
	FREE (matrix[i]);
	matrix[i] = 0;
    }
    FREE (matrix);
#endif /* STACKALLOCOK */

    return d;
}