1 /*
2  * Copyright (C) 2010 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.quicksearchbox;
18 
19 import com.android.quicksearchbox.MockTextAppearanceFactory.MockStyleSpan;
20 import com.android.quicksearchbox.util.LevenshteinDistance.Token;
21 
22 import android.test.AndroidTestCase;
23 import android.test.suitebuilder.annotation.SmallTest;
24 import android.text.Spanned;
25 
26 /**
27  * Tests for {@link LevenshteinSuggestionFormatter}.
28  */
29 @SmallTest
30 public class LevenshteinFormatterTest extends AndroidTestCase {
31 
32     private LevenshteinSuggestionFormatter mFormatter;
33     private int mSuggestedStyle;
34     private int mQueryStyle;
35 
36     @Override
setUp()37     protected void setUp() throws Exception {
38         mFormatter = new LevenshteinSuggestionFormatter(new MockTextAppearanceFactory());
39         mSuggestedStyle = MockTextAppearanceFactory.ID_SUGGESTED_TEXT;
40         mQueryStyle = MockTextAppearanceFactory.ID_QUERY_TEXT;
41     }
42 
verifyTokenizeResult(String input, String... output)43     private void verifyTokenizeResult(String input, String... output) {
44         Token[] tokens = mFormatter.tokenize(input);
45         assertEquals(output.length, tokens.length);
46         for (int i=0; i<output.length; ++i) {
47             assertEquals(output[i], tokens[i].toString());
48         }
49     }
50 
testTokenizeNoTokens()51     public void testTokenizeNoTokens() {
52         verifyTokenizeResult("");
53         verifyTokenizeResult("  ");
54     }
55 
testTokenizeSingleToken()56     public void testTokenizeSingleToken() {
57         verifyTokenizeResult("singleToken", "singleToken");
58     }
59 
testTokenizeTwoTokens()60     public void testTokenizeTwoTokens() {
61         verifyTokenizeResult("two tokens", "two", "tokens");
62     }
63 
testTokenizeLeadingSpaces()64     public void testTokenizeLeadingSpaces() {
65         verifyTokenizeResult(" evil kittens", "evil", "kittens");
66         verifyTokenizeResult("        furry lizards", "furry", "lizards");
67     }
68 
testTokenizeTrailingSpaces()69     public void testTokenizeTrailingSpaces() {
70         verifyTokenizeResult("mechanical elephant ", "mechanical", "elephant");
71         verifyTokenizeResult("disappointed dog       ", "disappointed", "dog");
72     }
73 
testTokenizeManySpaces()74     public void testTokenizeManySpaces() {
75         verifyTokenizeResult("happy     horses", "happy", "horses");
76     }
77 
testTokenizeLongSentence()78     public void testTokenizeLongSentence() {
79         verifyTokenizeResult("The fool looks at a finger that points at the sky",
80                 "The", "fool", "looks", "at", "a", "finger", "that", "points", "at", "the", "sky");
81     }
82 
testTokenizeWithPunctuation()83     public void testTokenizeWithPunctuation() {
84         verifyTokenizeResult("Hitchhiker's guide", "Hitchhiker's", "guide");
85         verifyTokenizeResult("full. stop. ", "full.", "stop.");
86         verifyTokenizeResult("' . ; . ..", "'", ".", ";", ".", "..");
87     }
88 
testTokenizeWithTabs()89     public void testTokenizeWithTabs() {
90         verifyTokenizeResult("don't\tpanic\t", "don't", "panic");
91     }
92 
verifyFindMatches(String source, String target, String... newTokensInTarget)93     private void verifyFindMatches(String source, String target, String... newTokensInTarget) {
94         Token[] sourceTokens = mFormatter.tokenize(source);
95         Token[] targetTokens = mFormatter.tokenize(target);
96 
97         int[] matches = mFormatter.findMatches(sourceTokens, targetTokens);
98         assertEquals(targetTokens.length, matches.length);
99         int newTokenCount = 0;
100         int lastSourceToken = -1;
101         for (int i=0; i<targetTokens.length; ++i) {
102 
103             int sourceIdx = matches[i];
104             if (sourceIdx < 0) {
105                 String targetToken = targetTokens[i].toString();
106                 assertTrue("Unexpected new token '" + targetToken + "'",
107                         newTokenCount < newTokensInTarget.length);
108 
109                 assertEquals(newTokensInTarget[newTokenCount], targetToken);
110                 ++newTokenCount;
111             } else {
112                 assertTrue("Source token out of order", lastSourceToken < sourceIdx);
113                 Token srcToken = sourceTokens[sourceIdx];
114                 Token trgToken = targetTokens[i];
115                 assertTrue("'" + srcToken + "' is not a prefix of '" + trgToken + "'",
116                         srcToken.prefixOf(trgToken));
117                 lastSourceToken = sourceIdx;
118             }
119         }
120     }
121 
testFindMatchesSameTokens()122     public void testFindMatchesSameTokens() {
123         verifyFindMatches("", "");
124         verifyFindMatches("one", "one");
125         verifyFindMatches("one two three", "one two three");
126     }
127 
testFindMatchesNewTokens()128     public void testFindMatchesNewTokens() {
129         verifyFindMatches("", "one", "one");
130         verifyFindMatches("one", "one two", "two");
131         verifyFindMatches("one", "one two three", "two", "three");
132         verifyFindMatches("two", "one two three", "one", "three");
133         verifyFindMatches("pictures", "pictures of kittens", "of", "kittens");
134     }
135 
testFindMatchesReplacedTokens()136     public void testFindMatchesReplacedTokens() {
137         verifyFindMatches("one", "two", "two");
138         verifyFindMatches("one", "two three", "two", "three");
139         verifyFindMatches("two", "one three", "one", "three");
140         verifyFindMatches("pictures", "of kittens", "of", "kittens");
141     }
142 
testFindMatchesDuplicateTokens()143     public void testFindMatchesDuplicateTokens() {
144         verifyFindMatches("badger", "badger badger", "badger");
145         verifyFindMatches("badger", "badger badger badger", "badger", "badger");
146         verifyFindMatches("badger badger", "badger badger badger", "badger");
147         verifyFindMatches("badger badger badger", "badger badger badger");
148         // mushroom!
149     }
150 
verifyFormatSuggestion(String query, String suggestion, SpanFormat... spans)151     private void verifyFormatSuggestion(String query, String suggestion, SpanFormat... spans) {
152         Spanned s = mFormatter.formatSuggestion(query, suggestion);
153         for (SpanFormat span : spans) {
154             span.verify(s);
155         }
156     }
157 
testFormatSuggestionEmptyStrings()158     public void testFormatSuggestionEmptyStrings() {
159         verifyFormatSuggestion("", "");
160     }
161 
testFormatSuggestionEmptyQuery()162     public void testFormatSuggestionEmptyQuery() {
163         verifyFormatSuggestion("", "suggestion",
164                 new SpanFormat(0, "suggestion", mSuggestedStyle));
165     }
166 
testFormatSuggestionQuerySuggested()167     public void testFormatSuggestionQuerySuggested() {
168         verifyFormatSuggestion("query", "query",
169                 new SpanFormat(0, "query", mQueryStyle));
170     }
171 
testFormatSuggestionExtraWordsSuggested()172     public void testFormatSuggestionExtraWordsSuggested() {
173         verifyFormatSuggestion("query", "query suggested",
174                 new SpanFormat(0, "query", mQueryStyle),
175                 new SpanFormat(6, "suggested", mSuggestedStyle));
176 
177         verifyFormatSuggestion("pictures", "pictures of kittens",
178                 new SpanFormat(0,  "pictures", mQueryStyle),
179                 new SpanFormat(9,  "of", mSuggestedStyle),
180                 new SpanFormat(12, "kittens", mSuggestedStyle));
181 
182         verifyFormatSuggestion("pictures of", "pictures of kittens dying",
183                 new SpanFormat(0,  "pictures", mQueryStyle),
184                 new SpanFormat(9,  "of", mQueryStyle),
185                 new SpanFormat(12, "kittens", mSuggestedStyle),
186                 new SpanFormat(20, "dying", mSuggestedStyle));
187     }
188 
testFormatSuggestionExtraWordSuggestedAtStart()189     public void testFormatSuggestionExtraWordSuggestedAtStart() {
190         verifyFormatSuggestion("query", "suggested query",
191                 new SpanFormat(0, "suggested", mSuggestedStyle),
192                 new SpanFormat(10, "query", mQueryStyle));
193     }
194 
testFormatSuggestionAlternativeWordSuggested()195     public void testFormatSuggestionAlternativeWordSuggested() {
196         verifyFormatSuggestion("query", "suggested",
197                 new SpanFormat(0, "suggested", mSuggestedStyle));
198     }
199 
testFormatSuggestionDuplicateWords()200     public void testFormatSuggestionDuplicateWords() {
201         verifyFormatSuggestion("", "badger badger",
202                 new SpanFormat(0, "badger", mSuggestedStyle),
203                 new SpanFormat(7, "badger", mSuggestedStyle));
204 
205         verifyFormatSuggestion("badger", "badger badger",
206                 new SpanFormat(0, "badger", mQueryStyle),
207                 new SpanFormat(7, "badger", mSuggestedStyle));
208 
209         verifyFormatSuggestion("badger badger", "badger badger",
210                 new SpanFormat(0, "badger", mQueryStyle),
211                 new SpanFormat(7, "badger", mQueryStyle));
212 
213         verifyFormatSuggestion("badger badger", "badger badger badger",
214                 new SpanFormat(0, "badger", mQueryStyle),
215                 new SpanFormat(7, "badger", mQueryStyle),
216                 new SpanFormat(14, "badger", mSuggestedStyle));
217     }
218 
testFormatSuggestionDuplicateSequences()219     public void testFormatSuggestionDuplicateSequences() {
220         verifyFormatSuggestion("dem bones", "dem bones dem bones",
221                 new SpanFormat(0, "dem", mQueryStyle),
222                 new SpanFormat(4, "bones", mQueryStyle),
223                 new SpanFormat(10, "dem", mSuggestedStyle),
224                 new SpanFormat(14, "bones", mSuggestedStyle)
225         );
226 
227         verifyFormatSuggestion("dem bones", "dem dry bones dem bones",
228                 new SpanFormat(0, "dem", mQueryStyle),
229                 new SpanFormat(4, "dry", mSuggestedStyle),
230                 new SpanFormat(8, "bones", mQueryStyle),
231                 new SpanFormat(14, "dem", mSuggestedStyle),
232                 new SpanFormat(18, "bones", mSuggestedStyle)
233         );
234 
235         verifyFormatSuggestion("dem dry bones", "dry bones dem dry bones dem dry bones",
236                 new SpanFormat(0, "dry", mSuggestedStyle),
237                 new SpanFormat(4, "bones", mSuggestedStyle),
238                 new SpanFormat(10, "dem", mQueryStyle),
239                 new SpanFormat(14, "dry", mQueryStyle),
240                 new SpanFormat(18, "bones", mQueryStyle),
241                 new SpanFormat(24, "dem", mSuggestedStyle),
242                 new SpanFormat(28, "dry", mSuggestedStyle),
243                 new SpanFormat(32, "bones", mSuggestedStyle)
244         );
245     }
246 
testFormatSuggestionWordCompletion()247     public void testFormatSuggestionWordCompletion() {
248         verifyFormatSuggestion("hitch", "hitchhiker",
249                 new SpanFormat(0, "hitch", mQueryStyle),
250                 new SpanFormat(5, "hiker", mSuggestedStyle)
251         );
252 
253         verifyFormatSuggestion("hitch", "hitchhiker's guide",
254                 new SpanFormat(0, "hitch", mQueryStyle),
255                 new SpanFormat(5, "hiker's", mSuggestedStyle),
256                 new SpanFormat(13, "guide", mSuggestedStyle)
257         );
258 
259         verifyFormatSuggestion("hitchhiker's g", "hitchhiker's guide",
260                 new SpanFormat(0, "hitchhiker's", mQueryStyle),
261                 new SpanFormat(13, "g", mQueryStyle),
262                 new SpanFormat(14, "uide", mSuggestedStyle)
263         );
264 
265         verifyFormatSuggestion("hitchhiker's g", "hitchhiker's guide to the galaxy",
266                 new SpanFormat(0, "hitchhiker's", mQueryStyle),
267                 new SpanFormat(13, "g", mQueryStyle),
268                 new SpanFormat(14, "uide", mSuggestedStyle),
269                 new SpanFormat(19, "to", mSuggestedStyle),
270                 new SpanFormat(22, "the", mSuggestedStyle),
271                 new SpanFormat(26, "galaxy", mSuggestedStyle)
272         );
273     }
274 
testFormatSuggestionWordSplitting()275     public void testFormatSuggestionWordSplitting() {
276         verifyFormatSuggestion("dimsum", "dim sum",
277                 new SpanFormat(0, "dim", mSuggestedStyle),
278                 new SpanFormat(4, "sum", mSuggestedStyle)
279         );
280 
281         verifyFormatSuggestion("dimsum london", "dim sum london",
282                 new SpanFormat(0, "dim", mSuggestedStyle),
283                 new SpanFormat(4, "sum", mSuggestedStyle),
284                 new SpanFormat(8, "london", mQueryStyle)
285         );
286 
287         verifyFormatSuggestion("dimsum london", "dim sum london yummy",
288                 new SpanFormat(0, "dim", mSuggestedStyle),
289                 new SpanFormat(4, "sum", mSuggestedStyle),
290                 new SpanFormat(8, "london", mQueryStyle),
291                 new SpanFormat(15, "yummy", mSuggestedStyle)
292         );
293     }
294 
testFormatSuggestionWordCombining()295     public void testFormatSuggestionWordCombining() {
296         verifyFormatSuggestion("hos pital", "hospital",
297                 new SpanFormat(0, "hos", mQueryStyle),
298                 new SpanFormat(3, "pital", mSuggestedStyle)
299         );
300 
301         verifyFormatSuggestion("hos pital", "hospital waiting times",
302                 new SpanFormat(0, "hos", mQueryStyle),
303                 new SpanFormat(3, "pital", mSuggestedStyle),
304                 new SpanFormat(9, "waiting", mSuggestedStyle),
305                 new SpanFormat(17, "times", mSuggestedStyle)
306         );
307 
308         verifyFormatSuggestion("hos pital waiting", "hospital waiting",
309                 new SpanFormat(0, "hos", mQueryStyle),
310                 new SpanFormat(3, "pital", mSuggestedStyle),
311                 new SpanFormat(9, "waiting", mQueryStyle)
312         );
313 
314         verifyFormatSuggestion("hospital wait ing times", "hospital waiting times",
315                 new SpanFormat(0, "hospital", mQueryStyle),
316                 new SpanFormat(9, "wait", mQueryStyle),
317                 new SpanFormat(13, "ing", mSuggestedStyle),
318                 new SpanFormat(17, "times", mQueryStyle)
319         );
320     }
321 
testFormatSuggestionCapitalization()322     public void testFormatSuggestionCapitalization() {
323         verifyFormatSuggestion("Flay", "flay",
324                 new SpanFormat(0, "flay", mQueryStyle));
325 
326         verifyFormatSuggestion("STEERPI", "steerpike",
327                 new SpanFormat(0, "steerpi", mQueryStyle),
328                 new SpanFormat(7, "ke", mSuggestedStyle));
329 
330         verifyFormatSuggestion("STEErpi", "steerpike",
331                 new SpanFormat(0, "steerpi", mQueryStyle),
332                 new SpanFormat(7, "ke", mSuggestedStyle));
333 
334         verifyFormatSuggestion("TITUS", "titus groan",
335                 new SpanFormat(0, "titus", mQueryStyle),
336                 new SpanFormat(6, "groan", mSuggestedStyle));
337 }
338 
339     private class SpanFormat {
340         private final int mStart;
341         private final int mEnd;
342         private final String mExpectedText;
343         private final int mStyle;
SpanFormat(int start, String expectedText, int style)344         public SpanFormat(int start, String expectedText, int style) {
345             mStart = start;
346             mEnd = start + expectedText.length();
347             mExpectedText = expectedText;
348             mStyle = style;
349         }
verify(Spanned spanned)350         public void verify(Spanned spanned) {
351             String spannedText = spanned.subSequence(mStart, mEnd).toString();
352             assertEquals("Test error", mExpectedText, spannedText);
353             MockStyleSpan[] spans = spanned.getSpans(mStart, mEnd, MockStyleSpan.class);
354             assertEquals("Wrong number of spans in '" + spannedText + "'", 1, spans.length);
355             assertEquals("Wrong style for '" + spannedText + "' at position " + mStart,
356                     mStyle, spans[0].getId());
357         }
358     }
359 
360 }
361