From 0eff06096bc4852f2580f20a0c5bf970ecf66987 Mon Sep 17 00:00:00 2001 From: 2xsaiko Date: Wed, 29 Apr 2020 18:24:29 +0200 Subject: Rewrite search dialog (#233) * Fix searching * Make buttons use localization * Fix rename field opening when pressing shift+space * Tweak search algorithm * Add a bit of documentation * Remove duplicate example line * Use max() when building the inner map instead of overwriting the old value * Keep search dialog state * Formatting * Fix cursor key selection not scrolling to selected item * Don't set font size * Rename close0 to exit * Fix wrong scrolling when selecting search dialog entry--- .../cuchaz/enigma/utils/search/SearchEntry.java | 17 ++ .../cuchaz/enigma/utils/search/SearchUtil.java | 195 +++++++++++++++++++++ 2 files changed, 212 insertions(+) create mode 100644 src/main/java/cuchaz/enigma/utils/search/SearchEntry.java create mode 100644 src/main/java/cuchaz/enigma/utils/search/SearchUtil.java (limited to 'src/main/java/cuchaz/enigma/utils/search') diff --git a/src/main/java/cuchaz/enigma/utils/search/SearchEntry.java b/src/main/java/cuchaz/enigma/utils/search/SearchEntry.java new file mode 100644 index 0000000..48b255f --- /dev/null +++ b/src/main/java/cuchaz/enigma/utils/search/SearchEntry.java @@ -0,0 +1,17 @@ +package cuchaz.enigma.utils.search; + +import java.util.List; + +public interface SearchEntry { + + List getSearchableNames(); + + /** + * Returns a type that uniquely identifies this search entry across possible changes. + * This is used for tracking the amount of times this entry has been selected. + * + * @return a unique identifier for this search entry + */ + String getIdentifier(); + +} diff --git a/src/main/java/cuchaz/enigma/utils/search/SearchUtil.java b/src/main/java/cuchaz/enigma/utils/search/SearchUtil.java new file mode 100644 index 0000000..e5ed35f --- /dev/null +++ b/src/main/java/cuchaz/enigma/utils/search/SearchUtil.java @@ -0,0 +1,195 @@ +package cuchaz.enigma.utils.search; + +import java.util.*; +import java.util.function.BiFunction; +import java.util.stream.Collectors; +import java.util.stream.Stream; + +import cuchaz.enigma.utils.Pair; + +public class SearchUtil { + + private final Map> entries = new HashMap<>(); + private final Map hitCount = new HashMap<>(); + + public void add(T entry) { + Entry e = Entry.from(entry); + entries.put(entry, e); + } + + public void add(Entry entry) { + entries.put(entry.searchEntry, entry); + } + + public void addAll(Collection entries) { + this.entries.putAll(entries.parallelStream().collect(Collectors.toMap(e -> e, Entry::from))); + } + + public void remove(T entry) { + entries.remove(entry); + } + + public void clear() { + entries.clear(); + } + + public void clearHits() { + hitCount.clear(); + } + + public Stream search(String term) { + return entries.values().parallelStream() + .map(e -> new Pair<>(e, e.getScore(term, hitCount.getOrDefault(e.searchEntry.getIdentifier(), 0)))) + .filter(e -> e.b > 0) + .sorted(Comparator.comparingDouble(o -> -o.b)) + .map(e -> e.a.searchEntry) + .sequential(); + } + + public void hit(T entry) { + if (entries.containsKey(entry)) { + hitCount.compute(entry.getIdentifier(), (_id, i) -> i == null ? 1 : i + 1); + } + } + + public static final class Entry { + + public final T searchEntry; + private final String[][] components; + + private Entry(T searchEntry, String[][] components) { + this.searchEntry = searchEntry; + this.components = components; + } + + public float getScore(String term, int hits) { + String ucTerm = term.toUpperCase(Locale.ROOT); + float maxScore = (float) Arrays.stream(components) + .mapToDouble(name -> getScoreFor(ucTerm, name)) + .max().orElse(0.0); + return maxScore * (hits + 1); + } + + /** + * Computes the score for the given name against the given search term. + * + * @param term the search term (expected to be upper-case) + * @param name the entry name, split at word boundaries (see {@link Entry#wordwiseSplit(String)}) + * @return the computed score for the entry + */ + private static float getScoreFor(String term, String[] name) { + int totalLength = Arrays.stream(name).mapToInt(String::length).sum(); + float scorePerChar = 1f / totalLength; + + // This map contains a snapshot of all the states the search has + // been in. The keys are the remaining characters of the search + // term, the values are the maximum scores for that remaining + // search term part. + Map snapshots = new HashMap<>(); + snapshots.put(term, 0f); + + // For each component, start at each existing snapshot, searching + // for the next longest match, and calculate the new score for each + // match length until the maximum. Then the new scores are put back + // into the snapshot map. + for (int componentIndex = 0; componentIndex < name.length; componentIndex++) { + String component = name[componentIndex]; + float posMultiplier = (name.length - componentIndex) * 0.3f; + Map newSnapshots = new HashMap<>(); + for (Map.Entry snapshot : snapshots.entrySet()) { + String remaining = snapshot.getKey(); + float score = snapshot.getValue(); + component = component.toUpperCase(Locale.ROOT); + int l = compareEqualLength(remaining, component); + for (int i = 1; i <= l; i++) { + float baseScore = scorePerChar * i; + float chainBonus = (i - 1) * 0.5f; + merge(newSnapshots, Collections.singletonMap(remaining.substring(i), score + baseScore * posMultiplier + chainBonus), Math::max); + } + } + merge(snapshots, newSnapshots, Math::max); + } + + // Only return the score for when the search term was completely + // consumed. + return snapshots.getOrDefault("", 0f); + } + + private static void merge(Map self, Map source, BiFunction combiner) { + source.forEach((k, v) -> self.compute(k, (_k, v1) -> v1 == null ? v : v == null ? v1 : combiner.apply(v, v1))); + } + + public static Entry from(T e) { + String[][] components = e.getSearchableNames().parallelStream() + .map(Entry::wordwiseSplit) + .toArray(String[][]::new); + return new Entry<>(e, components); + } + + private static int compareEqualLength(String s1, String s2) { + int len = 0; + while (len < s1.length() && len < s2.length() && s1.charAt(len) == s2.charAt(len)) { + len += 1; + } + return len; + } + + /** + * Splits the given input into components, trying to detect word parts. + *

+ * Example of how words get split (using | as seperator): + *

MinecraftClientGame -> Minecraft|Client|Game

+ *

HTTPInputStream -> HTTP|Input|Stream

+ *

class_932 -> class|_|932

+ *

X11FontManager -> X|11|Font|Manager

+ *

openHTTPConnection -> open|HTTP|Connection

+ *

open_http_connection -> open|_|http|_|connection

+ * + * @param input the input to split + * @return the resulting components + */ + private static String[] wordwiseSplit(String input) { + List list = new ArrayList<>(); + while (!input.isEmpty()) { + int take; + if (Character.isLetter(input.charAt(0))) { + if (input.length() == 1) { + take = 1; + } else { + boolean nextSegmentIsUppercase = Character.isUpperCase(input.charAt(0)) && Character.isUpperCase(input.charAt(1)); + if (nextSegmentIsUppercase) { + int nextLowercase = 1; + while (Character.isUpperCase(input.charAt(nextLowercase))) { + nextLowercase += 1; + if (nextLowercase == input.length()) { + nextLowercase += 1; + break; + } + } + take = nextLowercase - 1; + } else { + int nextUppercase = 1; + while (nextUppercase < input.length() && Character.isLowerCase(input.charAt(nextUppercase))) { + nextUppercase += 1; + } + take = nextUppercase; + } + } + } else if (Character.isDigit(input.charAt(0))) { + int nextNonNum = 1; + while (nextNonNum < input.length() && Character.isLetter(input.charAt(nextNonNum)) && !Character.isLowerCase(input.charAt(nextNonNum))) { + nextNonNum += 1; + } + take = nextNonNum; + } else { + take = 1; + } + list.add(input.substring(0, take)); + input = input.substring(take); + } + return list.toArray(new String[0]); + } + + } + +} -- cgit v1.2.3