1.1 --- a/src/share/jaxws_classes/com/sun/xml/internal/bind/v2/util/EditDistance.java Thu Aug 08 10:10:38 2013 -0700
1.2 +++ b/src/share/jaxws_classes/com/sun/xml/internal/bind/v2/util/EditDistance.java Fri Aug 23 09:57:21 2013 +0100
1.3 @@ -25,8 +25,10 @@
1.4
1.5 package com.sun.xml.internal.bind.v2.util;
1.6
1.7 +import java.util.AbstractMap;
1.8 +import java.util.Arrays;
1.9 import java.util.Collection;
1.10 -import java.util.Arrays;
1.11 +import java.util.WeakHashMap;
1.12
1.13 /**
1.14 * Computes the string edit distance.
1.15 @@ -41,13 +43,29 @@
1.16 public class EditDistance {
1.17
1.18 /**
1.19 + * Weak results cache to avoid additional computations.
1.20 + * Because of high complexity caching is required.
1.21 + */
1.22 + private static final WeakHashMap<AbstractMap.SimpleEntry<String,String>, Integer> CACHE = new WeakHashMap<AbstractMap.SimpleEntry<String, String>, Integer>();
1.23 +
1.24 + /**
1.25 * Computes the edit distance between two strings.
1.26 *
1.27 * <p>
1.28 * The complexity is O(nm) where n=a.length() and m=b.length().
1.29 */
1.30 public static int editDistance( String a, String b ) {
1.31 - return new EditDistance(a,b).calc();
1.32 + // let's check cache
1.33 + 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
1.34 + Integer result = null;
1.35 + if (CACHE.containsKey(entry))
1.36 + result = CACHE.get(entry); // looks like we have it
1.37 +
1.38 + if (result == null) {
1.39 + result = new EditDistance(a, b).calc();
1.40 + CACHE.put(entry, result); // cache the result
1.41 + }
1.42 + return result;
1.43 }
1.44
1.45 /**
