diff options
Diffstat (limited to 'kicker/applets/launcher/popularity.cpp')
| -rw-r--r-- | kicker/applets/launcher/popularity.cpp | 424 |
1 files changed, 424 insertions, 0 deletions
diff --git a/kicker/applets/launcher/popularity.cpp b/kicker/applets/launcher/popularity.cpp new file mode 100644 index 000000000..3bfcdd872 --- /dev/null +++ b/kicker/applets/launcher/popularity.cpp @@ -0,0 +1,424 @@ +/***************************************************************** + +Copyright (c) 2005 Fred Schaettgen <[email protected]> + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN +AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN +CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +******************************************************************/ + +#include "popularity.h" +#include "prefs.h" +#include <assert.h> +#include <algorithm> +#include <iterator> +#include <kconfig.h> +#include <kdebug.h> +#include <list> +#include <set> +#include <map> +#include <cmath> +#include <vector> + +using namespace std; + +class PopularityStatisticsImpl +{ +public: + struct SingleFalloffHistory + { + public: + // fallof is a number between 0 and 1. The popularity of + // each service is multiplied with the falloff value + // every time a service is used. Only the used service + // gets also 1-falloff added to its popularity. + double falloff; + // popularity values for each service + map<QString, double> vals; + // accumulated popularity of the unknown programs + // started before the statistic started + double iniVal; + }; + + struct Popularity + { + QString service; + double popularity; + bool operator<(const Popularity& p) const + { + return popularity > p.popularity; + } + }; + + PopularityStatisticsImpl(); + void normalizeHistory(SingleFalloffHistory& h); + void updateServiceRanks(); + + vector<SingleFalloffHistory> m_stats; + vector<Popularity> m_servicesByPopularity; + map<QString, int> m_serviceRanks; + double m_historyHorizon; +}; + +// ---- Public methods ---- + +PopularityStatistics::PopularityStatistics() : + d(new PopularityStatisticsImpl()) +{ +} + +PopularityStatistics::~PopularityStatistics() +{ + delete d; +} + +void PopularityStatistics::useService(const QString& service) +{ + vector<PopularityStatisticsImpl::SingleFalloffHistory>::iterator + it(d->m_stats.begin()), end(d->m_stats.end()); + for (; it != end; ++it) + { + map<QString, double>::iterator valIt; + bool found(false); + for (valIt = it->vals.begin(); valIt != it->vals.end(); ++valIt) + { + valIt->second = valIt->second * it->falloff; + if (valIt->first == service) + { + found = true; + valIt->second += 1-it->falloff; + } + } + it->iniVal = it->iniVal * it->falloff; + if (found == false) + { + it->vals[service] = 1-it->falloff; + } + d->normalizeHistory(*it); + } + d->updateServiceRanks(); +} + +void PopularityStatistics::moveToTop(const QStringList& newTopServiceList) +{ + vector<PopularityStatisticsImpl::SingleFalloffHistory>::iterator + histIt(d->m_stats.begin()), histEnd(d->m_stats.end()); + for (; histIt != histEnd; ++histIt) + { + set<QString> newTopServices; + for (uint n=0; n<newTopServiceList.size(); ++n) + newTopServices.insert(newTopServiceList[n]); + + // Sort by popularity + vector<PopularityStatisticsImpl::Popularity> ranking; + map<QString, double>::iterator valIt; + for (valIt = histIt->vals.begin(); valIt != histIt->vals.end(); ++valIt) + { + PopularityStatisticsImpl::Popularity pop; + pop.service = valIt->first; + pop.popularity = valIt->second; + ranking.push_back(pop); + } + stable_sort(ranking.begin(), ranking.end()); + + // Get the new positions of each service in the ranking. + // We don't touch the popularity values in the ranking. + list<QString> topServiceList, bottomServiceList; + vector<PopularityStatisticsImpl::Popularity>:: iterator rankIt; + for (rankIt = ranking.begin(); rankIt != ranking.end(); ++rankIt) + { + if (newTopServices.find(rankIt->service) != newTopServices.end()) + { + topServiceList.push_back(rankIt->service); + //kdDebug() << "top service: " << valIt->first << endl; + newTopServices.erase(rankIt->service); + } + else + { + //kdDebug() << "bottom service: " << valIt->first << endl; + bottomServiceList.push_back(rankIt->service); + } + } + // Append remaining new services to the topServices list + while (newTopServices.size() > 0) + { + topServiceList.push_back(*newTopServices.begin()); + newTopServices.erase(newTopServices.begin()); + } + + list<QString> newServiceList; + copy(topServiceList.begin(), topServiceList.end(), + back_insert_iterator<list<QString> >(newServiceList)); + copy(bottomServiceList.begin(), bottomServiceList.end(), + back_insert_iterator<list<QString> >(newServiceList)); + + // Merge the old list of service popularities + // with the new ordering of the services + histIt->vals.clear(); + list<QString>::iterator servIt; + uint serviceIndex = 0; + //kdDebug() << endl; + + for (servIt = newServiceList.begin(); servIt != newServiceList.end(); + ++servIt) + { + if (serviceIndex < ranking.size()) + { + histIt->vals[*servIt] = ranking[serviceIndex].popularity; + //kdDebug() << "->Re-Added service " << + //ranking[serviceIndex].popularity + // << " " << *servIt << endl; + //kdDebug() << "...was replaced by " << *servIt << endl; + } + else + { + //kdDebug() << "Service " << *servIt << endl; + //kdDebug() << "...was set to popularity=0" << endl; + histIt->vals[*servIt] = 0.00001; + } + // Make sure that the topServices are actually bigger than + // the bottomServices and not just bigger or equal + // and also that no services have popularity==0 + if (serviceIndex >= topServiceList.size()) + { + histIt->vals[*servIt] *= histIt->falloff; + } + ++serviceIndex; + } + d->normalizeHistory(*histIt); + } + d->updateServiceRanks(); +} + +/*v +Old version - moves everything else one position up +and 'service' to the bottom +void PopularityStatistics::moveToBottom(const QString& service) +{ + // Moves a service to the bottom of the ranking + // by moving everything else to the top + d->updateServiceRanks(); + QStringList allButOneServices; + vector<PopularityStatisticsImpl::Popularity>::iterator + it(d->m_servicesByPopularity.begin()), + end(d->m_servicesByPopularity.end()); + for (; it != end; ++it) + { + if (it->service != service) + allButOneServices << it->service; + } + moveToTop(allButOneServices); +}*/ + +void PopularityStatistics::moveToBottom(const QString& service) +{ + vector<PopularityStatisticsImpl::SingleFalloffHistory>::iterator + it(d->m_stats.begin()), end(d->m_stats.end()); + for (; it != end; ++it) + { + it->iniVal += it->vals[service]; + it->vals[service] = 0; + d->normalizeHistory(*it); + } + d->updateServiceRanks(); +} + +QString PopularityStatistics::serviceByRank(int n) const +{ + if (n >= 0 && n < int(d->m_servicesByPopularity.size())) + return d->m_servicesByPopularity[n].service; + else + return QString(); +} + +double PopularityStatistics::popularityByRank(int n) const +{ + if (n >= 0 && n < int(d->m_servicesByPopularity.size())) + return d->m_servicesByPopularity[n].popularity; + else + return 0.0; +} + +int PopularityStatistics::rankByService(const QString service) +{ + if (d->m_serviceRanks.find(service) != d->m_serviceRanks.end()) + { + return d->m_serviceRanks[service]; + } + return -1; +} + +void PopularityStatistics::writeConfig(Prefs* prefs) const +{ + QStringList serviceNames, serviceHistories; + int limit = prefs->serviceCacheSize(); + //kdDebug() << "popularityData: writeConfig" << endl; + for (int n=0; n<int(d->m_servicesByPopularity.size()) && n<limit; ++n) + { + PopularityStatisticsImpl::Popularity pop = d->m_servicesByPopularity[n]; + QStringList historyData; + for (int i=0; i<int(d->m_stats.size()); ++i) + { + historyData << QString::number(d->m_stats[i].vals[pop.service]); + } + serviceNames << pop.service; + serviceHistories << historyData.join("/"); + //kdDebug() << "popularityData: writeConfig -- " << pop.service << endl; + } + prefs->setServiceNames(serviceNames); + prefs->setServiceHistories(serviceHistories); +} + +void PopularityStatistics::readConfig(Prefs* prefs) +{ + int n = 0; + QStringList serviceNames = prefs->serviceNames(); + QStringList histories = prefs->serviceHistories(); + for (n = std::min(serviceNames.size(), histories.size())-1; n>=0; --n) + { + QString serviceName = serviceNames[n]; + QStringList serviceHistory = + QStringList::split("/", histories[n]); + for (int i=min(serviceHistory.size(), d->m_stats.size())-1; i>=0; --i) + { + d->m_stats[i].vals[serviceName] = serviceHistory[i].toDouble(); + } + } + + for (int i=0; i<int(d->m_stats.size()); ++i) + { + map<QString, double>::iterator valIt; + double valSum = 0; + for (valIt = d->m_stats[i].vals.begin(); + valIt != d->m_stats[i].vals.end(); ++valIt) + { + if (valIt->second < 0) valIt->second = 0; + valSum += valIt->second; + } + // Scale down values if their sum is bigger than 1 + // because of rounding errors or a corrupted config file + if (valSum > 1) + { + for (valIt = d->m_stats[i].vals.begin(); + valIt != d->m_stats[i].vals.end(); ++valIt) + { + valIt->second = valIt->second / valSum; + } + } + d->m_stats[i].iniVal = 1-valSum; + } + d->updateServiceRanks(); +} + +void PopularityStatistics::setHistoryHorizon(double h) +{ + d->m_historyHorizon = std::max(std::min(h, 1.0), 0.0); + d->updateServiceRanks(); +} + +double PopularityStatistics::historyHorizon() +{ + return d->m_historyHorizon; +} + + +// ---- Implementation methods ---- + +PopularityStatisticsImpl::PopularityStatisticsImpl() +{ + const int rateBaseCount(8); + + m_historyHorizon = 0.0; + + for (int n=0; n<rateBaseCount; ++n) + { + SingleFalloffHistory h; + h.falloff = 1.0 - (0.5 / std::exp(double(n)*1.5)); + m_stats.push_back(h); + } +} + +void PopularityStatisticsImpl::normalizeHistory(SingleFalloffHistory& h) +{ + //kdDebug() << "Normalize history" << endl; + double sum = h.iniVal; + map<QString, double>::iterator it; + for (it = h.vals.begin(); it != h.vals.end(); ++it) + { + sum += it->second; + } + for (it = h.vals.begin(); it != h.vals.end(); ++it) + { + it->second = it->second / sum; + } + h.iniVal = h.iniVal / sum; +} + +void PopularityStatisticsImpl::updateServiceRanks() +{ + // For each service calculate the average over the popularity + // for all falloff values and then sort by these averaged values + + vector<SingleFalloffHistory>::iterator + it(m_stats.begin()), end(m_stats.end()); + map<QString, double> serviceValSum, serviceValWeightSum; + int numStats = m_stats.size(); + for (int statIndex = 0; it != end; ++it, ++statIndex) + { + // Put more weight on the short term history if m_historyHorizon==0 + // and more on the the long term history for m_historyHorizon==1 + double a = 2*(numStats-1)*m_historyHorizon - numStats + 0.5; + if (statIndex < a || statIndex > a + numStats) + { + continue; + } + + map<QString, double>::iterator valIt; + /*double valSum = 0; + for (valIt = it->vals.begin(); valIt != it->vals.end(); ++valIt) + { + valSum += valIt->second; + } + if (valSum == 0) valSum = 1;*/ + for (valIt = it->vals.begin(); valIt != it->vals.end(); ++valIt) + { + serviceValWeightSum[valIt->first] += 1; + serviceValSum[valIt->first] += valIt->second; + } + } + + m_servicesByPopularity.clear(); + map<QString, double>::iterator sIt; + for (sIt = serviceValWeightSum.begin(); + sIt != serviceValWeightSum.end(); ++sIt) + { + Popularity p; + p.service = sIt->first; + assert(sIt->second > 0); + p.popularity = serviceValSum[sIt->first] / sIt->second; + m_servicesByPopularity.push_back(p); + } + stable_sort(m_servicesByPopularity.begin(), m_servicesByPopularity.end()); + m_serviceRanks.clear(); + for (uint n = 0; n < m_servicesByPopularity.size(); ++n) + { + m_serviceRanks[m_servicesByPopularity[n].service] = n; + /*kdDebug() << QString("Rank %1: %2 %3").arg(n) + .arg(m_servicesByPopularity[n].popularity) + .arg(m_servicesByPopularity[n].service) << endl;*/ + } +} |