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
17package com.android.quicksearchbox;
18
19import com.android.quicksearchbox.MockTextAppearanceFactory.MockStyleSpan;
20import com.android.quicksearchbox.util.LevenshteinDistance.Token;
21
22import android.test.AndroidTestCase;
23import android.test.suitebuilder.annotation.SmallTest;
24import android.text.Spanned;
25
26/**
27 * Tests for {@link LevenshteinSuggestionFormatter}.
28 */
29@SmallTest
30public class LevenshteinFormatterTest extends AndroidTestCase {
31
32    private LevenshteinSuggestionFormatter mFormatter;
33    private int mSuggestedStyle;
34    private int mQueryStyle;
35
36    @Override
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
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
51    public void testTokenizeNoTokens() {
52        verifyTokenizeResult("");
53        verifyTokenizeResult("  ");
54    }
55
56    public void testTokenizeSingleToken() {
57        verifyTokenizeResult("singleToken", "singleToken");
58    }
59
60    public void testTokenizeTwoTokens() {
61        verifyTokenizeResult("two tokens", "two", "tokens");
62    }
63
64    public void testTokenizeLeadingSpaces() {
65        verifyTokenizeResult(" evil kittens", "evil", "kittens");
66        verifyTokenizeResult("        furry lizards", "furry", "lizards");
67    }
68
69    public void testTokenizeTrailingSpaces() {
70        verifyTokenizeResult("mechanical elephant ", "mechanical", "elephant");
71        verifyTokenizeResult("disappointed dog       ", "disappointed", "dog");
72    }
73
74    public void testTokenizeManySpaces() {
75        verifyTokenizeResult("happy     horses", "happy", "horses");
76    }
77
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
83    public void testTokenizeWithPunctuation() {
84        verifyTokenizeResult("Hitchhiker's guide", "Hitchhiker's", "guide");
85        verifyTokenizeResult("full. stop. ", "full.", "stop.");
86        verifyTokenizeResult("' . ; . ..", "'", ".", ";", ".", "..");
87    }
88
89    public void testTokenizeWithTabs() {
90        verifyTokenizeResult("paranoid\tandroid\t", "paranoid", "android");
91    }
92
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
122    public void testFindMatchesSameTokens() {
123        verifyFindMatches("", "");
124        verifyFindMatches("one", "one");
125        verifyFindMatches("one two three", "one two three");
126    }
127
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
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
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
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
158    public void testFormatSuggestionEmptyStrings() {
159        verifyFormatSuggestion("", "");
160    }
161
162    public void testFormatSuggestionEmptyQuery() {
163        verifyFormatSuggestion("", "suggestion",
164                new SpanFormat(0, "suggestion", mSuggestedStyle));
165    }
166
167    public void testFormatSuggestionQuerySuggested() {
168        verifyFormatSuggestion("query", "query",
169                new SpanFormat(0, "query", mQueryStyle));
170    }
171
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
189    public void testFormatSuggestionExtraWordSuggestedAtStart() {
190        verifyFormatSuggestion("query", "suggested query",
191                new SpanFormat(0, "suggested", mSuggestedStyle),
192                new SpanFormat(10, "query", mQueryStyle));
193    }
194
195    public void testFormatSuggestionAlternativeWordSuggested() {
196        verifyFormatSuggestion("query", "suggested",
197                new SpanFormat(0, "suggested", mSuggestedStyle));
198    }
199
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
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
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
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
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
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;
344        public SpanFormat(int start, String expectedText, int style) {
345            mStart = start;
346            mEnd = start + expectedText.length();
347            mExpectedText = expectedText;
348            mStyle = style;
349        }
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