[Tutor] Restricting the type of passed-in objects

[Roeland Rengelink]

VanL wrote:

> I am working on implementing a tree. 
> 
> First I am going to do it as a class.  A tree would be defined as one or 
> more treenodes.
> 
> My constructor looks like this:
> 
> class TreeNode:
>
>   def __init__(self, name=None, data=None, objparent=None, childobjects=[]):
>       if name: self.__label = name
>       if data: self.__data = data
>       if objparent: self.__parentlink = objparent
>       if childobjects: self.__childrenlist = childobjects
>
>
> Now here is my quandry:  I think that I would want to restrict the type 
> of passed-in childobjects.  In my way of thinking, anyone who wanted a 
> tree could either use the vanilla class or they could subclass 
> TreeNode.  Ideally, then, the only objects passed in (as parents or 
> children, with the possible exception of the parent to the root node) 
> would be TreeNode instances (or whatever the subclass is).
>

[..snip..]

> Alternatively, am I thinking about this in the wrong way?  Do I *really* 
> want to restrict the accepted types?  If I do, how can I structure this 
> thing?

I think an important question to ask here is how you want your clients
to use the Tree.

Are clients going to add Nodes by calling the constructor of TreeNode
directly?

Apart from worrying about the types of the children (which can be
checked with isinstance(object, class), but see below) you then have
to worry about some more difficult problems. For instance:

self in self.__parentlink.__childrenlist 

should always be true, except for the root object, which has no
parentlink

Suppose on the other hand that clients add a treenode with:

class TreeNode:
    ...
    def add_node(self, name, data):
        newnode = TreeNode(name=name, data=data, objparent=self)
	self.__childrenlist.append(newnode)
        return newnode

Then you don't have to worry at all about clients creating
TreeNodes with bogus parents and children.

So, how do you go about designing your Tree interface?

It depends on what you're going to use the tree for.

I can think of several different answers.

o The tree is going to be the underlying data structure for a
  sequence.  For example, an AVL-tree to implement a sorted list

o The tree is going to be the underlying data structure for a
  mapping. To make a UserDict with sorted keys for instance.
  
In these cases the interface to your tree is pretty much determined
by the interface to your sequence or mapping respectively.

Another possibility is that you want to be able to inherit
a particular class from a tree. For example:

class FileSystem(Tree):
    pass

In this case the fact that the object is a tree seems central to the use
of the object (while in the previous cases, it was an implementation
detail). 

Writing a general Tree object (or even defining an abstract interface)
usable in all these cases is very difficult (I'm not smart enough to
confidently use the word impossible).  Note, for example, that in the
'data-structure' cases, it is essential that the tree decides where a
new node is inserted, while in the FileSystem case the user decides
where a new node is inserted. E.g. In an AVL tree you add values to
the tree in a FileSystem you add nodes to a TreeNode (Directory)

If you want to write a Tree class that you can provitably use for both

class FileSystem(Tree):

and 

class AVLTree(Tree):

a possible route might be to first write FileSystem and AVLTree
classes and then see what code they have in common.

A note on typechecking in Python:

Checking whether an object is an instance of a given class in general
doesn't buy you much in terms of safety, and may cost you in terms of
usability.

For example:

def doit(obj):
    if isinstance(obj, DoableClass):
        return obj.dosomething()
    else:
        print "Sorry, can't do it"

There are two problems here.

Suppose somebody did:

obj = DoableClass()
obj.dosomething = None
doit(obj):

you will get an exception, despite your test.
On the other hand:

class AlsoDoable:
    def dosomething(self):
        ...
obj = AlsoDoable()
doit(obj)

will result in "Sorry can't do it", even if AlsoDoable.dosomething()
pefectly matches what you expect an obj passed to doit() to be able to
do. You loose polymorphism.

An alternative is:

def doit(obj):
    try:
        return obj.dosomething()
    except:
        print "Sorry, can't do it"

The "It's easier to ask forgiveness than permission"-idiom

Alex Martelli has written extensively on comp.lang.python on this
subject (Polymorphism). If you insist on doing checks then have a look
at:

http://aspn.activestate.com/ASPN/Python/Cookbook/Recipe/52291

for a "Look before you leap"-idiom that's polymorphic


Hope this helps,

Roeland Rengelink