source: bidspace/src/main/java/geniusweb/bidspace/pareto/PartialPareto.java@ 52

package geniusweb.bidspace.pareto;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import geniusweb.issuevalue.Bid;
import geniusweb.issuevalue.Value;
import geniusweb.profile.utilityspace.LinearAdditive;

/**
 * PartialPareto contains a pareto surface of partial bids. Internal-only
 * utility class for computing LinearAdditive pareto surface. Immutable.
 */
class PartialPareto {
        private final List<ParetoPoint> points;

        /**
         * @param points the points to be contained in this PartialPareto
         */
        private PartialPareto(List<ParetoPoint> points) {
                this.points = points;
        }

        /**
         * Constructor. Avoided the standard 'new' constructor as this is
         * implemented recursively (O(log(#issues))).
         * 
         * @param utilSpaces the {@link LinearAdditive}s
         * @param issues     the issues (subset of all issues in the space) to be
         *                   used for this pareto
         * @return the pareto surface (non-dominated bids) when considering only the
         *         given issues.
         */
        public static PartialPareto create(List<LinearAdditive> utilSpaces,
                        List<String> issues) {

                if (issues.size() == 1) {
                        String issue = issues.get(0);
                        Map<String, Value> map = new HashMap<>();
                        List<ParetoPoint> list = new LinkedList<>();
                        for (Value value : utilSpaces.get(0).getDomain().getValues(issue)) {
                                map.put(issue, value);
                                list = add(list, new ParetoPoint(new Bid(map), utilSpaces));
                        }
                        return new PartialPareto(list);
                } else {
                        int halfway = issues.size() / 2;
                        return create(utilSpaces, issues.subList(0, halfway)).merge(
                                        create(utilSpaces, issues.subList(halfway, issues.size())));
                }
        }

        /**
         * 
         * @return the ParetoPoints on the (possibly partial) Pareto surface
         */
        public List<ParetoPoint> getPoints() {
                return points;
        }

        /**
         * This combines two partial paretos. Here is the heart of the algorithm.
         * 
         * @param other another {@link PartialPareto} to be merged with this. The
         *              other pareto must be composed with non-overlapping range.
         * @return merge of two partial paretos. Checks all partial1*partial2
         *         combinations and only non-dominated points are kept.
         */
        private PartialPareto merge(PartialPareto other) {
                List<ParetoPoint> merge = new LinkedList<>();// fast add and iterate
                for (ParetoPoint point : points) {
                        for (ParetoPoint otherpoint : other.points) {
                                merge = add(merge, point.merge(otherpoint));
                        }
                }
                return new PartialPareto(merge);
        }

        /**
         * Add a new ParetoPoint to a list
         * 
         * @param list      the existing list
         * @param candidate a new {@link ParetoPoint} candidate
         * @return a new list that either ignored the candidate, or added it and
         *         removed the old points that are dominated by the candidate
         */
        private static List<ParetoPoint> add(List<ParetoPoint> list,
                        ParetoPoint candidate) {
                for (ParetoPoint existing : list) {
                        if (candidate.isDominatedBy(existing)) {
                                return list;
                        }
                }
                // if we get here, candidate is not dominated so we add it
                // and remove existing ones now dominated
                List<ParetoPoint> newlist = new LinkedList<ParetoPoint>();
                newlist.add(candidate);
                for (ParetoPoint existing : list) {
                        if (!existing.isDominatedBy(candidate)) {
                                newlist.add(existing);
                        }
                }
                return newlist;
        }

}