Diagram G script

From Geb

#18:30 Tuesday 21 March 2006
#By Evgeni Sergeev
#First, construct a tree. Then call propagateSubtreeWidths() on the root.
#Then call printTree() on the root.

import sys

class Node:
    """Represents a node in the tree. """
    def __init__(self, content):
	self.children = []
	self.content = content
	self.subtree_width = 1
	self.root_offset = 0

    def addChild(self, child):
	self.children.append(child)

    def propagateSubtreeWidths(self):
	for child in self.children:
	    child.propagateSubtreeWidths()
	    
	if len(self.children) == 1:
	    self.subtree_width = self.children[0].subtree_width
	    self.root_offset = self.children[0].root_offset
	elif len(self.children) == 0:
	    self.subtree_width = len(str(self.content)) + 1
	    self.root_offset = 0
	else:
	    n = 0
	    for child in self.children:
		n = n + child.subtree_width
	    self.subtree_width = n

	    right_child_relative_offset = self.subtree_width - \\
	    (self.children[len(self.children)-1].subtree_width - \\
	    self.children[len(self.children)-1].root_offset)
	    
	    self.root_offset = (self.children[0].root_offset + \\
	    right_child_relative_offset) / 2

    def printLineTwo(self):
	n = self.root_offset - len(str(self.content))/2
	if n < 0: n = 0
	sys.stdout.write(' '*n)
	sys.stdout.write(str(self.content))
	sys.stdout.write(' '*(self.subtree_width - n - len(str(self.content))))

    def printLineOne(self):
	n = self.root_offset
	sys.stdout.write(' '*n)
	sys.stdout.write('|')
	sys.stdout.write(' '*(self.subtree_width - n - 1))

    def printLineThree(self, horizontal_char = '_'):
	if len(self.children) > 0:
	    if len(self.children) == 1:
		self.printLineOne()
	    elif len(self.children) == 0:
		sys.stdout.write(' '*self.subtree_width)
	    else:
		left_child_offset = self.children[0].root_offset
		
		right_child_offset = self.subtree_width - \\
		(self.children[len(self.children)-1].subtree_width - \\
		self.children[len(self.children)-1].root_offset)
		
		left_dashes = self.root_offset - left_child_offset - 1
		right_dashes = right_child_offset - self.root_offset - 1
		
		left_spaces = self.root_offset - left_dashes
		right_spaces = self.subtree_width - left_spaces - left_dashes \\
		- 1 - right_dashes

		sys.stdout.write(' '*left_spaces)
		sys.stdout.write(horizontal_char*left_dashes)
		sys.stdout.write('|')
		sys.stdout.write(horizontal_char*right_dashes)
		sys.stdout.write(' '*right_spaces)

    def addChildren(self, queue, levels, parent_level):
	queue.extend(self.children)
	new_levels = []
	for child in self.children:
	    new_levels.append(parent_level + 1)
	levels.extend(new_levels)

    def printTree(self, upside_down = 0):
	queue = [self]
	levels = [0]
	n = 0
	#Breadth queue
	while n < len(queue):
	    queue[n].addChildren(queue, levels, levels[n])
	    n = n + 1
	#levels[n] contains the level of n

	if not upside_down:
	    i = 0
	    while i < n:
		start_of_level = i
		end_of_level = i
		while end_of_level < n and \\
		levels[end_of_level] == levels[start_of_level]:
		    end_of_level = end_of_level + 1
		end_of_level = end_of_level - 1
		
		for item in range(start_of_level,end_of_level+1):
		    queue[item].printLineOne()
		print ' '
		
		for item in range(start_of_level,end_of_level+1):
		    queue[item].printLineTwo()
		print ' '
		
		for item in range(start_of_level,end_of_level+1):
		    queue[item].printLineThree()
		print ' '

		i = end_of_level + 1

	else:
	    i = n - 1
	    while i >= 0:
		start_of_level = i
		end_of_level = i
		while start_of_level >= 0 and \\
		levels[end_of_level] == levels[start_of_level]:
		    start_of_level = start_of_level - 1
		start_of_level = start_of_level + 1
		
		for item in range(start_of_level,end_of_level+1):
		    queue[item].printLineThree('"')
		print ' '
		
		for item in range(start_of_level,end_of_level+1):
		    queue[item].printLineTwo()
		print ' '
		
		for item in range(start_of_level,end_of_level+1):
		    queue[item].printLineOne()
		print ' '

		i = start_of_level - 1


def outputTree(f, n):
    n = n + 1
    nodes = range(n-1)
    i = 1
    while i < n:
	nodes[i-1] = Node(i)
	if (f(i) != i):
	    nodes[f(i)-1].addChild(nodes[i-1])
	i = i + 1

    nodes[0].propagateSubtreeWidths()
    nodes[0].printTree(upside_down = 1)
    
print "Diagram G up to n=55."
def G(n, cache={}): #cache is shared between calls (!)
    if n == 0:
	return 0

    if n not in cache:
	cache[n] = n - G(G(n-1))

    return cache[n]

outputTree(G, 55)

print "\

\ Diagram H up to n=59."

def H(n, cache={}):
    if n == 0:
	return 0

    if n not in cache:
	cache[n] = n - H(H(H(n-1)))

    return cache[n]

outputTree(H, 59)

print "\

\ Diagram I up to n=69."

def I(n, cache={}):
    if n == 0:
	return 0

    if n not in cache:
	cache[n] = n - I(I(I(I(n-1))))

    return cache[n]

outputTree(I, 69)

print "\

\ Diagram J up to n=80."

def J(n, cache={}):
    if n == 0:
	return 0

    if n not in cache:
	cache[n] = n - J(J(J(J(J(n-1)))))

    return cache[n]

outputTree(J, 80)

print "\

\ The tree for Q(n) up to n=64."

def Q(n, cache={}):
    if n == 0:
	return 0

    if n not in cache:
	cache[n] = n - Q(n-1)
    
    return cache[n]

outputTree(Q, 64)

print "\

\ The mirror tree MG(n) up to n=55."

def L(n, cache={}):
    if n == 1:
	return 1

    if n not in cache:
	cache[n] = L(G(n)) + 1

    return cache[n]

def F(n, cache={0:1, 1:1}):
    if n == 1 or n == 0:
	return 1

    if n not in cache:
	keys = cache.keys()
	keys.sort(reverse=True)
	max_known = keys[0]
	a, b = F(max_known), F(max_known - 1)
	for i in range(max_known + 1, n + 1):
	    a, b = a + b, a
	    cache[i] = a

    return cache[n]
	
def M(n):
    if n == 1:
	return 1

    return F(L(n)) - (n - F(L(n)-1)) + 1

def MG(n):
    return M(G(M(n)))


outputTree(MG, 55)


#Debugging code.
#print nodes
	    
#for node in nodes:
    #print node.content, ': ',
    #for child in node.children:
	#print child.content, ' ',
    #print ' '

See the Diagram G script output