# a4_2017sp_soln.py
# SOLUTION by Lillian Lee (LJL2)
# April 2017


class Outcome(object):
    """An instance is an outcome in a tournament tree.

    Attributes:
    winner [nonempty str]: name of the winner in this Outcome
        Must be the same as the name of *exactly one* of attributes input1 or
            input2, defined next.

    input1 [Outcome or nonempty string]:
        If a nonempty string, the name of a competitor in the tournament, and
            we say that the name of input1 is that string.
        If an Outcome, then the name of input1 is its winner attribute.

    input2 [Outcome or nonempty string]:
        If a nonempty string, the name of a competitor in the tournament, and
            we say that the name of input2 is that string
        If an Outcome, then the name of input2 is its winner attribute.

    Note that the constraints (invariants) on winner imply that the names of
        input1 and input2 must be different.
    """

    def __init__(self, in1, in2, one_won=True):
        """Makes an Outcome have input1 set to in1, input2 set to in2, and winner
        set as follows:
            If one_won is True or not given, winner is in1's winner (if in1 is
                an Outcome) or in1 itself (if in1 is a string)
            Otherwise, winner is set to in2's winner (if in2 is an Outcome) or
                in2 itself (if in2 is a string)

            We choose the default value of one_won as True because tournaments
                are often set up so that input1 is the competitor favored to win.

        Preconditions:
            in1 is either a nonempty string or an Outcome
            in2 is either a nonempty string or an Outcome.
            name1 is different from name2, where:
              if in1 is an Outcome, name1 is in1's winner, otherwise name1 is in1
              if in2 is an Outcome, name2 is in2's winner, otherwise name2 is in2
            one_won is a boolean."""
        self.input1 = in1
        self.input2 = in2
        if one_won:
            self.winner = _extract_name(in1)
        else:
            self.winner = _extract_name(in2)

    def __str__(self):
        """String representation of this Outcome"""

        output = self.winner + "\n"

        output += "\t"  # start indenting for the sub-Outcomes
        s1 = str(self.input1)  # A recursive call
        # Inspiration for using splitlines with True, which preserves newlines
        #  at line ends:
        # http://stackoverflow.com/questions/18389454/add-some-characters-at-the-beginning-of-each-line
        s1_lines = s1.splitlines(True)
        #
        # The join in the next line of code indents the 2nd through the last
        # line of s1, since it puts tabs "between" all the lines in the
        # split-line version.
        output += "\t".join(s1_lines)
        #
        if isinstance(self.input1, str):
            output += "\n"

        # More compact version of above recursion except on self.input2
        output += "\t" + "\t".join(str(self.input2).splitlines(True))
        if isinstance(self.input2, str):
            output += "\n"

        return output

    def teams(self):
        """Returns: alphabetized list of names of teams participating in this Outcome
        or any of its sub-Outcomes or any of their sub-Outcomes, and so on.
        No team should be included more than once."""
        output = []

        if isinstance(self.input1, str):
            output = [self.input1]
        else:
            output.extend(self.input1.teams())

        if isinstance(self.input2, str):
            output.append(self.input2)
        else:
            output.extend(self.input2.teams())

        output = list(set(output))  # remove duplicates
        return sorted(output)

    def pathToVictory(self):
        """Returns: list of teams that the winner of this Outcome defeated in
        this Outcome and all of its sub-Outcomes, sorted in order of earliest
        opponents first."""

        # Determine which sub-Outcome this Outcome's winner comes from, and
        # the name of the loser for the top-level game. This loser must be the
        # last item in our eventual output list.
        name1 = _extract_name(self.input1)
        if self.winner == name1:
            sub = self.input1
            loser = _extract_name(self.input2)
        else:
            sub = self.input2
            loser = name1

        if isinstance(sub, str):
            return [loser]
        else:
            outputlist = sub.pathToVictory()
            outputlist.append(loser)
            return outputlist

    def hasHeadToHead(self, c1, c2):
        """Returns True if anywhere in the tournament tree represented by this
        Outcome there is an Outcome oc where the name of one of oc's inputs
        is c1 and the name of the other of oc's inputs is c2.
        Returns False otherwise, including if c1 and c2 are not in self.teams()

        Precondition: c1 and c2 are different non-empty strings."""
        # base case
        if not (c1 in self.teams() and c2 in self.teams()):
            return False

        # base case
        self_names = [_extract_name(self.input1), _extract_name(self.input2)]
        if c1 in self_names and c2 in self_names:
            # This Outcome is a head-to-head matchup of c1 against c2
            return True

        if isinstance(self.input1, Outcome) and isinstance(self.input2, Outcome):
            return self.input1.hasHeadToHead(c1, c2) or \
                   self.input2.hasHeadToHead(c1, c2)
        elif isinstance(self.input1, Outcome):
            return self.input1.hasHeadToHead(c1, c2)
        else:
            return self.input2.hasHeadToHead(c1, c2)


## NON-METHOD FUNCTIONS GO BELOW THIS LINE

def _extract_name(x):
    """Returns: string that is the "name" of x, defined as follows:
    If x is an Outcome, then the name is x's winner.
    If x is a string, then the name of x is x itself.

    Precondition: x is either a non-empty string or an Outcome."""
    if isinstance(x, Outcome):
        return x.winner
    else:
        # x must be a string, by precondition
        assert isinstance(x, str), "_extract_name: bad input x: " + str(x)
        return x