source: bidspace/src/main/java/geniusweb/bidspace/PartialSpaceFromUtility.java@ 52

package geniusweb.bidspace;

import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import geniusweb.issuevalue.Bid;
import geniusweb.profile.DefaultPartialOrdering;
import geniusweb.profile.PartialOrdering;
import geniusweb.profile.utilityspace.UtilitySpace;
import tudelft.utilities.immutablelist.ListWithRemove;
import tudelft.utilities.immutablelist.Tuple;
import tudelft.utilities.immutablelist.Tuples;

/**
 * Simple demo converting a {@link UtilitySpace} into a {@link PartialOrdering}.
 * Notice, a UtilitySpace IS a PartialOrdering, but a special one that is in
 * fact a full ordering. This converter makes it a space that really has all
 * info removed except for a few basic "isBetter" informations.
 */
public class PartialSpaceFromUtility extends DefaultPartialOrdering {
        public PartialSpaceFromUtility(UtilitySpace space, int nRankings) {
                super(space.getName() + "_" + nRankings, space.getDomain(), space.getReservationBid(),
                                pickBetter(space, nRankings));
        }

        /**
         * Pick subset of static isbetter rankings. Notice, ShuffledList currently can't
         * handle really large lists which also limits this. This has to be fixed.
         * 
         * @param space     the space to sample from
         * @param nRankings the number of rankings to be placed in the PartialOrdering.
         * @return a subset creating a partial profile of the geiven UtilitySpace
         */
        private static Map<Bid, Set<Bid>> pickBetter(UtilitySpace space, int nRankings) {
                Map<Bid, Set<Bid>> eqOrBetter = new HashMap<>();

                AllBidsList allbids = new AllBidsList(space.getDomain());
                ListWithRemove<Tuple<Bid, Bid>> available = new ListWithRemove<>(new Tuples<Bid, Bid>(allbids, allbids));
                for (int n = 0; n < nRankings; n++) {
                        BigInteger sel = rnd(available.size());
                        Tuple<Bid, Bid> tuple = available.get(sel);
                        Bid bid1 = tuple.get1();
                        Bid bid2 = tuple.get2();
                        switch (space.getUtility(bid1).compareTo(space.getUtility(bid2))) {
                        case -1: // bid1 is worse
                                add(eqOrBetter, bid2, bid1);
                                break;
                        case 0:
                                add(eqOrBetter, bid2, bid1);
                                add(eqOrBetter, bid1, bid2);
                                break;
                        case 1:// bid1 is better
                                add(eqOrBetter, bid1, bid2);
                                break;
                        }
                        available = available.remove(sel);
                }
                return eqOrBetter;
        }

        /**
         * 
         * @param eqOrBetter map to be extended with (key=bid1, value=bid2)
         * @param bid1       the key to add a value to
         * @param bid2       the value to be added
         */
        private static void add(Map<Bid, Set<Bid>> eqOrBetter, Bid bid1, Bid bid2) {
                Set<Bid> set = eqOrBetter.get(bid1);
                if (set == null) {
                        set = new HashSet<Bid>();
                }
                set.add(bid2);
                eqOrBetter.put(bid1, set);
        }

        /**
         * Bit simplistic way to generate random in [0,n>. Simplistic because the mod()
         * operator that we use causes bias in the random numbers.
         * 
         * @param n the maximum value for the random number
         * @return random in [0,n>
         * 
         */
        private static final BigInteger rnd(BigInteger n) {
                return new BigInteger(n.bitLength(), new SecureRandom()).mod(n);
        }
}