Let me explain the following code a little:
# this is just for demonstration purposes, for large sets this will blow up quickly
# "element" is comprised of a character [0], special item (id here) [1], next list [2]
class Root():
root = []
Here you could read in your table data.
I just used a plain text file for convenience.
Name refers to the string you want to suggest whereas id is your row's id.
# read names from file
def __init__(self, fname):
with open(fname, 'r', encoding='utf-8') as infile:
for line in infile:
name, id = line.split(" ")
self.add(name, int(id))
def add(self, name, item):
current = self.root
last = None
# for every character of string traverse the list
for character in name:
has = False
# for every character in current list compare character
for element in current:
last = element
if element[0] == character:
current = element[2]
has = True
break
if not has:
current.append([character, None, []])
last = current[-1]
current = current[-1][2]
We are at the end of the string, add the id.
if last is not None:
last[1] = item
def delete(self):
pass # dunno if you need that =)
def traverse(self, node=root, partial=""):
list = []
for element in node:
if element[1] is not None:
print ("%s%s = %s" % (partial, element[0], element[1]))
list.append([partial+element[0], element[1]])
if len(element[2]) > 0:
list += self.traverse(element[2], partial+element[0])
return list
def lookup(self, partial):
print ("\nlooking up matches for \"%s%%\":" % (partial))
current = self.root
counter = 0
# for every character of string traverse
for character in partial:
# for every character in current list compare character
for element in current:
if element[0] == character:
current = element[2]
counter += 1
break
if counter == len(partial):
print (self.traverse(current, partial))
def test():
root = Root("names.txt")
root.traverse()
root.lookup("ro")
if __name__ == "__main__":
test()
I used the following names.txt:
michael 1
mick 2
miquel 3
bla 5
rodrigo 2
rosquez 51
roberto 13
rosquin 1111