Re: g_tree_traverse deprecation

[Owen Taylor <otaylor redhat com>]

Sven Neumann <sven gimp org> writes:

> Hi,
> 
> 2001-11-26  Matthias Clasen  <matthiasc poet de>
>         
>         * glib/gnode.c (g_node_traverse): Implement G_LEVEL_ORDER correctly.
> 
>         * tests/node-test.c: Add a testcase for G_LEVEL_ORDER implementation.
> 
>         * glib/gtree.h: Mark g_tree_traverse() as deprecated. (#65343)
>         
>         * glib/gtree.c (g_tree_traverse): Explain the deprecation in 
>         some detail.
> 
> the explanation reads as follows:
> 
>  * Calls the given function for each node in the GTree. This function is
>  * deprecated, since the order of a balanced tree is somewhat arbitrary.
>  * If you just want to visit all nodes in some order, use g_tree_foreach() 
>  * instead. If you really need to visit nodes in a specific order, consider
>  * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
> 
> 
> why on earth is the order of a balanced binary tree arbitrary? The opposite
> is true: the order is determined by the key_compare_func that was passed
> to g_tree_new(). I think having a function g_tree_foreach() that traverses
> the key in an arbitrary order makes sense, but deprecating g_tree_traverse()
> renders the whole GTree datatype useless. Using an N-ary Tree is definitely
> no alternative since an n-ary tree is not self-sorting.
> 
> For certain uses, there are certain container types that are suited best.
> A hash table is a good choice for data that needs to be looked up quickly
> and doesn't need to be accessed in a well-defined order. Lists are good
> suited for data that needs to be in order but doesn't need to be accessed
> randomly. Trees used to be container type of choice for data that needs 
> to be accessed in a certain order as well as "randomly". Without
> g_tree_traverse(), GTree is not different to a GHash from a usage point
> of view. Why did we choose to make this very useful container useless?
> 
> I'd strongly vote for reverting this change. If I remember correctly, 
> some of the traversal functions have been implemented wrong in 1.2.
> This needs to be fixed of course, but deprecating a perfectly fine
> interface without providing an alternative is not a good solution.

foreach() traverses in sorted order.  traverse() traverses in an order
that depends on the structure of the binary tree, which is useless.

Regards,
                                        Owen