import types
import  time
from random import *
SymbolError = 'Symbol Error'
DepthError = 'Depth Error'


class language:
	max_depth = 20
	dont_cross = ['ST']  # dont perform crossovers at the start symbol node
	def __init__(self,lang):
		self.lang = lang
		self.dsc = 0
	def generate(self):	
		new = self._gen()
		new.generate_symbol_table()
		return new
	def _gen(self, cur_sym = 'ST', active_node = None, depth = 0):
		#short circuit really large trees
		if(active_node and depth > self.max_depth):
			self.dsc = self.dsc + 1
			active_node.root().delete_circulars()
			raise DepthError
		depth = depth + 1	
		#reset derivation symbol
		if(str(cur_sym) == 'ST' or self.derive_type == ''):
			if(type(cur_sym) == types.StringType):
				self.derive_type = cur_sym
			else:	self.derive_type = cur_sym.node_type
		new_active_node = active_node
		if type(cur_sym) == types.StringType:
			if self.lang.has_key(cur_sym):
				rule = choice(self.lang[cur_sym])
				for sym in rule:
					new_active_node = self._gen(sym,new_active_node,depth)
			else:
				active_node.root().delete_circulars()
				raise SymbolError, "non-terminal symbol not found:%s" % cur_sym
	
		else:
			parent = new_active_node
			new_active_node = cur_sym.create(parent)
			new_active_node.derive_type = self.derive_type
			self.derive_type = ''
			if parent:
				parent.add_child(new_active_node)
			while new_active_node.filled() and new_active_node.get_parent():	
				new_active_node =new_active_node.get_parent()
		return new_active_node