1 /* 2 * Copyright (C) 2017 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License 15 */ 16 17 package com.android.dialer.searchfragment.cp2; 18 19 import android.support.v4.util.ArraySet; 20 import android.text.TextUtils; 21 import java.util.Set; 22 23 /** Ternary Search Tree for searching a list of contacts. */ 24 public class ContactTernarySearchTree { 25 26 private Node root; 27 28 /** 29 * Add {@code value} to all middle and end {@link Node#values} that correspond to {@code key}. 30 * 31 * <p>For example, if {@code key} were "FOO", {@code value} would be added to nodes "F", "O" and 32 * "O". But if the traversal required visiting {@link Node#left} or {@link Node#right}, {@code 33 * value} wouldn't be added to those nodes. 34 */ put(String key, int value)35 public void put(String key, int value) { 36 if (TextUtils.isEmpty(key)) { 37 return; 38 } 39 root = put(root, key, value, 0); 40 } 41 put(Node node, String key, int value, int position)42 private Node put(Node node, String key, int value, int position) { 43 char c = key.charAt(position); 44 if (node == null) { 45 node = new Node(); 46 node.key = c; 47 } 48 if (c < node.key) { 49 node.left = put(node.left, key, value, position); 50 } else if (c > node.key) { 51 node.right = put(node.right, key, value, position); 52 } else if (position < key.length() - 1) { 53 node.values.add(value); 54 node.mid = put(node.mid, key, value, position + 1); 55 } else { 56 node.values.add(value); 57 } 58 return node; 59 } 60 61 /** Returns true if {@code key} is contained in the trie. */ contains(String key)62 public boolean contains(String key) { 63 return !get(key).isEmpty(); 64 } 65 66 /** Return value stored at Node (in this case, a set of integers). */ get(String key)67 public Set<Integer> get(String key) { 68 Node x = get(root, key, 0); 69 return x == null ? new ArraySet<>() : x.values; 70 } 71 get(Node node, String key, int position)72 private Node get(Node node, String key, int position) { 73 if (node == null) { 74 return null; 75 } 76 char c = key.charAt(position); 77 if (c < node.key) { 78 return get(node.left, key, position); 79 } else if (c > node.key) { 80 return get(node.right, key, position); 81 } else if (position < key.length() - 1) { 82 return get(node.mid, key, position + 1); 83 } else { 84 return node; 85 } 86 } 87 88 /** Node in ternary search trie. Children are denoted as left, middle and right nodes. */ 89 private static class Node { 90 private char key; 91 private final Set<Integer> values = new ArraySet<>(); 92 93 private Node left; 94 private Node mid; 95 private Node right; 96 } 97 } 98