/*  Copyright (C) Wolfgang Menzel, Universität Hamburg, 2003-06-27

    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License
    as published by the Free Software Foundation; either version 2
    of the License, or (at your option) any later version.
*/

%%% elastic list comparison using Levenshtein metric

:- nl.
:- write_ln('matching of two lists, computes a string edit distance').
:- write_ln('returns all matchings').
:- write_ln('call: ?- match([a,b,c],[b,c,a],D).').
:- nl.

% match(+List1,+List2,?Distance) :-
% wrapper, calls match/4
match(L1,L2,Dist) :-
% compute a string mapping
  match(L1,L2,0,Dist).


% match(+List1,+List2,+OldDistance,?NewDistance)

match([],[],Dist,Dist).
% both lists are empty

match([],[_|R],Dist,DistNew) :-
% the first list is empty, assume an insertion and
% process the tail of the other
  Dist1 is Dist+1,
  match([],R,Dist1,DistNew).

match([_|R],[],Dist,DistNew) :-
% the second list is empty, assume an omission and
% process the tail of the other
  Dist1 is Dist+1,
  match(R,[],Dist1,DistNew).

match([H|R1],[H|R2],Dist,DistNew) :-
% the heads are equal, assume no error and compare the tails
  match(R1,R2,Dist,DistNew).

match([H1|R1],[H2|R2],Dist,DistNew) :-
% the heads are not equal, assume a substitution and compare the tails
  H1\=H2,
  Dist1 is Dist+1,
  match(R1,R2,Dist1,DistNew).

% the heads are not equal, assume an insertion and compare the tails
match([H1|R1],[H2|R2],Dist,DistNew) :-
% the heads are not equal, assume an insertion and compare the tails
  H1\=H2,
  Dist1 is Dist+1,
  match([H1|R1],R2,Dist1,DistNew).

match([H1|R1],[H2|R2],Dist,DistNew) :-
% the heads are not equal, assume an omission and compare the tails
  H1\=H2,
  Dist1 is Dist+1,
  match(R1,[H2|R2],Dist1,DistNew).