Allow name matching for contacts with numbers in their name
For SmartDialTrie, also include numbers as valid characters when
calculating indexes when generating the byte array.
For SmartDialNameMatcher, include '0'-'9' as valid latin characters,
and handle them appropriately after remapping accented characters.
Also fixed a subtle matching bug that would manifest itself when
matching against multiple tokens with similar initials - E.g.
"Dr.Dredd"
Bug 8659001
Change-Id: If461d2760a723ef7fd03dda0c1a1515cd7b44cf6
diff --git a/src/com/android/dialer/dialpad/SmartDialNameMatcher.java b/src/com/android/dialer/dialpad/SmartDialNameMatcher.java
index 4d39481..f8877c6 100644
--- a/src/com/android/dialer/dialpad/SmartDialNameMatcher.java
+++ b/src/com/android/dialer/dialpad/SmartDialNameMatcher.java
@@ -578,17 +578,42 @@
char ch = displayName.charAt(nameStart);
// Strip diacritics from accented characters if any
ch = remapAccentedChars(ch);
- if (isLowercaseLatin(ch)) {
- // a starts at index 0
- if (LATIN_LETTERS_TO_DIGITS[ch - 'a'] != query.charAt(queryStart)) {
- // we did not find a match
- queryStart = 0;
- seperatorCount = 0;
- while (nameStart < nameLength &&
- isLowercaseLatin(remapAccentedChars(displayName.charAt(nameStart)))) {
+ if (isLowercaseLatinLetterOrDigit(ch)) {
+ if (ch >= 'a' && ch <= 'z') {
+ // a starts at index 0. If ch >= '0' && ch <= '9', we don't have to do anything
+ ch = LATIN_LETTERS_TO_DIGITS[ch - 'a'];
+ }
+ 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 || isLowercaseLatinLetterOrDigit(remapAccentedChars(
+ displayName.charAt(nameStart - 1)))) {
+ // skip to the next token, in the case of 1 or 2.
+ while (nameStart < nameLength &&
+ isLowercaseLatinLetterOrDigit(remapAccentedChars(
+ displayName.charAt(nameStart)))) {
+ nameStart++;
+ }
nameStart++;
}
- nameStart++;
+
+ // Restart the query and set the correct token position
+ queryStart = 0;
+ seperatorCount = 0;
tokenStart = nameStart;
} else {
if (queryStart == queryLength - 1) {
@@ -605,7 +630,8 @@
// find the next separator in the query string
int j;
for (j = nameStart; j < nameLength; j++) {
- if (!isLowercaseLatin(remapAccentedChars(displayName.charAt(j)))) {
+ if (!isLowercaseLatinLetterOrDigit(remapAccentedChars(
+ displayName.charAt(j)))) {
break;
}
}
@@ -659,10 +685,10 @@
}
/*
- * Returns true if the character is a lowercase latin character(i.e. non-separator).
+ * Returns true if the character is a lowercase latin character or digit(i.e. non-separator).
*/
- private boolean isLowercaseLatin(char ch) {
- return ch >= 'a' && ch <= 'z';
+ private boolean isLowercaseLatinLetterOrDigit(char ch) {
+ return (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9');
}
public boolean matches(String displayName) {
diff --git a/src/com/android/dialer/dialpad/SmartDialTrie.java b/src/com/android/dialer/dialpad/SmartDialTrie.java
index 9dfc0c9..0de28a5 100644
--- a/src/com/android/dialer/dialpad/SmartDialTrie.java
+++ b/src/com/android/dialer/dialpad/SmartDialTrie.java
@@ -119,7 +119,7 @@
// Preconvert the display name into a byte array containing indexes to avoid having to
// remap each character over multiple passes
putForPrefix(contact, mRoot, toByteArray(contact.displayName), 0,
- contact.displayName.length(), true, true);
+ contact.displayName.length(), true);
// We don't need to do the same for phone numbers since we only make one pass over them.
// Strip the calling code from the phone number here
if (!TextUtils.isEmpty(contact.phoneNumber)) {
@@ -224,6 +224,8 @@
c = SmartDialNameMatcher.remapAccentedChars(chars.charAt(i));
if (c >= 'a' && c <= 'z') {
result[i] = (byte) (mCharacterMap[c - 'a'] - '0');
+ } else if (c >= '0' && c <= '9') {
+ result[i] = (byte) (c - '0');
} else {
result[i] = -1;
}
@@ -274,11 +276,9 @@
* @param end - Last index(not inclusive) of the byte array
* @param isFullName If true, prefix will be treated as a full name and recursive calls to add
* initial matches as well as name token matches into the trie will be made.
- * @param addInitials If true, recursive calls to add initial matches into the trie will be
- * made.
*/
private void putForPrefix(ContactNumber contact, Node root, byte[] prefix, int start, int end,
- boolean isFullName, boolean addInitials) {
+ boolean isFullName) {
Node current = root;
Node initialNode = root;
final int length = end;
@@ -291,22 +291,21 @@
atSeparator = false;
// encountered a new name token, so add this token into the tree starting from
// the root node
- if (addInitials || isFullName) {
- if (initialNode != this.mRoot) {
- if (isFullName) {
- putForPrefix(contact, this.mRoot, prefix, i, prefix.length, false,
- true);
- }
- putForPrefix(contact, initialNode,
- prefix, i, prefix.length, false, false);
+ if (initialNode != this.mRoot) {
+ if (isFullName) {
+ putForPrefix(contact, this.mRoot, prefix, i, prefix.length, false);
+ }
+ if (initialNode != root) {
+ putForPrefix(contact, initialNode, prefix, i, prefix.length,
+ false);
}
}
- // Finding a new name token means we find a new initial character as well.
- // Use initialNode to track the current node at which initial characters match.
- // E.g. If we are at character m of John W S(m)ith, then the current initial
- // node is indexed by the characters JWS.
- initialNode = initialNode.getChild(index, true);
+ // Set initial node to the node indexed by the first character of the current
+ // prefix
+ if (initialNode == root) {
+ initialNode = initialNode.getChild(index, true);
+ }
}
current = current.getChild(index, true);
} else {
@@ -316,6 +315,15 @@
current.add(contact);
}
+ /* Used only for testing to verify we insert the correct number of entries into the trie */
+ @VisibleForTesting
+ int numEntries() {
+ final ArrayList<ContactNumber> result = Lists.newArrayList();
+ getAll(mRoot, result);
+ return result.size();
+ }
+
+
@VisibleForTesting
public int size() {
return mSize;
diff --git a/tests/src/com/android/dialer/dialpad/SmartDialNameMatcherTest.java b/tests/src/com/android/dialer/dialpad/SmartDialNameMatcherTest.java
index 3c481d0..83b8560 100644
--- a/tests/src/com/android/dialer/dialpad/SmartDialNameMatcherTest.java
+++ b/tests/src/com/android/dialer/dialpad/SmartDialNameMatcherTest.java
@@ -89,10 +89,21 @@
checkMatches("William-John Smith", "95646", true, 0, 1, 8, 12);
// jsmi matches William (J)ohn-(Smi)th
checkMatches("William John-Smith", "5764", true, 8, 9, 13, 16);
+ // wsmi matches (W)illiam John (Smi)th
+ checkMatches("William John-Smith", "9764", true, 0, 1, 13, 16);
// make sure multiple spaces don't mess things up
checkMatches("William John---Smith", "5764", true, 15, 16, 22, 25);
-
+ // match tokens that are located directly after a non-space separator (studio)
checkMatches("Berkeley Hair-Studio", "788346", true, 14, 20);
+ // match tokens with same initials
+ checkMatches("H.Harold", "427653", true, 2, 8);
+ // various matching combinations of tokens with similar initials
+ checkMatches("Yo-Yoghurt Land", "964487", true, 3, 9);
+ checkMatches("Yo-Yoghurt Land", "96448785263", true, 3, 15);
+ checkMatches("Yo-Yoghurt Land", "95263", true, 3, 4, 11, 15);
+ checkMatches("Yo-Yoghurt Land", "995263", true, 0, 1, 3, 4, 11, 15);
+
+ checkMatches("ab zz ef", "23", true, 0, 1, 6, 7);
}
public void testMatches_repeatedSeparators() {
@@ -117,6 +128,17 @@
checkMatches("ÄÖÜäöü", "268268", true, 0, 6);
}
+ public void testMatches_NumberInName() {
+ // Number used as display name
+ checkMatches("+1-123-456-6789", "1234566789", true, 3, 15);
+ // Mix of numbers and letters
+ checkMatches("3rd Grade Teacher", "373", true, 0, 3);
+ checkMatches("1800 Win A Prize", "1800", true, 0, 4);
+ checkMatches("1800 Win A Prize", "1800946277493", true, 0, 16);
+ checkMatches("1800 Win A Prize", "977493", true, 5, 6, 11, 16);
+ }
+
+
// TODO: Great if it was treated as "s" or "ss. Figure out if possible without prefix trie?
@Suppress
public void testMatches_germanSharpS() {
diff --git a/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java b/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java
index 7f55263..cd87b66 100644
--- a/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java
+++ b/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java
@@ -106,6 +106,14 @@
assertTrue(checkContains(trie, martinjuniorharry, "6542"));
// 542 corresponds to jha = "Martin (J)r (Ha)rry"
assertTrue(checkContains(trie, martinjuniorharry, "542"));
+ // 642 corresponds to mha = "(M)artin Jr (Ha)rry"
+ assertTrue(checkContains(trie, martinjuniorharry, "642"));
+ // 6542779 (M)artin (J)r (Harry)
+ assertTrue(checkContains(trie, martinjuniorharry, "6542779"));
+ // 65742779 (M)artin (Jr) (Harry)
+ assertTrue(checkContains(trie, martinjuniorharry, "65742779"));
+ // 542779 Martin (J)r (Harry)
+ assertTrue(checkContains(trie, martinjuniorharry, "542779"));
// 547 doesn't match
assertFalse(checkContains(trie, martinjuniorharry, "547"));
// 655 doesn't match
@@ -114,6 +122,39 @@
assertFalse(checkContains(trie, martinjuniorharry, "653"));
// 6543 doesn't match
assertFalse(checkContains(trie, martinjuniorharry, "6543"));
+ // 7(2^3 -1) entries for the name, and 1 for the number
+ assertEquals(8, trie.numEntries());
+ }
+
+ public void testPutForInitialMatchesCombinations() {
+ final SmartDialTrie trie = new SmartDialTrie();
+ final ContactNumber alphabet = new ContactNumber(0, "abc def ghi jkl mno pqrs tuv wxyz",
+ "1", "1", 2);
+ trie.put(alphabet);
+ // 255 (2^8 - 1) combinations for the name, and 1 for the number
+ assertEquals(256, trie.numEntries());
+
+ // Test every single combination of the leading initials of each name token by generating
+ // strings consisting of all combinations of the digits 2-9.
+ final StringBuilder sb = new StringBuilder();
+
+ // Create an array of bit positions 0b10000000, 0b01000000, 0b00100000, ...
+ final int[] pos = new int[8];
+ for (int i = 2; i <= 9; i++) {
+ pos[i - 2] = 1 << (9 - i);
+ }
+ for (int i = 1; i < 256; i++) {
+ sb.setLength(0);
+ // If the bit at nth position is set to true, then add the nth initial to the target
+ // string
+ for (int j = 2; j <= 9; j++) {
+ if ((i & pos[j - 2]) > 0) {
+ sb.append(j);
+ }
+ }
+ assertTrue(checkContains(trie, alphabet, sb.toString()));
+ }
+
}
public void testSeparators() {
@@ -141,6 +182,19 @@
assertTrue(checkContains(trie, bronte, "276683"));
}
+ public void testNumbersInName() {
+ final SmartDialTrie trie = new SmartDialTrie();
+ final ContactNumber contact = new ContactNumber(0, "12345678", "0", "0", 1);
+ final ContactNumber teacher = new ContactNumber(1, "1st Grade Teacher", "0", "1", 2);
+ trie.put(contact);
+ trie.put(teacher);
+ assertTrue(checkContains(trie, contact, "12345678"));
+ // (1st Grade) Teacher
+ assertTrue(checkContains(trie, teacher, "17847233"));
+ // (1)st (G)rade (Tea)cher
+ assertTrue(checkContains(trie, teacher, "14832"));
+ }
+
public void testPutForNumbers() {
final SmartDialTrie trie = new SmartDialTrie();
final ContactNumber contactno1 = new ContactNumber(0, "James", "510-527-2357", "0", 1);
