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 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
