Welcome, guest | Sign In | My Account | Store | Cart

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.

Python, 221 lines
  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 don’t 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