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.settings.intelligence.search.query;
18 
19 import android.text.TextUtils;
20 
21 /**
22  * Utils for Query-time operations.
23  */
24 
25 public class SearchQueryUtils {
26 
27     public static final int NAME_NO_MATCH = -1;
28 
29     /**
30      * Returns "difference" between resultName and query string. resultName must contain all
31      * characters from query as a prefix to a word, in the same order.
32      * If not, returns NAME_NO_MATCH.
33      * If they do match, returns an int value representing  how different they are,
34      * and larger values means they are less similar.
35      * <p/>
36      * Example:
37      * resultName: Abcde, query: Abcde, Returns 0
38      * resultName: Abcde, query: abc, Returns 2
39      * resultName: Abcde, query: ab, Returns 3
40      * resultName: Abcde, query: bc, Returns NAME_NO_MATCH
41      * resultName: Abcde, query: xyz, Returns NAME_NO_MATCH
42      * resultName: Abc de, query: de, Returns 4
43      */
getWordDifference(String resultName, String query)44     public static int getWordDifference(String resultName, String query) {
45         if (TextUtils.isEmpty(resultName) || TextUtils.isEmpty(query)) {
46             return NAME_NO_MATCH;
47         }
48 
49         final char[] queryTokens = query.toLowerCase().toCharArray();
50         final char[] resultTokens = resultName.toLowerCase().toCharArray();
51         final int resultLength = resultTokens.length;
52         if (queryTokens.length > resultLength) {
53             return NAME_NO_MATCH;
54         }
55 
56         int i = 0;
57         int j;
58 
59         while (i < resultLength) {
60             j = 0;
61             // Currently matching a prefix
62             while ((i + j < resultLength) && (queryTokens[j] == resultTokens[i + j])) {
63                 // Matched the entire query
64                 if (++j >= queryTokens.length) {
65                     // Use the diff in length as a proxy of how close the 2 words match.
66                     // Value range from 0 to infinity.
67                     return resultLength - queryTokens.length;
68                 }
69             }
70 
71             i += j;
72 
73             // Remaining string is longer that the query or we have search the whole result name.
74             if (queryTokens.length > resultLength - i) {
75                 return NAME_NO_MATCH;
76             }
77 
78             // This is the first index where result name and query name are different
79             // Find the next space in the result name or the end of the result name.
80             while ((i < resultLength) && (!Character.isWhitespace(resultTokens[i++]))) ;
81 
82             // Find the start of the next word
83             while ((i < resultLength) && !(Character.isLetter(resultTokens[i])
84                     || Character.isDigit(resultTokens[i]))) {
85                 // Increment in body because we cannot guarantee which condition was true
86                 i++;
87             }
88         }
89         return NAME_NO_MATCH;
90     }
91 }
92