sfa/util/prefixTree.py

   1 class prefixNode:
   2
   3     def __init__(self, prefix):
   4         self.prefix = prefix
   5         self.children = []
   6
   7
   8 class prefixTree:
   9
  10     def __init__(self):
  11         self.root = prefixNode("")
  12
  13     def insert(self, prefix, node = None):
  14         """
  15         insert a prefix into the tree
  16         """
  17         if not node:
  18             node = self.root
  19
  20         parts = prefix.split(".")
  21         length = len(parts)
  22
  23         if length > 1:
  24             for i in range(1, length + 1):
  25                 name = ".".join(parts[:i])
  26                 if not self.exists(name) and not name == prefix:
  27                     self.insert(name)
  28
  29         if prefix.startswith(node.prefix):
  30             if prefix == node.prefix:
  31                 pass
  32             elif not node.children:
  33                 node.children.append(prefixNode(prefix))
  34             else:
  35                 inserted  = False
  36                 for child in node.children:
  37                     if prefix.startswith(child.prefix):
  38                         self.insert(prefix, child)
  39                         inserted = True
  40                 if not inserted:
  41                     node.children.append(prefixNode(prefix))
  42
  43     def load(self, prefix_list):
  44         """
  45         load a list of prefixes into the tree
  46         """
  47         for prefix in prefix_list:
  48             self.insert(prefix)
  49
  50     def exists(self, prefix, node = None):
  51         """
  52         returns true if the specified prefix exists anywhere in the tree,
  53         false if it doesnt.
  54         """
  55         if not node:
  56             node = self.root
  57
  58         if not prefix.startswith(node.prefix):
  59             return False
  60         elif node.prefix == prefix:
  61             return True
  62         elif not node.children:
  63             return False
  64         else:
  65             for child in node.children:
  66                 if prefix.startswith(child.prefix):
  67                     return self.exists(prefix, child)
  68
  69     def best_match(self, prefix, node = None):
  70         """
  71         searches the tree and returns the prefix that best matches the
  72         specified prefix
  73         """
  74         if not node:
  75             node = self.root
  76
  77         if prefix.startswith(node.prefix):
  78             if not node.children:
  79                 return node.prefix
  80             for child in node.children:
  81                 if prefix.startswith(child.prefix):
  82                     return self.best_match(prefix, child)
  83             return node.prefix
  84
  85     def dump(self, node = None):
  86         """
  87         print the tree
  88         """
  89         if not node:
  90             node = self.root
  91             print node.prefix
  92
  93         for child in node.children:
  94             print child.prefix,
  95
  96         for child in node.children:
  97             self.dump(child)