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;
	}

}