
package com.uwetrottmann.shopr.algorithm;

import com.uwetrottmann.shopr.algorithm.model.Item;

import java.util.ArrayList;
import java.util.List;

public class BoundedGreedySelection {

    public static final double ALPHA = 0.5;

    /**
     * Chooses <code>bound*limit</code> items most similar to current query.
     * Returns <code>limit</code> items most similar to query and most
     * dissimilar to already selected items out of those.
     */
    public static List<Item> boundedGreedySelection(Query query, List<Item> caseBase, int limit,
            int bound) {
        Utils.sortBySimilarityToQuery(query, caseBase);

        // TODO: get first b*k items

        List<Item> recommendations = new ArrayList<Item>();

        // add recommendations
        for (int i = 0; i < limit; i++) {
            sortByQuality(caseBase, recommendations, query);

            // get top item, remove it from remaining cases
            recommendations.add(caseBase.remove(0));
        }

        return recommendations;
    }

    /**
     * Calculates the quality for each item, sorts the case base with highest
     * quality first.
     */
    private static void sortByQuality(List<Item> caseBase, List<Item> recommendations, Query query) {
        // TODO Sort by quality
        for (Item item : caseBase) {
            double quality = ALPHA * item.querySimilarity()
                    + (1 - ALPHA) * relativeDiversity(item, recommendations);
        }
    }

    /**
     * Calculates the relative diversity of an item to the current list of
     * recommendations.
     */
    private static double relativeDiversity(Item item, List<Item> recommendations) {
        if (recommendations.size() == 0) {
            // default to 1 for R={}
            return 1;
        }

        double similarity = 0;
        for (Item recommendation : recommendations) {
            similarity += 1 - Similarity.similarity(item.attributes(), recommendation.attributes());
        }
        similarity /= recommendations.size();

        return similarity;
    }

}

@@ -139,52 +139,559 @@
 til.
-List;%0A%0Apublic class BoundedGreedySelection %7B
+Collections;%0Aimport java.util.Comparator;%0Aimport java.util.List;%0A%0Apublic class BoundedGreedySelection %7B%0A%0A    private static final class QualityComparator implements Comparator%3CItem%3E %7B%0A        @Override%0A        public int compare(Item o1, Item o2) %7B%0A            // is o2 smaller?%0A            if (o1.quality() %3E o2.quality()) %7B%0A                return -1;%0A            %7D%0A            // is o2 bigger?%0A            if (o1.quality() %3C o2.quality()) %7B%0A                return 1;%0A            %7D%0A            // they are equal!%0A            return 0;%0A        %7D%0A    %7D
 %0A%0A  
@@ -1764,20 +1764,25 @@
  // 
-TODO Sort by
+Calculate current
  qua
@@ -1839,25 +1839,21 @@
     
-double 
+item.
 quality
- = 
+(
 ALPH
@@ -1955,16 +1955,17 @@
 dations)
+)
 ;%0A      
@@ -1959,32 +1959,135 @@
 ons));%0A        %7D
+%0A%0A        // sort by highest quality first%0A        Collections.sort(caseBase, new QualityComparator());
 %0A    %7D%0A%0A    /**%0A

Implement sorting by quality.