import logging
from graphviz import Digraph
from collections import deque

logger = logging.getLogger(__name__)
# logging.basicConfig(level=logging.DEBUG)

import time

def timeMS(func, *args, **kwargs):
    startTime = time.perf_counter()
    result = func(*args, **kwargs)
    endTime = time.perf_counter()
    elapsedMS = (endTime - startTime) * 1000  # Convert to milliseconds
    print(f"{func.__name__} took {elapsedMS:.2f} ms")
    return result

from utils.memory_array import MemoryArray
from utils.memory_cell import MemoryCell
from utils.literal import Literal
from utils.memory_range import mrange
from utils.memory_manager import MemoryManager

class Graph:
    def __init__(self):
        self.adjacencyList = {}

    def addEdge(self, node1, node2, bidirectional=True):
        if node1 not in self.adjacencyList:
            self.adjacencyList[node1] = []
        if node2 not in self.adjacencyList:
            self.adjacencyList[node2] = []
        self.adjacencyList[node1].append(node2)
        if bidirectional:
            self.adjacencyList[node2].append(node1)

    def serialize(self):
        return self.adjacencyList

    def breadthFirstSearch(self, start, goal, edgesGonePassed = None):
        if start not in self.adjacencyList or goal not in self.adjacencyList:
            return None, None

        # Dont want to have a class for this, set suffices
        visited = set()
        queue = deque([(start, [start], set())])  # (current_node, path, edgesGoneToGetHere)

        while queue:
            currentNode, path, edgesGone = queue.popleft()

            if currentNode == goal:
                return path, edgesGone

            if currentNode not in visited:
                logger.info(f"visiting {currentNode}")
                visited.add(currentNode)
                for neighbor in self.adjacencyList[currentNode]:
                    edge = (currentNode, neighbor)
                    # We already went this Edge. Read Part3 as not allowing this to happen
                    edgeReverse = (neighbor, currentNode)
                    if neighbor not in visited and (edgesGonePassed is None or edge not in edgesGonePassed) and (edgesGonePassed is None or edgeReverse not in edgesGonePassed):
                        # Pythonic way of saying neighbour, path no next clear neighbour
                        # and union of edgesGone with current edge
                        queue.append((neighbor, path + [neighbor], edgesGone | {edge}))

        return None, None


def graphvizify(filePath: str, outputFile: str = 'build/hoehleGraph'):
    graph = Digraph()
    graph.attr(rankdir='TB')
    graph.attr('node', shape='circle', style='filled', fillcolor='lightgray')
    graph.attr('edge', arrowsize='0.7')

    # Reuse the function to also create our Graph... Waste not want not^^
    caveGraph = Graph();

    with open(filePath, 'r') as f:
        for line in f:
            line = line.strip()
            delimiter = '<>' if '<>' in line else '>' if '>' in line else None
            if delimiter:
                node1, node2 = map(str.strip, line.split(delimiter))
                node1, node2 = map(lambda x: x.strip('"'), map(str.strip, line.split(delimiter)))
                graph.edge(f"\"{node1}\"", f"\"{node2}\"", dir='none' if delimiter == '<>' else None)
                caveGraph.addEdge(node1, node2, (delimiter == '<>'));

    try:
        graph.render(outputFile, view=True)
    except Exception as e:
        print(f"Could not display graph: {e}\n Trying to save without viewing!")
        try:
            graph.render(outputFile, view=False)
            print(f"Your built map should be available here: {outputFile}.pdf")
        except Exception as e:
            print(f"Could not save graph file: {e}")

    return caveGraph

if __name__ == "__main__":
    for filename in [ "data/hoehle.txt", "data/hoehleLarger.txt"]:
        caveGraph = graphvizify(filename, 'build/hoehleGraph')

        start = "Höhleneingang"
        goal = "Schatzkammer"
        shortestPath, edgesGoneInitial = caveGraph.breadthFirstSearch(start, goal)
        logger.debug(caveGraph.adjacencyList)
        logger.debug(edgesGoneInitial)
        
        if shortestPath:
            print(f"Shortest path from {start} to {goal} is:")
            print(" -> ".join(shortestPath))
        else:
            print(f"No path found from {start} to {goal}.")

        returnpath, _ = caveGraph.breadthFirstSearch(goal, start, edgesGoneInitial)

        if returnpath:
            print(f"Shortest path from {goal} to {start} is:")
            print(" -> ".join(returnpath))
        else:
            print("No path back Home found. Good Luck")

    exit(0)