import random

class GrammarModel:

    def __init__(self, N):
        self.__N    = N
        self.__break = (0, ) * N
        self.__next = {}
        self.__prev = {}


    def get_break_tuple(self):
        return self.__break


    def add_sentence(self, sentence):

        if not sentence:
            return

        ta = self.get_break_tuple()
        
        for x in tuple(sentence) + ((0,) * self.__N):
            
            tb = ta[1:] +(x,)

            next = self.__next.setdefault(ta, [])
            prev = self.__prev.setdefault(tb, [])
            
            next.append(x)
            prev.append(ta[0])
            
            ta = tb


    def terminals(self):
        term = {}
        for x in self.__prev[self.__break]:
            term[x] = 1
        return term.keys()
        

    def step_next(self, t):
        L = self.__next.get(t)
        return L and random.choice(L)


    def step_prev(self, t):
        L = self.__prev.get(t)
        return L and random.choice(L)


    def spew(self):
        sentence = []
        t = self.get_break_tuple()
        while 1:
            x = self.step_next(t)
            if x is None:
                return None
            elif x == 0:
                return sentence
            sentence.append(x)
            t = t[1:] + (x,)