from modules.user import info as user_info
from modules.algorithms.univ import dict_key_verify
from modules.algorithms.uuid import hash_string

class User():
    def __init__(self, username, origin=False):
        self.username = username
        self.friends = user_info.friend(username=username)
        self.origin = origin

        self.exclude = []
        self.count = 1
        self.depth = 0
        self.score = 0

        self.friend_list = []

    def find_friends(self, exclude=[], **kwargs):
        self.exclude += exclude
        friends = self.friends.get()
        if dict_key_verify(friends, "friends"):
            self.__organise_friends(friends['friends'])

        self.__find_excluded()

    def __organise_friends(self, friends, **kwargs):
        # used to create the user objects of friends
        for friend in friends:
            if friend['username'] not in self.exclude:
                self.friend_list.append(User(friend['username']))

    def __find_excluded(self):
        # gathers the users to be excluded from the next nodes neigbours and sets this list = to self.exclude
        # this exclude list includes the previously passed exclude list
        if self.username not in self.exclude:
            self.exclude.append(self.username)
        if self.origin:
            self.exclude = self.exclude + [friend.username for friend in self.friend_list]
            requests = self.friends.get_requests()
            if dict_key_verify(requests, "requests"):
                self.exclude = self.exclude + [request for request in requests["requests"]]

    def __hash__(self):
        obj_hash = hash_string(self.username)
        return obj_hash

class Graph():
    def __init__(self, username):
        self.origin_user = User(username, True)
        self.graph = [[]] * (10**7+7)

        self.friend_directory = [None] * (10**7+7)
        self.friend_directory[hash(self.origin_user)] = self.origin_user
        self.exclude = []

    def generate(self, depth=1):
        self.origin_user.depth = depth-1
        self.__add_user_friends(self.origin_user, self.origin_user, depth)

    def __add_user_friends(self, origin, source, depth):
        origin.find_friends(self.exclude + [source.username])
        if hash(self.origin_user) == hash(origin):
            self.exclude += origin.exclude

        for friend in origin.friend_list:
            friend_hash = hash(friend)
            self.__add_edge(hash(origin), friend_hash)

            # if this user already exists in the graph add to their count in the user's object
            # this count keeps track of how many other users friend lists a certain user is
            if self.friend_directory[friend_hash]:
                self.friend_directory[friend_hash].count += 1
            else:
                self.friend_directory[friend_hash] = friend

            if depth-1 > 0:
                # recursively calls the function until the depth is 0. 
                self.__add_user_friends(friend, origin, depth-1)

    def __add_edge(self, node, edge):
        # using the + operator on the lists since .append() has some undefined behaviour on large arrays.
        self.graph[node] = self.graph[node] + [edge]

    def bft(self):
        self.visted = []
        # adds the hash of the selected orgin user to the edge queue
        self.edge_queue = [hash(self.origin_user)]

        self.__visit(self.edge_queue[0])

    def __visit(self, origin):
        # the origin is a number and so can be used as an index for the graph array
        start_pos = self.graph[origin]
        self.__on_visit(origin)

        # adds the current node to the vistsed lists and removes it from the queue
        self.edge_queue.pop(len(self.edge_queue)-1)
        self.visted.append(origin)

        for neigbour in start_pos:
            neigbour_obj = self.friend_directory[neigbour]
            origin_obj = self.friend_directory[origin]

            # checks if the node has been visted yet, if not adds it to the edge queue and assigns it a depth from the origin
            if neigbour not in self.visted and neigbour not in self.edge_queue:
                neigbour_obj.depth = origin_obj.depth - 1
                self.edge_queue = [neigbour] + self.edge_queue

        if len(self.edge_queue) > 0:
            # recursively calls this method until the edge_queue is empty
            self.__visit(self.edge_queue[len(self.edge_queue)-1])

    def __on_visit(self, origin):
        origin_obj = self.friend_directory[origin]
        # each node is only visited once in the graph so the count is calculated when constructing the graph
        origin_obj.score = origin_obj.depth * origin_obj.count

    def recomend_friends(self):
        self.recomendations = []

        # removing the user requesting the recomendations and their friends from the visited list
        # this is done so that the user or people who are already friends of the user dont get recomended
        possible = []
        for user in self.visted:
            user_obj = self.friend_directory[user]
            if user_obj.username not in self.exclude:
                possible = possible + [user]

        while len(self.recomendations) != len(possible):
            largest = User(username="")
            largest.score = -1
            for friend in possible:
                friend_obj = self.friend_directory[friend]
                if friend_obj not in self.recomendations and friend_obj.score > largest.score:
                    largest = friend_obj

            self.recomendations.append(largest)

def recomend_friend(username, amount=1, depth=1):
    if not (depth >= 1 and depth <= 4):
        depth = 4

    friend_graph = Graph(username)
    friend_graph.generate(depth)
    friend_graph.bft()
    friend_graph.recomend_friends()

    recomended = [{'username': recomended.username} for recomended in friend_graph.recomendations[:amount]]
    return recomended

def main():
    result = recomend_friend("Jack", 3, 4)

if __name__ == "__main__":
    main()