We revisit our own recipe http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/136529 for generalized trees, expanding on the functionality via some metaclass trickery.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 | """
The Tree module implementing generalized trees.
"""
#Import generators.
from __future__ import generators
__version__ = '0.9.1'
__needs__ = '2.2'
__author__ = "G. Rodrigues"
#Classes
class MetaTree(type):
"""The MetaTree metaclass.
A metaclass governing the family of generalized trees parameterized
by a node class.
Minimal protocol description of parameter node class:
It's a class defining __iter__ (but check code below). The
initializer takes an iterable as argument. There is no defined order
of iteration over the subtrees - implementation is free to muck with
it."""
class MTree(object):
"""The mixin MTree class, containing generic tree methods."""
def isAtom(self):
"""Return True if it has no subtrees, False otherwise."""
if self:
#ToDo: Ask node class to implement __nonzero__ to avoid
#this test?
iterator = iter(self.subtrees)
try:
iterator.next()
except StopIteration:
ret = True
else:
ret = False
else:
ret = True
return ret
#The Tree iterators.
def __iter__(self):
"""The standard preorder traversal iterator."""
if self:
yield self.cargo
for subtree in self.subtrees:
for elem in subtree:
yield elem
def postorder(self):
"""Postorder traversal of a tree."""
if self:
for subtree in self.subtrees:
for elem in subtree.postorder():
yield elem
yield self.cargo
#The "inplace" iterators.
def presubtree(self):
"""Preorder iterator over the subtrees.
Warning: As always, do not use this iterator in a for loop
while altering the structure of the tree."""
if self:
yield self
for subtree in self.subtrees:
for tree in subtree.presubtree():
yield tree
def postsubtree(self):
"""Postorder iterator over the subtrees.
Warning: As always, do not use this iterator in a for loop
while altering the structure of the tree."""
if self:
for subtree in self.subtrees:
for tree in subtree.postsubtree():
yield tree
yield self
def copy(self, cls = None):
"""Shallow copy of a tree.
An extra class argument can be given to copy with a different
(tree) class. No checks are made on the class."""
if cls is None:
cls = self.__class__
if self:
subtrees = tuple([subtree.copy(cls) for subtree in \
self.subtrees])
return cls(self.cargo, *subtrees)
else:
return cls()
#Metaclass instance methods.
def __init__(cls, name, bases, dct):
"""The initializer."""
node = dct.get('Node')
#Replace Node attribute.
if node is not None:
#Some early protocol checks.
if not callable(node):
raise TypeError("Object not callable", node)
try:
node.__iter__
except AttributeError:
#Valid node classes like list, tuple dont have __iter__.
#ToDo: Ditch this (brittle) test in 2.3.
try:
iter(node(()))
except TypeError:
raise TypeError("Object does not define __iter__", node)
del dct['Node']
else:
#Default node class.
node = list
#Call super initializer.
super(MetaTree, cls).__init__(name, bases, dct)
#Set *private* attribute.
cls.__node = node
#Inject methods if class (or super classes) do not define it.
for name in MetaTree.MTree.__dict__:
generic = MetaTree.MTree.__dict__[name]
#Filter out attributes added at class creation.
if callable(generic):
try:
#Warning: possiblity of Metaclass giving falses?
getattr(cls, name)
except AttributeError:
setattr(cls, name, generic)
#Properties.
def __get_node(cls):
return cls.__node
Node = property(__get_node,
doc = "The Node class of the tree class object.")
def __repr__(cls):
return "%s<Node:%r>" % (cls.__name__,
cls.Node)
def clone(cls, name, node):
"""Return a clone *child* class with a different Node class."""
bases, dct = (cls,), {'Node':node}
return cls.__class__(name, bases, dct)
#Object to tackle default arguments.
_NullArg = []
class MutableTree(object):
"""The generalized MutableTree tree class.
Minimal protocol description of tree classes:
Two attributes: cargo, subtrees. The subtrees attribute returns an
iterable over the subtrees of the tree.
If the tree is empty, fetching its cargo raises TypeError.
In the current implementation you can rebind subtrees or delete it
altogether. You can also do completely foolish things like adding
garbage to it. To prevent these things just write an apropriate
node class and/or a subtrees descriptor. Or pay attention to what
you are doing."""
__metaclass__ = MetaTree
def __init__(self, cargo = _NullArg, *subtrees):
"""The initializer."""
super(MutableTree, self).__init__(cargo, *subtrees)
if cargo is not _NullArg:
self.__cargo = cargo
self.subtrees = self.__class__.Node(subtrees)
else:
self.subtrees = self.__class__.Node(())
#Properties.
def __get_cargo(self):
try:
return self.__cargo
except AttributeError:
#Instead of AttributeError, as in earlier recipe, we
#raise TypeError - makes much more sense.
raise TypeError("Cannot fetch cargo of empty tree.")
def __set_cargo(self, cargo):
self.__cargo = cargo
cargo = property(__get_cargo,
__set_cargo,
doc = "The cargo (top node) of the tree.")
def __nonzero__(self):
"""Return True if it is the empty Tree, False otherwise."""
try:
self.cargo
except TypeError:
return False
else:
return True
def __repr__(self):
if self:
if self.isAtom():
ret = "%s" % self.cargo
else:
contents = [repr(subtree) for subtree in self.subtrees]
ret = "%s, %s" % (self.cargo, ", ".join(contents))
else:
ret = ''
return "%s<%s>" % (self.__class__.__name__,
ret)
|
In our (looong) recipe http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/136529 we gave implementations of binary and generalized trees. Looking at generalized trees, the implementation relied on a basic protocol consisting in two attributes cargo and subtrees (there called childs) to present an abstract (or mixin) class with all the generic methods. Two concrete implementations were presented, one for mutable trees and another for immutable ones. But staring at the code, the real difference between the two implementations was that the mutable used a list and the immutable used a tuple. In other words, only the type- of the subtrees attribute was different.
So, I started musing on how I could encapsulate and generalize. It became clear that what we have here is a family- of tree classes parameterized by another class (list, tuple, etc.) that describes the subtrees attribute. Once this is understood it is a small step in considering a metaclass governing this family of classes.
Notice also, that because we are using a metaclass we dont derive from some abstract tree class, we just inject the generic methods directly at class creation.
With the functionality in place you can create an immutable tree class (that is, you cannot alter the subtrees structure of the tree) in one line:
<pre> ImmutableTree = MutableTree.clone(ImmutableTree, tuple) </pre>
The recipe is, everything counted, about 220 lines long. The test code is just as long. For obvious reasons it was left out but the whole thingy works.
Have yourselves pythonic fun, G. Rodrigues