Notes

__license__ = 'Nathalie (c) EPITA'
__docformat__ = 'reStructuredText'
__revision__ = '$Id: prefixTrees.py 2019-02-18'

"""
Prefix Trees homework
2019
@author: antoine.petit
"""


from algopy import tree


################################################################################
## MEASURES

def countwords(T):
""" count words in dictionnary T

:param T: The prefix tree
:rtype: int
"""
s = 0
for i in range(T.nbchildren):
(a, b) = T.children[i]
if a:
s += 1
s += size(T.children[i])
return s

def longestwordlength(T):
""" longest word length

:param T: The prefix tree
:rtype: int
"""
h = 0
for child in T.children:
if h < (longestwordlength(child)+1):
h = longestwordlength(child)+1
return h



def _averagelength(T, count):
""" counting the total number of letters
"""
top = 0
i = T.nbchildren
while (i>=0):
(a, b) = T.children[i]
if b:
top = count + _averagelength(T.children[i],count + 1)
else:
top = _averagelength(T.children[i], count + 1)
return top

def averagelength(T):
""" average word length annex function

:param T: The prefix tree
:rtype: float
"""
return _averagelength(T, 0) // countwords(T)

###############################################################################
## Researches


def searchword(T, word):
""" search for a word in dictionary

:param T: The prefix tree
:param word: The word to search for
:rtype: bool
"""
word = word.lower()
for i in range(len(word)):
bicyclette = True
j = T.nbchildren
while (j >= 0) and bicyclette:
if (T.children[j] == word[i]):
T = T.children[j]
bicyclette = false
j = j-1
return (j>=0)


###############################################################################
## Lists

def _wordlist(T, res2): #Permet de passer la liste en parametre
s = ""
length = len(T)-1
res2 = []
while (length >= 0):
(a, b) = T[length]
s += a
if b:
res2.append(s)
res3 = _wordlist(T[length], res2)
for i in range (res3):
res2.append(res3[i])
length -= 1
return res2

def wordlist(T):
""" generate the word list

:param T: The prefix tree
:rtype: list
"""
return _wordlist(T, [])

def longestwords(T):
""" search for the longest words in dictionary

:param T: The prefix tree
:rtype: list
"""
temp = wordlist(T)
h = temp[0]
for i in range(1 ,len(temp)):
if len(temp[i]) > len(h):
h = temp[i]
return h


def completion(T, prefix):
""" generate the list of words with a common prefix

:param T: The prefix tree
:param pref: the prefix
:rtype: list
"""
temp = []
liste = wordlist(T)
prefix = prefix.lower()
for i in range(len(liste)):
frites = liste[i]
CeciEstUnBooleenMoche = True
j = 0
k = 0
while (j <len(prefix)) and (k < len(frites)) and CeciEstUnBooleenMoche:
if (prefix[j] != frites[k]):
CeciEstUnBooleenMoche = False
if CeciEstUnBooleenMoche:
temp.append(frites)
return temp

def treetofile(T, filename):
""" save the dictionary in a file

:param T: The prefix tree
:param filename: the file name
"""
f = open(filename, write)
h = wordlist(T)
for i in range(len(h)):
file.write(h[i] +"/n")
filename.close()


###############################################################################
## Build Tree

def addword(T, word):
""" add a word in dictionary

:param T: The prefix tree
:param word: The word to add
"""
for i in range(len(LOLALECHAT)):
char = string[i]
booh = False
j = 0
#Teste si le caractere est present dans l arbre
while (not booh) and (j < C.nbchildren):
(a, b) = C.children[j]
if a == char:
booh = True
j = j+1
if not booh:
C = C.children.append(char, False)
C.nbchildren = C.nbchildren+1
if (i+1) == len(LOLALECHAT):
(a, b) = C.children[C.nbchildren-1]
C.children[C.nbchildren-1] = (a, True)
#Passer sur le C.children[j] concerne
C = C.children[j]
return C

def treefromfile(filename):
""" build the prefix tree from a file of words

:param filename: The file name
:rtype: Tree
"""
T = tree.Tree(('', False), [])
file = open(filename, read)
for k in range(len(file)):
LOLALECHAT = file.readline(k)
C = T
if LOLALECHAT != '':
for i in range(len(LOLALECHAT)):
char = string[i]
booh = False
j = 0
#Teste si le caractere est present dans l arbre
while (not booh) and (j < C.nbchildren):
(a, b) = C.children[j]
if a == char:
booh = True
j = j+1
if not booh:
C = C.children.append(char, False)
C.nbchildren = C.nbchildren+1
if (i+1) == len(LOLALECHAT):
(a, b) = C.children[C.nbchildren-1]
C.children[C.nbchildren-1] = (a, True)
#Passer sur le C.children[j] concerne
C = C.children[j]
return C