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