C Extension Questions (Binary Trees)

[achatham at hotmail.com]

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?

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.

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.

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


Sent via Deja.com http://www.deja.com/
Before you buy.