/*  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
%%% computes only minimium error results
%%% returns an error description

%%% elastic list comparison using Levenshtein metric
%%% computes only minimium error results

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

% match(+List1,+List2,?Distance,?ErrorDescription) :-
% wrapper, calls match/5
match(L1,L2,Dist,_) :-
% compute a string mapping better than the current threshold
  flag(mindist,_,20000),
  retractall(errorlist(_)),
  match(L1,L2,0,Dist,[]),
  fail.

match(_,_,Dist,Errors) :-
% unable to find a better matching, return the error description
% stored in the data base
  flag(mindist,Dist,Dist),
  errorlist(Err),
  reverse(Err,Errors),
  retractall(errorlist(_)).

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

match([],[],Dist,Dist,Errors) :-
% both lists are empty, if the new distance is better than the
% old one, assert the new error description
  flag(mindist,MinDist,MinDist),
  (Dist<MinDist ->
     (flag(mindist,_,Dist),
      retractall(errorlist(_)),
      assert(errorlist(Errors))) ; true).

match([],[H|R],Dist,DistNew,Errors) :-
% the first list is empty, assume an insertion and
% process the tail of the other
  Dist1 is Dist+1,
  flag(mindist,MinDist,MinDist),
  Dist1<MinDist,
  match([],R,Dist1,DistNew,[[nil,H]|Errors]).

match([H|R],[],Dist,DistNew,Errors) :-
% the second list is empty, assume an omission and
% process the tail of the other
  Dist1 is Dist+1,
  flag(mindist,MinDist,MinDist),
  Dist1<MinDist,
  match(R,[],Dist1,DistNew,[[H,nil]|Errors]).

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

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

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

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