8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package com.sun.xml.internal.bind.v2.util;
  27 
  28 import java.util.Collection;
  29 import java.util.Arrays;


  30 
  31 /**
  32  * Computes the string edit distance.
  33  *
  34  * <p>
  35  * Refer to a computer science text book for the definition
  36  * of the "string edit distance".
  37  *
  38  * @author
  39  *     Kohsuke Kawaguchi (kohsuke.kawaguchi@sun.com)
  40  */
  41 public class EditDistance {
  42 
  43     /**






  44      * Computes the edit distance between two strings.
  45      *
  46      * <p>
  47      * The complexity is O(nm) where n=a.length() and m=b.length().
  48      */
  49     public static int editDistance( String a, String b ) {
  50         return new EditDistance(a,b).calc();










  51     }
  52 
  53     /**
  54      * Finds the string in the <code>group</code> closest to
  55      * <code>key</code> and returns it.
  56      *
  57      * @return null if group.length==0.
  58      */
  59     public static String findNearest( String key, String[] group ) {
  60         return findNearest(key, Arrays.asList(group));
  61     }
  62 
  63     /**
  64      * Finds the string in the <code>group</code> closest to
  65      * <code>key</code> and returns it.
  66      *
  67      * @return null if group.length==0.
  68      */
  69     public static String findNearest( String key, Collection<String> group ) {
  70         int c = Integer.MAX_VALUE;

   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package com.sun.xml.internal.bind.v2.util;
  27 
  28 import java.util.AbstractMap;
  29 import java.util.Arrays;
  30 import java.util.Collection;
  31 import java.util.WeakHashMap;
  32 
  33 /**
  34  * Computes the string edit distance.
  35  *
  36  * <p>
  37  * Refer to a computer science text book for the definition
  38  * of the "string edit distance".
  39  *
  40  * @author
  41  *     Kohsuke Kawaguchi (kohsuke.kawaguchi@sun.com)
  42  */
  43 public class EditDistance {
  44 
  45     /**
  46      * Weak results cache to avoid additional computations.
  47      * Because of high complexity caching is required.
  48      */
  49     private static final WeakHashMap<AbstractMap.SimpleEntry<String,String>, Integer> CACHE = new WeakHashMap<AbstractMap.SimpleEntry<String, String>, Integer>();
  50 
  51     /**
  52      * Computes the edit distance between two strings.
  53      *
  54      * <p>
  55      * The complexity is O(nm) where n=a.length() and m=b.length().
  56      */
  57     public static int editDistance( String a, String b ) {
  58         // let's check cache
  59         AbstractMap.SimpleEntry<String,String> entry = new AbstractMap.SimpleEntry<String, String>(a, b); // using this class to avoid creation of my own which will handle PAIR of values
  60         Integer result = null;
  61         if (CACHE.containsKey(entry))
  62             result = CACHE.get(entry); // looks like we have it
  63 
  64         if (result == null) {
  65             result = new EditDistance(a, b).calc();
  66             CACHE.put(entry, result); // cache the result
  67         }
  68         return result;
  69     }
  70 
  71     /**
  72      * Finds the string in the <code>group</code> closest to
  73      * <code>key</code> and returns it.
  74      *
  75      * @return null if group.length==0.
  76      */
  77     public static String findNearest( String key, String[] group ) {
  78         return findNearest(key, Arrays.asList(group));
  79     }
  80 
  81     /**
  82      * Finds the string in the <code>group</code> closest to
  83      * <code>key</code> and returns it.
  84      *
  85      * @return null if group.length==0.
  86      */
  87     public static String findNearest( String key, Collection<String> group ) {
  88         int c = Integer.MAX_VALUE;