Optimize contact search by using a Ternary Search Tree.

This change updates search fragment to now preprocess query
results and hold them in memory. This significantly improves the
lookup runtime to be O(logn) on average and O(N) worst case.

Bug: 69100384
Test: existing (plus some time measurement regression tests)
PiperOrigin-RevId: 175891990
Change-Id: I6d7ae61c478b544af42d954af4e8580e052693ba

3 files changed, 170 insertions, 17 deletions

diff --git a/java/com/android/dialer/searchfragment/common/QueryFilteringUtil.java b/java/com/android/dialer/searchfragment/common/QueryFilteringUtil.java
index 1ecb486d2..c4ff27545 100644
--- a/java/com/android/dialer/searchfragment/common/QueryFilteringUtil.java
+++ b/java/com/android/dialer/searchfragment/common/QueryFilteringUtil.java
@@ -137,7 +137,7 @@ public class QueryFilteringUtil {
    * @param context The context
    * @return The original string with characters replaced with T9 representations.
    */
-  static String getT9Representation(String s, Context context) {
+  public static String getT9Representation(String s, Context context) {
     StringBuilder builder = new StringBuilder(s.length());
     for (char c : s.toLowerCase().toCharArray()) {
       builder.append(getDigit(c, context));
diff --git a/java/com/android/dialer/searchfragment/cp2/ContactFilterCursor.java b/java/com/android/dialer/searchfragment/cp2/ContactFilterCursor.java
index 166902b2b..dc16f9dd0 100644
--- a/java/com/android/dialer/searchfragment/cp2/ContactFilterCursor.java
+++ b/java/com/android/dialer/searchfragment/cp2/ContactFilterCursor.java
@@ -39,6 +39,7 @@ import java.lang.annotation.RetentionPolicy;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
+import java.util.Locale;
 import java.util.Set;
 
 /**
@@ -52,6 +53,7 @@ final class ContactFilterCursor implements Cursor {
   private final Cursor cursor;
   // List of cursor ids that are valid for displaying after filtering.
   private final List<Integer> queryFilteredPositions = new ArrayList<>();
+  private final ContactTernarySearchTree contactTree;
 
   private int currentPosition = 0;
 
@@ -77,6 +79,7 @@ final class ContactFilterCursor implements Cursor {
    */
   ContactFilterCursor(Cursor cursor, @Nullable String query, Context context) {
     this.cursor = createCursor(cursor);
+    contactTree = buildContactSearchTree(context, this.cursor);
     filter(query, context);
   }
 
@@ -225,6 +228,69 @@ final class ContactFilterCursor implements Cursor {
   }
 
   /**
+   * Returns a ternary search trie based on the contact at the cursor's current position with the
+   * following terms inserted:
+   *
+   * <ul>
+   *   <li>Contact's whole display name, company name and nickname.
+   *   <li>The T9 representations of those values
+   *   <li>The T9 initials of those values
+   *   <li>All possible substrings a contact's phone number
+   * </ul>
+   */
+  private static ContactTernarySearchTree buildContactSearchTree(Context context, Cursor cursor) {
+    ContactTernarySearchTree tree = new ContactTernarySearchTree();
+    cursor.moveToPosition(-1);
+    while (cursor.moveToNext()) {
+      int position = cursor.getPosition();
+      Set<String> queryMatches = new ArraySet<>();
+      addMatches(context, queryMatches, cursor.getString(Projections.DISPLAY_NAME));
+      addMatches(context, queryMatches, cursor.getString(Projections.COMPANY_NAME));
+      addMatches(context, queryMatches, cursor.getString(Projections.NICKNAME));
+      for (String query : queryMatches) {
+        tree.put(query, position);
+      }
+      String number = QueryFilteringUtil.digitsOnly(cursor.getString(Projections.PHONE_NUMBER));
+      Set<String> numberSubstrings = new ArraySet<>();
+      numberSubstrings.add(number);
+      for (int start = 0; start < number.length(); start++) {
+        numberSubstrings.add(number.substring(start, number.length()));
+      }
+      for (String substring : numberSubstrings) {
+        tree.put(substring, position);
+      }
+    }
+    return tree;
+  }
+
+  /**
+   * Returns a set containing:
+   *
+   * <ul>
+   *   <li>The white space divided parts of phrase
+   *   <li>The T9 representation of the white space divided parts of phrase
+   *   <li>The T9 representation of the initials (i.e. first character of each part) of phrase
+   * </ul>
+   */
+  private static void addMatches(Context context, Set<String> existingMatches, String phrase) {
+    if (TextUtils.isEmpty(phrase)) {
+      return;
+    }
+    String initials = "";
+    phrase = phrase.toLowerCase(Locale.getDefault());
+    existingMatches.add(phrase);
+    for (String name : phrase.split("\\s")) {
+      if (TextUtils.isEmpty(name)) {
+        continue;
+      }
+      existingMatches.add(name);
+      existingMatches.add(QueryFilteringUtil.getT9Representation(name, context));
+      initials += name.charAt(0);
+    }
+    existingMatches.add(QueryFilteringUtil.getT9Representation(initials, context));
+  }
+
+  /**
    * Filters out contacts that do not match the query.
    *
    * <p>The query can have at least 1 of 3 forms:
@@ -249,24 +315,14 @@ final class ContactFilterCursor implements Cursor {
       query = "";
     }
     queryFilteredPositions.clear();
-    query = query.toLowerCase();
-    cursor.moveToPosition(-1);
-
-    while (cursor.moveToNext()) {
-      int position = cursor.getPosition();
-      String number = cursor.getString(Projections.PHONE_NUMBER);
-      String name = cursor.getString(Projections.DISPLAY_NAME);
-      String companyName = cursor.getString(Projections.COMPANY_NAME);
-      String nickName = cursor.getString(Projections.NICKNAME);
-      if (TextUtils.isEmpty(query)
-          || QueryFilteringUtil.nameMatchesT9Query(query, name, context)
-          || QueryFilteringUtil.numberMatchesNumberQuery(query, number)
-          || QueryFilteringUtil.nameContainsQuery(query, name)
-          || QueryFilteringUtil.nameContainsQuery(query, companyName)
-          || QueryFilteringUtil.nameContainsQuery(query, nickName)) {
-        queryFilteredPositions.add(position);
+    if (TextUtils.isEmpty(query)) {
+      for (int i = 0; i < cursor.getCount(); i++) {
+        queryFilteredPositions.add(i);
       }
+    } else {
+      queryFilteredPositions.addAll(contactTree.get(query.toLowerCase(Locale.getDefault())));
     }
+    Collections.sort(queryFilteredPositions);
     currentPosition = 0;
     cursor.moveToFirst();
   }
diff --git a/java/com/android/dialer/searchfragment/cp2/ContactTernarySearchTree.java b/java/com/android/dialer/searchfragment/cp2/ContactTernarySearchTree.java
new file mode 100644
index 000000000..88738e281
--- /dev/null
+++ b/java/com/android/dialer/searchfragment/cp2/ContactTernarySearchTree.java
@@ -0,0 +1,97 @@
+/*
+ * Copyright (C) 2017 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.searchfragment.cp2;
+
+import android.support.v4.util.ArraySet;
+import android.text.TextUtils;
+import java.util.Set;
+
+/** Ternary Search Tree for searching a list of contacts. */
+public class ContactTernarySearchTree {
+
+  private Node root;
+
+  /**
+   * Add {@code value} to all middle and end {@link Node#values} that correspond to {@code key}.
+   *
+   * <p>For example, if {@code key} were "FOO", {@code value} would be added to nodes "F", "O" and
+   * "O". But if the traversal required visiting {@link Node#left} or {@link Node#right}, {@code
+   * value} wouldn't be added to those nodes.
+   */
+  public void put(String key, int value) {
+    if (TextUtils.isEmpty(key)) {
+      return;
+    }
+    root = put(root, key, value, 0);
+  }
+
+  private Node put(Node node, String key, int value, int position) {
+    char c = key.charAt(position);
+    if (node == null) {
+      node = new Node();
+      node.key = c;
+    }
+    if (c < node.key) {
+      node.left = put(node.left, key, value, position);
+    } else if (c > node.key) {
+      node.right = put(node.right, key, value, position);
+    } else if (position < key.length() - 1) {
+      node.values.add(value);
+      node.mid = put(node.mid, key, value, position + 1);
+    } else {
+      node.values.add(value);
+    }
+    return node;
+  }
+
+  /** Returns true if {@code key} is contained in the trie. */
+  public boolean contains(String key) {
+    return !get(key).isEmpty();
+  }
+
+  /** Return value stored at Node (in this case, a set of integers). */
+  public Set<Integer> get(String key) {
+    Node x = get(root, key, 0);
+    return x == null ? new ArraySet<>() : x.values;
+  }
+
+  private Node get(Node node, String key, int position) {
+    if (node == null) {
+      return null;
+    }
+    char c = key.charAt(position);
+    if (c < node.key) {
+      return get(node.left, key, position);
+    } else if (c > node.key) {
+      return get(node.right, key, position);
+    } else if (position < key.length() - 1) {
+      return get(node.mid, key, position + 1);
+    } else {
+      return node;
+    }
+  }
+
+  /** Node in ternary search trie. Children are denoted as left, middle and right nodes. */
+  private static class Node {
+    private char key;
+    private final Set<Integer> values = new ArraySet<>();
+
+    private Node left;
+    private Node mid;
+    private Node right;
+  }
+}