Python 访问母亲 class 字段
Python access mother class fields
在 python 中为树 class 编写迭代器时，我偶然发现了这个问题，我显然无法在不实例化迭代器实例的情况下访问母亲 class 的字段和方法引用一个已经存在的 Tree 实例，所以我总是需要调用像 "it.iterate(tree)" 这样的迭代器，这非常难看。我想知道是否有某种方法可以设计这些东西，因此不需要迭代器及其方法的实例引用。那么，我能否以某种方式从迭代器实例访问 Tree 实例的字段，而不将 Tree 实例的引用传递给迭代器？
########################################################################
# basic tree class, can be traversed bottom up from right hand corner
########################################################################
import sys
########################################################################
########################################################################
class Node:
"""!
@brief node class
"""
def __init__(self, pred=-1, ID=0, label=None):
self.sucs = list()
self.pred = pred
self.ID = ID
self.suc_count = 0
self.label = label
########################################################################
def make_suc(self, ID, label=None):
"""!
@brief generates new successor node, assigning it a unique ID
"""
self.suc_count += 1
sucID = ID+1
suc = Node(self, sucID, label)
self.sucs.append(suc)
return suc
########################################################################
########################################################################
class Tree:
"""!
@brief tree class
"""
def __init__(self):
self.root = Node()
self.allNodes = dict() # mapping from IDs (strings) to nodes
self.init()
self.leaves = list()
########################################################################
# initializes node dict
def init(self):
self.allNodes[0] = self.root
########################################################################
def find_node(self, ID):
"""!
@brief looks up a node's ID and returns the node itself
"""
return self.allNodes[ID]
########################################################################
def add(self, parent, label=None):
"""!
@brief adds a new node under parent with label label
"""
if parent != Node:
parent = self.find_node(parent)
suc = parent.make_suc(len(self.allNodes)-1, label)
self.allNodes[suc.ID] = suc
########################################################################
def traverse(self, node):
"""!
@brief traverses tree
"""
for suc in node.sucs:
self.traverse(suc)
print suc.label
########################################################################
def get_leaves(self, node):
"""!
@brief when called resets leveas field and build it up anew by
traversing tree and adding all leaves to it
"""
self.leaves = list()
self._find_leaves(node)
return self.leaves
########################################################################
def get_dominated(self, node, dom_nodes=[]):
"""!
@brief finds all dominated nodes
"""
for suc in node.sucs:
self.get_dominated(suc, dom_nodes)
dom_nodes.append(suc)
########################################################################
def _find_leaves(self, node):
"""!
@brief traverses tree in in order and adds all leaves to leaves field
last leaf in list will be right hand corner of tree, due to in
order travsersal
"""
if node.suc_count == 0:
self.leaves.append(node)
for suc in node.sucs:
self._find_leaves(suc)
########################################################################
class TreeRHCIterator:
"""!
@brief Right hand corner initialised iterator, traverses tree bottom
up, right to left
"""
def __init__(self, tree):
self.current = tree.get_leaves(tree.root)[-1] # last leaf is right corner
self.csi = len(self.current.sucs)-1 # right most index of sucs
self.visited = list() # visisted nodes
########################################################################
def begin(self, tree):
return tree.get_leaves(tree.root)[-1]
########################################################################
def end(self, tree):
return tree.root
########################################################################
def find_unvisited(self, node, tree):
"""!
@brief finds rightmost unvisited node transitively dominated by node
"""
leaves = tree.get_leaves(tree.root)
# loop through leaves from right to left, as leaves are listed
# in order, thus rightmost list elememt is rightmost leaf
for i in range(len(leaves)-1, -1, -1):
# return the first leaf, that has not been visited yet
if leaves[i] not in self.visited:
return leaves[i]
# return None if all leaves have been visited
return None
########################################################################
def go_up(self, node, tree):
"""!
@brief sets self.current to pred of self.current,
appends current node to visited nodes, reassignes csi
"""
self.visited.append(self.current)
self.current = self.current.pred
if self.current.sucs[0] not in self.visited:
self.current = self.find_unvisited(self.current, tree)
self.csi = len(self.current.sucs)-1
self.visited.append(self.current)
########################################################################
def iterate(self, tree):
"""!
@brief advances iterator
"""
# if current node is a leaf, go to its predecessor
if self.current.suc_count == 0 or self.current in self.visited:
self.go_up(self.current, tree)
# if current node is not a leaf, find the next unvisited
else:
self.current = self.find_unvisited(self.current, tree)
########################################################################
########################################################################
这样调用：
tree = Tree()
it = tree.TreeRHCIterator(tree)
end = it.end(tree)
while (it.current != end):
print it.current.label
it.iterate(tree)
编辑
实施标准迭代器协议后，我对它的工作原理有些困惑。在树上循环时以某种方式跳过起始节点。所以我做了一个测试 class 来研究行为，没有元素被跳过，即使迭代方法基本上以相同的方式工作。有人可以帮我解释一下吗？
重新设计的迭代器：
########################################################################
# RIGHT-HAND-CORNER-BOTTOM-UP-POST-ORDER-TRAVERSAL-ITERATOR
########################################################################
class RBPIter:
"""!
@brief Right hand corner initialised iterator, traverses tree bottom
up, right to left
"""
def __init__(self, tree):
self.current = tree.get_leaves(tree.root)[-1] # last leaf is right corner
self.csi = len(self.current.sucs)-1 # right most index of sucs
self.visited = list() # visisted nodes
self.tree = tree
self.label = self.current.label
########################################################################
def __iter__(self):
print "iter: ", self.label
return self
########################################################################
def begin(self):
return self.tree.get_leaves(self.tree.root)[-1]
########################################################################
def end(self):
return self.tree.root
########################################################################
def find_unvisited(self, node):
"""!
@brief finds rightmost unvisited node transitively dominated by node
"""
leaves = self.tree.get_leaves(self.tree.root)
# loop through leaves from right to left, as leaves are listed
# in order, thus rightmost list elememt is rightmost leaf
for i in range(len(leaves)-1, -1, -1):
# return the first leaf, that has not been visited yet
if leaves[i] not in self.visited:
self.label = leaves[i].label
return leaves[i]
# return None if all leaves have been visited
return None
########################################################################
def go_up(self, node):
"""!
@brief sets self.current to pred of self.current,
appends current node to visited nodes, reassignes csi
"""
self.visited.append(self.current)
self.current = self.current.pred
if self.current.sucs[0] not in self.visited:
self.current = self.find_unvisited(self.current)
self.label = self.current.label
self.csi = len(self.current.sucs)-1
self.visited.append(self.current)
########################################################################
def next(self):
"""!
@brief advances iterator
"""
print "next: ", self.label
# if current node is a leaf, go to its predecessor
if self.current.suc_count == 0 or self.current in self.visited:
self.go_up(self.current)
# if current node is not a leaf, find the next unvisited
else:
self.current = self.find_unvisited(self.current)
if self.current == self.end():
raise StopIteration
return self
########################################################################
########################################################################
对于以下测试文件，我得到以下输出：
tree1 = Tree()
tree1.add(0, "t")
tree1.add(1, "e")
tree1.add(2, "s")
tree1.add(3, "t")
tree1.add(2, "t")
tree1.add(5, "r")
tree1.add(6, "i")
tree1.add(7, "s")
tree1.add(6, "a")
for node in tree1.RBPIter(tree1):
print node.label
输出：
iter: a
next: a
s
next: s
i
next: i
r
next: r
t
next: t
t
next: t
s
next: s
e
next: e
t
next: t
这棵树看起来像这样：
！ 1 [一棵树]
因此，如您所见，"a" - 表示缺少右手角节点，我不明白为什么，因为迭代器方法 returns 第一个元素正确，如你可以在调试输出中看到。
你可以用这样的东西让迭代器看起来不错：
class TreeIter:
def __init__(self, parametersIfAny):
code godes here
def __iter__(self):
return self
def __next__(self):
code that makes the iteration
class Tree:
def __iter__(self):
return TreeIter(parametersIfAny)
然后你可以这样调用它：
tree = Tree()
for node in tree:
print node.label
如果您需要许多不同的迭代器，即中序、后序等。去年我不得不做这样的事情（尽管有图表）。我当时所做的是：
class PostOrderIter:
def __init__(self, tree):
self.tree = tree #and some more stuff
def __iter__(self):
return self
class PostOrder:
def __init__(self, tree):
self.tree = tree #and some more stuff
def __iter__(self):
return PostOrderIter(self.tree)
调用它：
for node in PostOrder(tree):
print node.label
在 python 中为树 class 编写迭代器时，我偶然发现了这个问题，我显然无法在不实例化迭代器实例的情况下访问母亲 class 的字段和方法引用一个已经存在的 Tree 实例，所以我总是需要调用像 "it.iterate(tree)" 这样的迭代器，这非常难看。我想知道是否有某种方法可以设计这些东西，因此不需要迭代器及其方法的实例引用。那么，我能否以某种方式从迭代器实例访问 Tree 实例的字段，而不将 Tree 实例的引用传递给迭代器？
########################################################################
# basic tree class, can be traversed bottom up from right hand corner
########################################################################
import sys
########################################################################
########################################################################
class Node:
"""!
@brief node class
"""
def __init__(self, pred=-1, ID=0, label=None):
self.sucs = list()
self.pred = pred
self.ID = ID
self.suc_count = 0
self.label = label
########################################################################
def make_suc(self, ID, label=None):
"""!
@brief generates new successor node, assigning it a unique ID
"""
self.suc_count += 1
sucID = ID+1
suc = Node(self, sucID, label)
self.sucs.append(suc)
return suc
########################################################################
########################################################################
class Tree:
"""!
@brief tree class
"""
def __init__(self):
self.root = Node()
self.allNodes = dict() # mapping from IDs (strings) to nodes
self.init()
self.leaves = list()
########################################################################
# initializes node dict
def init(self):
self.allNodes[0] = self.root
########################################################################
def find_node(self, ID):
"""!
@brief looks up a node's ID and returns the node itself
"""
return self.allNodes[ID]
########################################################################
def add(self, parent, label=None):
"""!
@brief adds a new node under parent with label label
"""
if parent != Node:
parent = self.find_node(parent)
suc = parent.make_suc(len(self.allNodes)-1, label)
self.allNodes[suc.ID] = suc
########################################################################
def traverse(self, node):
"""!
@brief traverses tree
"""
for suc in node.sucs:
self.traverse(suc)
print suc.label
########################################################################
def get_leaves(self, node):
"""!
@brief when called resets leveas field and build it up anew by
traversing tree and adding all leaves to it
"""
self.leaves = list()
self._find_leaves(node)
return self.leaves
########################################################################
def get_dominated(self, node, dom_nodes=[]):
"""!
@brief finds all dominated nodes
"""
for suc in node.sucs:
self.get_dominated(suc, dom_nodes)
dom_nodes.append(suc)
########################################################################
def _find_leaves(self, node):
"""!
@brief traverses tree in in order and adds all leaves to leaves field
last leaf in list will be right hand corner of tree, due to in
order travsersal
"""
if node.suc_count == 0:
self.leaves.append(node)
for suc in node.sucs:
self._find_leaves(suc)
########################################################################
class TreeRHCIterator:
"""!
@brief Right hand corner initialised iterator, traverses tree bottom
up, right to left
"""
def __init__(self, tree):
self.current = tree.get_leaves(tree.root)[-1] # last leaf is right corner
self.csi = len(self.current.sucs)-1 # right most index of sucs
self.visited = list() # visisted nodes
########################################################################
def begin(self, tree):
return tree.get_leaves(tree.root)[-1]
########################################################################
def end(self, tree):
return tree.root
########################################################################
def find_unvisited(self, node, tree):
"""!
@brief finds rightmost unvisited node transitively dominated by node
"""
leaves = tree.get_leaves(tree.root)
# loop through leaves from right to left, as leaves are listed
# in order, thus rightmost list elememt is rightmost leaf
for i in range(len(leaves)-1, -1, -1):
# return the first leaf, that has not been visited yet
if leaves[i] not in self.visited:
return leaves[i]
# return None if all leaves have been visited
return None
########################################################################
def go_up(self, node, tree):
"""!
@brief sets self.current to pred of self.current,
appends current node to visited nodes, reassignes csi
"""
self.visited.append(self.current)
self.current = self.current.pred
if self.current.sucs[0] not in self.visited:
self.current = self.find_unvisited(self.current, tree)
self.csi = len(self.current.sucs)-1
self.visited.append(self.current)
########################################################################
def iterate(self, tree):
"""!
@brief advances iterator
"""
# if current node is a leaf, go to its predecessor
if self.current.suc_count == 0 or self.current in self.visited:
self.go_up(self.current, tree)
# if current node is not a leaf, find the next unvisited
else:
self.current = self.find_unvisited(self.current, tree)
########################################################################
########################################################################
这样调用：
tree = Tree()
it = tree.TreeRHCIterator(tree)
end = it.end(tree)
while (it.current != end):
print it.current.label
it.iterate(tree)
编辑
实施标准迭代器协议后，我对它的工作原理有些困惑。在树上循环时以某种方式跳过起始节点。所以我做了一个测试 class 来研究行为，没有元素被跳过，即使迭代方法基本上以相同的方式工作。有人可以帮我解释一下吗？
重新设计的迭代器：
########################################################################
# RIGHT-HAND-CORNER-BOTTOM-UP-POST-ORDER-TRAVERSAL-ITERATOR
########################################################################
class RBPIter:
"""!
@brief Right hand corner initialised iterator, traverses tree bottom
up, right to left
"""
def __init__(self, tree):
self.current = tree.get_leaves(tree.root)[-1] # last leaf is right corner
self.csi = len(self.current.sucs)-1 # right most index of sucs
self.visited = list() # visisted nodes
self.tree = tree
self.label = self.current.label
########################################################################
def __iter__(self):
print "iter: ", self.label
return self
########################################################################
def begin(self):
return self.tree.get_leaves(self.tree.root)[-1]
########################################################################
def end(self):
return self.tree.root
########################################################################
def find_unvisited(self, node):
"""!
@brief finds rightmost unvisited node transitively dominated by node
"""
leaves = self.tree.get_leaves(self.tree.root)
# loop through leaves from right to left, as leaves are listed
# in order, thus rightmost list elememt is rightmost leaf
for i in range(len(leaves)-1, -1, -1):
# return the first leaf, that has not been visited yet
if leaves[i] not in self.visited:
self.label = leaves[i].label
return leaves[i]
# return None if all leaves have been visited
return None
########################################################################
def go_up(self, node):
"""!
@brief sets self.current to pred of self.current,
appends current node to visited nodes, reassignes csi
"""
self.visited.append(self.current)
self.current = self.current.pred
if self.current.sucs[0] not in self.visited:
self.current = self.find_unvisited(self.current)
self.label = self.current.label
self.csi = len(self.current.sucs)-1
self.visited.append(self.current)
########################################################################
def next(self):
"""!
@brief advances iterator
"""
print "next: ", self.label
# if current node is a leaf, go to its predecessor
if self.current.suc_count == 0 or self.current in self.visited:
self.go_up(self.current)
# if current node is not a leaf, find the next unvisited
else:
self.current = self.find_unvisited(self.current)
if self.current == self.end():
raise StopIteration
return self
########################################################################
########################################################################
对于以下测试文件，我得到以下输出：
tree1 = Tree()
tree1.add(0, "t")
tree1.add(1, "e")
tree1.add(2, "s")
tree1.add(3, "t")
tree1.add(2, "t")
tree1.add(5, "r")
tree1.add(6, "i")
tree1.add(7, "s")
tree1.add(6, "a")
for node in tree1.RBPIter(tree1):
print node.label
输出：
iter: a
next: a
s
next: s
i
next: i
r
next: r
t
next: t
t
next: t
s
next: s
e
next: e
t
next: t
这棵树看起来像这样：
！ 1 [一棵树]
因此，如您所见，"a" - 表示缺少右手角节点，我不明白为什么，因为迭代器方法 returns 第一个元素正确，如你可以在调试输出中看到。
你可以用这样的东西让迭代器看起来不错：
class TreeIter:
def __init__(self, parametersIfAny):
code godes here
def __iter__(self):
return self
def __next__(self):
code that makes the iteration
class Tree:
def __iter__(self):
return TreeIter(parametersIfAny)
然后你可以这样调用它：
tree = Tree()
for node in tree:
print node.label
如果您需要许多不同的迭代器，即中序、后序等。去年我不得不做这样的事情（尽管有图表）。我当时所做的是：
class PostOrderIter:
def __init__(self, tree):
self.tree = tree #and some more stuff
def __iter__(self):
return self
class PostOrder:
def __init__(self, tree):
self.tree = tree #and some more stuff
def __iter__(self):
return PostOrderIter(self.tree)
调用它：
for node in PostOrder(tree):
print node.label