from Node import *
from clone_graph import *
import copy

def create_graph(data):
    if len(data) == 0:
        return Node(1)
    nodes = []
    for i in range(len(data)):
        nodes.append(Node(i+1))
    
    for i, node in enumerate(nodes):
        for neighbor in data[i]:
            node.neighbors.append(nodes[neighbor-1])
    return nodes[0] 

def create_2D_list(root):
    if root == None:
        return []
    # Initialize a queue for breadth-first traversal
    queue = [root]
    # Initialize a dict to keep track of visited nodes
    visited = {}
    # Initialize a 2D list to store the graph
    graph = []
    # Initialize a dict to store the index of each node
    node_index = {}
    # Perform breadth-first traversal
    while queue:
        # Get the next node in the queue
        node = queue.pop(0)
        # Create a new list to store the neighbors of the current node
        neighbors = []
        # Iterate through the neighbors of the current node
        for neighbor in node.neighbors:
            # Append the neighbor's value to the list of neighbors
            neighbors.append(visited.get(neighbor, neighbor).data)
            # Add the neighbor to the queue if it hasn't been visited yet
            if neighbor not in visited and neighbor not in queue:
                visited[neighbor] = neighbor
                queue.append(neighbor)
        # Sort the list of neighbors
        neighbors.sort()
        # Append the current node's value and its neighbors to the 2D list
        if node not in node_index:
            node_index[node] = len(graph)
            graph.append([node.data, neighbors])
        else:
            graph[node_index[node]][1] = neighbors
    # Sort the graph by node value
    graph.sort(key=lambda x: x[0])
    # return second sublist
    return [sublist[1] for sublist in graph]

def compare_addresses(original, cloned):
    original_queue = [original]
    cloned_queue = [cloned]
    visited = set()
    while original_queue and cloned_queue:
        original_node = original_queue.pop(0)
        cloned_node = cloned_queue.pop(0)
        if original_node not in visited:
            visited.add(original_node)
            if hex(id(original_node)) == hex(id(cloned_node)):
                return True
                #print(f"Original Node {original_node.data}: {hex(id(original_node))} || Cloned Node {cloned_node.data}: {hex(id(cloned_node))}  || Address Equal")
                #print("---------------------------------------------------------------------------------------------")
            original_queue += original_node.neighbors
            cloned_queue += cloned_node.neighbors
    return False

def clones(root):
    node = create_graph(root)
    r_copy = clone(node)
    flg = compare_addresses(node, r_copy)
    if flg:
        print("The graph is not properly cloned.")
        return []
    return create_2D_list(r_copy)