# Copyright (C) 2010, 2011 Sebastian Thiel (byronimo@gmail.com) and contributors
#
# This module is part of async and is released under
# the New BSD License: http://www.opensource.org/licenses/bsd-license.php
"""Simplistic implementation of a graph"""

__all__ = ('Node', 'Graph')

class Node(object):
    """A Node in the graph. They know their neighbours, and have an id which should 
    resolve into a string"""
    __slots__ = ('in_nodes', 'out_nodes', 'id')
    
    def __init__(self, id=None):
        self.id = id
        self.in_nodes = list()
        self.out_nodes = list()
        
    def __str__(self):
        return str(self.id)
        
    def __repr__(self):
        return "%s(%s)" % (type(self).__name__, self.id)
    
    
class Graph(object):
    """A simple graph implementation, keeping nodes and providing basic access and 
    editing functions. The performance is only suitable for small graphs of not 
    more than 10 nodes !"""
    __slots__ = "nodes"
    
    def __init__(self):
        self.nodes = list()

    def __del__(self):
        """Deletes bidericational dependencies"""
        for node in self.nodes:
            node.in_nodes = None
            node.out_nodes = None
        # END cleanup nodes
        
        # otherwise the nodes would keep floating around
    

    def add_node(self, node):
        """Add a new node to the graph
        :return: the newly added node"""
        self.nodes.append(node)
        return node
    
    def remove_node(self, node):
        """Delete a node from the graph
        :return: self"""
        try:
            del(self.nodes[self.nodes.index(node)])
        except ValueError:
            return self
        # END ignore if it doesn't exist
        
        # clear connections
        for outn in node.out_nodes:
            del(outn.in_nodes[outn.in_nodes.index(node)])
        for inn in node.in_nodes:
            del(inn.out_nodes[inn.out_nodes.index(node)])
        node.out_nodes = list()
        node.in_nodes = list()
        return self
    
    def add_edge(self, u, v):
        """Add an undirected edge between the given nodes u and v.
        
        :return: self
        :raise ValueError: If the new edge would create a cycle"""
        if u is v:
            raise ValueError("Cannot connect a node with itself")
        
        # are they already connected ?
        if  u in v.in_nodes and v in u.out_nodes or \
            v in u.in_nodes and u in v.out_nodes:
            return self
        # END handle connection exists
        
        # cycle check - if we can reach any of the two by following either ones 
        # history, its a cycle
        for start, end in ((u, v), (v,u)):
            if not start.in_nodes: 
                continue
            nodes = start.in_nodes[:]
            seen = set()
            # depth first search - its faster
            while nodes:
                n = nodes.pop()
                if n in seen:
                    continue
                seen.add(n)
                if n is end:
                    raise ValueError("Connecting u with v would create a cycle")
                nodes.extend(n.in_nodes)
            # END while we are searching
        # END for each direction to look
        
        # connection is valid, set it up
        u.out_nodes.append(v)
        v.in_nodes.append(u)
        
        return self
    
    def input_inclusive_dfirst_reversed(self, node):
        """Return all input nodes of the given node, depth first,
        It will return the actual input node last, as it is required
        like that by the pool"""
        stack = [node]
        seen = set()
        
        # depth first
        out = list()
        while stack:
            n = stack.pop()
            if n in seen:
                continue
            seen.add(n)
            out.append(n)
            
            # only proceed in that direction if visitor is fine with it
            stack.extend(n.in_nodes)
            # END call visitor
        # END while walking
        out.reverse()
        return out