1/*
2 * Copyright 2002-2005 The Apache Software Foundation.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 *
16 * NOTE: This class has been stripped down to the Levenshtein distance
17 * algorithm alone (Amin Ahmad).
18 */
19package org.ahmadsoft.postal;
20
21
22/**
23 * A modified version of the original StringUtils.java to only include
24 * the Levenshtein distance algorithm.
25 */
26class StringUtils {
27
28    // Misc
29    //-----------------------------------------------------------------------
30    /**
31     * <p>Find the Levenshtein distance between two Strings.</p>
32     *
33     * <p>This is the number of changes needed to change one String into
34     * another, where each change is a single character modification (deletion,
35     * insertion or substitution).</p>
36     *
37     * <p>This implementation of the Levenshtein distance algorithm
38     * is from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a></p>
39     *
40     * <pre>
41     * StringUtils.getLevenshteinDistance(null, *)             = IllegalArgumentException
42     * StringUtils.getLevenshteinDistance(*, null)             = IllegalArgumentException
43     * StringUtils.getLevenshteinDistance("","")               = 0
44     * StringUtils.getLevenshteinDistance("","a")              = 1
45     * StringUtils.getLevenshteinDistance("aaapppp", "")       = 7
46     * StringUtils.getLevenshteinDistance("frog", "fog")       = 1
47     * StringUtils.getLevenshteinDistance("fly", "ant")        = 3
48     * StringUtils.getLevenshteinDistance("elephant", "hippo") = 7
49     * StringUtils.getLevenshteinDistance("hippo", "elephant") = 7
50     * StringUtils.getLevenshteinDistance("hippo", "zzzzzzzz") = 8
51     * StringUtils.getLevenshteinDistance("hello", "hallo")    = 1
52     * </pre>
53     *
54     * @param s  the first String, must not be null
55     * @param t  the second String, must not be null
56     * @return result distance
57     * @throws IllegalArgumentException if either String input <code>null</code>
58     */
59    public static int getLevenshteinDistance(String s, String t) {
60        if (s == null || t == null) {
61            throw new IllegalArgumentException("Strings must not be null");
62        }
63        int d[][]; // matrix
64        int n; // length of s
65        int m; // length of t
66        int i; // iterates through s
67        int j; // iterates through t
68        char s_i; // ith character of s
69        char t_j; // jth character of t
70        int cost; // cost
71
72        // Step 1
73        n = s.length();
74        m = t.length();
75        if (n == 0) {
76            return m;
77        }
78        if (m == 0) {
79            return n;
80        }
81        d = new int[n + 1][m + 1];
82
83        // Step 2
84        for (i = 0; i <= n; i++) {
85            d[i][0] = i;
86        }
87
88        for (j = 0; j <= m; j++) {
89            d[0][j] = j;
90        }
91
92        // Step 3
93        for (i = 1; i <= n; i++) {
94            s_i = s.charAt(i - 1);
95
96            // Step 4
97            for (j = 1; j <= m; j++) {
98                t_j = t.charAt(j - 1);
99
100                // Step 5
101                if (s_i == t_j) {
102                    cost = 0;
103                } else {
104                    cost = 1;
105                }
106
107                // Step 6
108                d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
109            }
110        }
111
112        // Step 7
113        return d[n][m];
114    }
115
116    /**
117     * <p>Gets the minimum of three <code>int</code> values.</p>
118     *
119     * @param a  value 1
120     * @param b  value 2
121     * @param c  value 3
122     * @return  the smallest of the values
123     */
124    private static int min(int a, int b, int c) {
125        // Method copied from NumberUtils to avoid dependency on subpackage
126        if (b < a) {
127            a = b;
128        }
129        if (c < a) {
130            a = c;
131        }
132        return a;
133    }
134
135}
136