#	-*- coding: iso-8859-2 -*-
#
#	Traversing trees without stack
#	
#	Author: Wojciech Muła
#	e-mail: wojciech_mula@poczta.onet.pl
#	www:    http://0x80.pl/articles/traversing-trees.html
#	
#	License: public domain
#	
#	initial release 17-02-2011
#	
#	$Id$

class TreeNode(object):
	def __init__(self, name, parent):
		self._parent	= parent
		self.children	= []
		self.name	= name

	def add_child(self, node):
		self.children.append(node)

	def parent(self):
		return self._parent

	def is_leaf(self):
		return len(self.children) == 0

	def is_child(self, node):
		try:
			self.children.index(node)
		except ValueError:
			return False
		else:
			return True

	def first_child(self):
		if self.is_leaf():
			return None
		else:
			return self.children[0]

	def next_sibling(self, node):
		i = self.children.index(node)
		try:
			return self.children[i+1]
		except IndexError:
			return None

import random
def make_random_tree(k, m):
	"k - max. number of nodes in a tree, m - max. number of child"

	def aux(parent, i, k, m):
		if i <= k:
			n = random.randint(0, m)
			nodes = [TreeNode(i+j, parent) for j in range(n)]

			for node in nodes:
				parent.add_child(node)

			i += n
			for node in nodes:
				aux(node, i, k, m)
				i += 1
		pass

	root = TreeNode(0, None)
	aux(root, 1, k, m)

	return root


def dfs_stack(node, visit):
	"classic algorithm"
	if node:
		visit(node)
		for child in node.children:
			dfs_stack(child, visit)


def dfs(root, visit):
	p = None
	x = root

	visit(x)
	while x:
		# 1
		if x.is_leaf():
			p = x
			x = x.parent()

		# 2/3
		elif p == None or p == x.parent():
			p = x
			x = x.first_child()
			visit(x)

		# 4
		elif x.is_child(p):
			t = x
			x = x.next_sibling(p)
			if x == None:
				x = t.parent()
			else:
				visit(x)
			
			p = t
		else:
			assert false, "impossible"


if __name__ == '__main__':
	# usage: script [[[rand_seed] k] m]
	import sys
	def try_get_int(index):
		try:
			return int(sys.argv[index])
		except (IndexError, ValueError):
			return None

	seed = try_get_int(1)
	if seed is not None:
		random.seed(seed)

	k = try_get_int(2) or 50
	m = try_get_int(3) or 5

	root = make_random_tree(20, 3)

	class acc(object):
		def __init__(self):
			self.L = []
		
		def visit(self, node):
			self.L.append(node.name)

	
	v1 = acc()
	dfs_stack(root, v1.visit)

	v2 = acc()
	dfs(root, v2.visit)

	print v1.L
	print v2.L
	assert v1.L == v2.L

# eof