1 from __future__ import print_function
5 def __init__(self, prefix):
13 self.root = prefixNode("")
15 def insert(self, prefix, node = None):
17 insert a prefix into the tree
22 parts = prefix.split(".")
26 for i in range(1, length + 1):
27 name = ".".join(parts[:i])
28 if not self.exists(name) and not name == prefix:
31 if prefix.startswith(node.prefix):
32 if prefix == node.prefix:
34 elif not node.children:
35 node.children.append(prefixNode(prefix))
38 for child in node.children:
39 if prefix.startswith(child.prefix):
40 self.insert(prefix, child)
43 node.children.append(prefixNode(prefix))
45 def load(self, prefix_list):
47 load a list of prefixes into the tree
49 for prefix in prefix_list:
52 def exists(self, prefix, node = None):
54 returns true if the specified prefix exists anywhere in the tree,
60 if not prefix.startswith(node.prefix):
62 elif node.prefix == prefix:
64 elif not node.children:
67 for child in node.children:
68 if prefix.startswith(child.prefix):
69 return self.exists(prefix, child)
71 def best_match(self, prefix, node = None):
73 searches the tree and returns the prefix that best matches the
79 if prefix.startswith(node.prefix):
82 for child in node.children:
83 if prefix.startswith(child.prefix):
84 return self.best_match(prefix, child)
87 def dump(self, node = None):
95 for child in node.children:
96 print(child.prefix, end=' ')
98 for child in node.children: