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(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(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.
* @param precision the number of digits used in Intervals.
*/
public BidsWithUtility(List 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 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 ImmutableList getBids(Interval range) {
return get(issueInfo.size() - 1, range.round(precision));
}
public List 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 Bid getExtremeBid(boolean isMax) {
Map map = new HashMap<>();
for (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.
*/
protected ImmutableList get(int n, 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<>();
}
Tuple cachetuple = new Tuple<>(n, goal);
ImmutableList cached = cache.get(cachetuple);
if (cached != null) {
// hits++;
return cached;
}
ImmutableList result = checkedGet(n, goal);
cache.put(cachetuple, result);
return result;
}
private static List getInfo(LinearAdditive space2,
int precision) {
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().getIssues().stream()
.map(issue -> new IssueInfo(issue, dom.getValues(issue),
space2.getUtilities().get(issue),
space2.getWeight(issue), precision))
.collect(Collectors.toList());
}
private ImmutableList checkedGet(int n, Interval goal) {
IssueInfo info = issueInfo.get(n);
// issue is the first issuesWithRange.
String issue = info.getName();
if (n == 0)
return new OneIssueSubset(info, goal);
// make new list, joining all sub-lists
ImmutableList fulllist = emptylist;
for (Value val : info.getValues()) {
BigDecimal weightedutil = info.getWeightedUtil(val);
Interval subgoal = goal.subtract(weightedutil);
// recurse: get list of bids for the subspace
ImmutableList partialbids = get(n - 1, subgoal);
ImmutableList fullbids = new MapList(
(Function) pbid -> pbid
.merge(new Bid(issue, val)),
partialbids);
if (!fullbids.size().equals(BigInteger.ZERO))
fulllist = new JoinedList(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 Interval getRange(int n) {
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 {
private final IssueInfo info;
private final Interval interval;
private BigInteger size;
/**
*
* @param info the {@link IssueInfo}
* @param interval a utility interval (weighted)
*/
OneIssueSubset(IssueInfo info, Interval interval) {
this.info = info;
this.interval = interval;
this.size = BigInteger.valueOf(info.subsetSize(interval));
}
@Override
public Bid get(BigInteger index) {
return new Bid(info.getName(),
info.subset(interval).get(index.intValue()));
}
@Override
public BigInteger size() {
return size;
}
}