#!/usr/local/bin/python
#
#	r t n . p y
#
#	Based on states labeled as numbers (start at 1, end at END)
#	Arcs contain what to match in order to advance to next state
#
from __future__ import generators
import random
from simple import TITLE, END
debug = 0

def gen1(network) :
	"Generate random sentence from network. Non recursive"
	p = network[1]; s = ""
	while 1 :
		choose = random.randrange(len(p))
		s = s + " " + p[choose][0]
		next = p[choose][1]
		if next == END : return s
		p = network[next]

def gen2(item) :
	"Generate random sentence, allow recursive network"
	if type(item) == type("") : return item
	p = item[1]; s = ""
	while 1 :
		choose = random.randrange(len(p))
		s = s + " " + gen2(p[choose][0])
		next = p[choose][1]
		if next == END : return s
		p = item[next]

def gen3(item, Start=1) :
	"Use generator to yield all possible sentences"
	if        Start == END      : yield ""
	elif type(item) == type("") : yield item
	else :
		p = item[Start]; s = ""
		for arc in p :
			for word in gen3(arc[0]) :
				for rest in gen3(item,Start=arc[1]) :
					yield word + " " + rest

def match1 (item, input, Start=1) :
	"Use generator to yield all possible matching sentences"
	if        Start == END      : yield input
	elif not input              : return
	elif type(item) == type("") :
		if item == input[0] : yield input[1:]
	else :
		p = item[Start]; s = ""
		for arc in p :
			for input1 in match1 (arc[0], input) :
				for rest in match1 (item, input1, Start=arc[1]) :
					yield rest

def match2 (item, input, Start=1, depth=0) :
	"Use generator to yield all possible matching sentences"
	if debug and type(item) == type({}) and Start > 0 :
		print ".."*depth,"match2 %s(%d) from %s" % (item[TITLE],Start,input)
	if   depth > 20 : print "Bailing"; return
	if   Start == END : yield input,None
	elif not input    : return
	elif type(item) == type("") :
		if item == input[0] : yield input[1:], item
	else :
		p = item[Start]; s = ""
		trace = [item[TITLE]]
		for arc in p :
			sav1 = trace[:]
			for input1,trace1 in match2 (arc[0], input, depth=depth+1) :
				if trace1 : trace.append(trace1)
				sav2 = trace[:]
				for rest,trace2 in match2 (item, input1, Start=arc[1], depth=depth+1) :
					if trace2 : trace = trace + list(trace2[1:])
					yield rest, tuple(trace[:])
					trace = sav2[:]
				trace = sav1[:]

def match3 (item, input) :
	"Use generator to yield all possible matching sentences that consume input"
	import string
	for input,trace in match2(item, string.split(input)) :
		if debug : print "#match3. ", input
		if not input : yield trace

def display(trace, Indent="") :
	if not Indent : print "-------------------"
	if type(trace) == type("") : print Indent, trace
	else :
		print Indent, trace[0]
		for item in trace[1:] : display(item, Indent=Indent+"  ")

if __name__ == "__main__" :
	import english, string, sys
	for t in match3(english.noun3,string.join(sys.argv)) : print display(t)