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

2 files changed, 64 insertions, 30 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;