etienne buxin wrote:
> hi,
>
> i'd like to use a structure similar to glib's Nary tree, but with the difference
>that many parent
> nodes can share one or several children nodes.
> any clue?
This is going to be rather difficult.
Unless you enforce a policy that only sibling-nodes can share child
nodes, you are going to have a lot of trouble. Even then, any trivial
operation on a child node (e.g., remove from tree) will require
searching over the full set of parent-siblings and checking the child
pointers against the full set of siblings for the child-node.
Don't do it.
If a fellow developer at work suggested such a data-storage approach, I
would require a tone of convincing that this was a reasonable thing to do.
If you do, I strongly suggest that you do not base it off of the current
glib n-ary tree implimentation. At a minimum, I would enforce a policy
that a node has a numbered depth N, that all children are depth N+1 and
parents are N-1. This may seem obvious, but in a multi-parent scenario
it would be easy to violate if moving a set of nodes within the tree.
A suggested structure:
struct eb_manymany {
uint node_level;
uint num_parents;
uint num_par_max;
struct eb_manymany **par_ptr_array;
uint num_children;
uint num_child_max;
struct eb_manymany **chd_ptr_array;
gpointer data;
}
That lets you reference count the parents and children, so that, for
example, when removing a node you can go to all the parents and remove
that child from their list of children.
The _max allows dynamix allocation of the pointer arrays, if you
previously allocated space for 12 children and need a 13th, you can
reallocate that array up to size 24 or somthing, with 13 places occupied.
If the above doesn't make sense after a few readings, you're not ready
to tackle this. I have done a two-level parent-child that was
many-to-many, where entities were by definitions either parents or
children, and by the time I had the appropriate API and error checking
all in place it was very cumersome.
For example, what policy do you generically implement if a the last
parent of a node is freed? In my application, that meant that the child
was now a discard and could be freed, but that may or may not be
appropriate for a generic storage library. Specify a calllback for the
child node in that situation, defaulting to freeing? Complexity!
If you do get it working as infinite level many-to-many, please post the
code. :)
Eric
_______________________________________________
gtk-list mailing list
[EMAIL PROTECTED]
http://mail.gnome.org/mailman/listinfo/gtk-list
