From 3a737b3a2789038814d141a0bbfe57eb4cc96da8 Mon Sep 17 00:00:00 2001 From: rmichela Date: Fri, 16 Mar 2012 03:42:01 -0400 Subject: [Bleeding] Moved HelpTopicComparator to Bukkit.jar. Addresses BUKKIT-1193 --- .../org/bukkit/command/defaults/HelpCommand.java | 95 +++++++++++++++++++++- .../java/org/bukkit/help/HelpTopicComparator.java | 46 +++++++++++ 2 files changed, 139 insertions(+), 2 deletions(-) create mode 100644 src/main/java/org/bukkit/help/HelpTopicComparator.java (limited to 'src/main/java') 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 possibleMatches = new TreeSet(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 sd = new HashMap(); + 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 { + + // 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 { + 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); + } + } + } +} -- cgit v1.2.3