Greetings!

This is my first post here; I'm hoping to be able to help as well as be helped. However, for now, I'd like to start off with a question.

I am writing a program to do proofs in sentential logic. I've got a parser that correctly imports text such as "(a&b)|c" into a binary tree structure in memory.

I've also written an iterator structure and set of functions, so that I can visit each node in order (with the order being left-to-right, same as the text the tree came from). Right now, it does work. But it seems like a kludge to me -- there must be a somewhat more elegant solution, although I'm at a loss to find it.

bintree.h declares 5 functions related to the iterator (iter_prev() is not implemented yet):

The function iter_next() is supposed to return the next iterator, going from left to right, such that you can write a piece of code likeCode:/* initialize an iterator, attaching with root as node * returns: newly allocated iterator * side effects: none */ bintree_iter_t *make_iter( node_t *node ); /* move the iterator to the next node. * Returns: node at new location, or NULL if no more nodes */ node_t *iter_next( bintree_iter_t *iter ); /* move the iterator to the previous node. * Returns: node at previous location, or NULL if already at root */ /* WARNING: UNIMPLEMENTED! */ node_t *iter_prev( bintree_iter_t *iter ); /* get the node at the current location * Returns: current node */ node_t *iter_node(bintree_iter_t *iter); /* free the iterator. */ void free_iter( bintree_iter_t *iter );

and do_something_to() will be run once for each node, in order.Code:bintree_iter_t *iter = make_iter(some_tree); while( iter_next(iter) != NULL ) { do_something_to( iter_node(iter) ); }

This is the code for iter_next(), and the data structure in use:

My strategy was a case analysis, based on keeping track of what direction I went down (and came back up).Code:/* this is in bintree.c */ typedef struct bintree_iter_s bintree_iter_t; /* copied from bintree.h */ struct bintree_iter_s { node_t *current; /* current node being looked at */ int depth; /* depth within the tree */ node_next_t *path; /* a stack of paths taken thus far. Defaults to 100 items. */ int path_len; /* total # of spots in the path stack. */ int pathc; /* current spot in the path stack. */ int up; /* -1 = left, 0 = neither, 1 = right */ }; /* move the iterator to the next node. * Returns: node at new location, or NULL if no more nodes */ node_t *iter_next( bintree_iter_t *iter ) { char l = 0, r = 0; /* we could go left/ we could go right */ /* check for our special marker (see below) */ if( iter->up == 37) return NULL; /* try left. */ left: while( iter->up != -1 && iter->current->left != NULL ) { l = 1; /* we could go left. */ iter->current = iter->current->left; iter->depth++; iter->up = 0; iter_push(iter, left); } if( l == 1 ) /* we were able to go left some */ return iter->current; /* try right. */ if( iter->up != 1 && iter->current->right != NULL ) { r = 1; /* we could go left. */ iter->current = iter->current->right; iter->depth++; iter->up = 0; iter_push(iter, right); if( iter->current->left != NULL ) goto left; /* we may be able to go right as well, after going left after this. That's recursive, so avoid (real) recursion with a goto. */ return iter->current; } /* try up */ do { if( iter->depth == 0 ) /* can't go up, either. Special case: only one node. */ { if( iter->up == 0 ) /*we haven't come up */ { iter->up = 37; /* arbitrary marker that we did this last time. */ return iter->current; /* but we do want to get the one node with node_next() ;) */ } else /* we did come up, so we must be done. */ return NULL; } iter->current = iter->current->parent; iter->depth--; if( iter->path[iter->pathc-1] == left ) iter->up = -1; else iter->up = 1; iter->pathc--; } while ( iter->path[iter->pathc] != left ); return iter->current; }

The code, however, is just horrid (as you can see). Using recursion, a function that iterates through the entire tree is relatively painless (then again, I happen to like Scheme!). Writing one in an iterative fashion turns out to be a pain.

I uploaded a tarball of all my sources on this program so far. The files of interest would be test/bintree_test.c (a bit of test code for the tree), bintree.h, and bintree.c. Just compile those together, and if it's working right you should get "123456789ABCDEFG" as output. Anything else is an error.

Does anyone have any ideas that might make this a little cleaner?