#
# Code from:
#
# https://github.com/llimllib/pymag-trees/
#

# This is for the `debug' function below.
from inspect import currentframe

#
# The tree class.
#
# Used to define trees the main class (`DrawTrees') can use as input.
#
class Tree:
    def __init__ (self, node="", *children):
        self.node = node;
        self.width = len (node);
        if children:
            self.children = children;
        else:
            self.children = [];

    def __str__ (self):
        return ("%s" % (self.node));

    def __repr__ (self):
        return ("%s" % (self.node));

    def __getitem__ (self, key):
        if isinstance (key, int) or isinstance (key, slice):
            return self.children[key];
        if isinstance (key, str):
            for child in self.children:
                if child.node == key:
                    return (child)

    def __iter__ (self):
        return (self.children.__iter__());

    def __len__ (self):
        return len (self.children);

#
# Pre-defined trees. Just copied the one I'm working on from `demo-trees.py'.
#
trees = [
#2 deep right
Tree("r",
  Tree("l1"),
  Tree("r1",
    Tree("r2",
      Tree("r3",
        Tree("r4"))))
  ),
];
#
# Debug function, much like it could be done with the C-preprocessor.
#
def debug (*p):
    print ("listing12.py:", currentframe().f_back.f_code.co_name, ":", \
           currentframe().f_back.f_lineno, ": ", *p, sep='')

#
# DrawTree class.
#
# Trees from `trees' vector above get read into nodes of this class which
# computation functions below use as input.
#
class DrawTree (object):
    def __init__ (self, tree, parent = None, depth = 0, number = 1):
        self.x = -1.0;
        self.y = depth;
        self.tree = tree;
        self.children = [DrawTree (c, self, depth+1, i + 1)
                         for i, c in enumerate (tree.children)]
        self.parent = parent;
        self.thread = None;
        self.offset = 0;
        self.ancestor = self;
        self.change = 0;
        self.shift = 0;
        self.mod = 0;
        self._lmost_sibling = None;
        # this is the number of the node in its group of siblings 1..n
        self.number = number;

    def left_brother (self):
        n = None;
        if self.parent:
            for node in self.parent.children:
                if node == self:
                    return (n);
                else:
                    n = node;
        return (n);

    def left (self):
        return (self.thread or len (self.children) and self.children[0]);

    def right (self):
        return (self.thread or len (self.children) and self.children[-1]);

    def get_lmost_sibling (self):
        if not self._lmost_sibling and self.parent and self != \
        self.parent.children[0]:
            self._lmost_sibling = self.parent.children[0];

        return (self._lmost_sibling);

    leftmost_sibling = property (get_lmost_sibling)

#
# The entry point for this module.
#
def buchheim (tree):
    dt = firstwalk (tree)
    second_walk (dt)
    return (dt)

#
# Do a first (post-order) traversal, assigning initial `x' coordinates, `mod's
# value, etc.
#
def firstwalk (v, distance = 1.0):
    if len (v.children) == 0:
        if v.leftmost_sibling:
            v.x = (v.left_brother ().x + distance);
        else:
            v.x = 0.0;
    else:
        default_ancestor = v.children[0];
        for w in v.children:
            firstwalk (w);
            default_ancestor = apportion (w, default_ancestor, distance);

        debug ("executing shifts on ", v.tree);
        execute_shifts (v);

        midpoint = ((v.children[0].x + v.children[-1].x) / 2);

        debug (v.tree, ".midpoint: " , midpoint);

        ell = v.children[0];
        arr = v.children[-1];
        w = v.left_brother ();

        if w:
            v.x = (w.x + distance);
            v.mod = (v.x - midpoint);
        else:
            debug (v.tree, ".x = ", midpoint);
            v.x = midpoint

    return (v);

#
# Takes care of placement of the resulting tree a bit more in depth.
#
def apportion (v, default_ancestor, distance):
    w = v.left_brother ();
    if w is not None:
        # in buchheim notation:
        # i == inner; o == outer; r == right; l == left;
        vir = vor = v;
        vil = w;
        vol = v.leftmost_sibling;
        sir = sor = v.mod;
        sil = vil.mod;
        sol = vol.mod;

        while vil.right () and vir.left ():
            vil = vil.right ();
            vir = vir.left ();
            vol = vol.left ();
            vor = vor.right ();
            vor.ancestor = v;
            shift = (vil.x + sil) - (vir.x + sir) + distance
            if (shift > 0):
                a = ancestor (vil, v, default_ancestor);
                move_subtree (a, v, shift);
                sir = (sir + shift);
                sor = (sor + shift);
            sil += vil.mod;
            sir += vir.mod;
            sol += vol.mod;
            sor += vor.mod;
        if vil.right () and not vor.right ():
            vor.thread = vil.right ();
            vor.mod += sil - sor;
        else:
            if vir.left () and not vol.left ():
                vol.thread = vir.left ();
                vol.mod += sir - sol;
            default_ancestor = v;

    return (default_ancestor);

#
# Moves a whole (sub) tree a given ammount.
#
def move_subtree (wl, wr, shift):
    subtrees = (wr.number - wl.number);
    wr.change -= (shift / subtrees);
    wr.shift += shift;
    wl.change += (shift / subtrees);
    wr.x += shift;
    wr.mod += shift;

#
# Shifts the given (sub) tree as previously computed.
#
def execute_shifts (v):
    shift = change = 0;
    for w in v.children[::-1]:
        w.x += shift;
        w.mod += shift;
        change += w.change;
        shift += (w.shift + change);

#
# Returns the parent of `vil', or the value of `default-ancestor'. Seems pretty
# useless at a first glance.
#
def ancestor (vil, v, default_ancestor):
    if vil.ancestor in v.children:
        return (vil.ancestor);

    return (default_ancestor);

#
# Sets the depth an `x' coordinate based on results of `first-walk'.
#
def second_walk (v, m = 0, depth = 0, min = 0):
    v.x += m;
    v.y = depth;

    for w in v.children:
        second_walk (w, (m + v.mod), (depth + 1), min);

#
# Traverse the `DrawTree' (sub) tree pointed to by `p', printing information
# about each node.
#
def show_tree_info (p):
    print ("                x:", p.x);
    print ("                y:", p.y);
    print ("             tree:", p.tree);
    print ("           parent:", p.parent.tree if p.parent else "None" );
    print ("           thread:", p.thread.tree if p.thread else "None" );
    print ("           offset:", p.offset);
    print ("         ancestor:", p.ancestor.tree);
    print ("           change:", p.change);
    print ("            shift:", p.shift);
    print ("              mod:", p.mod);
    print (" leftmost-sibling:", p._lmost_sibling.tree if p._lmost_sibling else "None");
    print ("           number:", p.number);
    print ("------------------");

    for c in p.children:
        show_tree (c);

# Generate a tree
dt = buchheim (DrawTree (trees[0]));

def str (p):
    print ("hello", p);

# show_tree_info (dt);
debug (str ("algo"));

debug (str (trees[0]));