git://git.onelab.eu
/
sfa.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
rough cleanup of component manager
[sfa.git]
/
sfa
/
util
/
prefixTree.py
diff --git
a/sfa/util/prefixTree.py
b/sfa/util/prefixTree.py
index
0d7a557
..
2f5b5f0
100755
(executable)
--- a/
sfa/util/prefixTree.py
+++ b/
sfa/util/prefixTree.py
@@
-1,18
+1,19
@@
from __future__ import print_function
from __future__ import print_function
+
class prefixNode:
def __init__(self, prefix):
self.prefix = prefix
self.children = []
class prefixNode:
def __init__(self, prefix):
self.prefix = prefix
self.children = []
-
+
class prefixTree:
class prefixTree:
-
+
def __init__(self):
self.root = prefixNode("")
def __init__(self):
self.root = prefixNode("")
- def insert(self, prefix, node
=
None):
+ def insert(self, prefix, node
=
None):
"""
insert a prefix into the tree
"""
"""
insert a prefix into the tree
"""
@@
-27,20
+28,20
@@
class prefixTree:
name = ".".join(parts[:i])
if not self.exists(name) and not name == prefix:
self.insert(name)
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:
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:
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):
"""
def load(self, prefix_list):
"""
@@
-49,7
+50,7
@@
class prefixTree:
for prefix in prefix_list:
self.insert(prefix)
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.
"""
returns true if the specified prefix exists anywhere in the tree,
false if it doesnt.
@@
-68,14
+69,14
@@
class prefixTree:
if prefix.startswith(child.prefix):
return self.exists(prefix, child)
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
"""
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(node.prefix):
if not node.children:
return node.prefix
@@
-83,8
+84,8
@@
class prefixTree:
if prefix.startswith(child.prefix):
return self.best_match(prefix, child)
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 the tree
"""
@@
-93,7
+94,7
@@
class prefixTree:
print(node.prefix)
for child in node.children:
print(node.prefix)
for child in node.children:
- print(child.prefix, end=' ')
-
+ print(child.prefix, end=' ')
+
for child in node.children:
self.dump(child)
for child in node.children:
self.dump(child)