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