from-scratch.py

import tkinter as tk

def construct_tree_from_lisp(lisp):
    """
   Creates a Tree object from a LISP-style list:
   
       [1, 2, [3, 4, 5], [6, 7], 8]
   """
    if isinstance(lisp, list):
        v = lisp[0]
        c = []
        for child in lisp[1:]:
            c.append(construct_tree_from_lisp(child))
        return Tree(value = v, children = c)
    else:
        return Tree(value=lisp)
 
class Tree:
    """
   Children is a list of subtrees
   """
    def __init__(self, value=None, children=None):
        if not children:
            self.children = list()
        else:
            self.children = children
        #self.children = children if children else list()
        self.value = value

    def is_leaf(self):
        return not self.children

    def add_child(self, v):
        """Adds a direct child with the given value.

        """
        subtree = Tree(value=v)
        print(subtree.children)
        self.children.append(subtree)

    def get_child (self, v):
        """Finds and returns the direct child with the given value.

        """
        return filter(lambda t:t.value is v, self.children)[0]

    def minimum(self):
        """find the minimum of the tree recursively...

        ...by finding the minimum across every subtree if they exist.

        """
        if self.is_leaf():
            return self.value
        else:
            minchildren = [self.value]
            for item in self.children:
                minchildren.append(item.minimum())
            return min(minchildren)

    def depth(self, current=0):
        """Finds the depth of the tree.

        """
        if self.is_leaf(): return current
        return max(map(lambda t: t.depth(current + 1), self.children))

    def find(self, search):
        """Finds some search object in the tree using DFS

        it can either be a tree object (as returned by find) or some
        value.  if it is some value, it will return the first found,
        depth-first, left to right (since children is an ordered
        list).

        """
        if self.value is search or self is search:
            return self
        for child in self.children:
            target = child.find(search)
            if target:
                return target

    def to_networkx(self, graph=None):
        if graph is None:
            graph = nx.DiGraph()

        for child in self.children:
            graph.add_edge(self.value, child.value)
            child.to_networkx(graph)

        return graph

    def layout(self, _positions=None, _nexts=None, _depth=0):
        """
        Adapted from <http://billmill.org/pymag-trees>
        """
        if not _positions: _positions = dict()
        if not _nexts: _nexts = [0] * (self.depth() + 1)

        _positions[self] = _nexts[_depth], _depth

        _nexts[_depth] += 1

        for subtree in self.children:
            subtree.layout(_positions, _nexts, _depth + 1)

        return _positions

    def __int__(self):
        return self.value
    def __repr__(self):
        return str(self.value)

    def __str__(self):
        if not self.children: return str(self.value)
        return '[{value}, {children}]'.format(
            value=self.value,
            children=', '.join(str(x) for x in list(
                map(lambda c: str(int(c)), self.children)))
        )

    def str_full(self):
        if not self.children: return str(self.value)
        
        r = '[' + str(self.value)
        for subtree in self.children:
            r += ', '
            r += subtree.str_full()
        return r + ']'
#        return '[{value}, {children}]'.format(
#            value=self.value,
#            children=', '.join(list(map(lambda t: t.str_full(),
#                                        self.children)))
#        )
# 
tree1 = [1,[2,3,4],5,[6,7,[8]]]
tree2 = [[1,2],3, [4,[5,6,7,[8,9]]]]
 
class Zipper:
    def __init__ (self, tree):
        self.tree = construct_tree_from_lisp (tree)
        self.path = [self.tree]
 
       
    def move_to_child (self, child):
        assert child in self.tree.children
        self.tree = child
       
    def Zip (self, child):
        self.path.append (self.tree)
        self.move_to_child (child)
       
    def UnZip (self):
        self.tree = self.path.pop()
       
    def Add (self, item):
        self.tree.children.append(item)
       
    def Remove (self, item):
        assert item in self.tree.children
        assert type(item) is not instance  
        self.tree.children.remove (item)
        return self.tree
       
    def Min (self):
        return self.tree.minimum()

    def to_networkx(self):
        G = self.tree.to_networkx()
        setattr(G, '_my_root', self.tree.value)

        # set all nodes to be blue with radius 5
        for node in G.nodes():
            G.node[node]['color'] = (0, 0, 255)
            G.node[node]['radius'] = 5
            G.node[node]['data'] = node

        # Set the root node to be black
        G.node[self.tree.value]['color'] = (0, 0, 0)

        return G

class TreeDrawing(tk.Canvas):
    def __init__(self, *args, **kwargs):
        tk.Canvas.__init__(self, *args, **kwargs)

    def draw(self, tree, scale=50, xshift=10, yshift=10):
        self.delete('all')
        layout = tree.layout()

        lt = {tree: (scale*layout[tree][0] + xshift,
                     scale*layout[tree][1] + yshift)
              for tree in layout}

        self.draw_tree(tree, lt)

    def draw_tree(self, tree, layout):
        root_position = layout[tree]
        self.create_text(root_position, text=tree.value)
        for subtree in tree.children:
            # draw subtrees
            self.draw_tree(subtree, layout)
            # draw edges to subtrees
            subtree_position = layout[subtree]
            self.create_line(root_position[0],    root_position[1],
                          subtree_position[0], subtree_position[1])

from pprint import pprint

tree=construct_tree_from_lisp([1,[2,3,4],5,[6,7,[8]]])

print('ready')

if True:
    root=tk.Tk()
    root.title('Graph Painter 2000')
    root.geometry('640x480+5+5')

    grapher = TreeDrawing(root)
    grapher.pack()

    grapher.draw(tree)

    import time
    five = tree.find(5)
    five.add_child(10)
    #five.add_child(40)
    #five.find(40).add_child(50)
    #print(tree.str_full())


# Local Variables:
# python-shell-interpreter: "python3"
# End: