/*******************************************************************************
 * Copyright (c) 2000, 2003 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials 
 * are made available under the terms of the Common Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/cpl-v10.html
 * 
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/

package net.sourceforge.phpdt.internal.ui.text.spelling.engine;

/**
 * Default phonetic distance algorithm for english words.
 * <p>
 * This algorithm implements the Levenshtein text edit distance.
 * </p>
 * 
 * @since 3.0
 */
public final class DefaultPhoneticDistanceAlgorithm implements
		IPhoneticDistanceAlgorithm {

	/** The change case cost */
	public static final int COST_CASE = 10;

	/** The insert character cost */
	public static final int COST_INSERT = 95;

	/** The remove character cost */
	public static final int COST_REMOVE = 95;

	/** The substitute characters cost */
	public static final int COST_SUBSTITUTE = 100;

	/** The swap characters cost */
	public static final int COST_SWAP = 90;

	/*
	 * @see org.eclipse.spelling.done.IPhoneticDistanceAlgorithm#getDistance(java.lang.String,java.lang.String)
	 */
	public final int getDistance(final String from, final String to) {

		final char[] first = (" " + from).toCharArray(); //$NON-NLS-1$
		final char[] second = (" " + to).toCharArray(); //$NON-NLS-1$

		final int rows = first.length;
		final int columns = second.length;

		final int[][] metric = new int[rows][columns];
		for (int column = 1; column < columns; column++)
			metric[0][column] = metric[0][column - 1] + COST_REMOVE;

		for (int row = 1; row < rows; row++)
			metric[row][0] = metric[row - 1][0] + COST_INSERT;

		char source, target;

		int swap = Integer.MAX_VALUE;
		int change = Integer.MAX_VALUE;

		int minimum, diagonal, insert, remove;
		for (int row = 1; row < rows; row++) {

			source = first[row];
			for (int column = 1; column < columns; column++) {

				target = second[column];
				diagonal = metric[row - 1][column - 1];

				if (source == target) {
					metric[row][column] = diagonal;
					continue;
				}

				change = Integer.MAX_VALUE;
				if (Character.toLowerCase(source) == Character
						.toLowerCase(target))
					change = COST_CASE + diagonal;

				swap = Integer.MAX_VALUE;
				if (row != 1 && column != 1 && source == second[column - 1]
						&& first[row - 1] == target)
					swap = COST_SWAP + metric[row - 2][column - 2];

				minimum = COST_SUBSTITUTE + diagonal;
				if (swap < minimum)
					minimum = swap;

				remove = metric[row][column - 1];
				if (COST_REMOVE + remove < minimum)
					minimum = COST_REMOVE + remove;

				insert = metric[row - 1][column];
				if (COST_INSERT + insert < minimum)
					minimum = COST_INSERT + insert;
				if (change < minimum)
					minimum = change;

				metric[row][column] = minimum;
			}
		}
		return metric[rows - 1][columns - 1];
	}
}