source: geniuswebcore/geniusweb/bidspace/pareto/PartialPareto.py@ 93

from typing import List, Dict

from geniusweb.bidspace.pareto.ParetoPoint import ParetoPoint
from geniusweb.issuevalue.Bid import Bid
from geniusweb.issuevalue.Value import Value
from geniusweb.profile.utilityspace.LinearAdditive import LinearAdditive


class PartialPareto:
        '''
         PartialPareto contains a pareto surface of partial bids. Internal-only
         utility class for computing LinearAdditive pareto surface. Immutable.
        '''

        def __init__(self, points:List[ParetoPoint]):
                '''
                @param points the points to be contained in this PartialPareto
'''
                self._points = points

        @staticmethod
        def create(utilSpaces:List[LinearAdditive] ,
                        issues: List[str]) -> "PartialPareto":
                '''
                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.
                '''

                if len(issues) == 1:
                        issue = issues[0]
                        map:Dict[str, Value] = {}
                        list:List[ParetoPoint] = []
                        for value in utilSpaces[0].getDomain().getValues(issue):
                                map[issue] = value
                                list = PartialPareto._add(list, ParetoPoint.create(Bid(map), utilSpaces))
                        return PartialPareto(list)
                else:
                        halfway = int(len(issues) / 2)
                        return PartialPareto.create(utilSpaces, issues[0: halfway])._merge(
                                        PartialPareto.create(utilSpaces, issues[halfway:]))

        def getPoints(self) -> List[ParetoPoint]:
                '''
                @return the ParetoPoints on the (possibly partial) Pareto surface
                '''
                return self._points

        def _merge(self, other:"PartialPareto") -> "PartialPareto":
                '''
                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.
                '''
                merge:List[ParetoPoint] = []
                for point in  self._points:
                        for otherpoint in other._points:
                                merge = PartialPareto._add(merge, point.merge(otherpoint))
                return PartialPareto(merge)

        @staticmethod
        def _add(list:List[ParetoPoint], candidate:ParetoPoint) -> List[ParetoPoint]:
                '''
                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
                '''
                for existing in 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
                newlist:List[ParetoPoint] = []
                newlist.append(candidate)
                for existing in list:
                        if not existing.isDominatedBy(candidate):
                                newlist.append(existing)
                return newlist