How do you correctly implement a bidirectional range on a linked list?

I have a linked list implementation and I've added a range interface to it but after a while I've realized it not quite right. The problem is when I call the save method of the forward range interface I don't get a copy I only get another view to the same state. So when i remove nodes from the original list the range becomes invalid.

How can you implement such a range over a type whose state is accessed via pointers?

Here's my implementation:

https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d#L533

On Monday, 6 July 2015 at 20:50:19 UTC, Gary Willoughby wrote:
> The problem is when I call the save method of the forward range interface I don't get a copy I only get another view to the same state. So when i remove nodes from the original list the range becomes invalid.
>

This is why modifying a sequence while iterating over it is generally forbidden; there's no good way to make it work. You could duplicate the entire list for each range, but that's expensive for the usual case of simply reading the list.

Forward ranges don't require that ranges be independent of the data they iterate over [1]:

> Saving a range is not duplicating it; in the example above, r1
> and r2 still refer to the same underlying data. They just
> navigate that data independently.

IMO your implementation is fine.

[1]: http://dlang.org/phobos/std_range_primitives.html#isForwardRange

On Monday, 6 July 2015 at 20:50:19 UTC, Gary Willoughby wrote:
> How do you correctly implement a bidirectional range on a linked list?
>
> I have a linked list implementation and I've added a range interface to it but after a while I've realized it not quite right. The problem is when I call the save method of the forward range interface I don't get a copy I only get another view to the same state. So when i remove nodes from the original list the range becomes invalid.
>
> How can you implement such a range over a type whose state is accessed via pointers?
>
> Here's my implementation:
>
> https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d#L533

There's no requirement for a range to stay valid when the underlying container changes. std.container defines "stable" variants of the various insertion and removal operations. They promise not to invalidate any ranges. When the unstable variants are used, it's to be expected that ranges are invalidated.

To make your removal methods stable, it may be enough to not free the removed node. That is, don't do this:
https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection

There's a doubly linked list in phobos: std.container.dlist; maybe look how things are done there:
https://github.com/D-Programming-Language/phobos/blob/master/std/container/dlist.d

Off topic: I think `@trusted:` is horrible. It's easy to forget that you're in a @trusted environment when editing things later. And even worse, you're trusting everything that's passed through template parameters.

On Monday, 6 July 2015 at 21:58:31 UTC, anonymous wrote:
> To make your removal methods stable, it may be enough to not free the removed node. That is, don't do this:
> https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection

Looks like I messed up the URL. Here's the right one:

https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d#L205-L206

On Monday, July 06, 2015 21:58:30 anonymous via Digitalmars-d-learn wrote:
> Off topic: I think `@trusted:` is horrible. It's easy to forget that you're in a @trusted environment when editing things later. And even worse, you're trusting everything that's passed through template parameters.

This is why you almost never use @trusted on templated functions. You should
_never_ mark anything with @trusted unless you can guarantee that it's
actually @safe. @safe is inferred for templated functions, so unless you're
doing @system operations in a templated function, there is no need for
@trusted, and if you are doing @system operations, then they need to be
segregated in a way that you can mark that section of code as @trusted
and guarantee that it's @safe regardless of what the template argument is.
But you should _never_ mark code as @trusted if it involves calling
functions that you can't guarantee are @safe, which almost always means that
you should not mark code which calls functions on template arguments as
@trusted.

That being said, @trusted is very much a necessity in certain types of code, so it would be really bad if we didn't have it. But if you're marking much code as @trusted, or if you're marking templated code as @trusted, then you really need to be examining what you're doing. Very little code should need to be marked as @trusted, and every time that it is, you need to be able to absolutely guarantee that it's actually @safe in spite of the @system operations that you're doing in that code.

- Jonathan M Davis

On Tuesday, 7 July 2015 at 09:35:12 UTC, Jonathan M Davis wrote:
> This is why you almost never use @trusted on templated functions. You should
> _never_ mark anything with @trusted unless you can guarantee that it's
> actually @safe. @safe is inferred for templated functions, so unless you're
> doing @system operations in a templated function, there is no need for
> @trusted, and if you are doing @system operations, then they need to be
> segregated in a way that you can mark that section of code as @trusted
> and guarantee that it's @safe regardless of what the template argument is.
> But you should _never_ mark code as @trusted if it involves calling
> functions that you can't guarantee are @safe, which almost always means that
> you should not mark code which calls functions on template arguments as
> @trusted.
>
> That being said, @trusted is very much a necessity in certain types of code, so it would be really bad if we didn't have it. But if you're marking much code as @trusted, or if you're marking templated code as @trusted, then you really need to be examining what you're doing. Very little code should need to be marked as @trusted, and every time that it is, you need to be able to absolutely guarantee that it's actually @safe in spite of the @system operations that you're doing in that code.
>
> - Jonathan M Davis

Thanks for the advice.