[519] | 1 | package geniusweb.bidspace;
|
---|
| 2 |
|
---|
| 3 | import java.math.BigInteger;
|
---|
| 4 | import java.security.SecureRandom;
|
---|
| 5 | import java.util.HashMap;
|
---|
| 6 | import java.util.HashSet;
|
---|
| 7 | import java.util.Map;
|
---|
| 8 | import java.util.Set;
|
---|
| 9 |
|
---|
| 10 | import geniusweb.issuevalue.Bid;
|
---|
| 11 | import geniusweb.profile.DefaultPartialOrdering;
|
---|
| 12 | import geniusweb.profile.PartialOrdering;
|
---|
| 13 | import geniusweb.profile.utilityspace.UtilitySpace;
|
---|
| 14 | import tudelft.utilities.immutablelist.ListWithRemove;
|
---|
| 15 | import tudelft.utilities.immutablelist.Tuple;
|
---|
| 16 | import tudelft.utilities.immutablelist.Tuples;
|
---|
| 17 |
|
---|
| 18 | /**
|
---|
| 19 | * Simple demo converting a {@link UtilitySpace} into a {@link PartialOrdering}.
|
---|
| 20 | * Notice, a UtilitySpace IS a PartialOrdering, but a special one that is in
|
---|
| 21 | * fact a full ordering. This converter makes it a space that really has all
|
---|
| 22 | * info removed except for a few basic "isBetter" informations.
|
---|
| 23 | */
|
---|
| 24 | public class PartialSpaceFromUtility extends DefaultPartialOrdering {
|
---|
| 25 | public PartialSpaceFromUtility(UtilitySpace space, int nRankings) {
|
---|
| 26 | super(space.getName() + "_" + nRankings, space.getDomain(), space.getReservationBid(),
|
---|
| 27 | pickBetter(space, nRankings));
|
---|
| 28 | }
|
---|
| 29 |
|
---|
| 30 | /**
|
---|
| 31 | * Pick subset of static isbetter rankings. Notice, ShuffledList currently can't
|
---|
| 32 | * handle really large lists which also limits this. This has to be fixed.
|
---|
| 33 | *
|
---|
| 34 | * @param space the space to sample from
|
---|
| 35 | * @param nRankings the number of rankings to be placed in the PartialOrdering.
|
---|
| 36 | * @return a subset creating a partial profile of the geiven UtilitySpace
|
---|
| 37 | */
|
---|
| 38 | private static Map<Bid, Set<Bid>> pickBetter(UtilitySpace space, int nRankings) {
|
---|
| 39 | Map<Bid, Set<Bid>> eqOrBetter = new HashMap<>();
|
---|
| 40 |
|
---|
| 41 | AllBidsList allbids = new AllBidsList(space.getDomain());
|
---|
| 42 | ListWithRemove<Tuple<Bid, Bid>> available = new ListWithRemove<>(new Tuples<Bid, Bid>(allbids, allbids));
|
---|
| 43 | for (int n = 0; n < nRankings; n++) {
|
---|
| 44 | BigInteger sel = rnd(available.size());
|
---|
| 45 | Tuple<Bid, Bid> tuple = available.get(sel);
|
---|
| 46 | Bid bid1 = tuple.get1();
|
---|
| 47 | Bid bid2 = tuple.get2();
|
---|
| 48 | switch (space.getUtility(bid1).compareTo(space.getUtility(bid2))) {
|
---|
| 49 | case -1: // bid1 is worse
|
---|
| 50 | add(eqOrBetter, bid2, bid1);
|
---|
| 51 | break;
|
---|
| 52 | case 0:
|
---|
| 53 | add(eqOrBetter, bid2, bid1);
|
---|
| 54 | add(eqOrBetter, bid1, bid2);
|
---|
| 55 | break;
|
---|
| 56 | case 1:// bid1 is better
|
---|
| 57 | add(eqOrBetter, bid1, bid2);
|
---|
| 58 | break;
|
---|
| 59 | }
|
---|
| 60 | available = available.remove(sel);
|
---|
| 61 | }
|
---|
| 62 | return eqOrBetter;
|
---|
| 63 | }
|
---|
| 64 |
|
---|
| 65 | /**
|
---|
| 66 | *
|
---|
| 67 | * @param eqOrBetter map to be extended with (key=bid1, value=bid2)
|
---|
| 68 | * @param bid1 the key to add a value to
|
---|
| 69 | * @param bid2 the value to be added
|
---|
| 70 | */
|
---|
| 71 | private static void add(Map<Bid, Set<Bid>> eqOrBetter, Bid bid1, Bid bid2) {
|
---|
| 72 | Set<Bid> set = eqOrBetter.get(bid1);
|
---|
| 73 | if (set == null) {
|
---|
| 74 | set = new HashSet<Bid>();
|
---|
| 75 | }
|
---|
| 76 | set.add(bid2);
|
---|
| 77 | eqOrBetter.put(bid1, set);
|
---|
| 78 | }
|
---|
| 79 |
|
---|
| 80 | /**
|
---|
| 81 | * Bit simplistic way to generate random in [0,n>. Simplistic because the mod()
|
---|
| 82 | * operator that we use causes bias in the random numbers.
|
---|
| 83 | *
|
---|
| 84 | * @param n the maximum value for the random number
|
---|
| 85 | * @return random in [0,n>
|
---|
| 86 | *
|
---|
| 87 | */
|
---|
| 88 | private static final BigInteger rnd(BigInteger n) {
|
---|
| 89 | return new BigInteger(n.bitLength(), new SecureRandom()).mod(n);
|
---|
| 90 | }
|
---|
| 91 | }
|
---|