Do not use any helper functions or new functions and use tester to test code

Given: You are given a Python Class template, and a list of words in the

file 'american-english-no-accents.txt'. In the template

Task:Implement recursive trie data structure. Each node should store either

a character or a word. Then, implement the autocomplete method. This

method should recursively explore the trie and return a list of all

words in the trie that match that prefix. The list must be in

alphabetical order.

Example:

Given the words 'dad', 'daddy', 'daddio', 'danny', 'mum',

and 'mummy', the trie should look like this:

|d|m|

/\

|a||u|

/\

|d | n||m|

/\\

|d | #|danny|m | #|

/\/\

|i | y|dadmummymum

/\

daddiodaddy

When the prefix 'da' is autocompleted, the list returned should be:

['dad', 'daddio', 'daddy', 'danny']. When the prefix '' is given,

every word in the trie should be returned, in alphabetical order.

When the prefix 'uncl' is given, an empty list should be returned.

Notes: Ensure that duplicate words do not get added to the trie twice.

Both lower and upper case letters will be used. Consider them as

seperate characters, upper case letters coming before lower case.

The file 'american-english-no-accents.txt' is used by the tester.

Use Lab-Tester.py to test your code

Example command line

$python Lab5-Tester.py Lab-Template.py

Lab-Template.py

def getName():

return "Last name, first name"

class MyTrie:

def __init__(self):

# Initialize the trie node as needed

self.children = {}

self.children_count = 0

self.word = None

self.autocomplete_list = []

def insert(self, word):

# Insert a word into this trie node

pass

def exists(self, word, position=0):

# Return true if the passed word exists in this trie node

# A terminal node will return true if the word passed is ""

pass

def isTerminal(self):

# Return true if this node is the terminal point of a word

pass

def autoComplete(self, prefix, position=0):

# Return every word that extends this prefix in alphabetical order

pass

def __len__(self):

# Return the number of words that either terminate at this node or descend from this node

# A terminal leaf should have length 1, the node A with terminal child leaves B|C should have length 2

pass

Lab-Tester.py - Link to 'american-english-no-accents.txt' - https://easyupload.io/c8reqf

import random

import string

import re

#Module Imports

import string

import sys

from importlib import import_module

wordlist = []

def GenerateWord(size):

chars=string.ascii_letters+"'"

word=""

for i in range(0, random.randint(size/2, size)):

word += random.choice(chars)

return word

def diff(li1, li2):

return (list(list(set(li1)-set(li2)) + list(set(li2)-set(li1))))

def Test(lib, seed=0, size=10, rounds=10, verbose=False, wordlist=None):

if wordlist is None: wordlist = []

if not lib:

print("You need to include a testable library")

return False

if not wordlist:

f = open("american-english-no-accents.txt", "r")

readwords = f.readlines()

for word in readwords:

wordlist.append(word.rstrip())

random.seed(a=seed)

trie = lib.MyTrie()

for word in wordlist:

trie.insert(word)

if len(wordlist) != len(trie):

if verbose:

print("Trie size mismatch!")

return False

if verbose:

print("Insertion test complete")

yield True

for j in range(0, rounds):

expected = True

c=""

if random.randint(0,2) == 0:

c = GenerateWord(6)

else:

c = wordlist[random.randint(0, len(wordlist))]

expected = c in wordlist

res = trie.exists(c)

if res != expected:

if verbose:

print("Word " + c + " was " + ("found" if res else "not found") + " and was expected to " + ("" if expected else "not") + " be.")

return False

if verbose:

print("Trie item test complete")

yield True

try:

mlist = trie.autoComplete("")

except:

if verbose:

print("Error: Autocomplete method not callable")

return False

if not(mlist == wordlist):

if verbose:

print("Error: Autocomplete missing items for empty list")

missing = diff(mlist, wordlist)

print(missing)

return False

if verbose:

print("Complete retrieval test complete")

yield True

try:

emptyList = trie.autoComplete("fasdfasdfasdfasfawef")

except:

if verbose:

print("Error: Autocomplete does not respond to unmatched prefix")

return False

if len(emptyList) != 0:

if verbose:

print("Error: Autocomplete returning items for unmatchable prefix")

return False

if verbose:

print("Unmatchable prefix test complete")

yield True

for j in range(0,rounds):

w = ""

while len(w) < 4:

w = random.choice(wordlist)

prefix = w[0:3]

matchlist = list(filter(lambda x: x.startswith(prefix), wordlist))

try:

autocompletelist = trie.autoComplete(prefix)

except:

if verbose:

print("Error: Autocomplete method not callable")

return False

if not (matchlist == autocompletelist): # Check more problems? ie not in order, in order but missing, etc

if verbose:

print("Error: Autocomplete method not returning correct information")

return False

if verbose:

print("Autocomplete test complete")

yield True

if __name__ == "__main__":

try:

f = open("american-english-no-accents.txt", "r")

except:

print("Error: Please ensure the wordlist file is in this directory.")

exit()

readwords = f.readlines()

for word in readwords:

wordlist.append(word.rstrip())

if len(sys.argv) < 2:

print("Include at least a library name as an argument.")

exit()

name = sys.argv[1]

if name.startswith(".\\"):

name = name[2:]

if name.endswith(".py"):

name = name[:-3]

module=import_module(name,package=__name__)

print(f"Testing module {name} by {module.getName()}")

score=0

for i in Test(module,seed=123456, size=20, verbose=True, wordlist = wordlist):

if i:

score+=1

print(f"Test result: {score}/5")