RankAwarePromoter.java revision af1ca2cc65a2c2fdf6f396126e235d64e4da0936 
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.google.common.annotations.VisibleForTesting;
20
21import android.util.Log;
22
23import java.util.Iterator;
24import java.util.LinkedList;
25
26/**
27 * A promoter that gives preference to suggestions from higher ranking corpora.
28 */
29public class RankAwarePromoter extends AbstractPromoter {
30
31    private static final boolean DBG = false;
32    private static final String TAG = "QSB.RankAwarePromoter";
33
34    public RankAwarePromoter(Config config, SuggestionFilter filter) {
35        super(filter, config);
36    }
37
38    @Override
39    public void pickPromoted(Suggestions suggestions,
40            int maxPromoted, ListSuggestionCursor promoted) {
41        promoteSuggestions(suggestions.getCorpusResults(), maxPromoted, promoted);
42    }
43
44    @VisibleForTesting
45    void promoteSuggestions(Iterable<CorpusResult> suggestions, int maxPromoted,
46            ListSuggestionCursor promoted) {
47        if (DBG) Log.d(TAG, "Available results: " + suggestions);
48
49        // Split non-empty results into important suggestions and not-so-important
50        // suggestions, each corpus's cursor positioned at the first suggestion.
51        LinkedList<CorpusResult> highRankingSuggestions = new LinkedList<CorpusResult>();
52        LinkedList<CorpusResult> lowRankingSuggestions = new LinkedList<CorpusResult>();
53        partitionSuggestionsByRank(suggestions, highRankingSuggestions, lowRankingSuggestions);
54
55        // Top results, evenly distributed between each high-ranking corpus.
56        promoteTopSuggestions(highRankingSuggestions, promoted, maxPromoted);
57
58        // Then try to fill promoted list with the remaining high-ranking suggestions,
59        // and then use the low-ranking suggestions if the list isn't full yet.
60        promoteEquallyFromEachCorpus(highRankingSuggestions, promoted, maxPromoted);
61        promoteEquallyFromEachCorpus(lowRankingSuggestions, promoted, maxPromoted);
62
63        if (DBG) Log.d(TAG, "Returning " + promoted.toString());
64    }
65
66    /**
67     * Shares the top slots evenly among each of the high-ranking (default) corpora.
68     *
69     * The corpora will appear in the promoted list in the order they are listed
70     * among the incoming suggestions (this method doesn't change their order).
71     */
72    private void promoteTopSuggestions(LinkedList<CorpusResult> highRankingSuggestions,
73            ListSuggestionCursor promoted, int maxPromoted) {
74
75        int slotsLeft = getSlotsLeft(promoted, maxPromoted);
76        if (slotsLeft > 0 && !highRankingSuggestions.isEmpty()) {
77            int slotsToFill = Math.min(getSlotsAboveKeyboard() - promoted.getCount(), slotsLeft);
78
79            if (slotsToFill > 0) {
80                int stripeSize = Math.max(1, slotsToFill / highRankingSuggestions.size());
81                roundRobin(highRankingSuggestions, slotsToFill, stripeSize, promoted);
82            }
83        }
84    }
85
86    /**
87     * Tries to promote the same number of elements from each corpus.
88     *
89     * The corpora will appear in the promoted list in the order they are listed
90     * among the incoming suggestions (this method doesn't change their order).
91     */
92    private void promoteEquallyFromEachCorpus(LinkedList<CorpusResult> suggestions,
93            ListSuggestionCursor promoted, int maxPromoted) {
94
95        int slotsLeft = getSlotsLeft(promoted, maxPromoted);
96        if (slotsLeft == 0) {
97            // No more items to add.
98            return;
99        }
100
101        if (suggestions.isEmpty()) {
102            return;
103        }
104
105        int stripeSize = Math.max(1, slotsLeft / suggestions.size());
106        roundRobin(suggestions, slotsLeft, stripeSize, promoted);
107
108        // We may still have a few slots left
109        slotsLeft = getSlotsLeft(promoted, maxPromoted);
110        roundRobin(suggestions, slotsLeft, slotsLeft, promoted);
111    }
112
113    /**
114     * Partitions the suggestions into "important" (high-ranking)
115     * and "not-so-important" (low-ranking) suggestions, dependent on the
116     * rank of the corpus the result is part of.
117     *
118     * @param suggestions
119     * @param highRankingSuggestions These should be displayed first to the
120     *     user.
121     * @param lowRankingSuggestions These should be displayed if the
122     *     high-ranking suggestions don't fill all the available space in the
123     *     result view.
124     */
125    private void partitionSuggestionsByRank(Iterable<CorpusResult> suggestions,
126            LinkedList<CorpusResult> highRankingSuggestions,
127            LinkedList<CorpusResult> lowRankingSuggestions) {
128
129        for (CorpusResult result : suggestions) {
130            if (result.getCount() > 0) {
131                result.moveTo(0);
132                Corpus corpus = result.getCorpus();
133                if (isCorpusHighlyRanked(corpus)) {
134                    highRankingSuggestions.add(result);
135                } else {
136                    lowRankingSuggestions.add(result);
137                }
138            }
139        }
140    }
141
142    private boolean isCorpusHighlyRanked(Corpus corpus) {
143        // The default corpora shipped with QSB (apps, etc.) are
144        // more important than ones that were registered later.
145        return corpus == null || corpus.isCorpusDefaultEnabled();
146    }
147
148    private int getSlotsLeft(ListSuggestionCursor promoted, int maxPromoted) {
149        // It's best to calculate this after each addition because duplicates
150        // may get filtered out automatically in the list of promoted items.
151        return Math.max(0, maxPromoted - promoted.getCount());
152    }
153
154    private int getSlotsAboveKeyboard() {
155        return getConfig().getNumSuggestionsAboveKeyboard();
156    }
157
158    /**
159     * Promotes "stripes" of suggestions from each corpus.
160     *
161     * @param results     the list of CorpusResults from which to promote.
162     *                    Exhausted CorpusResults are removed from the list.
163     * @param maxPromoted maximum number of suggestions to promote.
164     * @param stripeSize  number of suggestions to take from each corpus.
165     * @param promoted    the list to which promoted suggestions are added.
166     * @return the number of suggestions actually promoted.
167     */
168    private int roundRobin(LinkedList<CorpusResult> results, int maxPromoted, int stripeSize,
169            ListSuggestionCursor promoted) {
170        int count = 0;
171        if (maxPromoted > 0 && !results.isEmpty()) {
172            for (Iterator<CorpusResult> iter = results.iterator();
173                 count < maxPromoted && iter.hasNext();) {
174                CorpusResult result = iter.next();
175                count += promote(result, stripeSize, promoted);
176                if (result.getPosition() == result.getCount()) {
177                    iter.remove();
178                }
179            }
180        }
181        return count;
182    }
183
184    /**
185     * Copies suggestions from a SuggestionCursor to the list of promoted suggestions.
186     *
187     * @param cursor from which to copy the suggestions
188     * @param count maximum number of suggestions to copy
189     * @param promoted the list to which to add the suggestions
190     * @return the number of suggestions actually copied.
191     */
192    private int promote(SuggestionCursor cursor, int count, ListSuggestionCursor promoted) {
193        if (count < 1 || cursor.getPosition() >= cursor.getCount()) {
194            return 0;
195        }
196        int addedCount = 0;
197        do {
198            if (accept(cursor)) {
199                if (promoted.add(new SuggestionPosition(cursor))) {
200                    // Added successfully (wasn't already promoted).
201                    addedCount++;
202                }
203            }
204        } while (cursor.moveToNext() && addedCount < count);
205        return addedCount;
206    }
207
208}
209