import networkx as nx
from src.helper.debug_printer import debug_print
from src.helper.display_graph import display_graph

def parcours_eulerien(graph, drone_edges, debug_mode=False, start_node=None):
    """
    Parcours de la déneigeuse à partir de l'algorithme de Hierholzer.
    | DEUXIEME VERSION - Celle-ci est plus robuste et peut gérer les impasses ou cycles présents dans le graphe.
    Parameters:
        graph : Le graphe orienté de Montréal
        drone_edges : Liste des arêtes trouvées par le drone [(u,v), ...]
        debug_mode : Mode debug pour l'affichage des informations
        start_node : Le noeud de départ [OPTIONNEL]
    
    Returns:
        list : Liste des arêtes formant le chemin de la déneigeuse
    """
    if not drone_edges:
        debug_print("/!\\ Aucun parcours de drone effectué.", debug_mode)
        return []

    # Point de départ du parcours
    if start_node is None:
        start_node = drone_edges[0][0]
    
    debug_print(f"Start node: {start_node}", debug_mode)
    
    result = []
    stack = [start_node]
    current_node = start_node
    
    # Récupération des arêtes du drone
    drone_edges_dict = {}
    for u, v in drone_edges:
        if graph.has_edge(u, v) or graph.has_edge(v, u):
            drone_edges_dict[(u, v)] = True
            drone_edges_dict[(v, u)] = True
    
    # Arêtes du drone non visitées
    unvisited_drone_edges = set(drone_edges_dict.keys())
    
    def get_next_valid_edge(current, actual_edges):
        '''
        Trouve la prochaine arête valide depuis le nœud courant.
        '''
        for succ in graph.successors(current):
            if (current, succ) in actual_edges:
                return (current, succ)
        return None

    def find_path_to_next_drone_edge(current, actual_edges):
        '''
        Trouve un chemin valide vers la prochaine arête du drone non visitée.
        '''
        for node in graph.nodes():
            for succ in graph.successors(node):
                if (node, succ) in actual_edges:
                    try:
                        # Récupération du chemin le plus court entre noeud actuel => noeud suivant (avec poids = longueur)
                        path = nx.shortest_path(graph, current, node, weight='length')
                        if path:
                            return path
                    except nx.NetworkXNoPath:
                        continue
        return None

    last_edges = []
    visited_nodes = set() 
    retry_count = 0 
    max_retries = 100 # Cas d'arrêt si on est bloqué trop fortement
    debug_print("Début du parcours eulerien...", debug_mode)
    while unvisited_drone_edges and retry_count < max_retries*2:
        # Récupération de la prochaine arête correcte
        next_edge = get_next_valid_edge(current_node, unvisited_drone_edges)
        
        if next_edge:
            stack.append(current_node)
            visited_nodes.add(current_node)
            retry_count = 0
            
            unvisited_drone_edges.discard(next_edge)
            unvisited_drone_edges.discard((next_edge[1], next_edge[0])) # Autre sens (orienté)
            
            result.append(next_edge)
            last_edges.append(next_edge)
            
            current_node = next_edge[1]
        else:
            # STUCK HERE => On trouve un chemin vers la prochaine arête
            next_path = find_path_to_next_drone_edge(current_node, unvisited_drone_edges)
            
            if next_path:
                # Ajout du parcours effectué pour atteindre la prochaine arête
                for i in range(len(next_path) - 1):
                    u, v = next_path[i], next_path[i + 1]
                    result.append((u, v))
                    last_edges.append((u, v))
                    visited_nodes.add(u)
                    if (u, v) in drone_edges_dict:
                        unvisited_drone_edges.discard((u, v))
                        unvisited_drone_edges.discard((v, u)) # Autre sens (orienté)
                current_node = next_path[-1]
                stack = [current_node]
                retry_count = 0

            elif stack: # Si on est vraiment bien bloqué, on remonte
                current_node = stack.pop()
                retry_count += 1
            else:
                # On fait demi-tour si vraiment sens unique
                if result and retry_count < max_retries and len(last_edges) > 0:
                    last_edge = last_edges.pop()
                    current_node = last_edge[0]
                    result.append((last_edge[1], last_edge[0]))
                    retry_count += 1
                elif retry_count >= max_retries:
                    # On va essayer de trouver le chemin le plus court vers une arête non visitée
                    closest_edge = None
                    closest_edge_path = None
                    min_distance = float('inf') # max
                    for edge in unvisited_drone_edges:
                        path = find_path_to_next_drone_edge(current_node, {edge})
                        if path and len(path) < min_distance:
                            closest_edge = edge
                            closest_edge_path = path
                            min_distance = len(path)
                    
                    if closest_edge:
                        result.extend(closest_edge_path)
                        current_node = closest_edge[0]
                        stack = [current_node]
                        retry_count = 0
                    else:
                        break
                else:
                    break
    
    debug_print("Fin du parcours eulerien...", debug_mode)
    if retry_count >= max_retries * 2:
        debug_print("/!\\ Problème rencontré : Déneigeuse bloquée dans un cycle.", debug_mode)
        return result[:len(result)-retry_count] # suppression du cycle de la path
    
    debug_print(f"Longueur du chemin : {len(result)}", debug_mode)
    debug_print(f"Nombre d'arêtes du drone : {len(drone_edges)}", debug_mode)
    
    if not result:
        debug_print("/!\\ Aucun chemin possible avec cet algorithme", debug_mode)
        return []
        
    return result

def process_hierholzer_v2(graph, drone_edges, debug_mode=False):
    """
    Traite le graphe avec l'algorithme de Hierholzer en utilisant les arêtes du drone.
    
    Parameters:
        graph : Le graphe orienté de Montréal
        drone_edges : Liste des arêtes trouvées par le drone [(u,v), ...]
        debug_mode : Mode debug pour l'affichage d'informations supplémentaires
    
    Returns:
        list : Liste des arêtes formant le chemin de la déneigeuse
    """
    debug_print("Application de l'algorithme de Hierholzer avec les arêtes du drone...", debug_mode)
    
    path = parcours_eulerien(graph, drone_edges, debug_mode)
    
    return path