# reads in a list of words, binary search for user-supplied word
# assumes sorted list
# also print number of words checked for each search
# and at the end, the average number of words checked per search
# 
# Matt Bishop   ECS 36A, Winter 2019
#

# this is global just to emphasize how that works
wordlist = []

# this counts how many words you check before finding the word
# (or giving up)
wordcount = 0

# search a list of words for a word (binary search)
# parameters: word, the word to find in the list
# returns: index (+1) of word in list
#          -1 if not in list
# globals: wordlist, list to search
def recsearch(word, low, high):
        # declarations
        global wordlist, wordcount
        # base case: the low and high bounds cross each other
        if high < low:
                return -1
        # now the recursive part
        wordcount += 1
        mid = (low + high) // 2
        print("high =", high, " low =", low, "mid =", mid, ' word =', word, ' wordlist[mid] =', wordlist[mid])
        if word < wordlist[mid]:
                return recsearch(word, low, mid-1)
        elif word > wordlist[mid]:
                return recsearch(word, mid+1, high)
        # low == high, so see if the word is this one
        elif word == wordlist[mid]:
                return mid
        else:
                return -1
                
#
# a wrapper to call the recursive search
# we need this because the parameter lists are different
# the recursive one needs the lower, upper bounds for the search
#
def search(word):
        # declarations
        global wordlist, wordcount
        # just call the recursive oner
        return recsearch(word, 0, len(wordlist)-1)

                

# append words from a file to a list; assumes one word per line
# note: lines separated by *newlines*, not *carriage returns*
# parameters: none
# returns: True if words loaded successfully
#          False if problem opening file
# globals: wordlist, list to append words to
def loadfile():
        # declaration
        global wordlist
        # open the file, trapping errors
        try:
                infile = open("list.txt", "r")
        except IOError as errmsg:
                # say why it failed, return error code
                print("Could not open 'list.txt':", errmsg)
                return False
        except Exception as errmsg:
                # say why it failed, return error code
                print("Opening 'list.txt' failed:", errmsg)
                return False
        # go through the file line by line
        for i in infile:
                # strip any trailing white space (inc. newline)
                i = i.rstrip()
                # tack the word onto the list
                wordlist.append(i)
        # all done! close file and return success code
        infile.close()
        return True


# this puts it all together
def main():
        # declaration
        global wordlist, wordcount
        # load the word list; on error, quit
        if not loadfile():
                return
        # this counts total words checked across all searches
        totalwords = 0
        # count number of searches to compute average number
        # of words examined per search
        nsearch = 0
        # loop 
        while True:
                # read in word; quit on EOF
                try:
                        find = input("What word should I look for (EOF to quit)? ")
                except EOFError:
                        break
                # count number of words searched for
                nsearch += 1
                # initialize number of words checked
                wordcount = 0
                # find the word if it's there
                found = search(find)
                # announce result
                if found == -1:
                        print("'%s' is not in the list --" % find, end=' ')
                else:
                        print("'%s' is word number %d --" % (find, found), end=' ')
                # print number of words checked
                if wordcount == 1:
                        print("checked 1 word")
                else:
                        print("checked", wordcount, "words")
                # increment total words checked
                totalwords += wordcount
        # give the average number of words checked per search
        avgwdct = totalwords / nsearch
        if avgwdct == 1:
                print("On average, checked 1 word")
        else:
                print("On average, checked %.2f words" % avgwdct)

main()