1 package org.unicode.cldr.draft.keyboard; 2 3 import static com.google.common.base.Preconditions.checkArgument; 4 import static com.google.common.base.Preconditions.checkNotNull; 5 6 import java.util.EnumSet; 7 import java.util.Iterator; 8 import java.util.List; 9 import java.util.Set; 10 import java.util.TreeSet; 11 12 import com.google.common.base.Joiner; 13 import com.google.common.collect.ImmutableList; 14 import com.google.common.collect.ImmutableMap; 15 import com.google.common.collect.ImmutableSet; 16 import com.google.common.collect.ImmutableTable; 17 import com.google.common.collect.Lists; 18 import com.google.common.collect.Sets; 19 import com.google.common.collect.Sets.SetView; 20 21 /** 22 * A helper class which helps simplify single key combinations. That is, keys which come in a parent 23 * and child variants. 24 * 25 * The strategy used to build this simplification table was to minimize the number of terms in the 26 * boolean algebra by simplifying most keys into a "don't care (?)" state as much as possible. For 27 * example, to represent an empty combination of keys, we use "Parent = 0, Left Child = ?, Right 28 * Child = ?" as opposed to "Parent = 0, Left Child = 0, Right Child = 0". (See the table above for 29 * more details). Both forms are functionally equivalent but we feel that the first form is much 30 * simpler to represent. 31 */ 32 public final class ModifierKeySimplifier { 33 /** 34 * A mapping from input (given by a ON set and a DON'T CARE set) to the internal representation of 35 * the combination. The order is always {@code <PARENT><LEFT_CHILD><RIGHT_CHILD>}. 36 * <p> 37 * Notation: 38 * <ul> 39 * <li>"-" = Missing (not in any set) 40 * <li>"1" = In the ON set 41 * <li>"?" = In the DON'T CARE set 42 * <li>"0" = In the OFF set 43 * <ul> 44 */ 45 private static final ImmutableMap<String, String> INPUT_COMBINATION_TO_INTERNAL = ImmutableMap 46 .<String, String> builder().put("---", "0??").put("--1", "?01").put("--?", "?0?") 47 .put("-1-", "?10").put("-11", "?11").put("-1?", "?1?").put("-?-", "??0").put("-?1", "??1") 48 .put("-??", "???").put("1--", "1??").put("1-1", "??1").put("1-?", "1??").put("11-", "?1?") 49 .put("111", "?11").put("11?", "?1?").put("1?-", "1??").put("1?1", "??1").put("1??", "1??") 50 .put("?--", "???").put("?-1", "??1").put("?-?", "?0?").put("?1-", "?1?").put("?11", "?11") 51 .put("?1?", "?1?").put("??-", "??0").put("??1", "??1").put("???", "???").build(); 52 53 /** 54 * A mapping which maps the result of an OR between two combinations. Takes two combinations 55 * (represented in the internal notation) and returns the simplified combination (also in the 56 * internal notation). 57 * 58 * <p> 59 * For example, "A? AL" simplifies to "A?", "AL AL+AR" simplifies to "AL+AR?" and so on. The 60 * equivalence table is included in the document linked in the class header. 61 * 62 * <p> 63 * Notation: 64 * <ul> 65 * <li>"%" = No simplification possible, both combinations must stay. 66 * <li>"1" = In the ON set 67 * <li>"?" = In the DON'T CARE set 68 * <li>"0" = In the OFF set 69 * <ul> 70 */ 71 private static final ImmutableTable<String, String, String> COMBINATIONS_TO_SIMPLIFCATION = ImmutableTable 72 .<String, String, String> builder().put("1??", "0??", "???").put("?10", "0??", "??0") 73 .put("?1?", "0??", "%").put("??0", "0??", "??0").put("?11", "0??", "%") 74 .put("?01", "0??", "?0?").put("??1", "0??", "%").put("?0?", "0??", "?0?") 75 .put("???", "0??", "???").put("?10", "1??", "1??").put("?1?", "1??", "1??") 76 .put("??0", "1??", "???").put("?11", "1??", "1??").put("?01", "1??", "1??") 77 .put("??1", "1??", "1??").put("?0?", "1??", "???").put("???", "1??", "???") 78 .put("?1?", "?10", "?1?").put("??0", "?10", "??0").put("?11", "?10", "?1?") 79 .put("?01", "?10", "%").put("??1", "?10", "%").put("?0?", "?10", "%") 80 .put("???", "?10", "???").put("??0", "?1?", "%").put("?11", "?1?", "?1?") 81 .put("?01", "?1?", "%").put("??1", "?1?", "1??").put("?0?", "?1?", "???") 82 .put("???", "?1?", "???").put("?11", "??0", "%").put("?01", "??0", "%") 83 .put("??1", "??0", "???").put("?0?", "??0", "%").put("???", "??0", "???") 84 .put("?01", "?11", "??1").put("??1", "?11", "??1").put("?0?", "?11", "%") 85 .put("???", "?11", "???").put("??1", "?01", "??1").put("?0?", "?01", "?0?") 86 .put("???", "?01", "???").put("?0?", "??1", "%").put("???", "??1", "???") 87 .put("???", "?0?", "???").build(); 88 89 /** 90 * Given a set of ON keys and DON'T CARE keys, simplify and determine the internal representation 91 * of the combination. 92 */ 93 public static ModifierKeyCombination simplifyInput(Set<ModifierKey> onKeys, Set<ModifierKey> dontCareKeys) { 94 checkArgument(Sets.intersection(onKeys, dontCareKeys).size() == 0); 95 ImmutableSet.Builder<ModifierKey> onKeysBuilder = ImmutableSet.builder(); 96 ImmutableSet.Builder<ModifierKey> offKeysBuilder = ImmutableSet.builder(); 97 // Add parent keys and their children. 98 for (ModifierKey parentKey : ModifierKey.parents()) { 99 StringBuilder inputRepresentation = new StringBuilder(); 100 // Parent key. 101 inputRepresentation.append(getInputKeyState(parentKey, onKeys, dontCareKeys)); 102 // Children. 103 for (ModifierKey child : parentKey.children()) { 104 inputRepresentation.append(getInputKeyState(child, onKeys, dontCareKeys)); 105 } 106 // Get the internal representation 107 String result = INPUT_COMBINATION_TO_INTERNAL.get(inputRepresentation.toString()); 108 checkNotNull(result, "No internal mapping for %s", inputRepresentation); 109 // Transform the String representation into the internal representation and add them to the ON 110 // and OFF sets. 111 addInternalRepresentationFromString(parentKey, result, onKeysBuilder, offKeysBuilder); 112 } 113 // Add single keys. 114 for (ModifierKey singleKey : ModifierKey.singles()) { 115 if (onKeys.contains(singleKey)) { 116 onKeysBuilder.add(singleKey); 117 } else if (!dontCareKeys.contains(singleKey)) { 118 offKeysBuilder.add(singleKey); 119 } 120 } 121 return ModifierKeyCombination.of(onKeysBuilder.build(), offKeysBuilder.build()); 122 } 123 124 /** Find the state of the given modifier key by evaluating the given sets. */ 125 private static char getInputKeyState(ModifierKey modifierKey, Set<ModifierKey> onKeys, 126 Set<ModifierKey> dontCareKeys) { 127 return onKeys.contains(modifierKey) ? '1' : dontCareKeys.contains(modifierKey) ? '?' : '-'; 128 } 129 130 private static Joiner PLUS_JOINER = Joiner.on('+'); 131 132 /** 133 * Given a set of ON keys and OFF keys in the internal representation, simplify the combination 134 * and produce a string representing the combination in the format defined by the LDML Keyboard 135 * Standard. 136 * <p> 137 * Namely: 138 * <ul> 139 * <li>All keys are separated by a '+'. 140 * <li>All don't care keys are suffixed by a '?'. 141 * <li>ON keys are grouped together and are displayed first, followed by the don't care keys. 142 * <li>The modifier keys should be in the order defined in the standard within a group. 143 * <li>The combination should be in its simplest form. 144 * </ul> 145 */ 146 public static String simplifyToString(ModifierKeyCombination combination) { 147 ImmutableSet<ModifierKey> onKeys = combination.onKeys(); 148 ImmutableSet<ModifierKey> offKeys = combination.offKeys(); 149 TreeSet<ModifierKey> onKeysForOutput = Sets.newTreeSet(); 150 TreeSet<ModifierKey> dontCareKeysForOutput = Sets.newTreeSet(); 151 for (ModifierKey parentKey : ModifierKey.parents()) { 152 String result = getStringFromInternalRepresentation(parentKey, onKeys, offKeys); 153 char parentState = result.charAt(0); 154 char leftChildState = result.charAt(1); 155 char rightChildState = result.charAt(2); 156 // If both children are don't cares, output the parent only in its state (don't output the OFF 157 // ones). 158 if (leftChildState == '?' && rightChildState == '?') { 159 if (parentState == '1') { 160 onKeysForOutput.add(parentKey); 161 } else if (parentState == '?') { 162 dontCareKeysForOutput.add(parentKey); 163 } 164 } 165 // Otherwise, add the child keys in their states (don't output the OFF ones). 166 else { 167 ImmutableList<ModifierKey> children = parentKey.children(); 168 if (leftChildState == '1') { 169 onKeysForOutput.add(children.get(0)); 170 } else if (leftChildState == '?') { 171 dontCareKeysForOutput.add(children.get(0)); 172 } 173 if (rightChildState == '1') { 174 onKeysForOutput.add(children.get(1)); 175 } else if (rightChildState == '?') { 176 dontCareKeysForOutput.add(children.get(1)); 177 } 178 } 179 } 180 // Add single keys 181 for (ModifierKey singleKey : ModifierKey.singles()) { 182 if (onKeys.contains(singleKey)) { 183 onKeysForOutput.add(singleKey); 184 } else if (!offKeys.contains(singleKey)) { 185 dontCareKeysForOutput.add(singleKey); 186 } 187 } 188 // Join on-keys. 189 String onKeysString = PLUS_JOINER.join(onKeysForOutput); 190 // Join don't care keys. 191 List<String> dontCareKeysList = Lists.newArrayList(); 192 for (ModifierKey dontCareKey : dontCareKeysForOutput) { 193 dontCareKeysList.add(dontCareKey.toString() + "?"); 194 } 195 String dontCareKeysString = PLUS_JOINER.join(dontCareKeysList); 196 return dontCareKeysString.isEmpty() ? onKeysString 197 : onKeysString.isEmpty() ? dontCareKeysString 198 : PLUS_JOINER.join(onKeysString, dontCareKeysString); 199 } 200 201 /** Find the state of the given modifier key by evaluating the given sets. */ 202 private static char getInternalKeyState(ModifierKey modifierKey, Set<ModifierKey> onKeys, 203 Set<ModifierKey> offKeys) { 204 return onKeys.contains(modifierKey) ? '1' : offKeys.contains(modifierKey) ? '0' : '?'; 205 } 206 207 /** 208 * Simplifies the set of combinations into its most simple forms and returns a modifier key 209 * combination set. 210 */ 211 public static ImmutableSet<ModifierKeyCombination> simplifySet(Set<ModifierKeyCombination> combinations) { 212 // Make a defensive copy of the input. 213 Set<ModifierKeyCombination> finalCombinations = Sets.newHashSet(combinations); 214 // Keep simplifying the combination until a stable version is attained. 215 int sizeChange = Integer.MAX_VALUE; 216 while (sizeChange != 0) { 217 int initialSize = finalCombinations.size(); 218 finalCombinations = simplifyCombinationsOnePass(finalCombinations); 219 sizeChange = initialSize - finalCombinations.size(); 220 } 221 return ImmutableSet.copyOf(finalCombinations); 222 } 223 224 /** 225 * Make a single pass over the set of combinations to attempt to simplify them. Multiple calls to 226 * this method are necessary to achieve the simplest form. 227 */ 228 private static Set<ModifierKeyCombination> simplifyCombinationsOnePass( 229 Set<ModifierKeyCombination> combinations) { 230 if (combinations.size() < 2) { 231 return combinations; 232 } 233 Iterator<ModifierKeyCombination> iterator = Sets.newTreeSet(combinations).iterator(); 234 Set<ModifierKeyCombination> finalCombinations = Sets.newHashSet(); 235 // Take two consecutive objects in the sorted set and attempt to simplify them. 236 ModifierKeyCombination combination1 = iterator.next(); 237 while (iterator.hasNext()) { 238 ModifierKeyCombination combination2 = iterator.next(); 239 Set<ModifierKeyCombination> result = simplifyTwoCombinations(combination1, combination2); 240 // If the simplification was successful, use it as a new pointer. 241 if (result.size() == 1) { 242 combination1 = result.iterator().next(); 243 } else { 244 finalCombinations.add(combination1); 245 combination1 = combination2; 246 } 247 } 248 finalCombinations.add(combination1); 249 return finalCombinations; 250 } 251 252 /** 253 * Given two modifier key combinations, attempt to simplify them into a single combination. If no 254 * simplification is possible, the method simply returns a set containing the two original 255 * combinations. 256 */ 257 private static ImmutableSet<ModifierKeyCombination> simplifyTwoCombinations( 258 ModifierKeyCombination combination1, ModifierKeyCombination combination2) { 259 // If the combinations are identical, the simplification is trivial. 260 if (combination1.equals(combination2)) { 261 return ImmutableSet.of(combination1); 262 } 263 SetView<ModifierKey> onKeyDifferences = Sets.symmetricDifference(combination1.onKeys(), 264 combination2.onKeys()); 265 SetView<ModifierKey> offKeyDifferences = Sets.symmetricDifference(combination1.offKeys(), 266 combination2.offKeys()); 267 // Simplification is only possible if there is some sort of relationship between the keys (and 268 // even then, simplification is not guaranteed. 269 if (!keysAreRelated(onKeyDifferences, offKeyDifferences)) { 270 return ImmutableSet.of(combination1, combination2); 271 } 272 // Get the modifier key parent in question. 273 ModifierKey key = null; 274 if (onKeyDifferences.size() > 0) { 275 key = onKeyDifferences.iterator().next(); 276 } else { 277 key = offKeyDifferences.iterator().next(); 278 } 279 ModifierKey parentKey = key.parent(); 280 // Set up a new combination with all the common keys from the two combinations. 281 Sets.SetView<ModifierKey> onKeysIntersect = Sets.intersection(combination1.onKeys(), 282 combination2.onKeys()); 283 EnumSet<ModifierKey> onKeys = onKeysIntersect.isEmpty() ? EnumSet.noneOf(ModifierKey.class) 284 : EnumSet.copyOf(onKeysIntersect); 285 Sets.SetView<ModifierKey> offKeysIntersect = Sets.intersection(combination1.offKeys(), combination2.offKeys()); 286 EnumSet<ModifierKey> offKeys = offKeysIntersect.isEmpty() ? EnumSet.noneOf(ModifierKey.class) 287 : EnumSet.copyOf(offKeysIntersect); 288 // Get the internal state of both combinations for this particular modifier key 289 String combination1States = getStringFromInternalRepresentation(parentKey, 290 combination1.onKeys(), combination1.offKeys()); 291 String combination2States = getStringFromInternalRepresentation(parentKey, 292 combination2.onKeys(), combination2.offKeys()); 293 // Attempt to get simplification (may need to reverse the col/row keys because we are just 294 // storing a triangular matrix with the simplification codes). 295 String result = COMBINATIONS_TO_SIMPLIFCATION.get(combination1States, combination2States); 296 if (result == null) { 297 result = COMBINATIONS_TO_SIMPLIFCATION.get(combination2States, combination1States); 298 } 299 checkNotNull(result, "Unknown combination %s", combination1States + "," + combination2States); 300 // The "%" return code means that the two combinations cannot be combined. 301 if (result.equals("%")) { 302 return ImmutableSet.of(combination1, combination2); 303 } 304 // Transform the String representation into the internal representation and add them to the ON 305 // and OFF sets. 306 ImmutableSet.Builder<ModifierKey> onKeysBuilder = ImmutableSet.builder(); 307 ImmutableSet.Builder<ModifierKey> offKeysBuilder = ImmutableSet.builder(); 308 addInternalRepresentationFromString(parentKey, result, onKeysBuilder, offKeysBuilder); 309 onKeysBuilder.addAll(onKeys); 310 offKeysBuilder.addAll(offKeys); 311 return ImmutableSet 312 .of(ModifierKeyCombination.of(onKeysBuilder.build(), offKeysBuilder.build())); 313 } 314 315 /** 316 * Given the set difference between two combinations ON keys and OFF keys, determine if the 317 * differences in both sets are related (simplification is only possible if there is a 318 * relationship between the different keys). 319 */ 320 private static boolean keysAreRelated(Set<ModifierKey> onKeys, Set<ModifierKey> offKeys) { 321 // Combine all keys. 322 Set<ModifierKey> allKeys = EnumSet.noneOf(ModifierKey.class); 323 allKeys.addAll(onKeys); 324 allKeys.addAll(offKeys); 325 // Get a test key. 326 ModifierKey testKey = allKeys.iterator().next(); 327 // Remove all keys which have some sort of relationship to the test key from all keys. 328 allKeys.remove(testKey); 329 allKeys.remove(testKey.parent()); 330 allKeys.remove(testKey.sibling()); 331 allKeys.removeAll(testKey.children()); 332 // Check that set is empty, if it isn't there are some extra keys. 333 return allKeys.size() == 0; 334 } 335 336 /** 337 * Return a length 3 String representing the state of a parent key and its two children in their 338 * internal representation given a set of ON keys and OFF keys (in internal representation). 339 */ 340 private static String getStringFromInternalRepresentation( 341 ModifierKey parentKey, Set<ModifierKey> onKeys, Set<ModifierKey> offKeys) { 342 StringBuilder internalRepresentationBuilder = new StringBuilder(); 343 internalRepresentationBuilder.append(getInternalKeyState(parentKey, onKeys, offKeys)); 344 // Children 345 ImmutableList<ModifierKey> children = parentKey.children(); 346 // If there are no children, mark them as ?? (effectively removing them from the boolean 347 // equation). 348 if (children.size() == 0) { 349 internalRepresentationBuilder.append("??"); 350 } else { 351 internalRepresentationBuilder.append(getInternalKeyState(children.get(0), onKeys, offKeys)); 352 internalRepresentationBuilder.append(getInternalKeyState(children.get(1), onKeys, offKeys)); 353 } 354 return internalRepresentationBuilder.toString(); 355 } 356 357 /** 358 * Transform a length 3 String containing the state of a modifier key and its children and add it 359 * to the onKeys and offKeys builders. 360 */ 361 private static void addInternalRepresentationFromString( 362 ModifierKey parentKey, 363 String modifierKeyState, 364 ImmutableSet.Builder<ModifierKey> onKeysOut, 365 ImmutableSet.Builder<ModifierKey> offKeysOut) { 366 checkArgument(modifierKeyState.length() == 3, modifierKeyState); 367 ImmutableList<ModifierKey> children = parentKey.children(); 368 List<ModifierKey> keys = children.isEmpty() 369 ? Lists.newArrayList(parentKey, parentKey, parentKey) 370 : Lists.newArrayList(parentKey, children.get(0), children.get(1)); 371 for (int i = 0; i < modifierKeyState.length(); i++) { 372 char state = modifierKeyState.charAt(i); 373 ModifierKey key = keys.get(i); 374 if (state == '1') { 375 onKeysOut.add(key); 376 } else if (state == '0') { 377 offKeysOut.add(key); 378 } 379 } 380 } 381 382 private ModifierKeySimplifier() { 383 } 384 } 385
