Re: Node to first or last element of a sequential list in module list/xlist

[Bruno Haible <bruno@clisp.org>]

[Adding back bug-gnulib in CC.]

Hi Marc,

> > Yes, some algorithms need a second, temporary list. Not all algorithms
> > can be written to use the original list, be efficient in O() terms, and
> > be implementation-independent.
> >
> 
> Is there a fundamental reason why a list walking algorithm that both
> inserts and removes items is not possible with an arbitrary Gnulib list
> container? Obviously, the current API doesn't allow it. If it is just the
> limitation of an API that forces one to work with a second, temporary list,
> 
> Would it be possible for all list types to provide a
> 
> gl_list_node_t gl_list_remove_node_then (gl_list_t list, gl_list_node_t
> node, gl_list_node_t then)
> 
> that removes NODE from LIST and returns the node of that element
> represented by THEN before the removal.  The precondition is, of course,
> that THEN != NODE.  Furthermore, if THEN is NULL, NULL is returned.
> 
> A typical pattern would be:
> 
> for (gl_list_node_t i = gl_list_first_node (list); i != NULL;)
>   {
>     Fruit fruit;
>     if (is_apple (fruit))
>       node = gl_list_next_node (list, gl_list_next_node (list,
> gl_list_add_before (list, node, make_pear ())));
>     else if (is_peach (fruit))
>       node = gl_list_next_node (gl_list_add_after (list, node,
> make_strawberry ()));
>     else if (is_banana (fruit))
>       node = gl_list_remove_node_then (list, node, gl_list_next_node
> (list));
>   }
> (This is just a silly example for an algorithm that may want to replace
> elements by sublists (including sublists of length 0).)

This example makes it clear what you mean.

And what if the programmer wants to preserve not one 'then' node, but
several at once? One could generalize the function to

  void gl_list_remove_preserving_nodes (gl_list_t list, gl_list_node_t victim,
                                        size_t count, gl_list_node_t *to_preserve);

which would preserve the nodes to_preserve[0 .. count-1].

But for my feeling, programmers will not want to code like this. It is
so much easier to allocate a new list and destroy the old one afterwards.

Bruno