3 def __init__(self, prefix):
11 self.root = prefixNode("")
13 def insert(self, prefix, node = None):
15 insert a prefix into the tree
20 parts = prefix.split(".")
24 for i in range(1, length + 1):
25 name = ".".join(parts[:i])
26 if not self.exists(name) and not name == prefix:
29 if prefix.startswith(node.prefix):
30 if prefix == node.prefix:
32 elif not node.children:
33 node.children.append(prefixNode(prefix))
36 for child in node.children:
37 if prefix.startswith(child.prefix):
38 self.insert(prefix, child)
41 node.children.append(prefixNode(prefix))
43 def load(self, prefix_list):
45 load a list of prefixes into the tree
47 for prefix in prefix_list:
50 def exists(self, prefix, node = None):
52 returns true if the specified prefix exists anywhere in the tree,
58 if not prefix.startswith(node.prefix):
60 elif node.prefix == prefix:
62 elif not node.children:
65 for child in node.children:
66 if prefix.startswith(child.prefix):
67 return self.exists(prefix, child)
69 def best_match(self, prefix, node = None):
71 searches the tree and returns the prefix that best matches the
77 if prefix.startswith(node.prefix):
80 for child in node.children:
81 if prefix.startswith(child.prefix):
82 return self.best_match(prefix, child)
85 def dump(self, node = None):
93 for child in node.children:
96 for child in node.children: