from random import choice 
import re
import sys 

class markov:
    "Generate text using algorithm of Markov chains"
    
    def __init__( self, prefixLength ):
        self.map = {}
        self.prefixLength = prefixLength
        self.noneKey = (None,) * self.prefixLength

    def prepare( self, text ):
        key = self.noneKey
        words = re.split('(?s)\s+',text.strip())
        for word in words:
            self.map.setdefault(key,[]).append(word)
            key = tuple(list(key[1:]) + [word])

    def next(self, key, word):
        """gets old key and word
        returns new key and word
        if old key = None, generate random key"""

        if None == key:
            key = choice(self.map.keys())
        else:
            key = tuple(list(key[1:]) + [word])
     
        if not self.map.has_key(key):
            key = self.noneKey
        return (key,choice(self.map[key]))

    def generate( self, length ):
        words = []
        key,word = None,None
        for i in xrange(length):
            key,word = self.next(key,word)
            words.append(word)
        return words

class randomMarkov:
    """generate text using algorithm of Markov chains
    using random prefixes length of 2,3,4 words"""

    def __init__(self):
        self.gens = dict([(i,markov(i)) for i in xrange(2,5)])

    def prepare(self,text):
        for gen in self.gens.itervalues():
            gen.prepare(text)

    def adoptKey(self,key,length):
        if None == key:
            return None
        key = list(key)
        diff = len(key) - length
        if diff > 0:
            key = key[diff:]
        elif diff < 0:
            key[0:0] = (None,) * abs(diff)
        return tuple(key)

    def generate(self,length):
        words = []
        key,word = None,None
        for i in xrange(length):
            length,gen = choice(self.gens.items())
            key = self.adoptKey(key,length)
            #print 1,'length:',length,'key:',key
            key,word = gen.next(key,word)
            #print 'word',word
            #print 2,key
            words.append(word)
        return words