# COMP 157
# Project 2:Fuzz search
# Author: Kelvin

# open and close input file
# input: name of the file
# output: the content of the file string
import time

def openFile(filename):
    try:
        myfile = open(filename, 'r')
    except IOError:
        print("file cannot be found, please try again")
        exit(0)

    text = myfile.readlines()
    text = ''.join(text)
    myfile.close()
    return text


# build a shift table for horspool's algorithm
# input: pattern to search for
# output: a table in the form of dictionary
def shiftTable(pattern):
    T = {}
    l = len(pattern)
    for i in range(l-1):
        T[pattern[i]]=l-i-1
    return T


# horspool algorithm to for string searching
# input: pattern and text
# ouput: the postion of the string if found, -1 if not found
def horspoolMatching(pattern, text):
    table = shiftTable(pattern)
    patternLength = len(pattern)
    textLength = len(text)
    if patternLength > textLength:
        return -1
    k = patternLength-1
    while k < textLength:
        j = patternLength-1; i=k
        while j >=0 and text[i]==pattern[j]:
            j-=1; i-=1
        if j == -1:
            return i + 1
        k += table.get(text[k], patternLength)
    return -1


# generate all the suggestions from pattern
# input: pattern
# output: a list of all suggestions
def deletion(pattern):
    suggestions = []
    patternLength = len(pattern)
    if patternLength<2: # return empty string if pattern contains 0 or 1 char
        return suggestions

    for i in range(1,patternLength+1):
        newPattern = pattern[:i-1] + pattern[i:]
        suggestions.append(newPattern)

    return suggestions


# generate all the new patterns from swapping adjacent char
# input: pattern
# output: a list of all suggestions from swapping
def swap(pattern_string):
    patternLength = len(pattern_string)
    pattern = list(pattern_string)
    patternList = []
    i = 0; j = i+1
    while j<=patternLength-1:
        newPattern = pattern[:]
        newPattern[i], newPattern[j] = pattern_string[j], pattern_string[i] # swap the adjacent char
        i+=1; j+=1
        patternList.append(newPattern)
    for i in range(len(patternList)):
        patternList[i] = "".join(patternList[i])
    return patternList


# find a list of substitutions that are off by only 1 char
# input: pattern and text
# output: suggestions from substitutions
def findSub(pattern, text):
    table = shiftTable(pattern)
    patternLength = len(pattern)
    textLength = len(text)
    suggestions = []
    k = patternLength - 1
    if patternLength > textLength:
        return -1
    while k < textLength:
        j = patternLength - 1; i = k; unmatched_char=0 # keep track of # of unmatched
        while j >= 0 and unmatched_char < 2:
            if pattern[j] != text[i]:
                unmatched_char += 1
            j -= 1; i -= 1
        if j==-1 and unmatched_char == 1: # when j=-1, the whole pattern is traversed, so we have a match
            if text[i+1:patternLength+i+1] not in suggestions:
                suggestions.append(text[i+1:patternLength+i+1])
        k += table.get(text[k], patternLength)
    return suggestions


# find a list of suggestion from insertion
# input: pattern and text
# output: a list of suggestions from insertion
def insertion(pattern, text):
    table = shiftTable(pattern)
    patternLength = len(pattern)
    textLength = len(text)
    suggestions = []
    k = patternLength - 1
    if patternLength > textLength:
        return -1
    while k+1 < textLength:
        j = patternLength - 1; i = k; unmatched_char=0
        while j >= 0 and unmatched_char < 2:
            if pattern[j] != text[i + 1]: # if char doesn't match, increment the text while keep the index of pattern to see if match
                unmatched_char += 1; j += 1
            j -= 1; i -= 1
        if j==-1: # when j = -1, the whole pattern is traversed
            if text[i+2:patternLength+i+3] not in suggestions:
                suggestions.append(text[i+2:patternLength+i+3])
        k += table.get(text[k], patternLength)
    return suggestions


# call all the suggestion functions
# input: pattern and text
# output: list from deletion, swap, institution, and insertion
def findAllSuggestions(pattern, text):
    delete_list = deletion(pattern)
    delete_list = findMatch(delete_list,text)
    swap_list = swap(pattern)
    swap_list = findMatch(swap_list,text)
    sub = findSub(pattern, text)
    ins = insertion(pattern, text)
    return delete_list, swap_list, sub, ins


# filter out the unmatched patterns generated by deletion and swapping
# input: suggestion list and text
# output: a final list that actually appear in the text
def findMatch(suggest_list, text):
    not_match=[]
    for i in range(len(suggest_list)):
        result = horspoolMatching(suggest_list[i], text)
        if result==-1:
            not_match.append(i)
    for i in sorted(not_match, reverse=True): # filter out unmatched suggestions
        del suggest_list[i]
    return suggest_list


def main():
    choice = 'n'
    while (choice == 'n'):
        filename = input("Enter the name of the file: ")
        text = openFile(filename)
        pattern = input("Enter the pattern/phrase that you want to search for: ")
        horspool_time = time.time()
        result = horspoolMatching(pattern, text)
        if result != -1: # an exact match is found
            horspool_time_end = time.time()
            time_elapsed = horspool_time_end-horspool_time
            print("Found exact match at position",result)
            print("Horspool takes" + str(time_elapsed) + "seconds")
        else:
            print("No exact match found, here are some suggestions\n")
            sug_time = time.time()
            d, s, sub, ins= findAllSuggestions(pattern, text)
            sug_time_elapsed = time.time()
            print("Suggestions from deletion:",d)
            print("Suggestions from swap:", s)
            print("Suggestions from substitution:", sub)
            print("Suggestions from insertion: ", ins)
            print("It takes " + str(sug_time_elapsed-sug_time) + " seconds")
        choice=input("\nQuit?(y/n):")
        print("\n")


if __name__=='__main__':
    main()