# Your file header here!

import networkx as nx
# Your other import(s) here!

FACEBOOK_PATH = "facebook-links-small.txt"


def read_facebook(facebook: nx.Graph, filename: str) -> None:
    """
    Given a graph and file path, this function reads in
    the file path and adds every entry as an edge in the graph.
    """
    with open(filename) as f:
        for row in f:
            items = row.split()
            person1, person2 = items[0], items[1]
            facebook.add_edge(int(person1), int(person2))


def friends(graph: nx.Graph, user: int) -> set[int]:
    """
    Returns a set of the friends of the given user, in the given graph.
    """
    return set(graph.neighbors(user))


def friends_of_friends(graph: nx.Graph, user: int) -> set[int]:
    """
    Finds and returns a set of the friends of friends of the given user
    in the given graph
    """
    f_of_f = set()
    user_friends = friends(graph, user)
    for friend in user_friends:
        f_of_f = f_of_f | friends(graph, friend)
    return f_of_f - user_friends - set([user])


def common_friends(graph: nx.Graph, user1: int, user2: int) -> set[int]:
    # Add your code below. Feel free to keep or remove the scaffolding comments

    # 1. Use the friends function to get the set of friends of user1
    #    and of user2.


    # 2. Use set operations (i.e., &, |, -) to determine which friends
    #    are common between both sets. DO NOT USE LOOPS.
    #    HINT: See the slide on sets from section 2


    # 3. Return the result below
    return None

def recs_by_common_friends(graph: nx.Graph, user: int) -> list[int]:
    # Add your code below. Feel free to keep or remove the scaffolding comments
    # You are not required to follow the scaffolding exactly. Don't panic!
    # It may look long, but the implementation should require
    # around 10 lines of code or less.


    # 1. Gather the set of potential friends using the
    #    friends_of_friends function


    # 2. Initialize a single data structure that will keep track of each
    #    potential friend and what their score is. Since we have one value
    #    to keep track of per *unique* user (*wink wink nudge nudge*)
    #    what might the ideal data structure be?


    # 3. Iterate through each potential friend (from step 1).
    
        # 4. For each potential friend, use the common_friends function to
        # get the set of friends in common between the user passed in and
        # this potential friend, and get its length.


        # 5. Store the number of friends in common for this potential friend
        #    in your data structure from step 2
        
    
    # 6. After iterating through all potential friends, sort the data
    #    structure from step 2 using the sorted() function. The key= parameter
    #    and lambda functions will be useful here. The key (;D) is that if we
    #    have a user ID and a score, what can we generate as the sort key?
    #    (see Lesson 7: Inheritance for info on sorted and lambda functions)
    #    This will end up being one line of code.
    #    HINTS:
    #       - You may need to create another data structure as part of the
    #         sort key
    #       - Consider how negating a value changes the sort order.
    

    # NOTE: sorted() returns a new list of values in ascending order. You
    # should not need to iterate through the result of sorted() further before
    # returning. If you face this, you may need to revisit the data structure
    # of choice (in step 2).


    # 7. Return the result below.
    return None


def recs_by_influence(graph: nx.Graph, user: int) -> list[int]:
    # Now you give it a try! Implement recs_by_influence below. MOST of your
    # code will be the same as recs_by_common_friends, but calculating the
    # influence score will require an additional nested loop in place of
    # steps 4 (if following the scaffolding that we've provided).
    
    return None

def main():
    g = nx.Graph()
    read_facebook(g, FACEBOOK_PATH)

    # Your code here!


if __name__ == '__main__':
    main()
