#line 2 "edit-distance.c.tmpl"
#include <string.h>
#include <stdio.h>
/* For INT_MAX/INT_MIN */
#include <limits.h>
/* For malloc. */
#include <stdlib.h>

#include "config.h"
#include "text-fuzzy.h"
#include "edit-distance-char-trans.h"
#line 14 "edit-distance.c.tmpl"


/* Our unsorted dictionary linked list.       */

struct dictionary {
    unsigned char key;    /* the character        */
    unsigned int value;  /* character occurance  */
    struct dictionary* next;
};

typedef struct dictionary item;

/* http://ppm4.activestate.com/sun4-solaris-64/5.12/1200/B/BK/BKB/Text-Fuzzy-0.11.d/log-20130328T025706.txt */

#ifdef __GNUC__
#define INLINE inline
#else
#define INLINE 
#endif

static INLINE item * push (unsigned int key, item * curr)
{
    item * head;
    head = malloc (sizeof (item));   
    head->key = key;
    head->value = 0;
    head->next = curr;
    return head;
}

static INLINE item * find (item * head, unsigned int key)
{
    item * iterator = head;
    while (iterator) {
	if (iterator->key == key){
	    return iterator;
	}
	iterator = iterator->next;
    }
    return NULL;
}

/* find & push in 1 function (sperg optimization) */

static INLINE item * uniquePush (item * head, unsigned int key)
{
    item * iterator = head;

    while(iterator){
	if(iterator->key == key){
	    return head;
	}
	iterator = iterator->next;
    }
    return push(key,head); 
}

/* Free the memory associated with "head". */

static void dict_free (item * head)
{
    item * iterator = head;
    while(iterator){
	item * temp = iterator;
	iterator = iterator->next;
	free(temp);
    }
    
    head = NULL;
}

static int minimum (int a, int b)
{
    if (a > b) {
	return b;
    }
    return a;
}


#line 1 "declaration"
int distance_char_trans (
                    text_fuzzy_t * tf)

{
#line 99 "edit-distance.c.tmpl"




#line 110 "edit-distance.c.tmpl"
    const unsigned char * word1 = (const unsigned char *) tf->b.text;
    int len1 = tf->b.length;
    const unsigned char * word2 = (const unsigned char *) tf->text.text;
    int len2 = tf->text.length;


    /* keep track of dictionary linked list position */

    item *head = NULL;

    unsigned int swapScore,targetCharCount,i;
    unsigned int score_ceil = len1 + len2;
#ifdef __GNUC__
    unsigned int matrix[len1 + 2][len2 + 2];
#else
    unsigned int ** matrix;
    int d;
#endif

#ifndef __GNUC__
    matrix = calloc (len1 + 2, sizeof (unsigned int *));
    for (i = 0; i < len1 + 2; i++) {
	matrix[i] = calloc (len2 + 2, sizeof (unsigned int));
    }
#endif

    if (len1 == 0) {
	return len2;
    }
    if (len2 == 0) {
	return len1;
    }
 
    /* intialize matrix start values */

    matrix[0][0] = score_ceil;  
    matrix[1][0] = score_ceil;
    matrix[0][1] = score_ceil;
    matrix[1][1] = 0;

    head = uniquePush (uniquePush (head, word1[0]), word2[0]);

    for (i = 1; i <= len1; i++) { 
	int swapCount;
	int j;

	head = uniquePush (head, word1[i]);
	matrix[i+1][1] = i;
	matrix[i+1][0] = score_ceil;
	
	swapCount = 0;

	for (j = 1; j <= len2; j++){
	    if (i == 1) {
		/* only initialize on the first pass     */
		/* optimized over 2 additional for loops */
		head = uniquePush (head, word2[j]);
		matrix[1][j + 1] = j;
		matrix[0][j + 1] = score_ceil;
	    }

	    targetCharCount = find (head, word2[j-1])->value;

	    swapScore = matrix[targetCharCount][swapCount] + i - targetCharCount - 1 + j - swapCount;
	    
	    if(word1[i-1] != word2[j-1]){      
		matrix[i+1][j + 1] = minimum(swapScore,(minimum(matrix[i][j], minimum(matrix[i+1][j], matrix[i][j + 1])) + 1));
	    }
	    else{ 
		swapCount = j;
		matrix[i+1][j + 1] = minimum (matrix[i][j], swapScore);
	    } 
	}
	
	find (head, word1[i-1])->value = i;
    }

    dict_free (head);

#ifdef __GNUC__

    return matrix[len1 + 1][len2 + 1];

#else

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

    for (i = 0; i < len1 + 2; i++) {
	free (matrix[i]);
    }
    free (matrix);

    return d;

#endif

#line 372 "edit-distance.c.tmpl"
}