summaryrefslogtreecommitdiff
path: root/src/main/java/cuchaz/enigma/utils/search
diff options
context:
space:
mode:
authorGravatar Runemoro2020-06-03 13:39:42 -0400
committerGravatar GitHub2020-06-03 18:39:42 +0100
commit0f47403d0220757fed189b76e2071e25b1025cb8 (patch)
tree879bf72c4476f0a5e0d82da99d7ff2b2276bcaca /src/main/java/cuchaz/enigma/utils/search
parentFix search dialog hanging for a short time sometimes (#250) (diff)
downloadenigma-fork-0f47403d0220757fed189b76e2071e25b1025cb8.tar.gz
enigma-fork-0f47403d0220757fed189b76e2071e25b1025cb8.tar.xz
enigma-fork-0f47403d0220757fed189b76e2071e25b1025cb8.zip
Split GUI code to separate module (#242)
* Split into modules * Post merge compile fixes Co-authored-by: modmuss50 <modmuss50@gmail.com>
Diffstat (limited to 'src/main/java/cuchaz/enigma/utils/search')
-rw-r--r--src/main/java/cuchaz/enigma/utils/search/SearchEntry.java17
-rw-r--r--src/main/java/cuchaz/enigma/utils/search/SearchUtil.java268
2 files changed, 0 insertions, 285 deletions
diff --git a/src/main/java/cuchaz/enigma/utils/search/SearchEntry.java b/src/main/java/cuchaz/enigma/utils/search/SearchEntry.java
deleted file mode 100644
index 48b255f..0000000
--- a/src/main/java/cuchaz/enigma/utils/search/SearchEntry.java
+++ /dev/null
@@ -1,17 +0,0 @@
1package cuchaz.enigma.utils.search;
2
3import java.util.List;
4
5public interface SearchEntry {
6
7 List<String> getSearchableNames();
8
9 /**
10 * Returns a type that uniquely identifies this search entry across possible changes.
11 * This is used for tracking the amount of times this entry has been selected.
12 *
13 * @return a unique identifier for this search entry
14 */
15 String getIdentifier();
16
17}
diff --git a/src/main/java/cuchaz/enigma/utils/search/SearchUtil.java b/src/main/java/cuchaz/enigma/utils/search/SearchUtil.java
deleted file mode 100644
index a51afbb..0000000
--- a/src/main/java/cuchaz/enigma/utils/search/SearchUtil.java
+++ /dev/null
@@ -1,268 +0,0 @@
1package cuchaz.enigma.utils.search;
2
3import java.util.*;
4import java.util.concurrent.Executor;
5import java.util.concurrent.Executors;
6import java.util.concurrent.atomic.AtomicBoolean;
7import java.util.concurrent.atomic.AtomicInteger;
8import java.util.concurrent.locks.Lock;
9import java.util.concurrent.locks.ReentrantLock;
10import java.util.function.BiFunction;
11import java.util.stream.Collectors;
12import java.util.stream.Stream;
13
14import cuchaz.enigma.utils.Pair;
15
16public class SearchUtil<T extends SearchEntry> {
17
18 private final Map<T, Entry<T>> entries = new HashMap<>();
19 private final Map<String, Integer> hitCount = new HashMap<>();
20 private final Executor searchExecutor = Executors.newWorkStealingPool();
21
22 public void add(T entry) {
23 Entry<T> e = Entry.from(entry);
24 entries.put(entry, e);
25 }
26
27 public void add(Entry<T> entry) {
28 entries.put(entry.searchEntry, entry);
29 }
30
31 public void addAll(Collection<T> entries) {
32 this.entries.putAll(entries.parallelStream().collect(Collectors.toMap(e -> e, Entry::from)));
33 }
34
35 public void remove(T entry) {
36 entries.remove(entry);
37 }
38
39 public void clear() {
40 entries.clear();
41 }
42
43 public void clearHits() {
44 hitCount.clear();
45 }
46
47 public Stream<T> search(String term) {
48 return entries.values().parallelStream()
49 .map(e -> new Pair<>(e, e.getScore(term, hitCount.getOrDefault(e.searchEntry.getIdentifier(), 0))))
50 .filter(e -> e.b > 0)
51 .sorted(Comparator.comparingDouble(o -> -o.b))
52 .map(e -> e.a.searchEntry)
53 .sequential();
54 }
55
56 public SearchControl asyncSearch(String term, SearchResultConsumer<T> consumer) {
57 Map<String, Integer> hitCount = new HashMap<>(this.hitCount);
58 Map<T, Entry<T>> entries = new HashMap<>(this.entries);
59 float[] scores = new float[entries.size()];
60 Lock scoresLock = new ReentrantLock();
61 AtomicInteger size = new AtomicInteger();
62 AtomicBoolean control = new AtomicBoolean(false);
63 AtomicInteger elapsed = new AtomicInteger();
64 for (Entry<T> value : entries.values()) {
65 searchExecutor.execute(() -> {
66 try {
67 if (control.get()) return;
68 float score = value.getScore(term, hitCount.getOrDefault(value.searchEntry.getIdentifier(), 0));
69 if (score <= 0) return;
70 score = -score; // sort descending
71 try {
72 scoresLock.lock();
73 if (control.get()) return;
74 int dataSize = size.getAndIncrement();
75 int index = Arrays.binarySearch(scores, 0, dataSize, score);
76 if (index < 0) {
77 index = ~index;
78 }
79 System.arraycopy(scores, index, scores, index + 1, dataSize - index);
80 scores[index] = score;
81 consumer.add(index, value.searchEntry);
82 } finally {
83 scoresLock.unlock();
84 }
85 } finally {
86 elapsed.incrementAndGet();
87 }
88 });
89 }
90
91 return new SearchControl() {
92 @Override
93 public void stop() {
94 control.set(true);
95 }
96
97 @Override
98 public boolean isFinished() {
99 return entries.size() == elapsed.get();
100 }
101
102 @Override
103 public float getProgress() {
104 return (float) elapsed.get() / entries.size();
105 }
106 };
107 }
108
109 public void hit(T entry) {
110 if (entries.containsKey(entry)) {
111 hitCount.compute(entry.getIdentifier(), (_id, i) -> i == null ? 1 : i + 1);
112 }
113 }
114
115 public static final class Entry<T extends SearchEntry> {
116
117 public final T searchEntry;
118 private final String[][] components;
119
120 private Entry(T searchEntry, String[][] components) {
121 this.searchEntry = searchEntry;
122 this.components = components;
123 }
124
125 public float getScore(String term, int hits) {
126 String ucTerm = term.toUpperCase(Locale.ROOT);
127 float maxScore = (float) Arrays.stream(components)
128 .mapToDouble(name -> getScoreFor(ucTerm, name))
129 .max().orElse(0.0);
130 return maxScore * (hits + 1);
131 }
132
133 /**
134 * Computes the score for the given <code>name</code> against the given search term.
135 *
136 * @param term the search term (expected to be upper-case)
137 * @param name the entry name, split at word boundaries (see {@link Entry#wordwiseSplit(String)})
138 * @return the computed score for the entry
139 */
140 private static float getScoreFor(String term, String[] name) {
141 int totalLength = Arrays.stream(name).mapToInt(String::length).sum();
142 float scorePerChar = 1f / totalLength;
143
144 // This map contains a snapshot of all the states the search has
145 // been in. The keys are the remaining characters of the search
146 // term, the values are the maximum scores for that remaining
147 // search term part.
148 Map<String, Float> snapshots = new HashMap<>();
149 snapshots.put(term, 0f);
150
151 // For each component, start at each existing snapshot, searching
152 // for the next longest match, and calculate the new score for each
153 // match length until the maximum. Then the new scores are put back
154 // into the snapshot map.
155 for (int componentIndex = 0; componentIndex < name.length; componentIndex++) {
156 String component = name[componentIndex];
157 float posMultiplier = (name.length - componentIndex) * 0.3f;
158 Map<String, Float> newSnapshots = new HashMap<>();
159 for (Map.Entry<String, Float> snapshot : snapshots.entrySet()) {
160 String remaining = snapshot.getKey();
161 float score = snapshot.getValue();
162 component = component.toUpperCase(Locale.ROOT);
163 int l = compareEqualLength(remaining, component);
164 for (int i = 1; i <= l; i++) {
165 float baseScore = scorePerChar * i;
166 float chainBonus = (i - 1) * 0.5f;
167 merge(newSnapshots, Collections.singletonMap(remaining.substring(i), score + baseScore * posMultiplier + chainBonus), Math::max);
168 }
169 }
170 merge(snapshots, newSnapshots, Math::max);
171 }
172
173 // Only return the score for when the search term was completely
174 // consumed.
175 return snapshots.getOrDefault("", 0f);
176 }
177
178 private static <K, V> void merge(Map<K, V> self, Map<K, V> source, BiFunction<V, V, V> combiner) {
179 source.forEach((k, v) -> self.compute(k, (_k, v1) -> v1 == null ? v : v == null ? v1 : combiner.apply(v, v1)));
180 }
181
182 public static <T extends SearchEntry> Entry<T> from(T e) {
183 String[][] components = e.getSearchableNames().parallelStream()
184 .map(Entry::wordwiseSplit)
185 .toArray(String[][]::new);
186 return new Entry<>(e, components);
187 }
188
189 private static int compareEqualLength(String s1, String s2) {
190 int len = 0;
191 while (len < s1.length() && len < s2.length() && s1.charAt(len) == s2.charAt(len)) {
192 len += 1;
193 }
194 return len;
195 }
196
197 /**
198 * Splits the given input into components, trying to detect word parts.
199 * <p>
200 * Example of how words get split (using <code>|</code> as seperator):
201 * <p><code>MinecraftClientGame -> Minecraft|Client|Game</code></p>
202 * <p><code>HTTPInputStream -> HTTP|Input|Stream</code></p>
203 * <p><code>class_932 -> class|_|932</code></p>
204 * <p><code>X11FontManager -> X|11|Font|Manager</code></p>
205 * <p><code>openHTTPConnection -> open|HTTP|Connection</code></p>
206 * <p><code>open_http_connection -> open|_|http|_|connection</code></p>
207 *
208 * @param input the input to split
209 * @return the resulting components
210 */
211 private static String[] wordwiseSplit(String input) {
212 List<String> list = new ArrayList<>();
213 while (!input.isEmpty()) {
214 int take;
215 if (Character.isLetter(input.charAt(0))) {
216 if (input.length() == 1) {
217 take = 1;
218 } else {
219 boolean nextSegmentIsUppercase = Character.isUpperCase(input.charAt(0)) && Character.isUpperCase(input.charAt(1));
220 if (nextSegmentIsUppercase) {
221 int nextLowercase = 1;
222 while (Character.isUpperCase(input.charAt(nextLowercase))) {
223 nextLowercase += 1;
224 if (nextLowercase == input.length()) {
225 nextLowercase += 1;
226 break;
227 }
228 }
229 take = nextLowercase - 1;
230 } else {
231 int nextUppercase = 1;
232 while (nextUppercase < input.length() && Character.isLowerCase(input.charAt(nextUppercase))) {
233 nextUppercase += 1;
234 }
235 take = nextUppercase;
236 }
237 }
238 } else if (Character.isDigit(input.charAt(0))) {
239 int nextNonNum = 1;
240 while (nextNonNum < input.length() && Character.isLetter(input.charAt(nextNonNum)) && !Character.isLowerCase(input.charAt(nextNonNum))) {
241 nextNonNum += 1;
242 }
243 take = nextNonNum;
244 } else {
245 take = 1;
246 }
247 list.add(input.substring(0, take));
248 input = input.substring(take);
249 }
250 return list.toArray(new String[0]);
251 }
252
253 }
254
255 @FunctionalInterface
256 public interface SearchResultConsumer<T extends SearchEntry> {
257 void add(int index, T entry);
258 }
259
260 public interface SearchControl {
261 void stop();
262
263 boolean isFinished();
264
265 float getProgress();
266 }
267
268}
HIC SVNT DRACONES