Implemented suggestion bolding.
The part of the query that the user did not type is highlighed, currently in bold.
Bug: 2806529.
Change-Id: I087c4cd80faf878a54e1fa8d4c2833eef4329a62
diff --git a/src/com/android/quicksearchbox/LevenshteinSuggestionFormatter.java b/src/com/android/quicksearchbox/LevenshteinSuggestionFormatter.java
new file mode 100644
index 0000000..418a7a9
--- /dev/null
+++ b/src/com/android/quicksearchbox/LevenshteinSuggestionFormatter.java
@@ -0,0 +1,158 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.quicksearchbox;
+
+import com.android.quicksearchbox.util.LevenshteinDistance;
+import com.google.common.annotations.VisibleForTesting;
+
+import android.text.SpannableString;
+import android.text.Spanned;
+import android.util.Log;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Suggestion formatter using the Levenshtein distance (minumum edit distance) to calculate the
+ * formatting.
+ */
+public class LevenshteinSuggestionFormatter extends SuggestionFormatter {
+ private static final boolean DBG = false;
+ private static final String TAG = "QSB.LevenshteinSuggestionFormatter";
+
+ @Override
+ public Spanned formatSuggestion(CharSequence query, CharSequence suggestion) {
+ if (DBG) Log.d(TAG, "formatSuggestion('" + query + "', '" + suggestion + "')");
+ query = normalizeQuery(query);
+ List<Token> queryTokens = tokenize(query);
+ List<Token> suggestionTokens = tokenize(suggestion);
+ int[] matches = findMatches(queryTokens, suggestionTokens);
+ if (DBG){
+ Log.d(TAG, "source = " + queryTokens);
+ Log.d(TAG, "target = " + suggestionTokens);
+ Log.d(TAG, "matches = " + matches);
+ }
+ SpannableString str = new SpannableString(suggestion);
+
+ for (int i = 0; i < matches.length; ++i) {
+ Token t = suggestionTokens.get(i);
+ int sourceLen = 0;
+ if (matches[i] >= 0) {
+ sourceLen = queryTokens.get(matches[i]).getLength();
+ }
+ applySuggestedTextStyle(str, t.getStart() + sourceLen, t.getEnd());
+ applyQueryTextStyle(str, t.getStart(), t.getStart() + sourceLen);
+ }
+
+ return str;
+ }
+
+ private CharSequence normalizeQuery(CharSequence query) {
+ return query.toString().toLowerCase();
+ }
+
+ /**
+ * Finds which tokens in the target match tokens in the source.
+ *
+ * @param source List of source tokens (i.e. user query)
+ * @param target List of target tokens (i.e. suggestion)
+ * @return The indices into source which target tokens correspond to. A non-negative value n at
+ * position i means that target token i matches source token n. A negative value means that
+ * the target token i does not match any source token.
+ */
+ @VisibleForTesting
+ int[] findMatches(List<Token> source, List<Token> target) {
+ LevenshteinDistance<Token> table = new LevenshteinDistance<Token>(source, target) {
+ @Override
+ protected boolean match(Token source, Token target) {
+ return source.prefixOf(target);
+ }
+ };
+ table.calculate();
+ int[] result = new int[target.size()];
+ LevenshteinDistance.EditOperation[] ops = table.getTargetOperations();
+ for (int i = 0; i < result.length; ++i) {
+ if (ops[i].getType() == LevenshteinDistance.EDIT_UNCHANGED) {
+ result[i] = ops[i].getPosition();
+ } else {
+ result[i] = -1;
+ }
+ }
+ return result;
+ }
+
+ @VisibleForTesting
+ List<Token> tokenize(CharSequence seq) {
+ int pos = 0;
+ ArrayList<Token> tokens = new ArrayList<Token>();
+ while (pos < seq.length()) {
+ while (pos < seq.length() && Character.isWhitespace(seq.charAt(pos))) {
+ pos++;
+ }
+ int start = pos;
+ while (pos < seq.length() && !Character.isWhitespace(seq.charAt(pos))) {
+ pos++;
+ }
+ int end = pos;
+ if (start != end) {
+ Token t = new Token(seq, start, end);
+ tokens.add(t);
+ }
+ }
+ return tokens;
+ }
+
+ @VisibleForTesting
+ static class Token {
+ private final CharSequence mContainer;
+ private final int mStart;
+ private final int mEnd;
+
+ public Token(CharSequence container, int start, int end) {
+ mContainer = container;
+ mStart = start;
+ mEnd = end;
+ }
+
+ public int getStart() {
+ return mStart;
+ }
+
+ public int getEnd() {
+ return mEnd;
+ }
+
+ public int getLength() {
+ return mEnd - mStart;
+ }
+
+ @Override
+ public String toString() {
+ return getSequence().toString();
+ }
+
+ public CharSequence getSequence() {
+ return mContainer.subSequence(mStart, mEnd);
+ }
+
+ public boolean prefixOf(Token that) {
+ return that.toString().startsWith(toString());
+ }
+
+ }
+
+}
diff --git a/src/com/android/quicksearchbox/QsbApplication.java b/src/com/android/quicksearchbox/QsbApplication.java
index b9ec771..2b0b0f5 100644
--- a/src/com/android/quicksearchbox/QsbApplication.java
+++ b/src/com/android/quicksearchbox/QsbApplication.java
@@ -33,6 +33,7 @@
import android.content.Context;
import android.content.pm.PackageInfo;
import android.content.pm.PackageManager;
+import android.graphics.Typeface;
import android.os.Build;
import android.os.Handler;
import android.os.Looper;
@@ -61,6 +62,7 @@
private GoogleSource mGoogleSource;
private VoiceSearch mVoiceSearch;
private Logger mLogger;
+ private SuggestionFormatter mSuggestionFormatter;
public QsbApplication(Context context) {
mContext = context;
@@ -398,4 +400,16 @@
protected Logger createLogger() {
return new EventLogLogger(getContext(), getConfig());
}
+
+ public SuggestionFormatter getSuggestionFormatter() {
+ if (mSuggestionFormatter == null) {
+ mSuggestionFormatter = createSuggestionFormatter();
+ mSuggestionFormatter.setSuggestedTextFormat(Typeface.BOLD, 0);
+ }
+ return mSuggestionFormatter;
+ }
+
+ protected SuggestionFormatter createSuggestionFormatter() {
+ return new LevenshteinSuggestionFormatter();
+ }
}
diff --git a/src/com/android/quicksearchbox/SuggestionFormatter.java b/src/com/android/quicksearchbox/SuggestionFormatter.java
new file mode 100644
index 0000000..37fe68d
--- /dev/null
+++ b/src/com/android/quicksearchbox/SuggestionFormatter.java
@@ -0,0 +1,86 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.quicksearchbox;
+
+import android.text.Spannable;
+import android.text.style.StyleSpan;
+
+/**
+ * Suggestion formatter interface. This is used to bold (or otherwise highlight) portions of a
+ * suggestion which were not a part of the query.
+ */
+public abstract class SuggestionFormatter {
+
+ private int mQueryTextStyle;
+ private int mQueryStyleFlags;
+
+ private int mSuggestedTextStyle;
+ private int mSuggestedStyleFlags;
+
+
+ protected SuggestionFormatter() {
+ }
+
+ /**
+ * Formats a suggestion for display in the UI.
+ *
+ * @param query the query as entered by the user
+ * @param suggestion the suggestion
+ * @return Formatted suggestion text.
+ */
+ public abstract CharSequence formatSuggestion(CharSequence query, CharSequence suggestion);
+
+ /**
+ * Sets the text format to use for portions of a suggestions which form a part of the original
+ * used query.
+ *
+ * @param style Style for query text. Values are constants defined in
+ * {@link android.graphics.Typeface}
+ * @param flags Flags to determine how the span will behave when text is inserted at the start
+ * or end of the span's range.
+ */
+ public void setQueryTextFormat(int style, int flags) {
+ mQueryTextStyle = style;
+ mQueryStyleFlags = flags;
+ }
+
+ /**
+ * Sets the text format to use for portions of a suggestion which are new.
+ *
+ * @param style Style for suggested text. Values are constants defined in
+ * {@link android.graphics.Typeface}
+ * @param flags Flags to determine how the span will behave when text is inserted at the start
+ * or end of the span's range.
+ */
+ public void setSuggestedTextFormat(int style, int flags) {
+ mSuggestedTextStyle = style;
+ mSuggestedStyleFlags = flags;
+ }
+
+ protected void applyQueryTextStyle(Spannable text, int start, int end) {
+ if (start == end) return;
+ StyleSpan style = new StyleSpan(mQueryTextStyle);
+ text.setSpan(style, start, end, mQueryStyleFlags);
+ }
+
+ protected void applySuggestedTextStyle(Spannable text, int start, int end) {
+ if (start == end) return;
+ StyleSpan style = new StyleSpan(mSuggestedTextStyle);
+ text.setSpan(style, start, end, mSuggestedStyleFlags);
+ }
+
+}
diff --git a/src/com/android/quicksearchbox/SuggestionNonFormatter.java b/src/com/android/quicksearchbox/SuggestionNonFormatter.java
new file mode 100644
index 0000000..379d484
--- /dev/null
+++ b/src/com/android/quicksearchbox/SuggestionNonFormatter.java
@@ -0,0 +1,33 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.quicksearchbox;
+
+
+/**
+ * Basic SuggestionFormatter that does no formatting.
+ */
+public class SuggestionNonFormatter extends SuggestionFormatter {
+
+ public SuggestionNonFormatter() {
+ }
+
+ @Override
+ public CharSequence formatSuggestion(CharSequence query, CharSequence suggestion) {
+ return suggestion;
+ }
+
+}
diff --git a/src/com/android/quicksearchbox/ui/DefaultSuggestionView.java b/src/com/android/quicksearchbox/ui/DefaultSuggestionView.java
index 28d3e3d..e7c1249 100644
--- a/src/com/android/quicksearchbox/ui/DefaultSuggestionView.java
+++ b/src/com/android/quicksearchbox/ui/DefaultSuggestionView.java
@@ -16,10 +16,12 @@
package com.android.quicksearchbox.ui;
+import com.android.quicksearchbox.QsbApplication;
import com.android.quicksearchbox.R;
import com.android.quicksearchbox.Source;
import com.android.quicksearchbox.Suggestion;
import com.android.quicksearchbox.SuggestionCursor;
+import com.android.quicksearchbox.SuggestionFormatter;
import android.content.Context;
import android.content.res.ColorStateList;
@@ -50,17 +52,21 @@
private TextView mText2;
private ImageView mIcon1;
private ImageView mIcon2;
+ private final SuggestionFormatter mSuggestionFormatter;
public DefaultSuggestionView(Context context, AttributeSet attrs, int defStyle) {
super(context, attrs, defStyle);
- }
+ mSuggestionFormatter = QsbApplication.get(context).getSuggestionFormatter();
+ }
public DefaultSuggestionView(Context context, AttributeSet attrs) {
super(context, attrs);
+ mSuggestionFormatter = QsbApplication.get(context).getSuggestionFormatter();
}
public DefaultSuggestionView(Context context) {
super(context);
+ mSuggestionFormatter = QsbApplication.get(context).getSuggestionFormatter();
}
@Override
@@ -73,13 +79,12 @@
}
public void bindAsSuggestion(SuggestionCursor suggestion) {
- String format = suggestion.getSuggestionFormat();
- CharSequence text1 = formatText(suggestion.getSuggestionText1(), format);
+ CharSequence text1 = formatText(suggestion.getSuggestionText1(), suggestion, true);
CharSequence text2 = suggestion.getSuggestionText2Url();
if (text2 != null) {
text2 = formatUrl(text2);
} else {
- text2 = formatText(suggestion.getSuggestionText2(), format);
+ text2 = formatText(suggestion.getSuggestionText2(), suggestion, false);
}
Drawable icon1 = getSuggestionDrawableIcon1(suggestion);
Drawable icon2 = getSuggestionDrawableIcon2(suggestion);
@@ -151,10 +156,14 @@
return iconId == null ? null : source.getIcon(iconId);
}
- private CharSequence formatText(String str, String format) {
- boolean isHtml = "html".equals(format);
+ private CharSequence formatText(String str, SuggestionCursor suggestion,
+ boolean highlightSuggested) {
+ boolean isHtml = "html".equals(suggestion.getSuggestionFormat());
if (isHtml && looksLikeHtml(str)) {
return Html.fromHtml(str);
+ } else if (highlightSuggested && suggestion.isWebSearchSuggestion() &&
+ !TextUtils.isEmpty(suggestion.getUserQuery())) {
+ return mSuggestionFormatter.formatSuggestion(suggestion.getUserQuery(), str);
} else {
return str;
}
diff --git a/src/com/android/quicksearchbox/util/LevenshteinDistance.java b/src/com/android/quicksearchbox/util/LevenshteinDistance.java
new file mode 100644
index 0000000..f5b99ec
--- /dev/null
+++ b/src/com/android/quicksearchbox/util/LevenshteinDistance.java
@@ -0,0 +1,172 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.quicksearchbox.util;
+
+import java.util.List;
+
+/**
+ * This class represents the matrix used in the Levenshtein distance algorithm, together
+ * with the algorithm itself which operates on the matrix.
+ *
+ * We also track of the individual operations applied to transform the source string into the
+ * target string so we can trace the path taken through the matrix afterwards, in order to
+ * perform the formatting as required.
+ */
+public abstract class LevenshteinDistance<T> {
+ public static final int EDIT_DELETE = 0;
+ public static final int EDIT_INSERT = 1;
+ public static final int EDIT_REPLACE = 2;
+ public static final int EDIT_UNCHANGED = 3;
+
+ private final List<T> mSource;
+ private final List<T> mTarget;
+ private final Entry[][] mTable;
+
+ public LevenshteinDistance(List<T> source, List<T> target) {
+ mTable = new Entry[source.size()+1][target.size()+1];
+ mSource = source;
+ mTarget = target;
+ set(0, 0, EDIT_UNCHANGED, 0);
+ for (int i = 1; i <= source.size(); ++i) {
+ set(i, 0, EDIT_DELETE, i);
+ }
+ for (int i = 1; i <= target.size(); ++i) {
+ set(0, i, EDIT_INSERT, i);
+ }
+ }
+
+ /**
+ * Compares a source and target token.
+ * @param source Token from the source string.
+ * @param target Token from the target string.
+ * @return {@code true} if the two are the same for the purposes of edit distance calculation,
+ * {@code false} otherwise.
+ */
+ protected abstract boolean match(T source, T target);
+
+ /**
+ * Implementation of Levenshtein distance algorithm.
+ *
+ * @return The Levenshtein distance.
+ */
+ public int calculate() {
+ for (int s = 1; s <= mSource.size(); ++s) {
+ T sourceToken = mSource.get(s-1);
+ for (int t = 1; t <= mTarget.size(); ++t) {
+ T targetToken = mTarget.get(t-1);
+ int cost = match(sourceToken, targetToken) ? 0 : 1;
+
+ Entry e = get(s - 1, t);
+ int distance = e.getDistance() + 1;
+ int type = EDIT_DELETE;
+
+ e = get(s, t - 1);
+ if (e.getDistance() + 1 < distance ) {
+ distance = e.getDistance() + 1;
+ type = EDIT_INSERT;
+ }
+
+ e = get(s - 1, t - 1);
+ if (e.getDistance() + cost < distance) {
+ distance = e.getDistance() + cost;
+ type = cost == 0 ? EDIT_UNCHANGED : EDIT_REPLACE;
+ }
+ set(s, t, type, distance);
+ }
+ }
+ return get(mSource.size(), mTarget.size()).getDistance();
+ }
+
+ /**
+ * Gets the list of operations which were applied to each target token; {@link #calculate} must
+ * have been called on this object before using this method.
+ * @return A list of {@link EditOperation}s indicating the origin of each token in the target
+ * string. The position of the token indicates the position in the source string of the
+ * token that was unchanged/replaced, or the position in the source after which a target
+ * token was inserted.
+ */
+ public EditOperation[] getTargetOperations() {
+ EditOperation[] ops = new EditOperation[mTarget.size()];
+ int targetPos = mTarget.size();
+ int sourcePos = mSource.size();
+ while (targetPos > 0) {
+ Entry e = get(sourcePos, targetPos);
+ int editType = e.getEditType();
+ switch (editType) {
+ case LevenshteinDistance.EDIT_DELETE:
+ sourcePos--;
+ break;
+ case LevenshteinDistance.EDIT_INSERT:
+ targetPos--;
+ ops[targetPos] = new EditOperation(editType, sourcePos);
+ break;
+ case LevenshteinDistance.EDIT_UNCHANGED:
+ case LevenshteinDistance.EDIT_REPLACE:
+ targetPos--;
+ sourcePos--;
+ ops[targetPos] = new EditOperation(editType, sourcePos);
+ break;
+ }
+ }
+
+ return ops;
+ }
+
+ private void set(int sourceIdx, int targetIdx, int editType, int distance) {
+ mTable[sourceIdx][targetIdx] = new Entry(editType, distance);
+ }
+
+ private Entry get(int sourceIdx, int targetIdx) {
+ Entry e = mTable[sourceIdx][targetIdx];
+ if (e == null) {
+ throw new NullPointerException("No entry at " + sourceIdx + "," + targetIdx +
+ "; size: " + (mSource.size() + 1) + "," + (mTarget.size() + 1));
+ }
+ return e;
+ }
+
+ private static class Entry {
+ private final int mEditType;
+ private final int mDistance;
+ public Entry(int editType, int distance) {
+ mEditType = editType;
+ mDistance = distance;
+ }
+ public int getDistance() {
+ return mDistance;
+ }
+ public int getEditType() {
+ return mEditType;
+ }
+ }
+
+ public static class EditOperation {
+ private final int mType;
+ private final int mPosition;
+ public EditOperation(int type, int position) {
+ mType = type;
+ mPosition = position;
+ }
+ public int getType() {
+ return mType;
+ }
+ public int getPosition() {
+ return mPosition;
+ }
+ }
+
+}
diff --git a/tests/src/com/android/quicksearchbox/LevenshteinFormatterTest.java b/tests/src/com/android/quicksearchbox/LevenshteinFormatterTest.java
new file mode 100644
index 0000000..efde9e6
--- /dev/null
+++ b/tests/src/com/android/quicksearchbox/LevenshteinFormatterTest.java
@@ -0,0 +1,361 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.quicksearchbox;
+
+import android.graphics.Typeface;
+import android.test.AndroidTestCase;
+import android.text.Spanned;
+import android.text.style.StyleSpan;
+
+import java.util.List;
+
+/**
+ * Tests for {@link LevenshteinSuggestionFormatter}.
+ */
+public class LevenshteinFormatterTest extends AndroidTestCase {
+
+ private LevenshteinSuggestionFormatter mFormatter;
+ private int mSuggestedStyle;
+ private int mQueryStyle;
+
+ @Override
+ protected void setUp() throws Exception {
+ mFormatter = new LevenshteinSuggestionFormatter();
+ mSuggestedStyle = Typeface.BOLD;
+ mQueryStyle = Typeface.ITALIC;
+ mFormatter.setSuggestedTextFormat(mSuggestedStyle, 0);
+ mFormatter.setQueryTextFormat(mQueryStyle, 0);
+ }
+
+ private void verifyTokenizeResult(String input, String... output) {
+ List<LevenshteinSuggestionFormatter.Token> tokens = mFormatter.tokenize(input);
+ assertEquals(output.length, tokens.size());
+ for (int i=0; i<output.length; ++i) {
+ assertEquals(output[i], tokens.get(i).toString());
+ }
+ }
+
+ public void testTokenizeNoTokens() {
+ verifyTokenizeResult("");
+ verifyTokenizeResult(" ");
+ }
+
+ public void testTokenizeSingleToken() {
+ verifyTokenizeResult("singleToken", "singleToken");
+ }
+
+ public void testTokenizeTwoTokens() {
+ verifyTokenizeResult("two tokens", "two", "tokens");
+ }
+
+ public void testTokenizeLeadingSpaces() {
+ verifyTokenizeResult(" evil kittens", "evil", "kittens");
+ verifyTokenizeResult(" furry lizards", "furry", "lizards");
+ }
+
+ public void testTokenizeTrailingSpaces() {
+ verifyTokenizeResult("mechanical elephant ", "mechanical", "elephant");
+ verifyTokenizeResult("disappointed dog ", "disappointed", "dog");
+ }
+
+ public void testTokenizeManySpaces() {
+ verifyTokenizeResult("happy horses", "happy", "horses");
+ }
+
+ public void testTokenizeLongSentence() {
+ verifyTokenizeResult("The fool looks at a finger that points at the sky",
+ "The", "fool", "looks", "at", "a", "finger", "that", "points", "at", "the", "sky");
+ }
+
+ public void testTokenizeWithPunctuation() {
+ verifyTokenizeResult("Hitchhiker's guide", "Hitchhiker's", "guide");
+ verifyTokenizeResult("full. stop. ", "full.", "stop.");
+ verifyTokenizeResult("' . ; . ..", "'", ".", ";", ".", "..");
+ }
+
+ public void testTokenizeWithTabsAndNewLines() {
+ verifyTokenizeResult("paranoid\nandroid\t", "paranoid", "android");
+ }
+
+ private void verifyFindMatches(String source, String target, String... newTokensInTarget) {
+ List<LevenshteinSuggestionFormatter.Token> sourceTokens = mFormatter.tokenize(source);
+ List<LevenshteinSuggestionFormatter.Token> targetTokens = mFormatter.tokenize(target);
+
+ int[] matches = mFormatter.findMatches(sourceTokens, targetTokens);
+ assertEquals(targetTokens.size(), matches.length);
+ int newTokenCount = 0;
+ int lastSourceToken = -1;
+ for (int i=0; i<targetTokens.size(); ++i) {
+
+ int sourceIdx = matches[i];
+ if (sourceIdx < 0) {
+ String targetToken = targetTokens.get(i).toString();
+ assertTrue("Unexpected new token '" + targetToken + "'",
+ newTokenCount < newTokensInTarget.length);
+
+ assertEquals(newTokensInTarget[newTokenCount], targetToken);
+ ++newTokenCount;
+ } else {
+ assertTrue("Source token out of order", lastSourceToken < sourceIdx);
+ LevenshteinSuggestionFormatter.Token srcToken = sourceTokens.get(sourceIdx);
+ LevenshteinSuggestionFormatter.Token trgToken = targetTokens.get(i);
+ assertTrue("'" + srcToken + "' is not a prefix of '" + trgToken + "'",
+ srcToken.prefixOf(trgToken));
+ lastSourceToken = sourceIdx;
+ }
+ }
+ }
+
+ public void testFindMatchesSameTokens() {
+ verifyFindMatches("", "");
+ verifyFindMatches("one", "one");
+ verifyFindMatches("one two three", "one two three");
+ }
+
+ public void testFindMatchesNewTokens() {
+ verifyFindMatches("", "one", "one");
+ verifyFindMatches("one", "one two", "two");
+ verifyFindMatches("one", "one two three", "two", "three");
+ verifyFindMatches("two", "one two three", "one", "three");
+ verifyFindMatches("pictures", "pictures of kittens", "of", "kittens");
+ }
+
+ public void testFindMatchesReplacedTokens() {
+ verifyFindMatches("one", "two", "two");
+ verifyFindMatches("one", "two three", "two", "three");
+ verifyFindMatches("two", "one three", "one", "three");
+ verifyFindMatches("pictures", "of kittens", "of", "kittens");
+ }
+
+ public void testFindMatchesDuplicateTokens() {
+ verifyFindMatches("badger", "badger badger", "badger");
+ verifyFindMatches("badger", "badger badger badger", "badger", "badger");
+ verifyFindMatches("badger badger", "badger badger badger", "badger");
+ verifyFindMatches("badger badger badger", "badger badger badger");
+ // mushroom!
+ }
+
+ private void verifyFormatSuggestion(String query, String suggestion, SpanFormat... spans) {
+ Spanned s = mFormatter.formatSuggestion(query, suggestion);
+ for (SpanFormat span : spans) {
+ span.verify(s);
+ }
+ }
+
+ public void testFormatSuggestionEmptyStrings() {
+ verifyFormatSuggestion("", "");
+ }
+
+ public void testFormatSuggestionEmptyQuery() {
+ verifyFormatSuggestion("", "suggestion",
+ new SpanFormat(0, "suggestion", mSuggestedStyle));
+ }
+
+ public void testFormatSuggestionQuerySuggested() {
+ verifyFormatSuggestion("query", "query",
+ new SpanFormat(0, "query", mQueryStyle));
+ }
+
+ public void testFormatSuggestionExtraWordsSuggested() {
+ verifyFormatSuggestion("query", "query suggested",
+ new SpanFormat(0, "query", mQueryStyle),
+ new SpanFormat(6, "suggested", mSuggestedStyle));
+
+ verifyFormatSuggestion("pictures", "pictures of kittens",
+ new SpanFormat(0, "pictures", mQueryStyle),
+ new SpanFormat(9, "of", mSuggestedStyle),
+ new SpanFormat(12, "kittens", mSuggestedStyle));
+
+ verifyFormatSuggestion("pictures of", "pictures of kittens dying",
+ new SpanFormat(0, "pictures", mQueryStyle),
+ new SpanFormat(9, "of", mQueryStyle),
+ new SpanFormat(12, "kittens", mSuggestedStyle),
+ new SpanFormat(20, "dying", mSuggestedStyle));
+ }
+
+ public void testFormatSuggestionExtraWordSuggestedAtStart() {
+ verifyFormatSuggestion("query", "suggested query",
+ new SpanFormat(0, "suggested", mSuggestedStyle),
+ new SpanFormat(10, "query", mQueryStyle));
+ }
+
+ public void testFormatSuggestionAlternativeWordSuggested() {
+ verifyFormatSuggestion("query", "suggested",
+ new SpanFormat(0, "suggested", mSuggestedStyle));
+ }
+
+ public void testFormatSuggestionDuplicateWords() {
+ verifyFormatSuggestion("", "badger badger",
+ new SpanFormat(0, "badger", mSuggestedStyle),
+ new SpanFormat(7, "badger", mSuggestedStyle));
+
+ verifyFormatSuggestion("badger", "badger badger",
+ new SpanFormat(0, "badger", mQueryStyle),
+ new SpanFormat(7, "badger", mSuggestedStyle));
+
+ verifyFormatSuggestion("badger badger", "badger badger",
+ new SpanFormat(0, "badger", mQueryStyle),
+ new SpanFormat(7, "badger", mQueryStyle));
+
+ verifyFormatSuggestion("badger badger", "badger badger badger",
+ new SpanFormat(0, "badger", mQueryStyle),
+ new SpanFormat(7, "badger", mQueryStyle),
+ new SpanFormat(14, "badger", mSuggestedStyle));
+ }
+
+ public void testFormatSuggestionDuplicateSequences() {
+ verifyFormatSuggestion("dem bones", "dem bones dem bones",
+ new SpanFormat(0, "dem", mQueryStyle),
+ new SpanFormat(4, "bones", mQueryStyle),
+ new SpanFormat(10, "dem", mSuggestedStyle),
+ new SpanFormat(14, "bones", mSuggestedStyle)
+ );
+
+ verifyFormatSuggestion("dem bones", "dem dry bones dem bones",
+ new SpanFormat(0, "dem", mQueryStyle),
+ new SpanFormat(4, "dry", mSuggestedStyle),
+ new SpanFormat(8, "bones", mQueryStyle),
+ new SpanFormat(14, "dem", mSuggestedStyle),
+ new SpanFormat(18, "bones", mSuggestedStyle)
+ );
+
+ verifyFormatSuggestion("dem dry bones", "dry bones dem dry bones dem dry bones",
+ new SpanFormat(0, "dry", mSuggestedStyle),
+ new SpanFormat(4, "bones", mSuggestedStyle),
+ new SpanFormat(10, "dem", mQueryStyle),
+ new SpanFormat(14, "dry", mQueryStyle),
+ new SpanFormat(18, "bones", mQueryStyle),
+ new SpanFormat(24, "dem", mSuggestedStyle),
+ new SpanFormat(28, "dry", mSuggestedStyle),
+ new SpanFormat(32, "bones", mSuggestedStyle)
+ );
+ }
+
+ public void testFormatSuggestionWordCompletion() {
+ verifyFormatSuggestion("hitch", "hitchhiker",
+ new SpanFormat(0, "hitch", mQueryStyle),
+ new SpanFormat(5, "hiker", mSuggestedStyle)
+ );
+
+ verifyFormatSuggestion("hitch", "hitchhiker's guide",
+ new SpanFormat(0, "hitch", mQueryStyle),
+ new SpanFormat(5, "hiker's", mSuggestedStyle),
+ new SpanFormat(13, "guide", mSuggestedStyle)
+ );
+
+ verifyFormatSuggestion("hitchhiker's g", "hitchhiker's guide",
+ new SpanFormat(0, "hitchhiker's", mQueryStyle),
+ new SpanFormat(13, "g", mQueryStyle),
+ new SpanFormat(14, "uide", mSuggestedStyle)
+ );
+
+ verifyFormatSuggestion("hitchhiker's g", "hitchhiker's guide to the galaxy",
+ new SpanFormat(0, "hitchhiker's", mQueryStyle),
+ new SpanFormat(13, "g", mQueryStyle),
+ new SpanFormat(14, "uide", mSuggestedStyle),
+ new SpanFormat(19, "to", mSuggestedStyle),
+ new SpanFormat(22, "the", mSuggestedStyle),
+ new SpanFormat(26, "galaxy", mSuggestedStyle)
+ );
+ }
+
+ public void testFormatSuggestionWordSplitting() {
+ verifyFormatSuggestion("dimsum", "dim sum",
+ new SpanFormat(0, "dim", mSuggestedStyle),
+ new SpanFormat(4, "sum", mSuggestedStyle)
+ );
+
+ verifyFormatSuggestion("dimsum london", "dim sum london",
+ new SpanFormat(0, "dim", mSuggestedStyle),
+ new SpanFormat(4, "sum", mSuggestedStyle),
+ new SpanFormat(8, "london", mQueryStyle)
+ );
+
+ verifyFormatSuggestion("dimsum london", "dim sum london yummy",
+ new SpanFormat(0, "dim", mSuggestedStyle),
+ new SpanFormat(4, "sum", mSuggestedStyle),
+ new SpanFormat(8, "london", mQueryStyle),
+ new SpanFormat(15, "yummy", mSuggestedStyle)
+ );
+ }
+
+ public void testFormatSuggestionWordCombining() {
+ verifyFormatSuggestion("hos pital", "hospital",
+ new SpanFormat(0, "hos", mQueryStyle),
+ new SpanFormat(3, "pital", mSuggestedStyle)
+ );
+
+ verifyFormatSuggestion("hos pital", "hospital waiting times",
+ new SpanFormat(0, "hos", mQueryStyle),
+ new SpanFormat(3, "pital", mSuggestedStyle),
+ new SpanFormat(9, "waiting", mSuggestedStyle),
+ new SpanFormat(17, "times", mSuggestedStyle)
+ );
+
+ verifyFormatSuggestion("hos pital waiting", "hospital waiting",
+ new SpanFormat(0, "hos", mQueryStyle),
+ new SpanFormat(3, "pital", mSuggestedStyle),
+ new SpanFormat(9, "waiting", mQueryStyle)
+ );
+
+ verifyFormatSuggestion("hospital wait ing times", "hospital waiting times",
+ new SpanFormat(0, "hospital", mQueryStyle),
+ new SpanFormat(9, "wait", mQueryStyle),
+ new SpanFormat(13, "ing", mSuggestedStyle),
+ new SpanFormat(17, "times", mQueryStyle)
+ );
+ }
+
+ public void testFormatSuggestionCapitalization() {
+ verifyFormatSuggestion("Flay", "flay",
+ new SpanFormat(0, "flay", mQueryStyle));
+
+ verifyFormatSuggestion("STEERPI", "steerpike",
+ new SpanFormat(0, "steerpi", mQueryStyle),
+ new SpanFormat(7, "ke", mSuggestedStyle));
+
+ verifyFormatSuggestion("STEErpi", "steerpike",
+ new SpanFormat(0, "steerpi", mQueryStyle),
+ new SpanFormat(7, "ke", mSuggestedStyle));
+
+ verifyFormatSuggestion("TITUS", "titus groan",
+ new SpanFormat(0, "titus", mQueryStyle),
+ new SpanFormat(6, "groan", mSuggestedStyle));
+}
+
+ private class SpanFormat {
+ private final int mStart;
+ private final int mEnd;
+ private final String mExpectedText;
+ private final int mStyle;
+ public SpanFormat(int start, String expectedText, int style) {
+ mStart = start;
+ mEnd = start + expectedText.length();
+ mExpectedText = expectedText;
+ mStyle = style;
+ }
+ public void verify(Spanned spanned) {
+ String spannedText = spanned.subSequence(mStart, mEnd).toString();
+ assertEquals("Test error", mExpectedText, spannedText);
+ StyleSpan[] spans = spanned.getSpans(mStart, mEnd, StyleSpan.class);
+ assertEquals("Wrong number of spans in '" + spannedText + "'", 1, spans.length);
+ assertEquals("Wrong style for '" + spannedText + "' at position " + mStart,
+ mStyle, spans[0].getStyle());
+ }
+ }
+
+}
diff --git a/tests/src/com/android/quicksearchbox/util/LevenshteinDistanceTest.java b/tests/src/com/android/quicksearchbox/util/LevenshteinDistanceTest.java
new file mode 100644
index 0000000..d1fa700
--- /dev/null
+++ b/tests/src/com/android/quicksearchbox/util/LevenshteinDistanceTest.java
@@ -0,0 +1,137 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.quicksearchbox.util;
+
+import com.android.quicksearchbox.util.LevenshteinDistance.EditOperation;
+
+import android.test.AndroidTestCase;
+
+import java.util.Arrays;
+
+/**
+ * Tests for class {@link LevenshteinDistance}.
+ */
+public class LevenshteinDistanceTest extends AndroidTestCase {
+ // to make the tests less verbose:
+ private static final int INSERT = LevenshteinDistance.EDIT_INSERT;
+ private static final int DELETE = LevenshteinDistance.EDIT_DELETE;
+ private static final int REPLACE = LevenshteinDistance.EDIT_REPLACE;
+ private static final int UNCHANGED = LevenshteinDistance.EDIT_UNCHANGED;
+
+ private void verifyTargetOperations(String[] source, String[] target, int[] expectedOps,
+ int expectedDistance) {
+
+ assertEquals("test error", target.length, expectedOps.length);
+ LevenshteinDistance<String> distance = new LevenshteinDistance<String>
+ (Arrays.asList(source), Arrays.asList(target)){
+ @Override
+ protected boolean match(String source, String target) {
+ return source.equals(target);
+ }};
+
+ assertEquals(expectedDistance, distance.calculate());
+ EditOperation[] ops = distance.getTargetOperations();
+ assertEquals(expectedOps.length, ops.length);
+ for (int i = 0; i < ops.length; ++i) {
+ assertEquals("Token " + i + " '" + target[i] + "' has wrong operation",
+ expectedOps[i], ops[i].getType());
+ if (expectedOps[i] == UNCHANGED) {
+ assertEquals(source[ops[i].getPosition()], target[i]);
+ } else if (expectedOps[i] == REPLACE) {
+ assertFalse(source[ops[i].getPosition()].equals(target[i]));
+ }
+ }
+ }
+
+ public void testGetTargetOperationsEmptySource() {
+ verifyTargetOperations(
+ new String[]{},
+ new String[]{},
+ new int[]{},
+ 0);
+
+ verifyTargetOperations(
+ new String[]{},
+ new String[]{"goo", "ball"},
+ new int[]{INSERT, INSERT},
+ 2);
+ }
+
+ public void testGetTargetOperationsEmptyTarget() {
+ verifyTargetOperations(
+ new String[]{"delete"},
+ new String[]{},
+ new int[] {},
+ 1);
+
+ verifyTargetOperations(
+ new String[]{"delete", "me"},
+ new String[]{},
+ new int[] {},
+ 2);
+ }
+
+ public void testGetTargetOperationsReplacement() {
+ verifyTargetOperations(
+ new String[]{"dennis"},
+ new String[]{"gnasher"},
+ new int[] {REPLACE},
+ 1);
+
+ verifyTargetOperations(
+ new String[]{"angry", "viking"},
+ new String[]{"happy", "kitten"},
+ new int[] {REPLACE, REPLACE},
+ 2);
+ }
+
+ public void testGetTargetOperationsUnchanged() {
+ verifyTargetOperations(
+ new String[]{"tweedledee"},
+ new String[]{"tweedledee"},
+ new int[] {UNCHANGED},
+ 0);
+
+ verifyTargetOperations(
+ new String[]{"tweedledee", "tweedledum"},
+ new String[]{"tweedledee", "tweedledum"},
+ new int[] {UNCHANGED, UNCHANGED},
+ 0);
+ }
+
+ public void testGetTargetOperationsDuplicateTokens() {
+ String rhubarb = "rhubarb";
+ verifyTargetOperations(
+ new String[]{rhubarb},
+ new String[]{rhubarb, rhubarb},
+ new int[] {UNCHANGED, INSERT},
+ 1);
+
+ verifyTargetOperations(
+ new String[]{rhubarb, rhubarb},
+ new String[]{rhubarb, rhubarb},
+ new int[] {UNCHANGED, UNCHANGED},
+ 0);
+
+ verifyTargetOperations(
+ new String[]{rhubarb, rhubarb},
+ new String[]{rhubarb, rhubarb, rhubarb},
+ new int[] {UNCHANGED, UNCHANGED, INSERT},
+ 1);
+ }
+
+}
