diff options
-rw-r--r-- | src/com/android/dialer/dialpad/SmartDialCache.java | 4 | ||||
-rw-r--r-- | src/com/android/dialer/dialpad/SmartDialTrie.java | 87 | ||||
-rw-r--r-- | tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java | 105 |
3 files changed, 143 insertions, 53 deletions
diff --git a/src/com/android/dialer/dialpad/SmartDialCache.java b/src/com/android/dialer/dialpad/SmartDialCache.java index 7a11b15d8..51e900ada 100644 --- a/src/com/android/dialer/dialpad/SmartDialCache.java +++ b/src/com/android/dialer/dialpad/SmartDialCache.java @@ -111,10 +111,10 @@ public class SmartDialCache { public static final int PHONE_DISPLAY_NAME = 6; // Current contacts - those contacted within the last 3 days (in milliseconds) - final static long LAST_TIME_USED_CURRENT_MS = 3 * 24 * 60 * 60 * 1000; + final static long LAST_TIME_USED_CURRENT_MS = 3L * 24 * 60 * 60 * 1000; // Recent contacts - those contacted within the last 30 days (in milliseconds) - final static long LAST_TIME_USED_RECENT_MS = 30 * 24 * 60 * 60 * 1000; + final static long LAST_TIME_USED_RECENT_MS = 30L * 24 * 60 * 60 * 1000; final static String TIME_SINCE_LAST_USED_MS = "(? - " + Data.LAST_TIME_USED + ")"; diff --git a/src/com/android/dialer/dialpad/SmartDialTrie.java b/src/com/android/dialer/dialpad/SmartDialTrie.java index 0de28a578..04ff64c5b 100644 --- a/src/com/android/dialer/dialpad/SmartDialTrie.java +++ b/src/com/android/dialer/dialpad/SmartDialTrie.java @@ -38,6 +38,15 @@ import java.util.Set; * that uses NANP numbers.</p> */ public class SmartDialTrie { + @VisibleForTesting + static class ParseInfo { + byte[] indexes; + int nthFirstTokenPos; + int nthLastTokenPos; + } + + private static final int LAST_TOKENS_FOR_INITIALS = 2; + private static final int FIRST_TOKENS_FOR_INITIALS = 2; final Node mRoot = new Node(); private int mSize = 0; private final char[] mCharacterMap; @@ -118,8 +127,9 @@ public class SmartDialTrie { public void put(ContactNumber contact) { // 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); + final ParseInfo info = parseToIndexes(contact.displayName, FIRST_TOKENS_FOR_INITIALS, + LAST_TOKENS_FOR_INITIALS); + putForPrefix(contact, mRoot, info, 0, 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)) { @@ -215,22 +225,52 @@ public class SmartDialTrie { return new int[0]; } + /** + * Converts the given characters into a byte array of index and returns it together with offset + * information in a {@link ParseInfo} data structure. + * @param chars Characters to convert into indexes + * @param firstNTokens The first n tokens we want the offset for + * @param lastNTokens The last n tokens we want the offset for + */ @VisibleForTesting - /* package */ byte[] toByteArray(CharSequence chars) { + ParseInfo parseToIndexes(CharSequence chars, int firstNTokens, int lastNTokens) { final int length = chars.length(); final byte[] result = new byte[length]; + final ArrayList<Integer> offSets = new ArrayList<Integer>(); char c; + int tokenCount = 0; + boolean atSeparator = true; for (int i = 0; i < length; i++) { 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'); + if (c >= 'a' && c <= 'z' || c >= '0' && c <= '9') { + if (atSeparator) { + tokenCount++; + } + atSeparator = false; + if (c <= '9') { + // 0-9 + result[i] = (byte) (c - '0'); + } else { + // a-z + result[i] = (byte) (mCharacterMap[c - 'a'] - '0'); + } } else { + // Found the last character of the current token + if (!atSeparator) { + offSets.add(i); + } result[i] = -1; + atSeparator = true; } } - return result; + + final ParseInfo info = new ParseInfo(); + info.indexes = result; + info.nthFirstTokenPos = offSets.size() >= firstNTokens ? offSets.get(firstNTokens - 1) : + length - 1; + info.nthLastTokenPos = offSets.size() >= lastNTokens ? offSets.get(offSets.size() - + lastNTokens) : 0; + return info; } /** @@ -248,7 +288,7 @@ public class SmartDialTrie { * * @param contact - Contact to add to the trie * @param phoneNumber - Phone number of the contact - * @param offset - The nth character of the phone number to start from + * @param offSet - The nth character of the phone number to start from */ private void putNumber(ContactNumber contact, String phoneNumber, int offSet) { Preconditions.checkArgument(offSet < phoneNumber.length()); @@ -268,24 +308,29 @@ public class SmartDialTrie { * Place an contact into the trie using at the provided node using the provided prefix. Uses as * the input prefix a byte array instead of a CharSequence, as we will be traversing the array * multiple times and it is more efficient to pre-convert the prefix into indexes before hand. + * Adds initial matches for the first token, and the last N tokens in the name. * * @param contact Contact to put * @param root Root node to use as the starting point - * @param prefix Sequence of bytes which represent the index at + * @param parseInfo ParseInfo data structure containing the converted byte array, as well as + * token offsets that determine which tokens should have entries added for initial + * search * @param start - Starting index of the byte array - * @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 isFullName If true, prefix will be treated as a full name and everytime a new name + * token is encountered, the rest of the name segment is added into the trie. */ - private void putForPrefix(ContactNumber contact, Node root, byte[] prefix, int start, int end, + private void putForPrefix(ContactNumber contact, Node root, ParseInfo info, int start, boolean isFullName) { + final boolean addInitialMatches = (start >= info.nthLastTokenPos || + start <= info.nthFirstTokenPos); + final byte[] indexes = info.indexes; Node current = root; Node initialNode = root; - final int length = end; + final int length = indexes.length; boolean atSeparator = true; byte index; for (int i = start; i < length; i++) { - index = prefix[i]; + index = indexes[i]; if (index > -1) { if (atSeparator) { atSeparator = false; @@ -293,14 +338,14 @@ public class SmartDialTrie { // the root node if (initialNode != this.mRoot) { if (isFullName) { - putForPrefix(contact, this.mRoot, prefix, i, prefix.length, false); + putForPrefix(contact, this.mRoot, info, i, false); } - if (initialNode != root) { - putForPrefix(contact, initialNode, prefix, i, prefix.length, - false); + if (addInitialMatches && + (i >= info.nthLastTokenPos || i <= info.nthFirstTokenPos) && + initialNode != root) { + putForPrefix(contact, initialNode, info, i, false); } } - // Set initial node to the node indexed by the first character of the current // prefix if (initialNode == root) { diff --git a/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java b/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java index cd87b6613..876e00de7 100644 --- a/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java +++ b/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java @@ -19,6 +19,7 @@ package com.android.dialer.dialpad; import static com.android.dialer.dialpad.SmartDialCache.ContactNumber; import com.android.dialer.dialpad.SmartDialTrie.Node; +import com.android.dialer.dialpad.SmartDialTrie.ParseInfo; import android.test.suitebuilder.annotation.SmallTest; @@ -129,47 +130,91 @@ public class SmartDialTrieTest extends TestCase{ 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); + "12345678", "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())); - } + assertEquals(20, trie.numEntries()); + // 8 name entries (abcdefghi..., defghi..., ...) + assertTrue(checkContains(trie, alphabet, "22233344455566677778889999")); + assertTrue(checkContains(trie, alphabet, "33344455566677778889999")); + assertTrue(checkContains(trie, alphabet, "44455566677778889999")); + assertTrue(checkContains(trie, alphabet, "55566677778889999")); + assertTrue(checkContains(trie, alphabet, "66677778889999")); + assertTrue(checkContains(trie, alphabet, "77778889999")); + assertTrue(checkContains(trie, alphabet, "8889999")); + assertTrue(checkContains(trie, alphabet, "9999")); + // 1 number entry + assertTrue(checkContains(trie, alphabet, "12345678")); + // 11 initial entries (adtw, adw, adt, ad, atw, at, aw, dt, dw, dtw, tw) + // 4c2(6) + 4c3(4) + 4c4(1) + assertTrue(checkContains(trie, alphabet, "2389999")); + assertTrue(checkContains(trie, alphabet, "239999")); + assertTrue(checkContains(trie, alphabet, "23888")); + assertTrue(checkContains(trie, alphabet, "2333")); + assertTrue(checkContains(trie, alphabet, "289999")); + assertTrue(checkContains(trie, alphabet, "2888")); + assertTrue(checkContains(trie, alphabet, "29999")); + assertTrue(checkContains(trie, alphabet, "3888")); + assertTrue(checkContains(trie, alphabet, "39999")); + assertTrue(checkContains(trie, alphabet, "389999")); + assertTrue(checkContains(trie, alphabet, "89999")); + } + public void testCheckLongToken() { + final SmartDialTrie trie = new SmartDialTrie(); + final ContactNumber alphabet = new ContactNumber(0, " aaaa bbbb cccc dddd eeee ffff gggg" + + " hhhh iiii jjjj kkkk llll mmmm nnnn oooo pppp qqqq rrrr ssss tttt uuuu vvvv " + + " wwww xxxx yyyy zzzz", "1", "1", 2); + // Make sure the check to prevent overly long tokens from causing an OOM kicks in + trie.put(alphabet); + assertTrue(checkContains(trie, alphabet, "2222")); + // 26 name entries (aaaabbbbcccc...., bbbbccccdddd...., ccccdddd...) + // 1 number entry + // 11 initial entries 4c2(6) + 4c3(4) + 4c4(1) + assertEquals(38, trie.numEntries()); + + final ContactNumber alphabet2 = new ContactNumber(0, "aaaabbbbccccddddeeeeffffgggg" + + "hhhhiiiijjjjkkkkllllmmmmnnnnooooppppqqqqrrrrssssttttuuuuvvvvwwwwxxxxyyyyzzzz", + "1", "1", 2); + trie.put(alphabet2); + // added one name, and one number entry + assertEquals(40, trie.numEntries()); } - public void testSeparators() { - SmartDialTrie trie = new SmartDialTrie(); - String name = "Mcdonald Jamie-Cullum"; - byte[] bytes = trie.toByteArray(name); + public void testParseInfo() { + final SmartDialTrie trie = new SmartDialTrie(); + final String name = "Mcdonald Jamie-Cullum"; + final ParseInfo info = trie.parseToIndexes(name, 2, 2); // Make sure the dash is correctly converted to a separator character for (int i = 0; i < name.length(); i++) { // separators at position 8 and 12 if (i == 8 || i == 14) { - assertTrue(bytes[i] == -1); + assertTrue(info.indexes[i] == -1); } else { - assertFalse(bytes[i] == -1); + assertFalse(info.indexes[i] == -1); } } + assertEquals(14, info.nthFirstTokenPos); + assertEquals(8, info.nthLastTokenPos); + + final String name2 = "aaa bbb ccc ddd eee fff ggg hhh iii jjj kkk"; + final ParseInfo info2 = trie.parseToIndexes(name2, 2, 2); + assertEquals(7, info2.nthFirstTokenPos); + assertEquals(35, info2.nthLastTokenPos); + + final String name3 = "this is- a,test name"; + final ParseInfo info3 = trie.parseToIndexes(name3, 3, 3); + assertEquals(11, info3.nthFirstTokenPos); + assertEquals(8, info3.nthLastTokenPos); + + final String name4 = "M c-Donald James"; + final ParseInfo info4 = trie.parseToIndexes(name4, 2, 3); + assertEquals(3, info4.nthFirstTokenPos); + assertEquals(1, info4.nthLastTokenPos); + + final String name5 = " Aa'Bb c dddd e'e"; + final ParseInfo info5 = trie.parseToIndexes(name5, 4, 4); + assertEquals(21, info5.nthFirstTokenPos); + assertEquals(8, info5.nthLastTokenPos); } public void testAccentedCharacters() { |