From 1636789520efce24c487c64f95f97f510c505661 Mon Sep 17 00:00:00 2001 From: calderwoodra Date: Wed, 15 Nov 2017 15:36:07 -0800 Subject: 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 --- .../searchfragment/common/QueryFilteringUtil.java | 2 +- .../searchfragment/cp2/ContactFilterCursor.java | 88 ++++++++++++++++---- .../cp2/ContactTernarySearchTree.java | 97 ++++++++++++++++++++++ 3 files changed, 170 insertions(+), 17 deletions(-) create mode 100644 java/com/android/dialer/searchfragment/cp2/ContactTernarySearchTree.java (limited to 'java/com/android/dialer/searchfragment') 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 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); } @@ -224,6 +227,69 @@ final class ContactFilterCursor implements Cursor { return contactIdContacts; } + /** + * Returns a ternary search trie based on the contact at the cursor's current position with the + * following terms inserted: + * + * + */ + private static ContactTernarySearchTree buildContactSearchTree(Context context, Cursor cursor) { + ContactTernarySearchTree tree = new ContactTernarySearchTree(); + cursor.moveToPosition(-1); + while (cursor.moveToNext()) { + int position = cursor.getPosition(); + Set 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 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: + * + *
    + *
  • The white space divided parts of phrase + *
  • The T9 representation of the white space divided parts of phrase + *
  • The T9 representation of the initials (i.e. first character of each part) of phrase + *
+ */ + private static void addMatches(Context context, Set 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. * @@ -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}. + * + *

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 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 values = new ArraySet<>(); + + private Node left; + private Node mid; + private Node right; + } +} -- cgit v1.2.3