60b28ac5 |
a = {
|
9c112cd3 |
0: set([1, 14, 16, 17, 19, 20, 21, 22]),
1: set([2]),
2: set([]),
14: set([15]),
15: set([]),
16: set([18]),
17: set([]),
18: set([]),
19: set([]),
20: set([]),
21: set([]),
|
60b28ac5 |
22: set([])
}
def lookup(lis, table):
cset = table[lis.pop(0)]
ckey = None
for x in lis[:-1]:
|
9c112cd3 |
if x in cset:
|
60b28ac5 |
ckey = x
cset = table[x]
print x, cset
else:
raise Exception()
if lis[-1] in cset:
key = lis[-1]
return key, table[key]
else:
raise Exception()
import UserDict
import operator
class Tree(object, UserDict.DictMixin):
def __init__(self, table, root):
self.key = root
self.filled = False
self.children = {}
if root in table:
result = []
for child in table[root]:
result.append((child, Tree(table, child)))
self.filled = True
self.children.update(result)
def __getitem__(self, key):
|
9c112cd3 |
if hasattr(key, '__iter__'):
|
60b28ac5 |
return self.find([self.key] + list(key))
return self.children[key]
|
9c112cd3 |
def keys(self):
|
60b28ac5 |
return self.children.keys()
def find(self, path):
if len(path) == 1:
return self
else:
value = self[path[1]]
if value is not None:
value = value.find(path[1:])
return value
|
9c112cd3 |
def __str__(self):
|
60b28ac5 |
return '\n'.join(self.mkstrtree(0))
def mkstrtree(self, level, space='--'):
result = [space*level+str(level+1)+space+str(self.key)]
for id, child in self.children.items():
|
9c112cd3 |
result.extend(child.mkstrtree(level+1))
|
60b28ac5 |
return result
def mktree(self):
result = {}
def setitem(dict, key, value): dict[key] = value
for key, value in self.children.items():
if value.filled:
|
9c112cd3 |
setitem(result, key, value.mktree())
|
60b28ac5 |
else:
|
9c112cd3 |
setitem(result, key, None)
|
60b28ac5 |
return result
def count(self):
|
9c112cd3 |
return len(self) + reduce(operator.add,
[x.count() for x in self.children.values()],
|
60b28ac5 |
0)
|
9c112cd3 |
b = Tree(a, 135);print b
|