'''
Project: Binary trees in Python
Author: Scott Sibley (also known as ss)

ChangeLog:
	June 30, 2005 -- Implemented Node and Tree (ss)	

'''

class Node:
	''' A node class for a binary tree '''
	def __init__(self,visitor=None,name=None,left=None,right=None):
		# First determine if this is a core node or not
		if visitor:
			self.core = visitor.core
		else:
			self.core = self

		# Do some initialization of instance members
		self.left = left
		self.right = right
		self.name = name

	def add_right(self,name):
		''' Set this node's right node '''
		self.right = Node(visitor=self,name=name)

	def add_left(self,name):
		''' Set this node's left node '''
		self.left = Node(visitor=self,name=name)

class Tree:
	core = None
	''' A binary tree '''
	def __init__(self):
		# Initialize the tree
		self.core = None
		self.cur = None

	def rewind(self):
		''' Point our cursor at the core node '''
		self.cur = self.core

	def add_node(self,name):		
		''' Traverse recursively through the tree till finding an empty node '''
		# If self.core is None, then we create our first node
		if self.core == None:
			self.core = Node(name=name)
		# Otherwise we begin to search for the best empty leaf position
		# but first check to make sure the node being added is not already
		# within the tree.
		elif name != self.cur.name:
			# Name is greater than this current node's name, so go right
			if name > self.cur.name:
				n_func, self.cur = self.cur.add_right, self.cur.right
			# Otherwise, go left
			else:
				n_func, self.cur = self.cur.add_left, self.cur.left

			# Is the new preselected node is empty, execute the provided method
			if self.cur == None:
				n_func(name=name)
			# Otherwise, continue in the recursion
			else:
				self.add_node(name)
		
		# All finished, so reset the tree's cursor
		self.rewind()

	def tree_stat(self):
		''' Returns a dict with accumulated totals for left and right tree depths '''
		left, right = 0,0
		self.rewind()
		while self.cur != None:
			self.cur = self.cur.right
			right = right + 1
		self.rewind()
		while self.cur != None:
			self.cur = self.cur.left
			left = left + 1
		self.rewind()
		return {'left':left, 'right':right}

	def in_order(self,cur):
		''' In order traversal 
			left, root, right
			prints the values in ascending order
		'''
		if( cur ):
			self.in_order(cur.left)
			print cur.name
			self.in_order(cur.right)

	def pre_order(self,cur):
		''' Pre order traversal 
			root, left, right
			processed as the node is visited
		'''
		if( cur ):
			print cur.name
			self.pre_order(cur.left)
			self.pre_order(cur.right)

	def post_order(self,cur):
		''' Post order traversal 
			left, right, roto
			node is not processed until the children are
		'''
		if( cur ):
			self.post_order(cur.left)
			self.post_order(cur.right)
			print cur.name

	def level_order(self,cur):
		''' Level order traversal
			from top to bottom, left to right 
		'''
		pass
		

if __name__ == '__main__':
	# Create a tree
	tree = Tree()

	# Fill the tree
	tree.add_node('Scott')
	tree.add_node('Achland')
	tree.add_node('Zippy')
	tree.add_node('Zippy')
	tree.add_node('Tux')
	tree.add_node('Art')
	tree.add_node('Achland')

	# Show the tree stat
	print tree.tree_stat()
	print "In order"
	tree.in_order(tree.core)
	print "\nPre order"
	tree.pre_order(tree.core)
	print "\nPost order"
	tree.post_order(tree.core)