import re, string, random, glob, operator, heapq
from collections import defaultdict
from math import log10
import functools

#helper functions

def memo(f):
    "Memoize function f."
    table = {}
    def fmemo(*args):
        if args not in table:
            table[args] = f(*args)
        return table[args]
    fmemo.memo = table
    return fmemo

def test(verbose=None):
    """Run some tests, taken from the chapter.
    Since the hillclimbing algorithm is randomized, some tests may fail."""
    import doctest
    #print 'Running tests...'
    doctest.testfile('ngrams-test.txt', verbose=verbose)

@memo
def segment(text):
    "Return a list of words that is the best segmentation of text."
    if not text: return []
    candidates = ([first]+segment(rem) for first,rem in splits(text))
    return max(candidates, key=Pwords)

def splits(text, L=20):
    "Return a list of all possible (first, rem) pairs, len(first)<=L."
    return [(text[:i+1], text[i+1:]) 
            for i in range(min(len(text), L))]

def Pwords(words): 
    "The Naive Bayes probability of a sequence of words."
    return product(Pw(w) for w in words)

def product(nums):
    "Return the product of a sequence of numbers."
    return functools.reduce(operator.mul, nums, 1)

class Pdist(dict):
    "A probability distribution estimated from counts in datafile."
    def __init__(self, data=[], N=None, missingfn=None):
        for key,count in data:
            self[key] = self.get(key, 0) + int(count)
        self.N = float(N or sum(self.values()))
        self.missingfn = missingfn or (lambda k, N: 1./N)
    def __call__(self, key): 
        if key in self: return self[key]/self.N  
        else: return self.missingfn(key, self.N)

def datafile(name, sep='\t'):
    "Read key,value pairs from file."
    f = open(name, encoding='utf-8')
    for line in f:
        yield line.split(sep)

def avoid_long_words(key, N):
    "Estimate the probability of an unknown word."
    return 10./(N * 10**len(key))

#N = 1024908267229 ## Number of tokens
N = 13412600 ## Number of tokens
#Pw  = Pdist(datafile('count_1w.txt'), N, avoid_long_words)
Pw  = Pdist(datafile('../part1/unigrams/vocab.txt'), N, avoid_long_words)

#spellcheck

#alphabet = "abcdefghijklmnopqrstuvwxyz"
alphabet = 'अआइईउऊािीुूऋॠऌॡएऐओऔृॄॢॣेैोौ॓॔ँंः़ऽॐऍऑऎऒॅॉॆॊकखगघङचछजझञटठडढणतथदधनपफबभमक़ख़ग़ज़ड़ढ़फ़यरलळवशषसहऱऴ्'

def corrections(text): 
    "Spell-correct all words in text." 
    return re.sub('[a-zA-Z]+', lambda m: correct(m.group(0)), text) 

def checker(l):
    return Pw(l[0])*(0.1**min(l[1][0],1))*(10**min(l[1][1],1))

sugg = open("suggestions.txt", "w")

def correct(w): 
    "Return the word that is the most likely spell correction of w." 
    """if w in Pw:
        return w"""
    candidates = edits2(w).items()
    s = []
    print(s)
    for item in candidates:
        s.append((item[0], item[1], checker(item)))
    print(s)
    j=-1
    t1 = -1
    t2 = -1
    t3 = -1
    max1 = 0
    max2 = 0
    max3 = 0
    for i in s:
        j += 1
        if i[2] > max1:
            t3=t2
            t2=t1
            t1=j
            max3 = max2
            max2 = max1
            max1 = i[2]
        elif i[2] > max2:
            t3=t2
            t2=j
            max3 = max2
            max2 = i[2]
        elif i[2] > max3:
            t3=j
            max3 = i[2]
    if t1 == -1:
        sugg.write(w+":"+"(No suggestion)\n")
    else:
        if t3 != -1:
            sugg.write(w+":"+s[t1][0]+"  "+s[t2][0]+"  "+s[t3][0]+"\n")
        elif t2 != -1:
            sugg.write(w+":"+s[t1][0]+"  "+s[t2][0]+"\n")
        else:
            sugg.write(w+":"+s[t1][0]+"\n")
    try:
        c, edit = max(candidates, key=checker)
        #print("hiiii", edit)
        return c
    except:
        return None

