1 /* 2 * Copyright (C) 2021 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.launcher3.search; 18 19 import java.text.Collator; 20 21 /** 22 * Utilities for matching query string to target string. 23 */ 24 public class StringMatcherUtility { 25 26 /** 27 * Returns {@code true} is {@code query} is a prefix substring of a complete word/phrase in 28 * {@code target}. 29 */ matches(String query, String target, StringMatcher matcher)30 public static boolean matches(String query, String target, StringMatcher matcher) { 31 int queryLength = query.length(); 32 33 int targetLength = target.length(); 34 35 if (targetLength < queryLength || queryLength <= 0) { 36 return false; 37 } 38 39 if (requestSimpleFuzzySearch(query)) { 40 return target.toLowerCase().contains(query); 41 } 42 43 int lastType; 44 int thisType = Character.UNASSIGNED; 45 int nextType = Character.getType(target.codePointAt(0)); 46 47 int end = targetLength - queryLength; 48 for (int i = 0; i <= end; i++) { 49 lastType = thisType; 50 thisType = nextType; 51 nextType = i < (targetLength - 1) 52 ? Character.getType(target.codePointAt(i + 1)) : Character.UNASSIGNED; 53 if (isBreak(thisType, lastType, nextType) 54 && matcher.matches(query, target.substring(i, i + queryLength))) { 55 return true; 56 } 57 } 58 return false; 59 } 60 61 /** 62 * Returns true if the current point should be a break point. Following cases 63 * are considered as break points: 64 * 1) Any non space character after a space character 65 * 2) Any digit after a non-digit character 66 * 3) Any capital character after a digit or small character 67 * 4) Any capital character before a small character 68 */ 69 private static boolean isBreak(int thisType, int prevType, int nextType) { 70 switch (prevType) { 71 case Character.UNASSIGNED: 72 case Character.SPACE_SEPARATOR: 73 case Character.LINE_SEPARATOR: 74 case Character.PARAGRAPH_SEPARATOR: 75 return true; 76 } 77 switch (thisType) { 78 case Character.UPPERCASE_LETTER: 79 if (nextType == Character.UPPERCASE_LETTER) { 80 return true; 81 } 82 // Follow through 83 case Character.TITLECASE_LETTER: 84 // Break point if previous was not a upper case 85 return prevType != Character.UPPERCASE_LETTER; 86 case Character.LOWERCASE_LETTER: 87 // Break point if previous was not a letter. 88 return prevType > Character.OTHER_LETTER || prevType <= Character.UNASSIGNED; 89 case Character.DECIMAL_DIGIT_NUMBER: 90 case Character.LETTER_NUMBER: 91 case Character.OTHER_NUMBER: 92 // Break point if previous was not a number 93 return !(prevType == Character.DECIMAL_DIGIT_NUMBER 94 || prevType == Character.LETTER_NUMBER 95 || prevType == Character.OTHER_NUMBER); 96 case Character.MATH_SYMBOL: 97 case Character.CURRENCY_SYMBOL: 98 case Character.OTHER_PUNCTUATION: 99 case Character.DASH_PUNCTUATION: 100 // Always a break point for a symbol 101 return true; 102 default: 103 return false; 104 } 105 } 106 107 /** 108 * Performs locale sensitive string comparison using {@link Collator}. 109 */ 110 public static class StringMatcher { 111 112 private static final char MAX_UNICODE = '\uFFFF'; 113 114 private final Collator mCollator; 115 StringMatcher()116 StringMatcher() { 117 // On android N and above, Collator uses ICU implementation which has a much better 118 // support for non-latin locales. 119 mCollator = Collator.getInstance(); 120 mCollator.setStrength(Collator.PRIMARY); 121 mCollator.setDecomposition(Collator.CANONICAL_DECOMPOSITION); 122 } 123 124 /** 125 * Returns true if {@param query} is a prefix of {@param target} 126 */ matches(String query, String target)127 public boolean matches(String query, String target) { 128 switch (mCollator.compare(query, target)) { 129 case 0: 130 return true; 131 case -1: 132 // The target string can contain a modifier which would make it larger than 133 // the query string (even though the length is same). If the query becomes 134 // larger after appending a unicode character, it was originally a prefix of 135 // the target string and hence should match. 136 return mCollator.compare(query + MAX_UNICODE, target) > -1; 137 default: 138 return false; 139 } 140 } 141 getInstance()142 public static StringMatcher getInstance() { 143 return new StringMatcher(); 144 } 145 } 146 147 /** 148 * Matching optimization to search in Chinese. 149 */ requestSimpleFuzzySearch(String s)150 private static boolean requestSimpleFuzzySearch(String s) { 151 for (int i = 0; i < s.length(); ) { 152 int codepoint = s.codePointAt(i); 153 i += Character.charCount(codepoint); 154 switch (Character.UnicodeScript.of(codepoint)) { 155 case HAN: 156 //Character.UnicodeScript.HAN: use String.contains to match 157 return true; 158 } 159 } 160 return false; 161 } 162 } 163