diff options
Diffstat (limited to 'java/com')
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; + } +} |