/*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
 * edit_dist.C - Example of how to compute edit distance.
 *
 * This code is copyrighted under the GPL by Sariel Har-Peled.
\*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/

#include  <stdlib.h>
#include  <stdio.h>
#include  <assert.h>
#include  <string.h>

#include  "cache.h"

/*--- Generic code ---*/

template <class  T>
T min( const T  &a, const T  & b ) {
    return  ( a < b )? a : b;
}


/*--- Start of Code ---*/

class  EditDistCalc
{
private:
    const char   * x;
    const char   * y;
    int            n_x, n_y;
    Cache2d<int>   cache;

    int  edit_dist( int  i_x, int  i_y );

public:
    EditDistCalc( const char  * _x, const char  * _y ) {
        x = _x;
        y = _y;
        n_x = strlen( x );
        n_y = strlen( y );
        cache.init( n_x + 1, n_y + 1 );
    }

    int  calculate() {
        return  edit_dist( n_x, n_y );
    }
};

int  EditDistCalc::edit_dist( int  i_x, int  i_y )
{
    if  ( i_x == 0 )
        return  i_y;
    if  ( i_y == 0 )
        return  i_x;
    
    if  ( cache.is_defined( i_x, i_y ) )
        return  cache.get( i_x, i_y );

    int  p_a, p_b, p_c, price;

    p_a = edit_dist( i_x, i_y - 1 ) + 1;
    p_b = edit_dist( i_x - 1, i_y ) + 1;
    price = min( p_a, p_b );

    p_c = edit_dist( i_x - 1, i_y - 1 );

    if  ( x[ i_x - 1 ] == y[ i_y - 1 ] ) 
        price = min( price, p_c );
    else
        price = min( price, p_c + 1 );

    cache.set( i_x, i_y, price );

    return  price;
}


int   edit_distance( const char   * x, const char  * y )
{
    EditDistCalc   edc( x, y );

    return  edc.calculate();
}


int  main( int  argc, char  ** argv )
{
    if  ( argc != 3 ) {
        printf( "edit_distance [str1] [str2]\n" );
        exit( -1 );
    }
    printf( "String x      : [%s]\n"
            "String y      : [%s]\n"
            "Edit distance : %d\n", 
            argv[ 1 ],
            argv[ 2 ],
            edit_distance( argv[ 1 ], argv[ 2 ] ) );

    return  0;
}

/* edit_dist.C - End of File ------------------------------------------*/