-- Purpose:   Compute the minimal edit distance between two strings over a
--            given alphabet. Edit operations: insert, delete, replcae. 
--            All operations have the same cost.
-- Algorithm: The routine uses the O(m*n) dynamic programming solution
-- Reference: The algorithm is described in "Introduction to Algorithms", Udi
--            Manber
------------------------------------------------------------------------------
-- Design decsions:
--    We do not use String_Index directly for the internal matrix indexes, 
--    this allows us to add row and col 0.
--    This requires some translating to be done.    
------------------------------------------------------------------------------
--  Ehud Lamm, 1999
------------------------------------------------------------------------------

function Minimal_Edit_Distance (S1,S2:String_Type) return Natural is

   type Cost_Matrix is array(0..S1'length,0..S2'length) of Natural;

   C:Cost_Matrix;
   x,y,z:Integer;

begin
   for i in 0..S1'length loop
      C(i,0):=i;
   end loop;

   for j in 0..S2'length loop
      C(0,j):=j;
   end loop;

   for i in 1..S1'length loop
      for j in 1..S2'length loop
         x:=C(i-1,j)+1;
         y:=C(i,j-1)+1;
         if S1(String_Index'val(i-1+String_Index'Pos(S1'first)))=
            S2(String_Index'val(j-1+String_Index'Pos(S2'first)))
         then
            z:=C(i-1,j-1);
         else
            z:=C(i-1,j-1)+1;
         end if;

         C(i,j):=Integer'Min(Integer'Min(x,y),z);

      end loop;
   end loop;

   return C(S1'length,S2'length);

end Minimal_Edit_Distance;