RankAwarePromoter.java revision b83882b9efa37ec0f20a0f1c85cf5ccc93194aee 
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 implements Promoter {
30
31    private static final boolean DBG = false;
32    private static final String TAG = "QSB.RankAwarePromoter";
33
34    private final Config mConfig;
35
36    public RankAwarePromoter(Config config) {
37        mConfig = config;
38    }
39
40    protected Config getConfig() {
41        return mConfig;
42    }
43
44    public void pickPromoted(Suggestions suggestions,
45            int maxPromoted, ListSuggestionCursor promoted) {
46        promoteSuggestions(suggestions.getCorpusResults(), maxPromoted, promoted);
47    }
48
49    @VisibleForTesting
50    void promoteSuggestions(Iterable<CorpusResult> suggestions, int maxPromoted,
51            ListSuggestionCursor promoted) {
52        if (DBG) Log.d(TAG, "Available results: " + suggestions);
53
54        // Split non-empty results into default sources and other, positioned at first suggestion
55        LinkedList<CorpusResult> defaultResults = new LinkedList<CorpusResult>();
56        LinkedList<CorpusResult> otherResults = new LinkedList<CorpusResult>();
57        for (CorpusResult result : suggestions) {
58            if (result.getCount() > 0) {
59                result.moveTo(0);
60                Corpus corpus = result.getCorpus();
61                if (corpus == null || corpus.isCorpusDefaultEnabled()) {
62                    defaultResults.add(result);
63                } else {
64                    otherResults.add(result);
65                }
66            }
67        }
68
69        // Share the top slots equally among each of the default corpora
70        if (maxPromoted > 0 && !defaultResults.isEmpty()) {
71            int slotsToFill = Math.min(getSlotsAboveKeyboard() - promoted.getCount(), maxPromoted);
72            if (slotsToFill > 0) {
73                int stripeSize = Math.max(1, slotsToFill / defaultResults.size());
74                maxPromoted -= roundRobin(defaultResults, slotsToFill, stripeSize, promoted);
75            }
76        }
77
78        // Then try to fill with the remaining promoted results
79        if (maxPromoted > 0 && !defaultResults.isEmpty()) {
80            int stripeSize = Math.max(1, maxPromoted / defaultResults.size());
81            maxPromoted -= roundRobin(defaultResults, maxPromoted, stripeSize, promoted);
82            // We may still have a few slots left
83            maxPromoted -= roundRobin(defaultResults, maxPromoted, maxPromoted, promoted);
84        }
85
86        // Then try to fill with the rest
87        if (maxPromoted > 0 && !otherResults.isEmpty()) {
88            int stripeSize = Math.max(1, maxPromoted / otherResults.size());
89            maxPromoted -= roundRobin(otherResults, maxPromoted, stripeSize, promoted);
90            // We may still have a few slots left
91            maxPromoted -= roundRobin(otherResults, maxPromoted, maxPromoted, promoted);
92        }
93
94        if (DBG) Log.d(TAG, "Returning " + promoted.toString());
95    }
96
97    private int getSlotsAboveKeyboard() {
98        return mConfig.getNumSuggestionsAboveKeyboard();
99    }
100
101    /**
102     * Promotes "stripes" of suggestions from each corpus.
103     *
104     * @param results     the list of CorpusResults from which to promote.
105     *                    Exhausted CorpusResults are removed from the list.
106     * @param maxPromoted maximum number of suggestions to promote.
107     * @param stripeSize  number of suggestions to take from each corpus.
108     * @param promoted    the list to which promoted suggestions are added.
109     * @return the number of suggestions actually promoted.
110     */
111    private int roundRobin(LinkedList<CorpusResult> results, int maxPromoted, int stripeSize,
112            ListSuggestionCursor promoted) {
113        int count = 0;
114        if (maxPromoted > 0 && !results.isEmpty()) {
115            for (Iterator<CorpusResult> iter = results.iterator();
116                 count < maxPromoted && iter.hasNext();) {
117                CorpusResult result = iter.next();
118                count += promote(result, stripeSize, promoted);
119                if (result.getPosition() == result.getCount()) {
120                    iter.remove();
121                }
122            }
123        }
124        return count;
125    }
126
127    /**
128     * Copies suggestions from a SuggestionCursor to the list of promoted suggestions.
129     *
130     * @param cursor from which to copy the suggestions
131     * @param count maximum number of suggestions to copy
132     * @param promoted the list to which to add the suggestions
133     * @return the number of suggestions actually copied.
134     */
135    private int promote(SuggestionCursor cursor, int count, ListSuggestionCursor promoted) {
136        if (count < 1 || cursor.getPosition() >= cursor.getCount()) {
137            return 0;
138        }
139        int addedCount = 0;
140        do {
141            if (accept(cursor)) {
142                promoted.add(new SuggestionPosition(cursor));
143                addedCount++;
144            }
145        } while (cursor.moveToNext() && addedCount < count);
146        return addedCount;
147    }
148
149    /**
150     * Determines if a suggestion should be added to the promoted suggestion list.
151     *
152     * @param s The suggestion in question
153     * @return true to include it in the results
154     */
155    protected boolean accept(Suggestion s) {
156        return true;
157    }
158
159}
160