'''
Created on Mar 14, 2016
@author: Brett Paufler
Copyright Brett Paufler

Commented 4-3-16 (good for cold storage)

Generic (default, non-optimized, so maybe sub-class)
    Node / Tree implementation

Intended to be used for:
    dungeon tile maker

Tree is comprised of Nodes
    Nodes can link to other Nodes or not
    So, a leaf is a non-linking Node


TODO: Check to see if change root was done right
    it's implemented, but how would a person test
    NOTE: Changing the Root won't change the networkx graph much
        reverses arrows


Default NetworkX graphs are the only output at this time
'''

from itertools import count, izip_longest


#gives each Node a unique id_num
node_num = count(1)


class Node(object):
    '''Individual Node in Tree.
    Nodes without sub-nodes are leafs.'''
    
    def __init__(self, links=None, data=None):
        '''links are similiar to children,
        but a link can be linked back to itself,
        so they define edges
            edges = [(self, link) for link in self.links)].
        
        links are id_num of children
            Not implemented as object list to avoid 
                endless recursion.'''
        
        self.num = next(node_num)
        self.links = links if links else []
        self.data = data
    
    def __repr__(self):
        text = 'NODE: num:%d, Links:%s:, data:%s' % (self.num, self.links, self.data)
        return text

    def edges(self):
        '''List of (self, link) pairs.
        
        These could be fed into networkx.
        All the edges in a Tree define a Tree
            (excepting isolated nodes).'''
        return [(self.num, link) for link in self.links]


class Tree(object):
    '''A holding container for individual Nodes.
        (i.e. a group of Nodes makes a Tree.)'''
    
    def __init__(self, name='default name', meta='No Meta Data', nodes=None):
        '''At this time, name and meta are empty holding variables.
            name used in repr
            meta not used anywhere
            
            nodes is a list of Node objects.'''
        
        self.name = name
        self.meta = meta
        self.nodes = nodes if nodes else []
        
    
    def __repr__(self):
        node_text = '\n\t'.join([str(node) for node in self.nodes])
        text = 'TREE: (%s):\n\t%s' % (self.name, node_text)
        return text

    def add_nodes(self, links_list=None, data_list=None):
        ''' '''
        
        links_list = links_list if links_list else []
        data_list = data_list if data_list else []
        
        for links, data in izip_longest(links_list, data_list, fillvalue=None):
            #print link, data
            self.nodes.append(Node(links=links, data=data))


    def flip(self):
        '''Change left links for right links in each node,
        which in this context means reversing each node's link list.'''
        
        for node in self.nodes:
            node.links = node.links[::-1]


    def all_edges(self):
        '''Returns all edges in the tree.
        This is enough to graph with NetworkX.'''
    
        return [edge for node in self.nodes for edge in node.edges()]

        
    def node_by_num(self, num):
        '''Returns a node by number id.
        
        There is no correction or testing,
            to insure there is a node
            or not more than one node.'''
        
        return [node for node in self.nodes if node.num == num][0]


    def links_clear(self):
        '''Zero out the link list in each node.'''
        
        for node in self.nodes:
            node.links = list()
    
    
    def invert(self):
        '''Links_from are converted into links_to.
        (i.e. the ordering of all edge tuple pairs are reversed.
            what was 'from' becomes 'to'.'''
        
        old_edges = self.all_edges()
        self.links_clear()
        
        for parent, child in old_edges:
            new_node = self.node_by_num(child)
            new_node.links.append(parent) 


    def is_root(self, num):
        '''True if there are no unreturned links 'to' this node.
        Thus, there can be more than one root.
        
        A root's links are either:
            bi-direction (anything to the node is returned)
            or point away from root (root links, other does not).'''
        
        potential_root_links = self.node_by_num(num).links
        
        for node in self.nodes:
            if num in node.links:
                if node.num not in potential_root_links:
                    return False
        else:
            return True
        


    #Yeah, maybe this works (no meaningful test, passes visual inspection)
    def root(self, num):
        '''Assigns Node(num) as a root node,
        which may well have no meaning in many situations.
        
        One directional links from current root to num, are reversed.
        
        In bi-directional (or non-directional) graphs changing root does nothing
            mathematically, same graph, even if it represented differently.'''
        
        #if it's a root, no action (think need)
        if self.is_root(num):
            return None
            
        processed = []
        to_process = [num] #list(self.node_by_num(num).links)
        
        while to_process:
            current = to_process.pop()
            
            #edge is tuple, so getting list of leading edges, nodes that link in
            inbound = [edge[0] for edge in self.all_edges() if edge[1] == current]

            for i in inbound:
                if i not in processed:
                    
                    #if haven't reached root, need to process links
                    if not self.is_root(i):
                        to_process.append(i)
                
                    #Meat and Potatoes: Remove link from inboound, add to current
                    self.node_by_num(i).links.remove(current)
                    self.node_by_num(current).links.append(i)
                
            processed.append(current)






if __name__ == '__main__':
    print 'nada done'