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

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.stream.Collectors;

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.
 * <h2>Rounding</h2> 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 List<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 Map<Tuple<Integer, Interval>, ImmutableList<Bid>> cache = new HashMap<>();
        private ImmutableList<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(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.
         *                  <p>
         *                  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.
         *                  <p>
         *                  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<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 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<Bid> getBids(Interval range) {
                return get(issueInfo.size() - 1, range.round(precision));
        }

        public List<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 Bid getExtremeBid(boolean isMax) {
                Map<String, Value> 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.
         * <h2>Memory use</h2> 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:
         * <table border="1">
         * <tr>
         * <td>domain</td>
         * <td>mem use (MB) of returned object</td>
         * <td>nr. of selected bids</td>
         * </tr>
         * <tr>
         * <td>jobs1</td>
         * <td>0.028</td>
         * <td>23</td>
         * </tr>
         * <tr>
         * <td>7issues1</td>
         * <td>34</td>
         * <td>346327</td>
         * </tr>
         * <tr>
         * <td>9issues1</td>
         * <td>98</td>
         * <td>37160666</td>
         * </tr>
         * </table>
         * 
         * @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<Bid> 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<Integer, Interval> cachetuple = new Tuple<>(n, goal);
                ImmutableList<Bid> cached = cache.get(cachetuple);
                if (cached != null) {
                        // hits++;
                        return cached;
                }

                ImmutableList<Bid> result = checkedGet(n, goal);
                cache.put(cachetuple, result);
                return result;
        }

        private static List<IssueInfo> getInfo(LinearAdditive space2,
                        int precision) {
                Domain dom = space2.getDomain();
                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<Bid> 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<Bid> 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<Bid> partialbids = get(n - 1, subgoal);

                        ImmutableList<Bid> fullbids = new MapList<Bid, Bid>(
                                        pbid -> pbid.merge(new Bid(issue, val)), partialbids);
                        if (!fullbids.size().equals(BigInteger.ZERO))
                                fulllist = new JoinedList<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 Interval getRange(int n) {
                Interval value = Interval.ZERO;
                for (int i = 0; i <= n; i++) {
                        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<Bid> {
        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;
        }

}