#include "common.h"
#include <stdio.h>

/* NOTE: It is important to assign 0 to NOP and 1 to SUBST */
#define NOP    0
#define SUBST  1
#define INSERT 2
#define DELETE 3

typedef struct {
    uint distance, operation;
} EDIT_INFO;

uint levenstein(char *s, char *t, EDIT_INFO **edit_info) {
    uint m = strlen(s), n = strlen(t), i, j, d, same;
    EDIT_INFO *e;

    edit_info[0][0].distance = 0;
    edit_info[0][0].operation = NOP;
    for (i = 1; i < m+1; i++) {
        edit_info[i][0].distance = i;
        edit_info[i][0].operation = DELETE;
    }
    for (j = 1; j < n+1; j++) {
        edit_info[0][j].distance = j;
        edit_info[0][j].operation = INSERT;
    }

    for (i = 1; i < m+1; i++) {
        for (j = 1; j < n+1; j++) {
            e = &edit_info[i][j];
            e->distance = edit_info[i-1][j].distance + 1;
            e->operation = DELETE;

            if (edit_info[i][j-1].distance + 1 < e->distance) {
                e->distance = edit_info[i][j-1].distance + 1;
                e->operation = INSERT;
            }

            same = (s[i-1] == t[j-1]) ? 1 : 0;
            d = edit_info[i-1][j-1].distance + (1-same); 
            if (d < e->distance) {
                e->distance = d;
                e->operation = 1-same; // see note before #define NOP, SUBST, etc.
            }
        }
    }

    return edit_info[m][n].distance;
}


int main(int ac, char *av[])
{
    char *s, *t;
    uint m, n, d, *ops;
    int i, j, k;
    EDIT_INFO **edit_info;

    if (ac != 3)
        ERR_MESG("Usage: levenstein <str1> <str2>");

    s = av[1]; t = av[2];
    m = strlen(s), n = strlen(t);

    matrix_alloc(edit_info, (m+1), (n+1), EDIT_INFO);

    d = levenstein(s, t, edit_info);
#ifdef DEBUG
    printf("Distances\n");
    for (i = 0; i < m+1; i++) {
        for (j = 0; j < n+1; j++)
            printf("%3d ", edit_info[i][j].distance);
        putchar('\n');
    }

    printf("Operations\n");
    for (i = 0; i < m+1; i++) {
        for (j = 0; j < n+1; j++)
            printf("%3d ", edit_info[i][j].operation);
        putchar('\n');
    }
#endif // DEBUG

    /* Output */
    printf("Edit distance(%s, %s) = %u\n", s, t, d);

    if (NULL == (ops = Malloc(m+n, uint))) // I think this is actually unnecessarily conservative
        ERR_MESG("levenstein: out of memory\n");
    for (i = m, j = n, k = 0; i>=1 || j>=1; k++) {
        ops[k] = edit_info[i][j].operation;
        switch (ops[k]) {
        case INSERT:
            j--; break;
        case DELETE:
            i--; break;
        case NOP:
        case SUBST:
            i--, j--; break;
        default:
            fprintf(stderr, "Unknown operation %u\n", ops[k]);
            exit(1);
        }
    }
    //fprintf(stderr, "k = %d\n", k++);

    for (i = j = 0, k--; k >= 0; k--)
        switch (ops[k]) {
        case INSERT:
            printf("_\tI\t%c\n", t[j++]);
            break;
        case DELETE:
            printf("%c\tD\t_\n", s[i++]);
            break;
        case NOP:
            printf("%c\t=\t%c\n", s[i++], t[j++]);
            break;
        case SUBST:
            printf("%c\tS\t%c\n", s[i++], t[j++]);
            break;
    }
    //fprintf(stderr, "i = %d\nj = %d\nm = %d\nn = %d\n", i, j, m, n);
    assert(i == m && j == n);

    matrix_free(edit_info); free(ops);
    return 0;
}