#!/usr/bin/python -tt
# vim:et:sw=4
import sys

# Python doesn't have "enum"s or "#define"s.  I think.
left_to_right = 1
right_to_left = 2

class treenode:
    def __init__(self, mydata):
        self.leftnode = None
        self.rightnode = None
        self.data = mydata
    
    # How many nodes below AND INCLUDING me?
    def nbelow(self):
        nleft = 0
        if self.leftnode:
            nleft = self.leftnode.nbelow()
        nright = 0
        if self.rightnode:
            nright = self.rightnode.nbelow()
        return nleft + nright + 1
    def setleft(self, val):
        self.leftnode = val
    def setright(self, val):
        self.rightnode = val

    def insert_tree(self, d2put):
        if self.data is None:
            self.data = d2put
            return self

        if d2put == self.data:     # it's a DUP
            return self            # return without doing anything

        if d2put < self.data:      # new one should go to the left 
            if self.leftnode == None:
                self.leftnode = treenode(d2put)
                return self
            self.leftnode = self.leftnode.insert_tree(d2put)
        else:                       # new one should go to the right
            if self.rightnode == None:
                self.rightnode = treenode(d2put)
                return self
            self.rightnode = self.rightnode.insert_tree(d2put)
        return self

    def move1(self, dir):
        if dir == left_to_right:
            from_side = lambda x: x.leftnode    # function pointer effectively
            to_side = lambda x: x.rightnode
            set_from = lambda x,v: x.setleft(v)
            set_to = lambda x,v: x.setright(v)
        else:
            if dir != right_to_left: 
                raise "illegal direction parameter"  # ASSERT
            from_side = lambda x: x.rightnode
            to_side = lambda x: x.leftnode
            set_from = lambda x,v: x.setright(v)
            set_to = lambda x,v: x.setleft(v)

        # Call when we move something from "from_side" to "to_side"
        oldParent = self
        node2move = from_side(self)             # parent = self

        while to_side(node2move):
            oldParent = node2move       # parent = node2move;
            node2move = to_side(node2move)

        set_to(node2move,self)

        # Unlink node2move; to_side is NULL so we only need from_side
        if oldParent != self:
           set_to(oldParent, from_side(node2move))
           set_from(node2move, from_side(self))

        # Now unlink "self" and move it into new position
        # Be lazy!
        set_from(self, None)
        return node2move;

    # Rebalance below (and including) "self" -- which shall be replaced.

    def rebal_below(self):
        if self == None:
            return self
        qty_left = 0
        qty_right = 0
        if self.leftnode:
            qty_left = self.leftnode.nbelow();
        if self.rightnode:
            qty_right = self.rightnode.nbelow();
        # Too many on left?  Then move 'em right
        while qty_left > 1+qty_right:
            self = self.move1(left_to_right)
            qty_left = qty_left - 1
            qty_right = qty_right + 1

        # Too many on right?  Then move 'em left */
        while qty_right > 1+qty_left:
            self = self.move1(right_to_left)
            qty_left = qty_left + 1
            qty_right = qty_right - 1

        if self.leftnode:
            self.leftnode = self.leftnode.rebal_below();
        if self.rightnode:
            self.rightnode = self.rightnode.rebal_below();
        return self;

root = treenode(None)

# display the tree in visible form.  

def BANNER(which):
    print("================ %s ================" % which)

INDENT = "-->"
def dump_tree(start, my_prefix):
    global root
    at_root = (root == start) 
    if at_root:
        BANNER("start tree dump");
    if start == None:
        return;

    if start.leftnode:
        new_prefix = my_prefix + "L" + INDENT
        dump_tree(start.leftnode, new_prefix)
    print("%s%s" % ( my_prefix, start.data))
    if start.rightnode:
        new_prefix = my_prefix + "R" + INDENT
        dump_tree(start.rightnode, new_prefix)

    if at_root:
        BANNER("end tree dump")


# Main program.  Take each word in the input (each input arg) and
# insert it into the tree.  After the last one, dump the tree,
# rebalance it, and dump it again.

def doit(argv):
    global root
    for one_arg in argv:
        root.insert_tree(one_arg)
        #DEBUG dump_tree(root, "after " + one_arg)

    dump_tree(root, "before: ")
    print "calling rebalance_below()"
    root = root.rebal_below()
    dump_tree(root, "after: ")

# main
if __name__ == '__main__':
    doit(sys.argv[1:])