source: java2python/geniuswebtranslator/geniuswebsrc/geniusweb/bidspace/pareto/PartialPareto.java@ 868

package geniusweb.bidspace.pareto;

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

import org.eclipse.jdt.annotation.NonNull;

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 @NonNull List<@NonNull ParetoPoint> points = new ArrayList<>();;

        /**
         * @param points the points to be contained in this PartialPareto
         */
        private PartialPareto(@NonNull List<@NonNull ParetoPoint> points) {
                if (points == null || points.contains(null))
                        throw new NullPointerException("points must not contain null");
                this.points.addAll(points);
        }

        @NonNull
        /**
         * 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(
                        @NonNull List<@NonNull LinearAdditive> utilSpaces,
                        @NonNull List<@NonNull String> issues) {
                if (issues.size() == 1) {
                        @NonNull
                        String issue = issues.get(0);
                        @NonNull
                        Map<@NonNull String, @NonNull Value> map = new HashMap<>();
                        @NonNull
                        List<@NonNull ParetoPoint> list = new LinkedList<>();
                        for (@NonNull
                        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())));
                }
        }

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

        @NonNull
        /**
         * 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(@NonNull PartialPareto other) {
                @NonNull
                List<@NonNull ParetoPoint> merge = new LinkedList<>();// fast add and iterate
                for (@NonNull
                ParetoPoint point : points) {
                        for (@NonNull
                        ParetoPoint otherpoint : other.points) {
                                merge = add(merge, point.merge(otherpoint));
                        }
                }
                return new PartialPareto(merge);
        }

        @NonNull
        /**
         * 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<@NonNull ParetoPoint> add(
                        @NonNull List<@NonNull ParetoPoint> list,
                        @NonNull ParetoPoint candidate) {
                for (@NonNull
                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
                @NonNull
                List<@NonNull ParetoPoint> newlist = new LinkedList<ParetoPoint>();
                newlist.add(candidate);
                for (@NonNull
                ParetoPoint existing : list) {
                        if (!existing.isDominatedBy(candidate)) {
                                newlist.add(existing);
                        }
                }
                return newlist;
        }

}