RankAwarePromoter.java revision a4cd9e7cdd5bdc6198ce73eed55696554a146514
1a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney/* 2a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * Copyright (C) 2010 The Android Open Source Project 3a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * 4a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * Licensed under the Apache License, Version 2.0 (the "License"); 5a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * you may not use this file except in compliance with the License. 6a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * You may obtain a copy of the License at 7a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * 8a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * http://www.apache.org/licenses/LICENSE-2.0 9a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * 10a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * Unless required by applicable law or agreed to in writing, software 11a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * distributed under the License is distributed on an "AS IS" BASIS, 12a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * See the License for the specific language governing permissions and 14a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * limitations under the License. 15a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney */ 16a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 17a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinneypackage com.android.quicksearchbox; 18a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 19a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinneyimport java.util.*; 20a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 21a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney/** 22a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * A promoter that gives preference to suggestions from higher ranking corpora. 23a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney */ 24a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinneypublic class RankAwarePromoter implements Promoter { 25a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 26a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney private final HashSet<Corpus> mPromotedCorpora; 27a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 28a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney public RankAwarePromoter(Corpora corpora, CorpusRanker corpusRanker, int maxPromotedCorpora) { 29a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney // Create a set of the corpora we consider to be promoted. Note that we 30a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney // only do this once, even though these may change slightly during a session. 31a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney ArrayList<Corpus> orderedCorpora = corpusRanker.rankCorpora(corpora.getAllCorpora()); 32a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney int count = Math.min(orderedCorpora.size(), maxPromotedCorpora); 33a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney mPromotedCorpora = new HashSet<Corpus>(orderedCorpora.subList(0, count)); 34a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 35a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 36a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney private boolean isPromoted(Corpus corpus) { 37a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney return mPromotedCorpora.contains(corpus); 38a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 39a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 40a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney public void pickPromoted(SuggestionCursor shortcuts, ArrayList<CorpusResult> suggestions, 41a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney int maxPromoted, ListSuggestionCursor promoted) { 42a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 43a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney // Split non-empty results into promoted and other, positioned at first suggestion 44a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney LinkedList<CorpusResult> promotedResults = new LinkedList<CorpusResult>(); 45a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney LinkedList<CorpusResult> otherResults = new LinkedList<CorpusResult>(); 46a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney for (int i = 0; i < suggestions.size(); i++) { 47a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney CorpusResult result = suggestions.get(i); 48a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney if (result.getCount() > 0) { 49a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney result.moveTo(0); 50a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney if (isPromoted(result.getCorpus())) { 51a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney promotedResults.add(result); 52a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } else { 53a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney otherResults.add(result); 54a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 55a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 56a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 57a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 58a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney // Pick 2 results from each of the promoted corpora 59a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney maxPromoted -= roundRobin(promotedResults, maxPromoted, 2, promoted); 60a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 61a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney // Then try to fill with the remaining promoted results 62a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney if (maxPromoted > 0 && !promotedResults.isEmpty()) { 63a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney int stripeSize = Math.max(1, maxPromoted / promotedResults.size()); 64a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney maxPromoted -= roundRobin(promotedResults, maxPromoted, stripeSize, promoted); 65a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney // We may still have a few slots left 66a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney maxPromoted -= roundRobin(promotedResults, maxPromoted, maxPromoted, promoted); 67a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 68a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 69a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney // Then try to fill with the rest 70a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney if (maxPromoted > 0 && !otherResults.isEmpty()) { 71a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney int stripeSize = Math.max(1, maxPromoted / otherResults.size()); 72a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney maxPromoted -= roundRobin(otherResults, maxPromoted, stripeSize, promoted); 73a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney // We may still have a few slots left 74a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney maxPromoted -= roundRobin(otherResults, maxPromoted, maxPromoted, promoted); 75a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 76a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 77a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 78a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney /** 79a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * Promotes "stripes" of suggestions from each corpus. 80a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * 81a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * @param results the list of CorpusResults from which to promote. 82a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * Exhausted CorpusResults are removed from the list. 83a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * @param maxPromoted maximum number of suggestions to promote. 84a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * @param stripeSize number of suggestions to take from each corpus. 85a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * @param promoted the list to which promoted suggestions are added. 86a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * @return the number of suggestions actually promoted. 87a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney */ 88a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney private int roundRobin(LinkedList<CorpusResult> results, int maxPromoted, int stripeSize, 89a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney ListSuggestionCursor promoted) { 90a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney int count = 0; 91a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney if (maxPromoted > 0 && !results.isEmpty()) { 92a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney for (Iterator<CorpusResult> iter = results.iterator(); 93a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney count < maxPromoted && iter.hasNext();) { 94a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney CorpusResult result = iter.next(); 95a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney count += promote(result, stripeSize, promoted); 96a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney if (result.getPosition() == result.getCount()) { 97a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney iter.remove(); 98a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 99a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 100a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 101a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney return count; 102a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 103a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney 104a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney /** 105a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * Copies suggestions from a SuggestionCursor to the list of promoted suggestions. 106a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * 107a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * @param cursor from which to copy the suggestions 108a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * @param count maximum number of suggestions to copy 109a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * @param promoted the list to which to add the suggestions 110a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney * @return the number of suggestions actually copied. 111a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney */ 112a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney private int promote(SuggestionCursor cursor, int count, ListSuggestionCursor promoted) { 113a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney int i = 0; 114a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney while (i < count && cursor.getPosition() < cursor.getCount()) { 115a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney promoted.add(new SuggestionPosition(cursor)); 116a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney cursor.moveTo(cursor.getPosition() + 1); 117a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney i++; 118a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 119a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney return i; 120a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney } 121a4cd9e7cdd5bdc6198ce73eed55696554a146514Bryan Mawhinney} 122