Home | History | Annotate | Download | only in quicksearchbox 
      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 
     17 package com.android.quicksearchbox;
     18 
     19 import com.google.common.annotations.VisibleForTesting;
     20 
     21 import android.util.Log;
     22 
     23 import java.util.Iterator;
     24 import java.util.LinkedList;
     25 
     26 /**
     27  * A promoter that gives preference to suggestions from higher ranking corpora.
     28  */
     29 public 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, Promoter next) {
     35         super(filter, next, config);
     36     }
     37 
     38     @Override
     39     public void doPickPromoted(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