// Copyright (C) 2013  Julián Urbano <urbano.julian@gmail.com>
// 
// 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 3 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see http://www.gnu.org/licenses/.

package jurbano.melodyshape.comparison.alignment;

import java.util.ArrayList;

import jurbano.melodyshape.comparison.NGram;
import jurbano.melodyshape.comparison.NGramComparer;

/**
 * An implementation of the Smith-Waterman alignment algorithm for sequences of {@link NGram}s.
 * 
 * @author Julián Urbano
 * @see NGram
 * @see NGramComparer
 */
public class LocalAligner implements MelodyAligner
{	
	protected NGramComparer comparer;
		
	/**
	 * Constructs a new {@code LocalAligner} with the specified {@link NGramComparer}. 
	 * 
	 * @param comparer the n-gram comparer to use.
	 */
	public LocalAligner(NGramComparer comparer) {
		this.comparer = comparer;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @return the {@link String} {@code "Local(comparer)"}, where
	 *         {@code comparer} is the name of the underlying
	 *         {@link NGramComparer}.
	 */
	@Override
	public String getName() {
		return "Local("+this.comparer.getName()+")";
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public double align(ArrayList<NGram> s1, ArrayList<NGram> s2) {
		double[][] matrix = new double[s1.size() + 1][s2.size() + 1];
		
		for (int i = 1; i <= s1.size(); i++) {
			for (int j = 1; j <= s2.size(); j++) {
				double left = matrix[i - 1][j] + this.comparer.compare(s1.get(i - 1), null);
				double up = matrix[i][j - 1] + this.comparer.compare(null, s2.get(j - 1));
				double diag = matrix[i - 1][j - 1] + this.comparer.compare(s1.get(i - 1), s2.get(j - 1));
				matrix[i][j] = Math.max(0, Math.max(left, Math.max(up, diag)));
			}
		}
		
		return matrix[s1.size()][s2.size()];
	}
	
}

@@ -1881,24 +1881,62 @@
 () + 1%5D;%0D%0A%09%09
+double max = Double.NEGATIVE_INFINITY;
 %0D%0A%09%09for (int
@@ -2336,16 +2336,71 @@
 ag)));%0D%0A
+%09%09%09%09if (max %3C matrix%5Bi%5D%5Bj%5D)%0D%0A%09%09%09%09%09max = matrix%5Bi%5D%5Bj%5D;%0D%0A
 %09%09%09%7D%0D%0A%09%09
@@ -2417,21 +2417,29 @@
 eturn ma
-trix%5B
+x / Math.min(
 s1.size(
@@ -2439,18 +2439,18 @@
 1.size()
-%5D%5B
+, 
 s2.size(
@@ -2450,17 +2450,17 @@
 2.size()
-%5D
+)
 ;%0D%0A%09%7D%0D%0A%09

Update LocalAligner.java