[Bleeding] Moved HelpTopicComparator to Bukkit.jar. Addresses BUKKIT-1193

2 files changed, 139 insertions, 2 deletions

diff --git a/src/main/java/org/bukkit/command/defaults/HelpCommand.java b/src/main/java/org/bukkit/command/defaults/HelpCommand.java
index 90523823..a85babb2 100644
--- a/src/main/java/org/bukkit/command/defaults/HelpCommand.java
+++ b/src/main/java/org/bukkit/command/defaults/HelpCommand.java
@@ -9,9 +9,11 @@ import org.bukkit.command.CommandSender;
 import org.bukkit.command.ConsoleCommandSender;
 import org.bukkit.help.HelpMap;
 import org.bukkit.help.HelpTopic;
+import org.bukkit.help.HelpTopicComparator;
+import org.bukkit.help.IndexHelpTopic;
 import org.bukkit.util.ChatPaginator;
 
-import java.util.Arrays;
+import java.util.*;
 
 public class HelpCommand extends VanillaCommand {
     public HelpCommand() {
@@ -48,13 +50,17 @@ public class HelpCommand extends VanillaCommand {
             pageHeight = ChatPaginator.CLOSED_CHAT_PAGE_HEIGHT - 1;
             pageWidth = ChatPaginator.GUARANTEED_NO_WRAP_CHAT_PAGE_WIDTH;
         }
-        
+
         HelpMap helpMap = Bukkit.getServer().getHelpMap();
         HelpTopic topic = helpMap.getHelpTopic(command);
 
         if (topic == null) {
             topic = helpMap.getHelpTopic("/" + command);
         }
+        
+        if (topic == null) {
+            topic = findPossibleMatches(command);
+        }
 
         if (topic == null || !topic.canSee(sender)) {
             sender.sendMessage(ChatColor.RED + "No help for " + command);
@@ -92,4 +98,89 @@ public class HelpCommand extends VanillaCommand {
     public boolean matches(String input) {
         return input.startsWith("help") || input.startsWith("?");
     }
+
+    protected HelpTopic findPossibleMatches(String searchString) {
+        int maxDistance = (searchString.length() / 5) + 3;
+        Set<HelpTopic> possibleMatches = new TreeSet<HelpTopic>(HelpTopicComparator.helpTopicComparatorInstance());
+        
+        if (searchString.startsWith("/")) {
+            searchString = searchString.substring(1);
+        }
+        
+        for (HelpTopic topic : Bukkit.getServer().getHelpMap().getHelpTopics()) {
+            String trimmedTopic = topic.getName().startsWith("/") ? topic.getName().substring(1) : topic.getName();
+            
+            if (trimmedTopic.length() < searchString.length()) {
+                continue;
+            }
+            
+            if (Character.toLowerCase(trimmedTopic.charAt(0)) != Character.toLowerCase(searchString.charAt(0))) {
+                continue;
+            }
+            
+            if (damerauLevenshteinDistance(searchString, trimmedTopic.substring(0, searchString.length())) < maxDistance) {
+                possibleMatches.add(topic);
+            }
+        }
+        
+        if (possibleMatches.size() > 0) {
+            return new IndexHelpTopic("Search", null, null, possibleMatches, "Search for: " + searchString);
+        } else {
+            return null;
+        }
+    }    
+    
+    /**
+     * Computes the Dameraur-Levenshtein Distance between two strings. Adapted from the algorithm at
+     * http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance
+     *
+     * @param s1 The first string being compared.
+     * @param s2 The second string being compared.
+     * @return The number of substitutions, deletions, insertions, and transpositions required to get from s1 to s2.
+     */
+    protected static int damerauLevenshteinDistance(String s1, String s2) {
+        if (s1 == null && s2 == null) return 0;
+        if (s1 != null && s2 == null) return s1.length();
+        if (s1 == null && s2 != null) return s2.length();
+
+        int s1Len = s1.length();
+        int s2Len = s2.length();
+        int[][] H = new int[s1Len + 2][s2Len + 2];
+
+        int INF = s1Len + s2Len;
+        H[0][0] = INF;
+        for (int i = 0; i <= s1Len; i++) {
+            H[i + 1][1] = i;
+            H[i + 1][0] = INF;
+        }
+        for (int j = 0; j <= s2Len; j++) {
+            H[1][j + 1] = j;
+            H[0][j + 1] = INF;
+        }
+
+        Map<Character, Integer> sd = new HashMap<Character, Integer>();
+        for (char Letter : (s1 + s2).toCharArray()) {
+            if (!sd.containsKey(Letter)) sd.put(Letter, 0);
+        }
+
+        for (int i = 1; i <= s1Len; i++) {
+            int DB = 0;
+            for (int j = 1; j <= s2Len; j++) {
+                int i1 = sd.get(s2.charAt(j - 1));
+                int j1 = DB;
+
+                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
+                    H[i + 1][j + 1] = H[i][j];
+                    DB = j;
+                } else {
+                    H[i + 1][j + 1] = Math.min(H[i][j], Math.min(H[i + 1][j], H[i][j + 1])) + 1;
+                }
+
+                H[i + 1][j + 1] = Math.min(H[i + 1][j + 1], H[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1));
+            }
+            sd.put(s1.charAt(i - 1), i);
+        }
+
+        return H[s1Len + 1][s2Len + 1];
+    }
 }
diff --git a/src/main/java/org/bukkit/help/HelpTopicComparator.java b/src/main/java/org/bukkit/help/HelpTopicComparator.java
new file mode 100644
index 00000000..5ab094c0
--- /dev/null
+++ b/src/main/java/org/bukkit/help/HelpTopicComparator.java
@@ -0,0 +1,46 @@
+package org.bukkit.help;
+
+import org.bukkit.help.HelpTopic;
+
+import java.util.Comparator;
+
+/**
+ * Used to impose a custom total ordering on help topics. All topics are listed in alphabetic order, but topics
+ * that start with a slash come after topics that don't.
+ */
+public class HelpTopicComparator implements Comparator<HelpTopic> {
+    
+    // Singleton implementations
+    private static final TopicNameComparator tnc = new TopicNameComparator();
+    public static TopicNameComparator topicNameComparatorInstance() {
+        return tnc;
+    }
+    
+    private static final HelpTopicComparator htc = new HelpTopicComparator();
+    public static HelpTopicComparator helpTopicComparatorInstance() {
+        return htc;
+    }
+    
+    private HelpTopicComparator() {}
+
+    public int compare(HelpTopic lhs, HelpTopic rhs) {
+        return tnc.compare(lhs.getName(), rhs.getName());
+    }
+
+    public static class TopicNameComparator implements Comparator<String> {
+        private TopicNameComparator(){}
+        
+        public int compare(String lhs, String rhs) {
+            boolean lhsStartSlash = lhs.startsWith("/");
+            boolean rhsStartSlash = rhs.startsWith("/");
+            
+            if (lhsStartSlash && !rhsStartSlash) {
+                return 1;
+            } else if (!lhsStartSlash && rhsStartSlash) {
+                return -1;
+            } else {
+                return lhs.compareToIgnoreCase(rhs);
+            }
+        }
+    }
+}