package geniusweb.bidspace;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
import org.eclipse.jdt.annotation.NonNull;
import geniusweb.issuevalue.Bid;
import geniusweb.issuevalue.Domain;
import geniusweb.issuevalue.Value;
import geniusweb.profile.utilityspace.LinearAdditive;
import tudelft.utilities.immutablelist.AbstractImmutableList;
import tudelft.utilities.immutablelist.FixedList;
import tudelft.utilities.immutablelist.ImmutableList;
import tudelft.utilities.immutablelist.JoinedList;
import tudelft.utilities.immutablelist.MapList;
import tudelft.utilities.immutablelist.Tuple;
/**
* Tool class containing functions dealing with utilities of all bids in a given
* {@link LinearAdditive}. This class caches previously computed values to
* accelerate the calls and subsequent calls. Re-use the object to keep/reuse
* the cache.
* Rounding
Internally, utilities of bids are rounded to the given
* precision. This may cause inclusion/exclusion of some bids in the results.
* See {@link #BidsWithUtility(LinearAdditive, int)} for more details
*/
public class BidsWithUtility {
private final @NonNull List<@NonNull IssueInfo> issueInfo;
private final int precision; // #digits used for Intervals
/**
* cache. Key = call arguments for {@link #get(int, Interval)}. Value=return
* value of that call.
*/
private final @NonNull Map<@NonNull Tuple<@NonNull Integer, @NonNull Interval>, @NonNull ImmutableList<@NonNull Bid>> cache = new HashMap<>();
private final @NonNull ImmutableList<@NonNull Bid> emptylist = new FixedList<>();
/**
* Default constructor, uses default precision 6. This value seems practical
* for the common range of issues, utilities and weights. See
* {@link #BidsWithUtility(LinearAdditive, int)} for more details on the
* precision.
*
* @param space the {@link LinearAdditive} to analyze
*/
public BidsWithUtility(@NonNull LinearAdditive space) {
this(space, 6);
}
/**
*
* @param space the {@link LinearAdditive} to analyze
* @param precision the number of digits to use for computations. In
* practice, 6 seems a good default value.
*
* All utilities * weight are rounded to this number of
* digits. This value should match the max number of
* (digits used in the weight of an issue + number of
* digits used in the issue utility). To determine the
* optimal value, one may consider the step size of the
* issues, and the range of interest. For instance if the
* utility function has values 1/3 and 2/3, then these have
* an 'infinite' number of relevant digits. But if the goal
* is to search bids between utility 0.1 and 0.2, then
* computing in 2 digits might already be sufficient.
*
* This algorithm has memory and space complexity O(
* |nissues| 10^precision ). For spaces up to 7 issues, 7
* digits should be feasible; for 9 issues, 6 digits may be
* the maximum.
*/
public BidsWithUtility(@NonNull LinearAdditive space, int precision) {
this(getInfo(space, precision), precision);
}
/**
*
* @param issuesInfo List of the relevant issues (in order of relevance) and
* all info of each issue. Must not be empty.
* @param precision the number of digits used in Intervals.
*/
public BidsWithUtility(@NonNull List<@NonNull IssueInfo> issuesInfo,
int precision) {
if (issuesInfo == null || issuesInfo.isEmpty()) {
throw new IllegalArgumentException(
"sortedissues list must contain at least 1 element");
}
this.issueInfo = issuesInfo;
this.precision = precision;
}
/**
* @return the (rounded) utility {@link Interval} of this space: minimum and
* maximum achievable utility.
*/
public @NonNull Interval getRange() {
return getRange(issueInfo.size() - 1);
}
/**
*
* @param range the minimum and maximum utility required of the bids. to be
* included (both ends inclusive).
* @return a list with bids that have a (rounded) utility inside range.
* possibly empty.
*/
public @NonNull ImmutableList<@NonNull Bid> getBids(
@NonNull Interval range) {
return get(issueInfo.size() - 1, range.round(precision));
}
public @NonNull List<@NonNull IssueInfo> getInfo() {
return Collections.unmodifiableList(issueInfo);
}
/**
*
* @param isMax the extreme bid required
* @return the extreme bid, either the minimum if isMax=false or maximum if
* isMax=true
*/
public @NonNull Bid getExtremeBid(boolean isMax) {
final @NonNull Map<@NonNull String, @NonNull Value> map = new HashMap<>();
for (final @NonNull IssueInfo info : issueInfo) {
map.put(info.getName(), info.getExtreme(isMax));
}
return new Bid(map);
}
/**
* Create partial BidsWithUtil list considering only issues 0..n, with
* utilities in given range.
*
Memory use
Memory use of the return value can be large, if large
* domains are given and the requested interval contains large numbers of
* bids. To give some idea, here are some typical memory uses:
*
*
* | domain |
* mem use (MB) of returned object |
* nr. of selected bids |
*
*
* | jobs1 |
* 0.028 |
* 23 |
*
*
* | 7issues1 |
* 34 |
* 346327 |
*
*
* | 9issues1 |
* 98 |
* 37160666 |
*
*
*
* @param n the number of issueRanges to consider, we consider 0..n here.
* The recursion decreases n until n=0
* @param goal the minimum and maximum utility required of the bids. to be
* included (both ends inclusive)
* @return BidsWithUtil list, possibly empty.
*/
@SuppressWarnings("unused")
protected @NonNull ImmutableList<@NonNull Bid> get(int n,
@NonNull Interval goal) {
if (goal == null) {
throw new NullPointerException("Interval=null");
}
// clamp goal into what is reachable. Avoid caching empty
goal = goal.intersect(getRange(n));
if (goal.isEmpty()) {
return new FixedList<>();
}
final @NonNull Tuple<@NonNull Integer, @NonNull Interval> cachetuple = new Tuple<>(
n, goal);
final ImmutableList<@NonNull Bid> cached = cache.get(cachetuple);
if (cached != null) {
// hits++;
return cached;
}
final @NonNull ImmutableList<@NonNull Bid> result = checkedGet(n, goal);
cache.put(cachetuple, result);
return result;
}
private static @NonNull List<@NonNull IssueInfo> getInfo(
@NonNull LinearAdditive space2, int precision) {
final @NonNull Domain dom = space2.getDomain();
/*#PY
* return [ IssueInfo(issue, dom.getValues(issue),
* space2.getUtilities().get(issue),
* space2.getWeight(issue), precision))
* for issue in space2.getDomain().getIssues() ]
*/
return space2.getDomain().getIssuesValues().stream()
.map(issue -> new IssueInfo(issue, dom.getValues(issue),
space2.getUtilities().get(issue),
space2.getWeight(issue), precision))
.collect(Collectors.toList());
}
private @NonNull ImmutableList<@NonNull Bid> checkedGet(int n,
final @NonNull Interval goal) {
final @NonNull IssueInfo info = issueInfo.get(n);
// issue is the first issuesWithRange.
final @NonNull String issue = info.getName();
if (n == 0)
return new OneIssueSubset(info, goal);
// make new list, joining all sub-lists
@NonNull
ImmutableList<@NonNull Bid> fulllist = emptylist;
for (@NonNull
Value val : info.getValues()) {
BigDecimal weightedutil = info.getWeightedUtil(val);
@NonNull
Interval subgoal = goal.subtract(weightedutil);
// recurse: get list of bids for the subspace
@NonNull
ImmutableList<@NonNull Bid> partialbids = get(n - 1, subgoal);
ImmutableList<@NonNull Bid> fullbids = new MapList<@NonNull Bid, @NonNull Bid>(
(Function<@NonNull Bid, @NonNull Bid>) pbid -> pbid
.merge(new Bid(issue, val)),
partialbids);
if (!fullbids.size().equals(BigInteger.ZERO))
fulllist = new JoinedList<@NonNull Bid>(fullbids, fulllist);
}
return fulllist;
}
/**
* @param n the maximum issuevalue utility to include. Use n=index of last
* issue s= (#issues in the domain - 1) for the full range of this
* domain.
* @return Interval (min, max) of the total weighted utility Interval of
* issues 0..n. All weighted utilities have been rounded to the set
* {@link #precision}
*/
private @NonNull Interval getRange(int n) {
@NonNull
Interval value = Interval.ZERO;
for (int i = 0; i <= n; i = i + 1) {
value = value.add(issueInfo.get(i).getInterval());
}
return value;
}
}
/**
* List of all one-issue bids that have utility inside given interval.
*/
class OneIssueSubset extends AbstractImmutableList<@NonNull Bid> {
private final @NonNull IssueInfo info;
private final @NonNull Interval interval;
private @NonNull BigInteger size;
/**
*
* @param info the {@link IssueInfo}
* @param interval a utility interval (weighted)
*/
OneIssueSubset(@NonNull IssueInfo info, @NonNull Interval interval) {
this.info = info;
this.interval = interval;
this.size = BigInteger.valueOf(info.subsetSize(interval));
}
@Override
public @NonNull Bid get(@NonNull BigInteger index) {
return new Bid(info.getName(),
info.subset(interval).get(index.intValue()));
}
@Override
public @NonNull BigInteger size() {
return size;
}
}