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