Re: Proposal for new functions in glib

[Owen Taylor <otaylor redhat com>]

Tim Janik <timj@gtk.org> writes:

> hi all,
> 
> i've composed a sample API for an n-way tree implementation in
> glib. i urge everyone to comment on this suggestion, since i'd
> like to get a basic imlementation going ASAP, so pavlov can
> start out with it in balsa. (we will need to make another glib
> release once the implementation has settled, in order to have
> something out there to base the upcoming balsa release on).
> 
> typedef enum
> {
>   G_TRAVERSE_PRE_ORDER,
>   G_TRAVERSE_POST_ORDER,
>   G_TRAVERSE_IN_ORDER,
>   G_TRAVERSE_LEVEL_ORDER
> } GTraverseType;

Hmmm, isn't adding the _TRAVERSE_ here unecessary breakage?
(For those not having glib.h at hand, GTree already uses:

typedef enum
{
  G_IN_ORDER,
  G_PRE_ORDER,
  G_POST_ORDER
} GTraverseType;
)

> typedef enum
> {
>   G_TRAVERSE_LEAFS_ONLY,
>   G_TRAVERSE_NON_LEAFS_ONLY
> } GTraverseFlags;
> 
> typedef void (*GNodeTraverseFunc) (Gnode   *node,
>                                    gpointer data);
> 
> typedef struct _GNode   GNode;
> 
> struct _GNode
> {
>   GNode *left;
>   GNode *right;
>   GNode *parent;
>   GNode *children;
>   
>   gpointer data;
> };
> 
> #define	G_NODE_IS_ROOT(node)    ((node)->parent == NULL && \
>                                  (node)->left == NULL && \
>                                  (node)->right == NULL)
> #define	G_NODE_IS_LEAF(node)	((node)->children == NULL)
> 
> 
> GNode* g_node_new (gpointer data);
> void   g_node_insert (GNode *parent,
>                       GNode *left_sibling /* may be NULL */,
>                       GNode *child);
> void  g_node_unlink (GNode *node); /* or g_node_remove() ? */
> void  g_node_destroy (GNode *node); /* acts recursive, pre-order */
> 
> /* returns 1 for root, 2 for first level children,
>  * 3 for children's children...
>  */
> guint g_node_depth (GNode *node);
 
We should probably provide macros/functions equivalent to:

#define g_list_previous(list)	((list) ? (((GList *)(list))->prev) : NULL)
#define g_list_next(list)	((list) ? (((GList *)(list))->next) : NULL)

Just for people who dislike ->'s. (On the other hand, the use
of g_list_first (list) in GtkPacker to mean 'list', is a bit
excessive...) 
 
> /* traversal function, assumes that `node' is root
>  * (only traverses `node' and its subtree).
>  * this function is just a high level interface to
>  * eight low level traversal functions, optimized for
>  * speed.
>  * (should we specify a `guint max_depth' here? that
>  *  would cause sixteen internal functions...)
>  */
> void  g_node_traverse (GNode             *node,
> 		       GTraverseType      order,
> 		       GTraverseFlags     flags,
>                        GNodeTraverseFunc  func,
>                        gpointer           data);
> 
> /* return the maximum tree height, this is an expensive operation, since
>  * we need to visit all nodes. this could be shortened by adding `guint height'
>  * to struct _GNode, but then again, this is not very often needed, and would
>  * make g_node_insert() more time consuming.
>  */
> guint g_node_max_height (GNode *node);

That all looks pretty reasonable. The only thing I sort of
object to is (guess? ;-), the name. We already have nodes
all over the place in GTK, is this type of node really
special enough to be GNode? Perhaps it is - it is a superset
of a GList.

(My best alternative is GHeirarchy; those of some political
 leanings might like GBush)

I think it will be a pretty useful data structure. One area
where it fits in nicely is manipulating XML-like heirarchical 
documents.

Regards,
                                        Owen