<s> from gen import Tree , gentree <EOL> from operator import lt , gt <EOL> from sys import stdout <EOL> class DrawTree : <EOL> def __init__ ( self , tree , depth = - <NUM_LIT:1> ) : <EOL> self . x = - <NUM_LIT:1> <EOL> self . y = depth <EOL> self . tree = tree <EOL> self . children = [ ] <EOL> self . thread = None <EOL> def left ( self ) : <EOL> return self . thread or len ( self . children ) and self . children [ <NUM_LIT:0> ] <EOL> def right ( self ) : <EOL> return self . thread or len ( self . children ) and self . children [ - <NUM_LIT:1> ] <EOL> def reingold_tilford ( tree , depth = <NUM_LIT:0> ) : <EOL> dt = DrawTree ( tree , depth ) <EOL> if len ( tree ) == <NUM_LIT:0> : <EOL> dt . x = <NUM_LIT:0> <EOL> return dt <EOL> if len ( tree ) == <NUM_LIT:1> : <EOL> dt . children = [ reingold_tilford ( tree [ <NUM_LIT:0> ] , depth + <NUM_LIT:1> ) ] <EOL> dt . x = dt . children [ <NUM_LIT:0> ] . x <EOL> return dt <EOL> left = reingold_tilford ( tree [ <NUM_LIT:0> ] , depth + <NUM_LIT:1> ) <EOL> right = reingold_tilford ( tree [ <NUM_LIT:1> ] , depth + <NUM_LIT:1> ) <EOL> dt . children = [ left , right ] <EOL> dt . x = fix_subtrees ( left , right ) <EOL> return dt <EOL> def fix_subtrees ( left , right ) : <EOL> wl = contour ( left , '<STR_LIT:right>' ) <EOL> wr = contour ( right , '<STR_LIT:left>' ) <EOL> if len ( wl ) != len ( wr ) : <EOL> fix_threads ( left , right , len ( wl ) , len ( wr ) ) <EOL> diff = max ( x - y for x , y in zip ( wl , wr ) ) + <NUM_LIT:1> <EOL> diff += ( right . x + diff + left . x ) % <NUM_LIT:2> <EOL> addtotree ( right , diff ) <EOL> return ( left . x + right . x ) / <NUM_LIT:2> <EOL> def fix_threads ( left , right , ldepth , rdepth ) : <EOL> if ldepth > rdepth : rattach ( left , right , rdepth ) <EOL> else : lattach ( left , right , ldepth ) <EOL> def rattach ( left , right , depth ) : <EOL> if depth > <NUM_LIT:1> : <EOL> return rattach ( left . right ( ) , right . right ( ) , depth - <NUM_LIT:1> ) <EOL> right . thread = left . right ( ) <EOL> def lattach ( left , right , depth ) : <EOL> if depth > <NUM_LIT:1> : <EOL> return lattach ( left . left ( ) , right . left ( ) , depth - <NUM_LIT:1> ) <EOL> left . thread = right . left ( ) <EOL> def addtotree ( tree , val ) : <EOL> tree . x += val <EOL> if len ( tree . children ) : <EOL> for child in tree . children [ : <NUM_LIT:2> ] : addtotree ( child , val ) <EOL> def contour ( tree , next ) : <EOL> next_node = getattr ( tree , next ) ( ) <EOL> if not next_node : return [ tree . x ] <EOL> else : return [ tree . x ] + contour ( next_node , next ) <EOL> def printrow ( level ) : <EOL> x = dict ( ( t . x , t . tree ) for t in level ) <EOL> for i in range ( max ( x . keys ( ) ) + <NUM_LIT:1> ) : <EOL> try : stdout . write ( str ( x [ i ] ) [ : <NUM_LIT:4> ] ) <EOL> except : stdout . write ( "<STR_LIT:U+0020>" ) <EOL> def p ( tree ) : <EOL> level = [ tree ] <EOL> while <NUM_LIT:1> : <EOL> newlevel = [ ] <EOL> printrow ( level ) <EOL> for t in level : <EOL> newlevel . extend ( t . children [ : <NUM_LIT:2> ] ) <EOL> print <EOL> if not newlevel : break <EOL> level = newlevel </s>
