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

package geniusweb.bidspace.pareto;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

import geniusweb.bidspace.AllBidsList;
import geniusweb.issuevalue.Bid;
import geniusweb.issuevalue.Domain;
import geniusweb.profile.PartialOrdering;
import geniusweb.profile.Profile;

/**
 * A set of all pareto points associated with a set of profiles. Generally
 * applicable but slow. It is recommended to use {@link ParetoLinearAdditive} if
 * applicable.
 */
public class GenericPareto implements ParetoFrontier {

        private final List<? extends PartialOrdering> profiles;
        private transient Set<Bid> paretobids = null; // cache

        /**
         * Constructs pareto from a general {@link PartialOrdering}. This is a
         * brute-force algorithm that will inspect (but not store) ALL bids in the
         * space, and therefore may be inapproproate depending on the size of your
         * domain. Complexity O( |bidspace|^2 |profiles| )
         * 
         * @param profiles a set of at least 2 {@link PartialOrdering}s. All must be
         *                 defined on the same domain.
         */
        public GenericPareto(List<? extends PartialOrdering> profiles) {
                if (profiles.size() < 2) {
                        throw new IllegalArgumentException(
                                        "at least 2 profiles are needed");
                }
                if (profiles.contains(null)) {
                        throw new IllegalArgumentException("Profiles must not be null");
                }
                Domain domain = profiles.get(0).getDomain();
                for (PartialOrdering profile : profiles) {
                        if (!domain.equals(profile.getDomain())) {
                                throw new IllegalArgumentException(
                                                "All profiles must be on same domain ("
                                                                + domain.getName() + ") but found " + profile);
                        }
                }
                this.profiles = new ArrayList<>(profiles);
        }

        @Override
        public List<Profile> getProfiles() {
                return Collections.unmodifiableList(profiles);
        }

        @Override
        public synchronized Set<Bid> getPoints() {
                if (paretobids == null)
                        computePareto();
                return Collections.unmodifiableSet(paretobids);
        }

        @Override
        public String toString() {
                return "Pareto " + getPoints();
        }

        /**
         * assigns {@link #paretobids}.
         */
        private void computePareto() {
                paretobids = new HashSet<Bid>();

                for (Bid newbid : new AllBidsList(profiles.get(0).getDomain())) {
                        /*
                         * invariant: paretobids contains bids not dominated by other bids
                         * in paretobids. That means we need (1) check if new bid is
                         * dominated (2) if existing bids are dominated if we add a new bid
                         */
                        boolean newBidIsDominated = paretobids.stream()
                                        .anyMatch(paretobid -> isDominatedBy(newbid, paretobid));

                        // if new bid is not dominated, we add it and we re-check existing
                        // if they are now dominated
                        if (!newBidIsDominated) {
                                paretobids = paretobids.stream()
                                                .filter(paretobid -> !isDominatedBy(paretobid, newbid))
                                                .collect(Collectors.toSet());
                                paretobids.add(newbid);
                        }
                }
        }

        /**
         * 
         * @param bid1        the bid to check
         * @param dominantbid the bid that is supposed to dominate bid1
         * @return true iff bid1 is dominated by dominant bid. "Dominated by" means
         *         that the bid is preferred or equal in all profiles.
         */
        private boolean isDominatedBy(Bid bid1, Bid dominantbid) {
                return profiles.stream().allMatch(
                                profile -> profile.isPreferredOrEqual(dominantbid, bid1));
        }
}