def Pedit(edit): 
    "The probability of an edit; can be '' or 'a|b' or 'a|b+c|d'." 
    if edit == '': return (1. - p_spell_error) 
    return p_spell_error*product(P1edit(e) for e in edit.split('+')) 

p_spell_error = 1./20. 

P1edit = Pdist(datafile('hi_phonet.dat')) ## Probabilities of single edits 

def edits2(word):
    results = {}
    def editsR(hd, tl, edits):
        C = hd+tl
        if C in Pw and C not in results:
            results[C] = edits
        if edits[0] >= 2: 
            return
        #insertions
        for a in alphabet:
            C = hd + a + tl
            e = (edits[0]+1, edits[1])
            if C in Pw:
                if C not in results:
                    results[C] = e
                elif e[0] < results[C][0]:
                    results[C] = e
            editsR(hd+a, tl, e)
        if edits[0] >= 1 or tl == '':
            return
        #deletions
        C = hd+tl[1:]
        e = (edits[0]+1, edits[1])
        if C in Pw:
            if C not in results:
                results[C] = e
            elif e[0] < results[C][0]:
                results[C] = e
        #editsR(hd, tl[1:], e)
        #substitution
        for a in alphabet:
            if a != tl[0]:
                C = hd + a + tl[1:]
                e = (edits[0]+1, edits[1])
                if a+'|'+tl[0] in P1edit or tl[0]+'|'+a in P1edit:
                    e = (e[0], e[1]+1)
                if C in Pw:
                    if C not in results:
                        results[C] = e
                    elif e[0] < results[C][0]:
                        results[C] = e
                #editsR(hd+a, tl[1:], e)
        #transpose
        if(len(hd)>=1):
            C = hd[:-1]+tl[0]+hd[-1]+tl[1:]
            e = (edits[0]+1, edits[1])
            if C in Pw:
                if C not in results:
                    results[C] = e
                elif e[0] < results[C][0]:
                    results[C] = e
            #editsR(hd[:-1]+tl[0]+hd[-1], tl[1:], e)
        #loop ahead
        editsR(hd+tl[0], tl[1:], edits)
    editsR('',word,(0,0))
    return results

def edits(word, d=2): 
    "Return a dict of {correct: edit} pairs within d edits of word." 
    results = {} 
    def editsR(hd, tl, d, edits): 
        def ed(L,R): return edits+[R+'|'+L] 
        C = hd+tl 
        if C in Pw: 
            e = '+'.join(edits) 
            if C not in results: results[C] = e 
            else: results[C] = max(results[C], e, key=Pedit) 
        if d <= 0: return 
        extensions = [hd+c for c in alphabet if hd+c in PREFIXES] 
        p = (hd[-1] if hd else '<') ## previous character 
        ## Insertion 
        for h in extensions: 
            editsR(h, tl, d-1, ed(p+h[-1], p)) 
        if not tl: return 
        ## Deletion 
        editsR(hd, tl[1:], d-1, ed(p, p+tl[0])) 
        for h in extensions: 
            if h[-1] == tl[0]: ## Match 
                editsR(h, tl[1:], d, edits) 
            else: ## Replacement 
                editsR(h, tl[1:], d-1, ed(h[-1], tl[0])) 
        ## Transpose 
        if len(tl)>=2 and tl[0]!=tl[1] and hd+tl[1] in PREFIXES: 
            editsR(hd+tl[1], tl[0]+tl[2:], d-1, 
                   ed(tl[1]+tl[0], tl[0:2])) 
    ## Body of edits: 
    editsR('', word, d, 0) 
    return results 

PREFIXES = set(w[:i] for w in Pw for i in range(len(w) + 1)) 
