Encapsulating mutable objects with special structure in Python

Question

I am writing a library for working with special types of trees, called Foo trees. A Foo tree has very special structure. There some operations, called bar and baz, which only make sense on Foo trees. So I'm designing a FooTree class to represent Foo trees.

To construct a FooTree instance, one might pass some object representing a tree. This object will be checked for special structure and stored internally:

class FooTree(object):

    def __init__(self, tree):
        ... # check that tree is a valid Foo tree
        self._tree = tree

    def bar(self):
        # operation that only makes sense on a foo tree

The problem is: what if I construct a FooTree from a mutable object? For example, say Tree is a type whose instances are mutable:

tree = Tree()
... # build a valid Foo tree
foo_tree = FooTree(tree)
tree.remove_node(0) # tree is no longer a Foo tree

Since tree is no longer a valid Foo tree, and foo_tree wraps a reference to tree, foo_tree is no longer valid.

Instead I might copy the tree when creating a FooTree:

class FooTree(object):

    def __init__(self, tree):
        ... # check that tree is a valid Foo tree
        self._tree = tree.copy()

    def bar(self):
        # operation that only makes sense on a foo tree

This solves the problem, but creates a new one: Foo trees are typically very large, so copying them is expensive.

What patterns exist for creating FooTree objects from Tree objects, without copying and without the mutability problem?

For example, I might have FooTree accept a callable which produces a Tree:

class FooTreeBuilder(object):
    def __init__(self, data):
        self.data = data

    def __call__(self):
        tree = Tree()
        ... # build tree from self.data
        return tree

class FooTree(object):

    def __init__(self, builder):
        self._tree = builder()

builder = FooTreeBuilder(data)
foo_tree = FooTree(builder)

Are there any better approaches? I'm specifically looking for approaches that lend well to Python implementations.

Answer 1

some options are:

• using immutable trees as basic data structure
• using a builder or mutation operations to construct a FooTree without needing a Tree
• copying the input tree (which is good practice unless you have really big data and performance issues)

Note that by builder I mean the builder pattern as described by Joshua Bloch. (Long article, but the design issue is relevant for Python just as it is for Java.) Your Builder callable does not really mitigate the problem, because if a user of FooTree already has a Tree, they will just call FooTree(lambda: myTree) and thus you'll have the mutability problem again.

The builder pattern (or making making FooTree mutable), on the other hand, allow your users to create FooTrees directly without needing a Tree first.

and the best choice depends on:

• whether Tree is a class that you can design (and make immutable) as opposed to using something that is given.
• in your application domain: do trees change often or is immutability actually a good abstraction?
• how much separation you want between your own FooTrees and the other Trees. Maybe copying the tree has good side benefits like using a specialized data structure for your own trees.
• do you actually need trees anyways? are they your given input material? or would a solution without the Tree class make any sense?

All of this is independent of the language who are using and making it Pythonic is a matter of implementing the chosen design.