// 
// Decompiled by Procyon v0.6.0
// 

package org.jline.utils;

import java.util.Map;
import java.util.HashMap;

public class Levenshtein
{
    public static int distance(final CharSequence lhs, final CharSequence rhs) {
        return distance(lhs, rhs, 1, 1, 1, 1);
    }
    
    public static int distance(final CharSequence source, final CharSequence target, final int deleteCost, final int insertCost, final int replaceCost, final int swapCost) {
        if (2 * swapCost < insertCost + deleteCost) {
            throw new IllegalArgumentException("Unsupported cost assignment");
        }
        if (source.length() == 0) {
            return target.length() * insertCost;
        }
        if (target.length() == 0) {
            return source.length() * deleteCost;
        }
        final int[][] table = new int[source.length()][target.length()];
        final Map<Character, Integer> sourceIndexByCharacter = new HashMap<Character, Integer>();
        if (source.charAt(0) != target.charAt(0)) {
            table[0][0] = Math.min(replaceCost, deleteCost + insertCost);
        }
        sourceIndexByCharacter.put(source.charAt(0), 0);
        for (int i = 1; i < source.length(); ++i) {
            final int deleteDistance = table[i - 1][0] + deleteCost;
            final int insertDistance = (i + 1) * deleteCost + insertCost;
            final int matchDistance = i * deleteCost + ((source.charAt(i) == target.charAt(0)) ? 0 : replaceCost);
            table[i][0] = Math.min(Math.min(deleteDistance, insertDistance), matchDistance);
        }
        for (int j = 1; j < target.length(); ++j) {
            final int deleteDistance = (j + 1) * insertCost + deleteCost;
            final int insertDistance = table[0][j - 1] + insertCost;
            final int matchDistance = j * insertCost + ((source.charAt(0) == target.charAt(j)) ? 0 : replaceCost);
            table[0][j] = Math.min(Math.min(deleteDistance, insertDistance), matchDistance);
        }
        for (int i = 1; i < source.length(); ++i) {
            int maxSourceLetterMatchIndex = (source.charAt(i) == target.charAt(0)) ? 0 : -1;
            for (int k = 1; k < target.length(); ++k) {
                final Integer candidateSwapIndex = sourceIndexByCharacter.get(target.charAt(k));
                final int jSwap = maxSourceLetterMatchIndex;
                final int deleteDistance2 = table[i - 1][k] + deleteCost;
                final int insertDistance2 = table[i][k - 1] + insertCost;
                int matchDistance2 = table[i - 1][k - 1];
                if (source.charAt(i) != target.charAt(k)) {
                    matchDistance2 += replaceCost;
                }
                else {
                    maxSourceLetterMatchIndex = k;
                }
                int swapDistance;
                if (candidateSwapIndex != null && jSwap != -1) {
                    final int iSwap = candidateSwapIndex;
                    int preSwapCost;
                    if (iSwap == 0 && jSwap == 0) {
                        preSwapCost = 0;
                    }
                    else {
                        preSwapCost = table[Math.max(0, iSwap - 1)][Math.max(0, jSwap - 1)];
                    }
                    swapDistance = preSwapCost + (i - iSwap - 1) * deleteCost + (k - jSwap - 1) * insertCost + swapCost;
                }
                else {
                    swapDistance = Integer.MAX_VALUE;
                }
                table[i][k] = Math.min(Math.min(Math.min(deleteDistance2, insertDistance2), matchDistance2), swapDistance);
            }
            sourceIndexByCharacter.put(source.charAt(i), i);
        }
        return table[source.length() - 1][target.length() - 1];
    }
}