[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Marc Nieper-Wißkirchen
Subject: Re: Node to first or last element of a sequential list in module list/xlist
Date: Mon, 5 Apr 2021 12:20:47 +0200

Hi Bruno,

Am Mo., 5. Apr. 2021 um 04:45 Uhr schrieb Bruno Haible <bruno@clisp.org>:
[Adding back bug-gnulib in CC.]

> 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].

I think there is a conceptual difference between preserving a single node and preserving an arbitrary number of nodes. The point is that gl_list_add_before and gl_list_add_after, which also mutate the list, return a single node from where the algorithm can continue (as the loop above shows). So it is one thing to ask for gl_list_remove_node to return a single valid node from where an iteration can proceed but quite a different thing to ask it to preserve an arbitrary number of nodes.

Instead of the THEN node being arbitrary, it could also make sense to force it to be the node before or after, i.e. to have gl_list_remove_node_next and gl_list_remove_node_previous.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]