1ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian/* 2ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * Copyright (C) 2012 The Android Open Source Project 3ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 4ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * Licensed under the Apache License, Version 2.0 (the "License"); 5ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * you may not use this file except in compliance with the License. 6ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * You may obtain a copy of the License at 7ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 8ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * http://www.apache.org/licenses/LICENSE-2.0 9ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 10ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * Unless required by applicable law or agreed to in writing, software 11ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * distributed under the License is distributed on an "AS IS" BASIS, 12ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * See the License for the specific language governing permissions and 14ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * limitations under the License. 15ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian */ 16ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 17ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanianpackage com.android.dialer.smartdial; 18ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 19ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanianimport android.support.annotation.Nullable; 20ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanianimport android.support.annotation.VisibleForTesting; 21ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanianimport android.text.TextUtils; 22ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanianimport com.android.dialer.smartdial.SmartDialPrefix.PhoneNumberTokens; 23ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanianimport java.util.ArrayList; 24ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 25ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian/** 26ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * {@link #SmartDialNameMatcher} contains utility functions to remove accents from accented 27ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * characters and normalize a phone number. It also contains the matching logic that determines if a 28ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * contact's display name matches a numeric query. The boolean variable {@link #ALLOW_INITIAL_MATCH} 29ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * controls the behavior of the matching logic and determines whether we allow matches like 57 - 30ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * (J)ohn (S)mith. 31ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian */ 32ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanianpublic class SmartDialNameMatcher { 33ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 34ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public static final SmartDialMap LATIN_SMART_DIAL_MAP = new LatinSmartDialMap(); 35ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Whether or not we allow matches like 57 - (J)ohn (S)mith 36ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian private static final boolean ALLOW_INITIAL_MATCH = true; 37ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 38ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // The maximum length of the initial we will match - typically set to 1 to minimize false 39ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // positives 40ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian private static final int INITIAL_LENGTH_LIMIT = 1; 41ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 42ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian private final ArrayList<SmartDialMatchPosition> mMatchPositions = new ArrayList<>(); 43ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian private final SmartDialMap mMap; 44ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian private String mQuery; 45ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian private String mNameMatchMask = ""; 46ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian private String mPhoneNumberMatchMask = ""; 47ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 48ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Controls whether to treat an empty query as a match (with anything). 49ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian private boolean mShouldMatchEmptyQuery = false; 50ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 51ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian @VisibleForTesting 52ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public SmartDialNameMatcher(String query) { 53ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian this(query, LATIN_SMART_DIAL_MAP); 54ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 55ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 56ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public SmartDialNameMatcher(String query, SmartDialMap map) { 57ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mQuery = query; 58ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mMap = map; 59ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 60ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 61ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian /** 62ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * Strips a phone number of unnecessary characters (spaces, dashes, etc.) 63ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 64ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param number Phone number we want to normalize 65ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @return Phone number consisting of digits from 0-9 66ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian */ 67ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public static String normalizeNumber(String number, SmartDialMap map) { 68ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return normalizeNumber(number, 0, map); 69ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 70ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 71ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian /** 72ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * Strips a phone number of unnecessary characters (spaces, dashes, etc.) 73ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 74ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param number Phone number we want to normalize 75ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param offset Offset to start from 76ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @return Phone number consisting of digits from 0-9 77ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian */ 78ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public static String normalizeNumber(String number, int offset, SmartDialMap map) { 79ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian final StringBuilder s = new StringBuilder(); 80ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian for (int i = offset; i < number.length(); i++) { 81ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian char ch = number.charAt(i); 82ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (map.isValidDialpadNumericChar(ch)) { 83ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian s.append(ch); 84ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 85ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 86ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return s.toString(); 87ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 88ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 89ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian /** 90ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * Constructs empty highlight mask. Bit 0 at a position means there is no match, Bit 1 means there 91ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * is a match and should be highlighted in the TextView. 92ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 93ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param builder StringBuilder object 94ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param length Length of the desired mask. 95ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian */ 96ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian private void constructEmptyMask(StringBuilder builder, int length) { 97ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian for (int i = 0; i < length; ++i) { 98ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian builder.append("0"); 99ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 100ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 101ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 102ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian /** 103ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * Replaces the 0-bit at a position with 1-bit, indicating that there is a match. 104ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 105ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param builder StringBuilder object. 106ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param matchPos Match Positions to mask as 1. 107ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian */ 108ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian private void replaceBitInMask(StringBuilder builder, SmartDialMatchPosition matchPos) { 109ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian for (int i = matchPos.start; i < matchPos.end; ++i) { 110ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian builder.replace(i, i + 1, "1"); 111ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 112ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 113ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 114ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian /** 115ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * Matches a phone number against a query. Let the test application overwrite the NANP setting. 116ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 117ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param phoneNumber - Raw phone number 118ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param query - Normalized query (only contains numbers from 0-9) 119ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param useNanp - Overwriting nanp setting boolean, used for testing. 120ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @return {@literal null} if the number and the query don't match, a valid SmartDialMatchPosition 121ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * with the matching positions otherwise 122ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian */ 123ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian @VisibleForTesting 124ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian @Nullable 125ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public SmartDialMatchPosition matchesNumber(String phoneNumber, String query, boolean useNanp) { 126ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (TextUtils.isEmpty(phoneNumber)) { 127ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return mShouldMatchEmptyQuery ? new SmartDialMatchPosition(0, 0) : null; 128ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 129ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian StringBuilder builder = new StringBuilder(); 130ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian constructEmptyMask(builder, phoneNumber.length()); 131ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mPhoneNumberMatchMask = builder.toString(); 132ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 133ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Try matching the number as is 134ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian SmartDialMatchPosition matchPos = matchesNumberWithOffset(phoneNumber, query, 0); 135ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (matchPos == null) { 136ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian final PhoneNumberTokens phoneNumberTokens = SmartDialPrefix.parsePhoneNumber(phoneNumber); 137ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 138ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (phoneNumberTokens == null) { 139ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return matchPos; 140ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 141ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (phoneNumberTokens.countryCodeOffset != 0) { 142ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian matchPos = matchesNumberWithOffset(phoneNumber, query, phoneNumberTokens.countryCodeOffset); 143ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 144ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (matchPos == null && phoneNumberTokens.nanpCodeOffset != 0 && useNanp) { 145ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian matchPos = matchesNumberWithOffset(phoneNumber, query, phoneNumberTokens.nanpCodeOffset); 146ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 147ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 148ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (matchPos != null) { 149ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian replaceBitInMask(builder, matchPos); 150ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mPhoneNumberMatchMask = builder.toString(); 151ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 152ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return matchPos; 153ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 154ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 155ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian /** 156ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * Matches a phone number against the saved query, taking care of formatting characters and also 157ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * taking into account country code prefixes and special NANP number treatment. 158ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 159ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param phoneNumber - Raw phone number 160ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @return {@literal null} if the number and the query don't match, a valid SmartDialMatchPosition 161ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * with the matching positions otherwise 162ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian */ 163ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public SmartDialMatchPosition matchesNumber(String phoneNumber) { 164ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return matchesNumber(phoneNumber, mQuery, true); 165ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 166ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 167ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian /** 168ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * Matches a phone number against a query, taking care of formatting characters and also taking 169ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * into account country code prefixes and special NANP number treatment. 170ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 171ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param phoneNumber - Raw phone number 172ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param query - Normalized query (only contains numbers from 0-9) 173ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @return {@literal null} if the number and the query don't match, a valid SmartDialMatchPosition 174ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * with the matching positions otherwise 175ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian */ 176ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public SmartDialMatchPosition matchesNumber(String phoneNumber, String query) { 177ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return matchesNumber(phoneNumber, query, true); 178ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 179ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 180ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian /** 181ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * Matches a phone number against a query, taking care of formatting characters 182ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 183ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param phoneNumber - Raw phone number 184ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param query - Normalized query (only contains numbers from 0-9) 185ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param offset - The position in the number to start the match against (used to ignore leading 186ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * prefixes/country codes) 187ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @return {@literal null} if the number and the query don't match, a valid SmartDialMatchPosition 188ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * with the matching positions otherwise 189ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian */ 190ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian private SmartDialMatchPosition matchesNumberWithOffset( 191ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian String phoneNumber, String query, int offset) { 192ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (TextUtils.isEmpty(phoneNumber) || TextUtils.isEmpty(query)) { 193ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return mShouldMatchEmptyQuery ? new SmartDialMatchPosition(offset, offset) : null; 194ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 195ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian int queryAt = 0; 196ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian int numberAt = offset; 197ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian for (int i = offset; i < phoneNumber.length(); i++) { 198ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (queryAt == query.length()) { 199ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian break; 200ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 201ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian char ch = phoneNumber.charAt(i); 202ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (mMap.isValidDialpadNumericChar(ch)) { 203ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (ch != query.charAt(queryAt)) { 204ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return null; 205ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 206ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian queryAt++; 207ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } else { 208ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (queryAt == 0) { 209ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Found a separator before any part of the query was matched, so advance the 210ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // offset to avoid prematurely highlighting separators before the rest of the 211ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // query. 212ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // E.g. don't highlight the first '-' if we're matching 1-510-111-1111 with 213ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // '510'. 214ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // However, if the current offset is 0, just include the beginning separators 215ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // anyway, otherwise the highlighting ends up looking weird. 216ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // E.g. if we're matching (510)-111-1111 with '510', we should include the 217ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // first '('. 218ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (offset != 0) { 219ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian offset++; 220ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 221ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 222ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 223ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian numberAt++; 224ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 225ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return new SmartDialMatchPosition(0 + offset, numberAt); 226ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 227ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 228ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian /** 229ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * This function iterates through each token in the display name, trying to match the query to the 230ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * numeric equivalent of the token. 231ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 232ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * <p>A token is defined as a range in the display name delimited by characters that have no latin 233ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * alphabet equivalents (e.g. spaces - ' ', periods - ',', underscores - '_' or chinese characters 234ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * - '王'). Transliteration from non-latin characters to latin character will be done on a best 235ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * effort basis - e.g. 'Ü' - 'u'. 236ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 237ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * <p>For example, the display name "Phillips Thomas Jr" contains three tokens: "phillips", 238ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * "thomas", and "jr". 239ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 240ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * <p>A match must begin at the start of a token. For example, typing 846(Tho) would match 241ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * "Phillips Thomas", but 466(hom) would not. 242ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 243ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * <p>Also, a match can extend across tokens. For example, typing 37337(FredS) would match (Fred 244ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * S)mith. 245ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * 246ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param displayName The normalized(no accented characters) display name we intend to match 247ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * against. 248ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param query The string of digits that we want to match the display name to. 249ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @param matchList An array list of {@link SmartDialMatchPosition}s that we add matched positions 250ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * to. 251ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * @return Returns true if a combination of the tokens in displayName match the query string 252ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * contained in query. If the function returns true, matchList will contain an ArrayList of 253ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian * match positions (multiple matches correspond to initial matches). 254ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian */ 255ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian @VisibleForTesting 256ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian boolean matchesCombination( 257ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian String displayName, String query, ArrayList<SmartDialMatchPosition> matchList) { 258ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian StringBuilder builder = new StringBuilder(); 259ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian constructEmptyMask(builder, displayName.length()); 260ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mNameMatchMask = builder.toString(); 261ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian final int nameLength = displayName.length(); 262ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian final int queryLength = query.length(); 263ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 264ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (nameLength < queryLength) { 265ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return false; 266ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 267ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 268ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (queryLength == 0) { 269ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return false; 270ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 271ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 272ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // The current character index in displayName 273ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // E.g. 3 corresponds to 'd' in "Fred Smith" 274ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian int nameStart = 0; 275ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 276ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // The current character in the query we are trying to match the displayName against 277ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian int queryStart = 0; 278ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 279ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // The start position of the current token we are inspecting 280ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian int tokenStart = 0; 281ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 282ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // The number of non-alphabetic characters we've encountered so far in the current match. 283ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // E.g. if we've currently matched 3733764849 to (Fred Smith W)illiam, then the 284ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // seperatorCount should be 2. This allows us to correctly calculate offsets for the match 285ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // positions 286ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian int seperatorCount = 0; 287ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 288ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian ArrayList<SmartDialMatchPosition> partial = new ArrayList<SmartDialMatchPosition>(); 289ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Keep going until we reach the end of displayName 290ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian while (nameStart < nameLength && queryStart < queryLength) { 291ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian char ch = displayName.charAt(nameStart); 292ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Strip diacritics from accented characters if any 293ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian ch = mMap.normalizeCharacter(ch); 294ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (mMap.isValidDialpadCharacter(ch)) { 295ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (mMap.isValidDialpadAlphabeticChar(ch)) { 296ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian ch = mMap.getDialpadNumericCharacter(ch); 297ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 298ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (ch != query.charAt(queryStart)) { 299ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Failed to match the current character in the query. 300ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 301ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Case 1: Failed to match the first character in the query. Skip to the next 302ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // token since there is no chance of this token matching the query. 303ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 304ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Case 2: Previous characters in the query matched, but the current character 305ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // failed to match. This happened in the middle of a token. Skip to the next 306ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // token since there is no chance of this token matching the query. 307ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 308ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Case 3: Previous characters in the query matched, but the current character 309ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // failed to match. This happened right at the start of the current token. In 310ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // this case, we should restart the query and try again with the current token. 311ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Otherwise, we would fail to match a query like "964"(yog) against a name 312ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Yo-Yoghurt because the query match would fail on the 3rd character, and 313ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // then skip to the end of the "Yoghurt" token. 314ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 315ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (queryStart == 0 316ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian || mMap.isValidDialpadCharacter( 317ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mMap.normalizeCharacter(displayName.charAt(nameStart - 1)))) { 318ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // skip to the next token, in the case of 1 or 2. 319ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian while (nameStart < nameLength 320ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian && mMap.isValidDialpadCharacter( 321ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mMap.normalizeCharacter(displayName.charAt(nameStart)))) { 322ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian nameStart++; 323ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 324ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian nameStart++; 325ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 326ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 327ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Restart the query and set the correct token position 328ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian queryStart = 0; 329ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian seperatorCount = 0; 330ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian tokenStart = nameStart; 331ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } else { 332ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (queryStart == queryLength - 1) { 333ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 334ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // As much as possible, we prioritize a full token match over a sub token 335ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // one so if we find a full token match, we can return right away 336ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian matchList.add( 337ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian new SmartDialMatchPosition(tokenStart, queryLength + tokenStart + seperatorCount)); 338ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian for (SmartDialMatchPosition match : matchList) { 339ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian replaceBitInMask(builder, match); 340ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 341ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mNameMatchMask = builder.toString(); 342ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return true; 343ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } else if (ALLOW_INITIAL_MATCH && queryStart < INITIAL_LENGTH_LIMIT) { 344ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // we matched the first character. 345ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // branch off and see if we can find another match with the remaining 346ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // characters in the query string and the remaining tokens 347ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // find the next separator in the query string 348ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian int j; 349ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian for (j = nameStart; j < nameLength; j++) { 350ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (!mMap.isValidDialpadCharacter(mMap.normalizeCharacter(displayName.charAt(j)))) { 351ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian break; 352ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 353ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 354ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // this means there is at least one character left after the separator 355ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (j < nameLength - 1) { 356ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian final String remainder = displayName.substring(j + 1); 357ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian final ArrayList<SmartDialMatchPosition> partialTemp = new ArrayList<>(); 358ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (matchesCombination(remainder, query.substring(queryStart + 1), partialTemp)) { 359ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 360ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // store the list of possible match positions 361ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian SmartDialMatchPosition.advanceMatchPositions(partialTemp, j + 1); 362ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian partialTemp.add(0, new SmartDialMatchPosition(nameStart, nameStart + 1)); 363ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // we found a partial token match, store the data in a 364ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // temp buffer and return it if we end up not finding a full 365ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // token match 366ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian partial = partialTemp; 367ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 368ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 369ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 370ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian nameStart++; 371ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian queryStart++; 372ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // we matched the current character in the name against one in the query, 373ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // continue and see if the rest of the characters match 374ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 375ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } else { 376ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // found a separator, we skip this character and continue to the next one 377ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian nameStart++; 378ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (queryStart == 0) { 379ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // This means we found a separator before the start of a token, 380ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // so we should increment the token's start position to reflect its true 381ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // start position 382ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian tokenStart = nameStart; 383ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } else { 384ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Otherwise this separator was found in the middle of a token being matched, 385ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // so increase the separator count 386ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian seperatorCount++; 387ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 388ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 389ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 390ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // if we have no complete match at this point, then we attempt to fall back to the partial 391ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // token match(if any). If we don't allow initial matching (ALLOW_INITIAL_MATCH = false) 392ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // then partial will always be empty. 393ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian if (!partial.isEmpty()) { 394ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian matchList.addAll(partial); 395ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian for (SmartDialMatchPosition match : matchList) { 396ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian replaceBitInMask(builder, match); 397ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 398ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mNameMatchMask = builder.toString(); 399ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return true; 400ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 401ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return false; 402ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 403ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 404ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public boolean matches(String displayName) { 405ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mMatchPositions.clear(); 406ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return matchesCombination(displayName, mQuery, mMatchPositions); 407ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 408ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 409ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public ArrayList<SmartDialMatchPosition> getMatchPositions() { 410ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // Return a clone of mMatchPositions so that the caller can use it without 411ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian // worrying about it changing 412ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return new ArrayList<SmartDialMatchPosition>(mMatchPositions); 413ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 414ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 415ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public String getNameMatchPositionsInString() { 416ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return mNameMatchMask; 417ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 418ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 419ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public String getNumberMatchPositionsInString() { 420ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return mPhoneNumberMatchMask; 421ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 422ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 423ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public String getQuery() { 424ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian return mQuery; 425ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 426ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 427ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public void setQuery(String query) { 428ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mQuery = query; 429ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 430ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian 431ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian public void setShouldMatchEmptyQuery(boolean matches) { 432ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian mShouldMatchEmptyQuery = matches; 433ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian } 434ccca31529c07970e89419fb85a9e8153a5396838Eric Erfanian} 435