% vit_merge( tr, j, k, w_ii, v_cur, vl_cur, vp_cur) - path merging
%
function w = vit_merge( tr, j, k, w_ii, v_cur, vl_cur, vp_cur);

% This routine needs to be fixed for K>1.  RP, 12 Feb. 2000

global DEBUG;
global HUGE_VAL;

global K;
global M;
global N;

% w, path_index, el_index, and perm_index are local variables here

n_tr = j - tr;

LL = length( v_cur);

% normalize the costs
%
w = w_ii;

% w % , v_cur, vl_cur, vp_cur

if( all(w == HUGE_VAL) == 0)      % not all HUGE_VAL

  i_min = k * (w' ~= HUGE_VAL);
  l_min = [1:LL]';

  [path_index, el_index, perm_index] = vit_back( tr, j, i_min, l_min, v_cur, vl_cur, vp_cur);

  if( DEBUG)
    path_index, el_index
    if( K > 1)
      perm_index
    end
  end

  path_index = path_index';
  el_index = el_index';
  perm_index = perm_index';

  merge = zeros(1,LL);

  % determine paths to be merged
  %
  for el = 1:LL
    if( merge(el) == 0) % not already merged
      merge(el) = el;
      for i=el+1:LL
        if( K == 1)
          r = merge_equal( path_index(:,el), path_index(:,i));
        else
          r = merge_equal_perm( path_index(:,el), path_index(:,i), perm_index(:,el), perm_index(:,i));
        end
        if( r)
          merge(i) = el;
        end
      end
    end
  end % el  

  if( DEBUG) merge, end;

  % merge the paths
  %
  for el = 1:LL
    f = find( merge == el);
    nf = length(f);
    if( nf > 1)
      if( DEBUG) disp('merging'), f, end;
%
% make f(1) the lowest cost choice
%
      [junk i] = sort(w(f));
      f = f(i);
%
% to try merge by pruning comment out the next 4 lines
%
      min_w = w(f(1));
      p = exp(-(w(f)-min_w));
      merge_update( tr, j, f, p, path_index, el_index);       % merge kalman paths
      w(f(1)) = -log(sum(p)) + min_w;                         % accumulate probabilities

      w(f(2:nf)) = HUGE_VAL;                                  % mark absorbed states as unreachable

    end
  end

end % not all HUGE_VAL
