Sha256: 4eb698112fbf6eae1e77adec9c8a2ba2b7a393973a08be7070f58bed2bce2115
Contents?: true
Size: 1.97 KB
Versions: 71
Compression:
Stored size: 1.97 KB
Contents
from json import dumps
class Tree(object):
def __init__(self, label, children=[]):
self.label = label
self.children = children
def __dict__(self):
return {self.label: [c.__dict__() for c in sorted(self.children)]}
def __str__(self, indent=None):
return dumps(self.__dict__(), indent=indent)
def __lt__(self, other):
return self.label < other.label
def __eq__(self, other):
return self.__dict__() == other.__dict__()
def __iter__(self):
yield self.label
for child in self.children:
for gchild in child:
yield gchild
def dup(self):
return Tree(self.label, [c.dup() for c in self.children])
def add(self, other):
tree = self.dup()
tree.children.append(other)
return tree
def remove(self, node):
tree = self.dup()
for child in list(tree.children):
tree.children.remove(child)
if child.label == node:
break
tree.children.append(child.remove(node))
return tree
def from_pov(self, from_node):
stack = [self]
visited = set()
while stack:
tree = stack.pop(0)
if tree.label in visited:
continue
visited.add(tree.label)
if from_node == tree.label:
return tree
for child in tree.children:
stack.append(child.add(tree.remove(child.label)))
raise ValueError("Tree could not be reoriented")
def path_to(self, from_node, to_node):
reordered = self.from_pov(from_node)
stack = reordered.children
path = [from_node]
while path[-1] != to_node:
try:
tree = stack.pop()
except IndexError:
raise ValueError("No path found")
if to_node in tree:
path.append(tree.label)
stack = tree.children
return path
Version data entries
71 entries across 71 versions & 1 rubygems