from __future__ import print_function
+
class prefixNode:
def __init__(self, prefix):
self.prefix = prefix
self.children = []
-
+
class prefixTree:
-
+
def __init__(self):
self.root = prefixNode("")
- def insert(self, prefix, node = None):
+ def insert(self, prefix, node=None):
"""
insert a prefix into the tree
"""
name = ".".join(parts[:i])
if not self.exists(name) and not name == prefix:
self.insert(name)
-
+
if prefix.startswith(node.prefix):
if prefix == node.prefix:
pass
elif not node.children:
node.children.append(prefixNode(prefix))
else:
- inserted = False
+ inserted = False
for child in node.children:
if prefix.startswith(child.prefix):
self.insert(prefix, child)
inserted = True
if not inserted:
- node.children.append(prefixNode(prefix))
+ node.children.append(prefixNode(prefix))
def load(self, prefix_list):
"""
for prefix in prefix_list:
self.insert(prefix)
- def exists(self, prefix, node = None):
+ def exists(self, prefix, node=None):
"""
returns true if the specified prefix exists anywhere in the tree,
false if it doesnt.
if prefix.startswith(child.prefix):
return self.exists(prefix, child)
- def best_match(self, prefix, node = None):
+ def best_match(self, prefix, node=None):
"""
searches the tree and returns the prefix that best matches the
specified prefix
"""
if not node:
node = self.root
-
+
if prefix.startswith(node.prefix):
if not node.children:
return node.prefix
if prefix.startswith(child.prefix):
return self.best_match(prefix, child)
return node.prefix
-
- def dump(self, node = None):
+
+ def dump(self, node=None):
"""
print the tree
"""
print(node.prefix)
for child in node.children:
- print(child.prefix, end=' ')
-
+ print(child.prefix, end=' ')
+
for child in node.children:
self.dump(child)