RankAwarePromoter.java revision fdb80c2962c88ac62dcd7ee7f2fab1857b61506b 
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        int slotsLeft = Math.max(0, maxPromoted - promoted.getCount());
70
71        // Share the top slots equally among each of the default corpora
72        if (slotsLeft > 0 && !defaultResults.isEmpty()) {
73            int slotsToFill = Math.min(getSlotsAboveKeyboard() - promoted.getCount(), slotsLeft);
74            if (slotsToFill > 0) {
75                int stripeSize = Math.max(1, slotsToFill / defaultResults.size());
76                slotsLeft -= roundRobin(defaultResults, slotsToFill, stripeSize, promoted);
77            }
78        }
79
80        // Then try to fill with the remaining promoted results
81        if (slotsLeft > 0 && !defaultResults.isEmpty()) {
82            int stripeSize = Math.max(1, slotsLeft / defaultResults.size());
83            slotsLeft -= roundRobin(defaultResults, slotsLeft, stripeSize, promoted);
84            // We may still have a few slots left
85            slotsLeft -= roundRobin(defaultResults, slotsLeft, slotsLeft, promoted);
86        }
87
88        // Then try to fill with the rest
89        if (slotsLeft > 0 && !otherResults.isEmpty()) {
90            int stripeSize = Math.max(1, slotsLeft / otherResults.size());
91            slotsLeft -= roundRobin(otherResults, slotsLeft, stripeSize, promoted);
92            // We may still have a few slots left
93            slotsLeft -= roundRobin(otherResults, slotsLeft, slotsLeft, promoted);
94        }
95
96        if (DBG) Log.d(TAG, "Returning " + promoted.toString());
97    }
98
99    private int getSlotsAboveKeyboard() {
100        return mConfig.getNumSuggestionsAboveKeyboard();
101    }
102
103    /**
104     * Promotes "stripes" of suggestions from each corpus.
105     *
106     * @param results     the list of CorpusResults from which to promote.
107     *                    Exhausted CorpusResults are removed from the list.
108     * @param maxPromoted maximum number of suggestions to promote.
109     * @param stripeSize  number of suggestions to take from each corpus.
110     * @param promoted    the list to which promoted suggestions are added.
111     * @return the number of suggestions actually promoted.
112     */
113    private int roundRobin(LinkedList<CorpusResult> results, int maxPromoted, int stripeSize,
114            ListSuggestionCursor promoted) {
115        int count = 0;
116        if (maxPromoted > 0 && !results.isEmpty()) {
117            for (Iterator<CorpusResult> iter = results.iterator();
118                 count < maxPromoted && iter.hasNext();) {
119                CorpusResult result = iter.next();
120                count += promote(result, stripeSize, promoted);
121                if (result.getPosition() == result.getCount()) {
122                    iter.remove();
123                }
124            }
125        }
126        return count;
127    }
128
129    /**
130     * Copies suggestions from a SuggestionCursor to the list of promoted suggestions.
131     *
132     * @param cursor from which to copy the suggestions
133     * @param count maximum number of suggestions to copy
134     * @param promoted the list to which to add the suggestions
135     * @return the number of suggestions actually copied.
136     */
137    private int promote(SuggestionCursor cursor, int count, ListSuggestionCursor promoted) {
138        if (count < 1 || cursor.getPosition() >= cursor.getCount()) {
139            return 0;
140        }
141        int addedCount = 0;
142        do {
143            if (accept(cursor)) {
144                promoted.add(new SuggestionPosition(cursor));
145                addedCount++;
146            }
147        } while (cursor.moveToNext() && addedCount < count);
148        return addedCount;
149    }
150
151    /**
152     * Determines if a suggestion should be added to the promoted suggestion list.
153     *
154     * @param s The suggestion in question
155     * @return true to include it in the results
156     */
157    protected boolean accept(Suggestion s) {
158        return true;
159    }
160
161}
162