Re: Splay trees

[Soeren Sandmann <sandmann daimi au dk>]

Josh MacDonald writes:

> Generally speaking, I like the sound of this propsal.  -josh

What about adding the following to glib.h:

typedef struct _GBinaryTree GBinaryTree;

struct _GBinaryTree {
	GBinaryTree *left;
	GBinaryTree*right;
};

#define g_binary_tree_rotate_left (node)   G_STMT_START { \
   GBinaryTree *_right = (GBinaryTree) node->right; \
   (GBinaryTree) node->right = _right->left; \
   _right->left = (GBinaryTree) node; \
   (GBinaryTree) node = _right; \
} G_STMT_END

#define g_binary_tree_rotate_right (node)   G_STMT_START { \
   GBinaryTree *_left = (GBinaryTree) node->left; \
   (GBinaryTree) node->left = _left->right; \
   _left->right = (GBinaryTree) node; \
   (GBinaryTree) node = _left; \
} G_STMT_END

gint g_binary_tree_traverse (GBinaryTree *node,
                             GTraverseFunc traverse_func,
                             GTraverseType traverse_type,
                             gpointer data);
gint g_binary_tree_lookup (GBinaryTree *node,
                           GCompareFunc compare,
                           gpointer key);
gint g_binary_tree_count (GBinaryTree *node);
gint g_binary_tree_height (GBinaryTree *node);

and then have a new file called gbinarytree.c that defines the above
functions.