C Extension Questions (Binary Trees)

[Michael P. Reilly]

achatham at hotmail.com wrote:
: I have been trying to work on an extension module in C, binary
: (search) trees. I know that you can do most of that stuff with lists or
: dictionaries, and I'm sure that someone has already created a tree data
: type, but I'm doing it mostly for practice (I have trouble coming up
: with my own examples). It has certainly given me a greater appreciation
: of how things work in Python: I now know a whole lot more about
: reference counting, attribute lookup, etc. And I have much greater
: respect for the built-in dictionary type (no matter how contrived my
: test cases are, a dictionary is still faster than my search trees by
: 10-20%).

: But I have some questions that I haven't been able to clear up:

: Question 1. I keep getting warnings from GCC (Redhat 6.1) such as:
: "tree.h: 34: warning: initialization from incompatible pointer type"
: I am not very fond of this warning, though things seem to work fine. The
: relevant parts of tree.h are:

: --------------------
: typedef struct {
:   PyObject_HEAD
:   PyObject *left;
:   PyObject *right;
:   PyObject *parent;
:   PyObject *key;
:   PyObject *data;
:   PyObject *current;
:   PyObject *func;
:   int nodes_in_tree;
: } treeobject;

: staticforward PyTypeObject TreeType;

: static PyObject *tree_insert(treeobject *self, PyObject *args);
: static PyObject *tree_search(treeobject *self, PyObject *args);
: static PyObject *tree_issibling(treeobject *self, PyObject *args);
: static PyObject *tree_successor(treeobject *self, PyObject *args);
: static PyObject *tree_predecessor(treeobject *self, PyObject *args);
: static PyObject *tree_remove(treeobject *self, PyObject *args);
: static PyObject *tree_map(treeobject *self, PyObject *args);
: static PyObject *tree_as_tuple(treeobject *self, PyObject *args);

: static struct PyMethodDef tree_methods[] =
: {
:   {"insert", tree_insert, METH_VARARGS},
:   {"issibling", tree_issibling, METH_VARARGS},
:   {"search", tree_search, METH_VARARGS},
:   {"succ", tree_successor, METH_VARARGS},
:   {"pred", tree_predecessor, METH_VARARGS},
:   {"remove", tree_remove, METH_VARARGS},
:   {"map", tree_map, METH_VARARGS},
:   {"datatuple", tree_as_tuple, METH_VARARGS},
:   {NULL, NULL}
: };
: -------------------

: The warnings are from the assignments in tree_methods. Every one (except
: {NULL, NULL}) generates that warning. How can I get rid of it?

Change the prototypes so the "self" argument is (PyObject *), or cast
the function as "PyCFunction":
  {"map", (PyCFunction),tree_map, METH_VARARGS},

: Question 2: Is there a way to override "map"? I created a nice little
: __getitem__ function for the tree class which works by getting the
: leftmost node in the tree if the index is 0, or the successor to the
: last item if the index > 0, so I can do something like "for x in T:
: print x.data" to print out all the data elements in the tree using an
: inorder traversal. The only problem is that repeatedly calling successor
: is not a very efficient way to do an inorder traversal of a tree. For
: __getitem__ I really don't have a choice about doing it that way, since
: it's hard to store the call stack necessary to do the recursive
: traversal between calls of __getitem__. But for "map", it would make
: more sense to do that, since it's a single call. But from what I can
: tell, map just called __getitem__ on its own until it gets an
: IndexError. This isn't such a big deal, since I just made a member
: function "map", but it'd be nice to override the real one.

The only ways would be to create a method which works like map() and to
use that instead, or to write your own version of map.  The built-in
functions "map", "filter" and "reduce" all access the object using
"__getitem__".

: Question 3: A minor question. How do I get member variables to show up
: when I do "dir(T)"? All I get is a list of methods, when I know that
: T.left is a valid reference (it works fine). Or maybe I'm just too tired
: and "dir()" doesn't show variables normally.

The dir() function access the "__members__" and "__methods__" attributes
of a C extension object.  Each should return a list of strings that are
the names of the attributes.  Below is a code fragment to help.

  static PyObject *
  tree_getattr(PyObject *self, char *attrname)
    {
      ...
      else if (strcmp(attrname, "__members__") == 0)
        return Py_BuildValue("[sssssss]",
           "data", "current", "func", "key", "left", "parent", "right",
        );
      else  /* used for __methods__ too */
        return Py_FindMethod(tree_methods, self, attrname);
      ...
    }

: Again, it's not like I really _need_ this thing working, but I'd like to
: at least get these things straight. And so far the files for this data
: structure have turned out larger than any single Python program I've
: ever written! Yeah, I'm a newbie :)

: Thanks,
: Andrew