package com.wrox.algorithms.wmatch;

public class LevenshteinWordDistanceCalculator {
    /** domyślna instancja klasy */
    public static final LevenshteinWordDistanceCalculator DEFAULT = 
                                       new LevenshteinWordDistanceCalculator(1, 1, 1);

    /** jednostkowy koszt zastąpienia znaku */
    private final int _costOfSubstitution;

    /** jednostkowy koszt usunięcia znaku */
    private final int _costOfDeletion;

    /** jednostkowy koszt wstawienia znaku */
    private final int _costOfInsertion;

    public LevenshteinWordDistanceCalculator
             (int costOfSubstitution, int costOfDeletion, int costOfInsertion) {
        assert costOfSubstitution >= 0 : "koszt zastąpienia znaku nie może być ujemny";
        assert costOfDeletion >= 0 : "koszt usunięcia znaku nie może być ujemny";
        assert costOfInsertion >= 0 : "koszt wstawienia znaku nie może być ujemny";

        _costOfSubstitution = costOfSubstitution;
        _costOfDeletion = costOfDeletion;
        _costOfInsertion = costOfInsertion;
    }

    public int calculate(CharSequence source, CharSequence target) {
        assert source != null : "nie określono pierwszego słowa";
        assert target != null : "nie określono drugiego słowa";

        int sourceLength = source.length();
        int targetLength = target.length();

        int[][] grid = new int[sourceLength + 1][targetLength + 1];

        grid[0][0] = 0;

        for (int row = 1; row <= sourceLength; ++row) {
            grid[row][0] = row;
        }

        for (int col = 1; col <= targetLength; ++col) {
            grid[0][col] = col;
        }

        for (int row = 1; row <= sourceLength; ++row) {
            for (int col = 1; col <= targetLength; ++col) {
                grid[row][col] = minCost(source, target, grid, row, col);
            }
        }

        return grid[sourceLength][targetLength];
    }

    private int minCost
            (CharSequence source, CharSequence target, int[][] grid, int row, int col) {
        return min(
                substitutionCost(source, target, grid, row, col),
                deleteCost(grid, row, col),
                insertCost(grid, row, col)
        );
    }

    private int substitutionCost
            (CharSequence source, CharSequence target, int[][] grid, int row, int col) {
        int cost = 0;
        if (source.charAt(row - 1) != target.charAt(col - 1)) {
            cost = _costOfSubstitution;
        }
        return grid[row - 1][col - 1] + cost;
    }

    private int deleteCost(int[][] grid, int row, int col) {
        return grid[row - 1][col] + _costOfDeletion;
    }

    private int insertCost(int[][] grid, int row, int col) {
        return grid[row][col - 1] + _costOfInsertion;
    }

    private static int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}
