diff options
4 files changed, 141 insertions, 31 deletions
diff --git a/src/com/android/dialer/dialpad/SmartDialNameMatcher.java b/src/com/android/dialer/dialpad/SmartDialNameMatcher.java index 4d3948100..f8877c665 100644 --- a/src/com/android/dialer/dialpad/SmartDialNameMatcher.java +++ b/src/com/android/dialer/dialpad/SmartDialNameMatcher.java @@ -578,17 +578,42 @@ public class SmartDialNameMatcher { 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 @@ public class SmartDialNameMatcher { // 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 @@ public class SmartDialNameMatcher { } /* - * 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 9dfc0c95a..0de28a578 100644 --- a/src/com/android/dialer/dialpad/SmartDialTrie.java +++ b/src/com/android/dialer/dialpad/SmartDialTrie.java @@ -119,7 +119,7 @@ public class SmartDialTrie { // 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 @@ public class SmartDialTrie { 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 @@ public class SmartDialTrie { * @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 @@ public class SmartDialTrie { 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 @@ public class SmartDialTrie { 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 3c481d0c7..83b856059 100644 --- a/tests/src/com/android/dialer/dialpad/SmartDialNameMatcherTest.java +++ b/tests/src/com/android/dialer/dialpad/SmartDialNameMatcherTest.java @@ -89,10 +89,21 @@ public class SmartDialNameMatcherTest extends TestCase { 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 @@ public class SmartDialNameMatcherTest extends TestCase { 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 7f55263e1..cd87b6613 100644 --- a/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java +++ b/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java @@ -106,6 +106,14 @@ public class SmartDialTrieTest extends TestCase{ 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 @@ public class SmartDialTrieTest extends TestCase{ 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 @@ public class SmartDialTrieTest extends TestCase{ 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); |