diff options
Diffstat (limited to 'java/com/android/dialer/smartdial/util/SmartDialNameMatcher.java')
| -rw-r--r-- | java/com/android/dialer/smartdial/util/SmartDialNameMatcher.java | 430 |
1 files changed, 430 insertions, 0 deletions
diff --git a/java/com/android/dialer/smartdial/util/SmartDialNameMatcher.java b/java/com/android/dialer/smartdial/util/SmartDialNameMatcher.java new file mode 100644 index 000000000..725c88c57 --- /dev/null +++ b/java/com/android/dialer/smartdial/util/SmartDialNameMatcher.java @@ -0,0 +1,430 @@ +/* + * Copyright (C) 2012 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.dialer.smartdial.util; + +import android.content.Context; +import android.support.annotation.Nullable; +import android.text.TextUtils; +import com.android.dialer.smartdial.map.CompositeSmartDialMap; +import com.android.dialer.smartdial.util.SmartDialPrefix.PhoneNumberTokens; +import java.util.ArrayList; + +/** + * {@link #SmartDialNameMatcher} contains utility functions to remove accents from accented + * characters and normalize a phone number. It also contains the matching logic that determines if a + * contact's display name matches a numeric query. The boolean variable {@link #ALLOW_INITIAL_MATCH} + * controls the behavior of the matching logic and determines whether we allow matches like 57 - + * (J)ohn (S)mith. + */ +public class SmartDialNameMatcher { + // Whether or not we allow matches like 57 - (J)ohn (S)mith + private static final boolean ALLOW_INITIAL_MATCH = true; + + // The maximum length of the initial we will match - typically set to 1 to minimize false + // positives + private static final int INITIAL_LENGTH_LIMIT = 1; + + private final ArrayList<SmartDialMatchPosition> mMatchPositions = new ArrayList<>(); + private String mQuery; + + // Controls whether to treat an empty query as a match (with anything). + private boolean mShouldMatchEmptyQuery = false; + + public SmartDialNameMatcher(String query) { + mQuery = query; + } + + /** + * Strips a phone number of unnecessary characters (spaces, dashes, etc.) + * + * @param number Phone number we want to normalize + * @return Phone number consisting of digits from 0-9 + */ + public static String normalizeNumber(Context context, String number) { + return normalizeNumber(context, number, /* offset = */ 0); + } + + /** + * Strips a phone number of unnecessary characters (spaces, dashes, etc.) + * + * @param number Phone number we want to normalize + * @param offset Offset to start from + * @return Phone number consisting of digits from 0-9 + */ + public static String normalizeNumber(Context context, String number, int offset) { + final StringBuilder s = new StringBuilder(); + for (int i = offset; i < number.length(); i++) { + char ch = number.charAt(i); + if (CompositeSmartDialMap.isValidDialpadNumericChar(context, ch)) { + s.append(ch); + } + } + return s.toString(); + } + + /** + * Constructs empty highlight mask. Bit 0 at a position means there is no match, Bit 1 means there + * is a match and should be highlighted in the TextView. + * + * @param builder StringBuilder object + * @param length Length of the desired mask. + */ + private void constructEmptyMask(StringBuilder builder, int length) { + for (int i = 0; i < length; ++i) { + builder.append("0"); + } + } + + /** + * Replaces the 0-bit at a position with 1-bit, indicating that there is a match. + * + * @param builder StringBuilder object. + * @param matchPos Match Positions to mask as 1. + */ + private void replaceBitInMask(StringBuilder builder, SmartDialMatchPosition matchPos) { + for (int i = matchPos.start; i < matchPos.end; ++i) { + builder.replace(i, i + 1, "1"); + } + } + + /** + * Matches a phone number against a query. Let the test application overwrite the NANP setting. + * + * @param phoneNumber - Raw phone number + * @param query - Normalized query (only contains numbers from 0-9) + * @return {@literal null} if the number and the query don't match, a valid SmartDialMatchPosition + * with the matching positions otherwise + */ + @Nullable + public SmartDialMatchPosition matchesNumber(Context context, String phoneNumber, String query) { + if (TextUtils.isEmpty(phoneNumber)) { + return mShouldMatchEmptyQuery ? new SmartDialMatchPosition(0, 0) : null; + } + StringBuilder builder = new StringBuilder(); + constructEmptyMask(builder, phoneNumber.length()); + + // Try matching the number as is + SmartDialMatchPosition matchPos = + matchesNumberWithOffset(context, phoneNumber, query, /* offset = */ 0); + if (matchPos == null) { + PhoneNumberTokens phoneNumberTokens = SmartDialPrefix.parsePhoneNumber(context, phoneNumber); + + if (phoneNumberTokens.countryCodeOffset != 0) { + matchPos = + matchesNumberWithOffset( + context, phoneNumber, query, phoneNumberTokens.countryCodeOffset); + } + if (matchPos == null && phoneNumberTokens.nanpCodeOffset != 0) { + matchPos = + matchesNumberWithOffset(context, phoneNumber, query, phoneNumberTokens.nanpCodeOffset); + } + } + if (matchPos != null) { + replaceBitInMask(builder, matchPos); + } + return matchPos; + } + + /** + * Matches a phone number against the saved query, taking care of formatting characters and also + * taking into account country code prefixes and special NANP number treatment. + * + * @param phoneNumber - Raw phone number + * @return {@literal null} if the number and the query don't match, a valid SmartDialMatchPosition + * with the matching positions otherwise + */ + public SmartDialMatchPosition matchesNumber(Context context, String phoneNumber) { + return matchesNumber(context, phoneNumber, mQuery); + } + + /** + * Matches a phone number against a query, taking care of formatting characters + * + * @param phoneNumber - Raw phone number + * @param query - Normalized query (only contains numbers from 0-9) + * @param offset - The position in the number to start the match against (used to ignore leading + * prefixes/country codes) + * @return {@literal null} if the number and the query don't match, a valid SmartDialMatchPosition + * with the matching positions otherwise + */ + private SmartDialMatchPosition matchesNumberWithOffset( + Context context, String phoneNumber, String query, int offset) { + if (TextUtils.isEmpty(phoneNumber) || TextUtils.isEmpty(query)) { + return mShouldMatchEmptyQuery ? new SmartDialMatchPosition(offset, offset) : null; + } + int queryAt = 0; + int numberAt = offset; + for (int i = offset; i < phoneNumber.length(); i++) { + if (queryAt == query.length()) { + break; + } + char ch = phoneNumber.charAt(i); + if (CompositeSmartDialMap.isValidDialpadNumericChar(context, ch)) { + if (ch != query.charAt(queryAt)) { + return null; + } + queryAt++; + } else { + if (queryAt == 0) { + // Found a separator before any part of the query was matched, so advance the + // offset to avoid prematurely highlighting separators before the rest of the + // query. + // E.g. don't highlight the first '-' if we're matching 1-510-111-1111 with + // '510'. + // However, if the current offset is 0, just include the beginning separators + // anyway, otherwise the highlighting ends up looking weird. + // E.g. if we're matching (510)-111-1111 with '510', we should include the + // first '('. + if (offset != 0) { + offset++; + } + } + } + numberAt++; + } + return new SmartDialMatchPosition(0 + offset, numberAt); + } + + /** + * This function iterates through each token in the display name, trying to match the query to the + * numeric equivalent of the token. + * + * <p>A token is defined as a range in the display name delimited by characters that have no latin + * alphabet equivalents (e.g. spaces - ' ', periods - ',', underscores - '_' or chinese characters + * - '王'). Transliteration from non-latin characters to latin character will be done on a best + * effort basis - e.g. 'Ü' - 'u'. + * + * <p>For example, the display name "Phillips Thomas Jr" contains three tokens: "phillips", + * "thomas", and "jr". + * + * <p>A match must begin at the start of a token. For example, typing 846(Tho) would match + * "Phillips Thomas", but 466(hom) would not. + * + * <p>Also, a match can extend across tokens. For example, typing 37337(FredS) would match (Fred + * S)mith. + * + * @param displayName The normalized(no accented characters) display name we intend to match + * against. + * @param query The string of digits that we want to match the display name to. + * @param matchList An array list of {@link SmartDialMatchPosition}s that we add matched positions + * to. + * @return Returns true if a combination of the tokens in displayName match the query string + * contained in query. If the function returns true, matchList will contain an ArrayList of + * match positions (multiple matches correspond to initial matches). + */ + private boolean matchesCombination( + Context context, + String displayName, + String query, + ArrayList<SmartDialMatchPosition> matchList) { + StringBuilder builder = new StringBuilder(); + constructEmptyMask(builder, displayName.length()); + final int nameLength = displayName.length(); + final int queryLength = query.length(); + + if (nameLength < queryLength) { + return false; + } + + if (queryLength == 0) { + return false; + } + + // The current character index in displayName + // E.g. 3 corresponds to 'd' in "Fred Smith" + int nameStart = 0; + + // The current character in the query we are trying to match the displayName against + int queryStart = 0; + + // The start position of the current token we are inspecting + int tokenStart = 0; + + // The number of non-alphabetic characters we've encountered so far in the current match. + // E.g. if we've currently matched 3733764849 to (Fred Smith W)illiam, then the + // seperatorCount should be 2. This allows us to correctly calculate offsets for the match + // positions + int seperatorCount = 0; + + ArrayList<SmartDialMatchPosition> partial = new ArrayList<SmartDialMatchPosition>(); + // Keep going until we reach the end of displayName + while (nameStart < nameLength && queryStart < queryLength) { + char ch = displayName.charAt(nameStart); + // Strip diacritics from accented characters if any + ch = CompositeSmartDialMap.normalizeCharacter(context, ch); + if (CompositeSmartDialMap.isValidDialpadCharacter(context, ch)) { + if (CompositeSmartDialMap.isValidDialpadAlphabeticChar(context, ch)) { + ch = CompositeSmartDialMap.getDialpadNumericCharacter(context, ch); + } + if (ch != query.charAt(queryStart)) { + // Failed to match the current character in the query. + + // Case 1: Failed to match the first character in the query. Skip to the next + // token since there is no chance of this token matching the query. + + // Case 2: Previous characters in the query matched, but the current character + // failed to match. This happened in the middle of a token. Skip to the next + // token since there is no chance of this token matching the query. + + // Case 3: Previous characters in the query matched, but the current character + // failed to match. This happened right at the start of the current token. In + // this case, we should restart the query and try again with the current token. + // Otherwise, we would fail to match a query like "964"(yog) against a name + // Yo-Yoghurt because the query match would fail on the 3rd character, and + // then skip to the end of the "Yoghurt" token. + + if (queryStart == 0 + || CompositeSmartDialMap.isValidDialpadCharacter( + context, + CompositeSmartDialMap.normalizeCharacter( + context, displayName.charAt(nameStart - 1)))) { + // skip to the next token, in the case of 1 or 2. + while (nameStart < nameLength + && CompositeSmartDialMap.isValidDialpadCharacter( + context, + CompositeSmartDialMap.normalizeCharacter( + context, displayName.charAt(nameStart)))) { + nameStart++; + } + nameStart++; + } + + // Restart the query and set the correct token position + queryStart = 0; + seperatorCount = 0; + tokenStart = nameStart; + } else { + if (queryStart == queryLength - 1) { + + // As much as possible, we prioritize a full token match over a sub token + // one so if we find a full token match, we can return right away + matchList.add( + new SmartDialMatchPosition(tokenStart, queryLength + tokenStart + seperatorCount)); + for (SmartDialMatchPosition match : matchList) { + replaceBitInMask(builder, match); + } + return true; + } else if (ALLOW_INITIAL_MATCH && queryStart < INITIAL_LENGTH_LIMIT) { + // we matched the first character. + // branch off and see if we can find another match with the remaining + // characters in the query string and the remaining tokens + // find the next separator in the query string + int j; + for (j = nameStart; j < nameLength; j++) { + if (!CompositeSmartDialMap.isValidDialpadCharacter( + context, + CompositeSmartDialMap.normalizeCharacter(context, displayName.charAt(j)))) { + break; + } + } + // this means there is at least one character left after the separator + if (j < nameLength - 1) { + final String remainder = displayName.substring(j + 1); + final ArrayList<SmartDialMatchPosition> partialTemp = new ArrayList<>(); + if (matchesCombination( + context, remainder, query.substring(queryStart + 1), partialTemp)) { + + // store the list of possible match positions + SmartDialMatchPosition.advanceMatchPositions(partialTemp, j + 1); + partialTemp.add(0, new SmartDialMatchPosition(nameStart, nameStart + 1)); + // we found a partial token match, store the data in a + // temp buffer and return it if we end up not finding a full + // token match + partial = partialTemp; + } + } + } + nameStart++; + queryStart++; + // we matched the current character in the name against one in the query, + // continue and see if the rest of the characters match + } + } else { + // found a separator, we skip this character and continue to the next one + nameStart++; + if (queryStart == 0) { + // This means we found a separator before the start of a token, + // so we should increment the token's start position to reflect its true + // start position + tokenStart = nameStart; + } else { + // Otherwise this separator was found in the middle of a token being matched, + // so increase the separator count + seperatorCount++; + } + } + } + // if we have no complete match at this point, then we attempt to fall back to the partial + // token match(if any). If we don't allow initial matching (ALLOW_INITIAL_MATCH = false) + // then partial will always be empty. + if (!partial.isEmpty()) { + matchList.addAll(partial); + for (SmartDialMatchPosition match : matchList) { + replaceBitInMask(builder, match); + } + return true; + } + return false; + } + + /** + * This function iterates through each token in the display name, trying to match the query to the + * numeric equivalent of the token. + * + * <p>A token is defined as a range in the display name delimited by characters that have no latin + * alphabet equivalents (e.g. spaces - ' ', periods - ',', underscores - '_' or chinese characters + * - '王'). Transliteration from non-latin characters to latin character will be done on a best + * effort basis - e.g. 'Ü' - 'u'. + * + * <p>For example, the display name "Phillips Thomas Jr" contains three tokens: "phillips", + * "thomas", and "jr". + * + * <p>A match must begin at the start of a token. For example, typing 846(Tho) would match + * "Phillips Thomas", but 466(hom) would not. + * + * <p>Also, a match can extend across tokens. For example, typing 37337(FredS) would match (Fred + * S)mith. + * + * @param displayName The normalized(no accented characters) display name we intend to match + * against. + * @return Returns true if a combination of the tokens in displayName match the query string + * contained in query. If the function returns true, matchList will contain an ArrayList of + * match positions (multiple matches correspond to initial matches). + */ + public boolean matches(Context context, String displayName) { + mMatchPositions.clear(); + return matchesCombination(context, displayName, mQuery, mMatchPositions); + } + + public ArrayList<SmartDialMatchPosition> getMatchPositions() { + // Return a clone of mMatchPositions so that the caller can use it without + // worrying about it changing + return new ArrayList<>(mMatchPositions); + } + + public String getQuery() { + return mQuery; + } + + public void setQuery(String query) { + mQuery = query; + } + + public void setShouldMatchEmptyQuery(boolean matches) { + mShouldMatchEmptyQuery = matches; + } +} |