1 /*
2  * Copyright (C) 2022 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 package com.android.quicksearchbox
17 
18 import android.text.SpannableString
19 import android.text.Spanned
20 import android.util.Log
21 import com.android.quicksearchbox.util.LevenshteinDistance
22 import com.android.quicksearchbox.util.LevenshteinDistance.Token
23 import com.google.common.annotations.VisibleForTesting
24 import java.util.Locale
25 
26 /**
27  * Suggestion formatter using the Levenshtein distance (minimum edit distance) to calculate the
28  * formatting.
29  */
30 class LevenshteinSuggestionFormatter(spanFactory: TextAppearanceFactory?) :
31   SuggestionFormatter(spanFactory!!) {
32   @Override
formatSuggestionnull33   override fun formatSuggestion(query: String?, suggestion: String?): Spanned {
34     var mQuery = query
35     if (DBG) Log.d(TAG, "formatSuggestion('$mQuery', '$suggestion')")
36     mQuery = normalizeQuery(mQuery)
37     val queryTokens: Array<Token?> = tokenize(mQuery)
38     val suggestionTokens: Array<Token?> = tokenize(suggestion)
39     val matches = findMatches(queryTokens, suggestionTokens)
40     if (DBG) {
41       Log.d(TAG, "source = $queryTokens")
42       Log.d(TAG, "target = $suggestionTokens")
43       Log.d(TAG, "matches = $matches")
44     }
45     val str = SpannableString(suggestion)
46     val matchesLen = matches.size
47     for (i in 0 until matchesLen) {
48       val t: Token? = suggestionTokens[i]
49       var sourceLen = 0
50       val thisMatch = matches[i]
51       if (thisMatch >= 0) {
52         sourceLen = queryTokens[thisMatch]!!.length
53       }
54       applySuggestedTextStyle(str, t!!.mStart + sourceLen, t.mEnd)
55       applyQueryTextStyle(str, t.mStart, t.mStart + sourceLen)
56     }
57     return str
58   }
59 
normalizeQuerynull60   private fun normalizeQuery(query: String?): String? {
61     return query?.lowercase(Locale.getDefault())
62   }
63 
64   /**
65    * Finds which tokens in the target match tokens in the source.
66    *
67    * @param source List of source tokens (i.e. user query)
68    * @param target List of target tokens (i.e. suggestion)
69    * @return The indices into source which target tokens correspond to. A non-negative value n at
70    * position i means that target token i matches source token n. A negative value means that the
71    * target token i does not match any source token.
72    */
73   @VisibleForTesting
findMatchesnull74   fun findMatches(source: Array<Token?>?, target: Array<Token?>): IntArray {
75     val table = LevenshteinDistance(source, target)
76     table.calculate()
77     val targetLen = target.size
78     val result = IntArray(targetLen)
79     val ops: Array<LevenshteinDistance.EditOperation?> = table.targetOperations
80     for (i in 0 until targetLen) {
81       if (ops[i]!!.type == LevenshteinDistance.EDIT_UNCHANGED) {
82         result[i] = ops[i]!!.position
83       } else {
84         result[i] = -1
85       }
86     }
87     return result
88   }
89 
90   @VisibleForTesting
tokenizenull91   fun tokenize(seq: String?): Array<Token?> {
92     var pos = 0
93     val len: Int = seq!!.length
94     val chars = seq.toCharArray()
95     // There can't be more tokens than characters, make an array that is large enough
96     val tokens: Array<Token?> = arrayOfNulls<Token>(len)
97     var tokenCount = 0
98     while (pos < len) {
99       while (pos < len && (chars[pos] == ' ' || chars[pos] == '\t')) {
100         pos++
101       }
102       val start = pos
103       while (pos < len && !(chars[pos] == ' ' || chars[pos] == '\t')) {
104         pos++
105       }
106       val end = pos
107       if (start != end) {
108         tokens[tokenCount++] = Token(chars, start, end)
109       }
110     }
111     // Create a token array of the right size and return
112     val ret: Array<Token?> = arrayOfNulls<Token>(tokenCount)
113     System.arraycopy(tokens, 0, ret, 0, tokenCount)
114     return ret
115   }
116 
117   companion object {
118     private const val DBG = false
119     private const val TAG = "QSB.LevenshteinSuggestionFormatter"
120   }
121 }
122