source: src/main/java/bargainingchips/analysis/ParetoFrontier.java@ 343

/**
 * 
 */
package bargainingchips.analysis;

import java.util.List;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import java.io.Serializable;

/**
 * 
 * This class is for storing Pareto-frontier by adding bundles at analysis time.
 * It adapts {@link genius.core.analysis.ParetoFrontier}.  
 *
 */

public class ParetoFrontier implements Serializable {

        /**
         * 
         */
        private static final long serialVersionUID = 1L;
        /** List holding the Pareto-frontier bids. */
        private List<BundleUtilityPoint> frontier;

        /**
         * Create an empty list to store the Pareto-frontier.
         */
        public ParetoFrontier() {
                frontier = new ArrayList<BundleUtilityPoint>();
        }

        /**
         * Determines if a bid should be added to the Pareto-frontier. A bid is
         * added when it strictly dominates a bid in the Pareto-frontier OR when it
         * is equal to a bid in the Pareto-frontier.
         * 
         * @param bidpoint
         *            bid to be added to the Pareto-frontier.
         */
        public void mergeIntoFrontier(BundleUtilityPoint bundleutilitypoint) {
                for (BundleUtilityPoint f : frontier) {
                        if (bundleutilitypoint.isStrictlyDominatedBy(f)) {
                                // the bundleutilitypoint is dominated, and therefore not added
                                return;
                        }
                        if (f.isStrictlyDominatedBy(bundleutilitypoint)) {
                                // the bundleutilitypoint dominates a Pareto-bid, which is therefore
                                // replaced
                                merge(bundleutilitypoint, f);
                                return;
                        }
                }
                // the bid must be equal to an existing bid, therefore add it
                frontier.add(bundleutilitypoint);
        }

        /**
         * Adds a bid to the Pareto frontier
         * 
         * @param newParetoBid
         *            new Pareto bid.
         * @param dominatedParetoBid
         *            old Pareto bid which must now be removed.
         */
        private void merge(BundleUtilityPoint newParetoBid, BundleUtilityPoint dominatedParetoBid) {
                // remove dominated bid.
                frontier.remove(dominatedParetoBid);
                // there might still be more bids which should be removed.
                ArrayList<BundleUtilityPoint> toBeRemoved = new ArrayList<BundleUtilityPoint>();
                for (BundleUtilityPoint f : frontier) {
                        if (f.isStrictlyDominatedBy(newParetoBid)) // delete dominated
                                                                                                                // frontier points
                                toBeRemoved.add(f);
                }
                frontier.removeAll(toBeRemoved);
                frontier.add(newParetoBid);
        }

        /**
         * Returns true if the given BundleUtilityPoint is not part of the Pareto-frontier.
         * 
         * @param bid
         *            to be checked if it is Pareto-optimal.
         * @return true if NOT pareto-optimal bid.
         */
        public boolean isBelowFrontier(BundleUtilityPoint bid) {
                for (BundleUtilityPoint f : this.getFrontier())
                        if (bid.isStrictlyDominatedBy(f))
                                return true;
                return false;
        }

        /**
         * Order the bids based on the utility for agent A.
         */
        public void sort() {
                Collections.sort(frontier, new Comparator<BundleUtilityPoint>() {
                        @Override
                        public int compare(BundleUtilityPoint x, BundleUtilityPoint y) {
                                if (x.getUtilityA() < y.getUtilityA())
                                        return -1;
                                else if (x.getUtilityA() > y.getUtilityA())
                                        return 1;
                                else
                                        return 0;
                        }
                });
        }

        /**
         * Returns the Pareto-optimal frontier.
         * 
         * @return Pareto-optimal frontier.
         */
        public List<BundleUtilityPoint> getFrontier() {
                return frontier;
        }
}