#!/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[0]:
            nleft = self.leftnode[0].nbelow()
        nright = 0
        if self.rightnode[0]:
            nright = self.rightnode[0].nbelow()
        return nleft + nright + 1

# Sorry about all the [0]s, but that's what lets me effectively
# store through a pointer.  Maybe the same trick would work in Java?

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

    # QUESTION 1: Does java let you assign function pointers so
    #             you can then just call thru the pointer -- change
    #             the semantics of the following code so you can
    #             write it just once?
    # I think Python is OK w/this -- see above.
    # But "leftnode" and "rightnode" must be arrays
    #    otherwise "can't assign to function call" ensues.


    # QUESTION 2: Does java let you assign through pointers?  This way
    #             we know that to unlink we just tweak *pptr; no need for
    #             special case code (if parent==start then update the
    #             parent's "from_side" ptr else update the parent's
    #             "to_side" ptr)
    # See above.  Need array return :( .

    # Call when we move something from "from_side" to "to_side"
    pptr = from_side(start)             # parent = start
    node2move = pptr[0]
    while to_side(node2move)[0]:
        pptr = to_side(node2move)       # parent = node2move;
        node2move = pptr[0]

    # Unlink node2move; to_side is NULL so we only need from_side
    pptr[0] =  from_side(node2move)[0]

    # node2move is now unlinked; make it the new "start"
    newstart = node2move
    newstart.leftnode[0] = start.leftnode[0]
    newstart.rightnode[0] = start.rightnode[0]

    # Now unlink "start" and move it into new position
    start.leftnode = [None]
    start.rightnode = [None]
    node2move = start
    start = newstart

    pptr = to_side(start)
    while pptr[0] != None:
        pptr = from_side(pptr[0])
    pptr[0] = node2move
    return start;

# Rebalance below!  The middle node (i.e., "start") may get
# replaced.

def rebal_below(start):
    if start == None:
        return start
    qty_left = 0
    qty_right = 0
    if start.leftnode[0]:
        qty_left = start.leftnode[0].nbelow();
    if start.rightnode[0]:
        qty_right = start.rightnode[0].nbelow();
    # Too many on left?  Then move 'em right
    while qty_left > 1+qty_right:
        start = move1(start, 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:
        start = move1(start, right_to_left)
        qty_left = qty_left + 1
        qty_right = qty_right - 1

    start.leftnode[0] = rebal_below(start.leftnode[0]);
    start.rightnode[0] = rebal_below(start.rightnode[0]);
    return start;

root = 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[0]:
        new_prefix = my_prefix + "L" + INDENT
        dump_tree(start.leftnode[0], new_prefix)
    print("%s%s" % ( my_prefix, start.data))
    if start.rightnode[0]:
        new_prefix = my_prefix + "R" + INDENT
        dump_tree(start.rightnode[0], new_prefix)

    if at_root:
        BANNER("end tree dump")

# Insert node into the tree.
# d2put = data to put.  
# start = subtree where new node should be put.
# We return new value of "start" -- which happens only when 
# NULL is passed in.

def insert_tree(start, d2put):
    if start == None:
        start = treenode(d2put);
        return start;

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

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

# 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:
        print "arg is", one_arg
        dump_tree(root, "")
        root = insert_tree(root, one_arg)

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

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