source: java2python/geniuswebtranslator/geniuswebsrc/geniusweb/bidspace/BidsWithUtility.java@ 814

Last change on this file since 814 was 814, checked in by wouter, 6 months ago

#278 more NonNull annotations
File size: 9.7 KB
Line 
1package geniusweb.bidspace;
2
3import java.math.BigDecimal;
4import java.math.BigInteger;
5import java.util.Collections;
6import java.util.HashMap;
7import java.util.List;
8import java.util.Map;
9import java.util.function.Function;
10import java.util.stream.Collectors;
11
12import org.eclipse.jdt.annotation.NonNull;
13
14import geniusweb.issuevalue.Bid;
15import geniusweb.issuevalue.Domain;
16import geniusweb.issuevalue.Value;
17import geniusweb.profile.utilityspace.LinearAdditive;
18import tudelft.utilities.immutablelist.AbstractImmutableList;
19import tudelft.utilities.immutablelist.FixedList;
20import tudelft.utilities.immutablelist.ImmutableList;
21import tudelft.utilities.immutablelist.JoinedList;
22import tudelft.utilities.immutablelist.MapList;
23import tudelft.utilities.immutablelist.Tuple;
24
25/**
26 * Tool class containing functions dealing with utilities of all bids in a given
27 * {@link LinearAdditive}. This class caches previously computed values to
28 * accelerate the calls and subsequent calls. Re-use the object to keep/reuse
29 * the cache.
30 * <h2>Rounding</h2> Internally, utilities of bids are rounded to the given
31 * precision. This may cause inclusion/exclusion of some bids in the results.
32 * See {@link #BidsWithUtility(LinearAdditive, int)} for more details
33 */
34public class BidsWithUtility {
35
36 private final @NonNull List<@NonNull IssueInfo> issueInfo;
37 private final int precision; // #digits used for Intervals
38
39 /**
40 * cache. Key = call arguments for {@link #get(int, Interval)}. Value=return
41 * value of that call.
42 */
43 private final @NonNull Map<@NonNull Tuple<@NonNull Integer, @NonNull Interval>, @NonNull ImmutableList<@NonNull Bid>> cache = new HashMap<>();
44 private final @NonNull ImmutableList<@NonNull Bid> emptylist = new FixedList<>();
45
46 /**
47 * Default constructor, uses default precision 6. This value seems practical
48 * for the common range of issues, utilities and weights. See
49 * {@link #BidsWithUtility(LinearAdditive, int)} for more details on the
50 * precision.
51 *
52 * @param space the {@link LinearAdditive} to analyze
53 */
54 public BidsWithUtility(@NonNull LinearAdditive space) {
55 this(space, 6);
56 }
57
58 /**
59 *
60 * @param space the {@link LinearAdditive} to analyze
61 * @param precision the number of digits to use for computations. In
62 * practice, 6 seems a good default value.
63 * <p>
64 * All utilities * weight are rounded to this number of
65 * digits. This value should match the max number of
66 * (digits used in the weight of an issue + number of
67 * digits used in the issue utility). To determine the
68 * optimal value, one may consider the step size of the
69 * issues, and the range of interest. For instance if the
70 * utility function has values 1/3 and 2/3, then these have
71 * an 'infinite' number of relevant digits. But if the goal
72 * is to search bids between utility 0.1 and 0.2, then
73 * computing in 2 digits might already be sufficient.
74 * <p>
75 * This algorithm has memory and space complexity O(
76 * |nissues| 10^precision ). For spaces up to 7 issues, 7
77 * digits should be feasible; for 9 issues, 6 digits may be
78 * the maximum.
79 */
80 public BidsWithUtility(@NonNull LinearAdditive space, int precision) {
81 this(getInfo(space, precision), precision);
82 }
83
84 /**
85 *
86 * @param issuesInfo List of the relevant issues (in order of relevance) and
87 * all info of each issue. Must not be empty.
88 * @param precision the number of digits used in Intervals.
89 */
90 public BidsWithUtility(@NonNull List<@NonNull IssueInfo> issuesInfo,
91 int precision) {
92 if (issuesInfo == null || issuesInfo.isEmpty()) {
93 throw new IllegalArgumentException(
94 "sortedissues list must contain at least 1 element");
95 }
96
97 this.issueInfo = issuesInfo;
98 this.precision = precision;
99
100 }
101
102 /**
103 * @return the (rounded) utility {@link Interval} of this space: minimum and
104 * maximum achievable utility.
105 */
106 public @NonNull Interval getRange() {
107 return getRange(issueInfo.size() - 1);
108 }
109
110 /**
111 *
112 * @param range the minimum and maximum utility required of the bids. to be
113 * included (both ends inclusive).
114 * @return a list with bids that have a (rounded) utility inside range.
115 * possibly empty.
116 */
117 public @NonNull ImmutableList<@NonNull Bid> getBids(
118 @NonNull Interval range) {
119 return get(issueInfo.size() - 1, range.round(precision));
120 }
121
122 public @NonNull List<@NonNull IssueInfo> getInfo() {
123 return Collections.unmodifiableList(issueInfo);
124 }
125
126 /**
127 *
128 * @param isMax the extreme bid required
129 * @return the extreme bid, either the minimum if isMax=false or maximum if
130 * isMax=true
131 */
132 public @NonNull Bid getExtremeBid(boolean isMax) {
133 final @NonNull Map<@NonNull String, @NonNull Value> map = new HashMap<>();
134 for (final @NonNull IssueInfo info : issueInfo) {
135 map.put(info.getName(), info.getExtreme(isMax));
136 }
137 return new Bid(map);
138 }
139
140 /**
141 * Create partial BidsWithUtil list considering only issues 0..n, with
142 * utilities in given range.
143 * <h2>Memory use</h2> Memory use of the return value can be large, if large
144 * domains are given and the requested interval contains large numbers of
145 * bids. To give some idea, here are some typical memory uses:
146 * <table border="1">
147 * <tr>
148 * <td>domain</td>
149 * <td>mem use (MB) of returned object</td>
150 * <td>nr. of selected bids</td>
151 * </tr>
152 * <tr>
153 * <td>jobs1</td>
154 * <td>0.028</td>
155 * <td>23</td>
156 * </tr>
157 * <tr>
158 * <td>7issues1</td>
159 * <td>34</td>
160 * <td>346327</td>
161 * </tr>
162 * <tr>
163 * <td>9issues1</td>
164 * <td>98</td>
165 * <td>37160666</td>
166 * </tr>
167 * </table>
168 *
169 * @param n the number of issueRanges to consider, we consider 0..n here.
170 * The recursion decreases n until n=0
171 * @param goal the minimum and maximum utility required of the bids. to be
172 * included (both ends inclusive)
173 * @return BidsWithUtil list, possibly empty.
174 */
175 @SuppressWarnings("unused")
176 protected @NonNull ImmutableList<@NonNull Bid> get(int n,
177 @NonNull Interval goal) {
178 if (goal == null) {
179 throw new NullPointerException("Interval=null");
180 }
181
182 // clamp goal into what is reachable. Avoid caching empty
183 goal = goal.intersect(getRange(n));
184 if (goal.isEmpty()) {
185 return new FixedList<>();
186 }
187
188 final @NonNull Tuple<@NonNull Integer, @NonNull Interval> cachetuple = new Tuple<>(
189 n, goal);
190 final ImmutableList<@NonNull Bid> cached = cache.get(cachetuple);
191 if (cached != null) {
192 // hits++;
193 return cached;
194 }
195
196 final @NonNull ImmutableList<@NonNull Bid> result = checkedGet(n, goal);
197 cache.put(cachetuple, result);
198 return result;
199 }
200
201 private static @NonNull List<@NonNull IssueInfo> getInfo(
202 @NonNull LinearAdditive space2, int precision) {
203 final @NonNull Domain dom = space2.getDomain();
204 /*#PY
205 * return [ IssueInfo(issue, dom.getValues(issue),
206 * space2.getUtilities().get(issue),
207 * space2.getWeight(issue), precision))
208 * for issue in space2.getDomain().getIssues() ]
209 */
210 return space2.getDomain().getIssuesValues().stream()
211 .map(issue -> new IssueInfo(issue, dom.getValues(issue),
212 space2.getUtilities().get(issue),
213 space2.getWeight(issue), precision))
214 .collect(Collectors.toList());
215 }
216
217 private @NonNull ImmutableList<@NonNull Bid> checkedGet(int n,
218 final @NonNull Interval goal) {
219 final @NonNull IssueInfo info = issueInfo.get(n);
220 // issue is the first issuesWithRange.
221 final @NonNull String issue = info.getName();
222
223 if (n == 0)
224 return new OneIssueSubset(info, goal);
225
226 // make new list, joining all sub-lists
227 @NonNull
228 ImmutableList<@NonNull Bid> fulllist = emptylist;
229 for (@NonNull
230 Value val : info.getValues()) {
231 BigDecimal weightedutil = info.getWeightedUtil(val);
232 @NonNull
233 Interval subgoal = goal.subtract(weightedutil);
234 // recurse: get list of bids for the subspace
235 @NonNull
236 ImmutableList<@NonNull Bid> partialbids = get(n - 1, subgoal);
237
238 ImmutableList<@NonNull Bid> fullbids = new MapList<@NonNull Bid, @NonNull Bid>(
239 (Function<@NonNull Bid, @NonNull Bid>) pbid -> pbid
240 .merge(new Bid(issue, val)),
241 partialbids);
242 if (!fullbids.size().equals(BigInteger.ZERO))
243 fulllist = new JoinedList<@NonNull Bid>(fullbids, fulllist);
244 }
245 return fulllist;
246 }
247
248 /**
249 * @param n the maximum issuevalue utility to include. Use n=index of last
250 * issue s= (#issues in the domain - 1) for the full range of this
251 * domain.
252 * @return Interval (min, max) of the total weighted utility Interval of
253 * issues 0..n. All weighted utilities have been rounded to the set
254 * {@link #precision}
255 */
256 private @NonNull Interval getRange(int n) {
257 @NonNull
258 Interval value = Interval.ZERO;
259 for (int i = 0; i <= n; i = i + 1) {
260 value = value.add(issueInfo.get(i).getInterval());
261 }
262 return value;
263 }
264
265}
266
267/**
268 * List of all one-issue bids that have utility inside given interval.
269 */
270class OneIssueSubset extends AbstractImmutableList<@NonNull Bid> {
271 private final @NonNull IssueInfo info;
272 private final @NonNull Interval interval;
273 private @NonNull BigInteger size;
274
275 /**
276 *
277 * @param info the {@link IssueInfo}
278 * @param interval a utility interval (weighted)
279 */
280 OneIssueSubset(@NonNull IssueInfo info, @NonNull Interval interval) {
281 this.info = info;
282 this.interval = interval;
283 this.size = BigInteger.valueOf(info.subsetSize(interval));
284 }
285
286 @Override
287 public @NonNull Bid get(@NonNull BigInteger index) {
288 return new Bid(info.getName(),
289 info.subset(interval).get(index.intValue()));
290 }
291
292 @Override
293 public @NonNull BigInteger size() {
294 return size;
295 }
296
297}
Note: See TracBrowser for help on using the repository browser.