1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
/*
* 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.dialpad;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.Lists;
import com.android.contacts.test.NeededForTesting;
import java.text.Normalizer;
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 {
private final String mQuery;
private static final char[] LETTERS_TO_DIGITS = {
'2', '2', '2', // A,B,C -> 2
'3', '3', '3', // D,E,F -> 3
'4', '4', '4', // G,H,I -> 4
'5', '5', '5', // J,K,L -> 5
'6', '6', '6', // M,N,O -> 6
'7', '7', '7', '7', // P,Q,R,S -> 7
'8', '8', '8', // T,U,V -> 8
'9', '9', '9', '9' // W,X,Y,Z -> 9
};
private final ArrayList<SmartDialMatchPosition> mMatchPositions = Lists.newArrayList();
public SmartDialNameMatcher(String query) {
mQuery = query;
}
/**
* Strips all accented characters in a name and converts them to their alphabetic equivalents.
*
* @param name Name we want to remove accented characters from.
* @return Name without accents in characters
*/
public static String stripDiacritics(String name) {
// NFD stands for normalization form D - Canonical Decomposition
// This means that for all characters with diacritics, e.g. ä, we decompose them into
// two characters, the first being the alphabetic equivalent, and the second being a
// a character that represents the diacritic.
final String normalized = Normalizer.normalize(name, Normalizer.Form.NFD);
final StringBuilder stripped = new StringBuilder();
for (int i = 0; i < normalized.length(); i++) {
// This pass through the string strips out all the diacritics by checking to see
// if they are in this list here:
// http://www.fileformat.info/info/unicode/category/Mn/list.htm
if (Character.getType(normalized.charAt(i)) != Character.NON_SPACING_MARK) {
stripped.append(normalized.charAt(i));
}
}
return stripped.toString();
}
/**
* Strips a phone number of unnecessary characters (zeros, ones, spaces, dashes, etc.)
*
* @param number Phone number we want to normalize
* @return Phone number consisting of digits from 2-9
*/
public static String normalizeNumber(String number) {
final StringBuilder s = new StringBuilder();
for (int i = 0; i < number.length(); i++) {
char ch = number.charAt(i);
if (ch >= '2' && ch <= '9') {
s.append(ch);
}
}
return s.toString();
}
/**
* This function iterates through each token in the display name, trying to match the query
* to the numeric equivalent of the token.
*
* A token is defined as a range in the display name delimited by whitespace. For example,
* the display name "Phillips Thomas Jr" contains three tokens: "phillips", "thomas", and "jr".
*
* A match must begin at the start of a token.
* For example, typing 846(Tho) would match "Phillips Thomas", but 466(hom) would not.
*
* 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. For now, matchList will contain a maximum of one match
* position. If we intend to support initial matching in the future, matchList could possibly
* contain more than one match position.
*/
@VisibleForTesting
boolean matchesCombination(String displayName, String query,
ArrayList<SmartDialMatchPosition> matchList) {
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);
if ((ch >= 'A') && (ch <= 'Z')) {
// Simply change the ascii code to the lower case version instead of using
// toLowerCase for efficiency
ch += 32;
}
if ((ch >= 'a') && (ch <= 'z')) {
// a starts at index 0
if (LETTERS_TO_DIGITS[ch - 'a'] != query.charAt(queryStart)) {
// we did not find a match
queryStart = 0;
seperatorCount = 0;
while (nameStart < nameLength &&
!Character.isWhitespace(displayName.charAt(nameStart))) {
nameStart++;
}
nameStart++;
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));
return true;
}
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++;
}
}
}
return false;
}
public boolean matches(String displayName) {
mMatchPositions.clear();
return matchesCombination(displayName, mQuery, mMatchPositions);
}
public ArrayList<SmartDialMatchPosition> getMatchPositions() {
return mMatchPositions;
}
public String getQuery() {
return mQuery;
}
}
|
