# a4.py  --- solution version. 
# Prof. Lillian Lee (LJL2), Apr 2021

# STUDENTS: do not change the import statement(s) --- our grading framework
# is assuming the same form
import post as post_mod


def num_user_posts(post, u):
    """Returns: The number of Posts whose listed author is u, from among all 
    Posts "reachable" from `post` via `replies` attributes. 
    The "reachable" Posts are:
        * the Post `post` itself
        * the Posts in post.replies
        * the Posts in the replies list of the Posts in post.replies ... and so on.

    Precondition: 
        post: a Post object.
        u: a non-empty string (meant to be a username).
    """

    # STUDENTS: leave these assert statements here. They help prevent recursion
    #           errors where calls are given unexpected argument types.
    assert isinstance(post, post_mod.Post), _type_help("post", 1, "Post")+str(type(post))
    assert isinstance(u, str), _type_help("u", 2, "str")+str(type(u))
    assert len(u) > 0, "2nd argument violates preconditions: "

    # STUDENTS: Complete the implementation, making effective use of recursion.
    # BEGIN REMOVE
    num = 0 if post.author != u else 1
    for r in post.replies: # might not have any
        num += num_user_posts(r, u)
    return num
    # END REMOVE


def user_paths(post):
    """Returns: list of strings, one for each reply-path starting from `post` 
    and going all the way down to a leaf post (one with no replies to it).  
    Each string is a comma-separated sequence of authors along the path, in order.

    If `post` has no replies, the only string to be included is the one 
    containing only the author of `post`.

    Preconditions: `post` is a Post object.
    """

    # STUDENTS: leave these assert statements here. They help prevent recursion
    #           errors where calls are given unexpected argument types.
    assert isinstance(post, post_mod.Post), _type_help("post", 1, "Post")+str(type(post))

    # STUDENTS: Complete this implementation, making effective use of recursion.
    # BEGIN REMOVE
    if post.replies == []:
        return [post.author]
    else:
        out = []
        for r in post.replies: # there may not be any
            r_paths = user_paths(r)  # a list of strings
            for rp in r_paths:
                out.append(post.author + ", " + rp)
        return out
    # END REMOVE


def bnf_starts_here(post, u1, u2, k):
    """If, ignoring the parent of `post`, a back-and-forth of length k (and not 
    longer) between users u1 and u2 starts at Post `post`, 
    returns a list of Post objects in that back-and-forth, in top-down order.
    (If there is more than one such back-and-forth, this function returns one of
    them.)

    Otherwise, returns False.

    Preconditions:
        post: a Post object.
        u1 and u2: usernames: non-empty strings that are distinct.
        k: int >= 1."""

    # STUDENTS: leave these assert statements here. They help prevent recursion
    #           errors where calls are given unexpected argument types.
    assert isinstance(post, post_mod.Post), _type_help("post", 1, "Post")+str(type(post))
    assert isinstance(u1, str), _type_help("u1", 2, "str")+str(type(u1))
    assert isinstance(u2, str), _type_help("u2", 3, "str")+str(type(u2))
    assert isinstance(k, int), _type_help("k", 4, "int")+str(type(k))
    assert len(u1) > 0 and len(u2) > 0 and u1 != u2, \
        "u1 and/or u2 violate preconditions"
    assert k >= 1, "k violates preconditions"

    # STUDENTS: Complete this implementation, making effective use of recursion.
    # BEGIN REMOVE
    if post.author != u1:
        return False
    
    if k == 1:          # check for maximality. For-loop skipped if no replies.
        for r in post.replies:
            if r.author == u2:
                return False
        # if got here, no child had author a2
        return [post]

    # if here, k >= 2
    if post.replies == []:
        return False

    # Recursive call: 
    for r in post.replies:
        replyresult = bnf_starts_here(r, u2, u1, k-1)
        if type(replyresult) == list:
            return [post] + replyresult
    # if got here, no child had the back-and-forth continuation
    return False
    # END REMOVE


# Helper function for reporting type mismatches for arguments
def _type_help(parname, argpos, partype):
    """Returns 'Arg <argpos>, for parameter <parname>, should have type <partype>, 
       but has type '.

    Precondition: parname, partype should be strings. parpos should be an int.
    """

    out =  "Arg " + str(argpos) + ", for parameter" + parname + ", should have"
    out += " type " + partype + ", but has type "
    return out