I'd like to remove a single element from a std.container.DList. For that I need a range, but I'm not sure how to get a single element 'range'.

I thought something like this might work:

auto list = DList!int([1,2,3,4]);
auto r = list[];
while(r.front != 3)
   r.popFront;

list.remove(r.take(1));

But the the range returned by r.take(1) is not valid as an argument to DList.remove. What is the correct way to do this?

On Saturday, 6 October 2012 at 21:39:29 UTC, cal wrote:
> I'd like to remove a single element from a std.container.DList. For that I need a range, but I'm not sure how to get a single element 'range'.
>
> I thought something like this might work:
>
> auto list = DList!int([1,2,3,4]);
> auto r = list[];
> while(r.front != 3)
>    r.popFront;
>
> list.remove(r.take(1));
>
> But the the range returned by r.take(1) is not valid as an argument to DList.remove. What is the correct way to do this?

One solution:
list.linearRemove(list[].find(3).takeOne);

On Saturday, October 06, 2012 23:27:31 cal wrote:
> I'd like to remove a single element from a std.container.DList. For that I need a range, but I'm not sure how to get a single element 'range'.
> 
> I thought something like this might work:
> 
> auto list = DList!int([1,2,3,4]);
> auto r = list[];
> while(r.front != 3)
>     r.popFront;
> 
> list.remove(r.take(1));
> 
> But the the range returned by r.take(1) is not valid as an argument to DList.remove. What is the correct way to do this?

The correct way is to use find combined with take (which is what you're doing, except that you're not using find). So, something like this should work

void main()
{
    auto list = DList!int([1,2,3,4]);
    list.remove(find(list[], 3).take(1));
}


However, for some reason, this is indeed not working right now. It's a bug. Please report it.

But! If you use linearRemove, it _does_ work.

void main()
{
    auto list = DList!int([1,2,3,4]);
    list.linearRemove(find(list[], 3).take(1));
}

I have no idea why remove doesn't work with take (because it's supposed to), and I have no idea why remove isn't an alias to linearRemove (or vice versa). I would have thought that they'd be one and the same for linked lists, but maybe I'm missing something, since I haven't spent a lot of time thinking about it.

Regardless, report it as a bug. Using take on the range returned by a container should work for _all_ of the various remove functions for _all_ containers in std.container. If it doesn't, it's a bug.

- Jonathan M Davis

On Sunday, 7 October 2012 at 01:14:48 UTC, Jonathan M Davis wrote:
> The correct way is to use find combined with take (which is what you're doing,
> except that you're not using find). So, something like this should work
>
> void main()
> {
>     auto list = DList!int([1,2,3,4]);
>     list.remove(find(list[], 3).take(1));
> }
>
>
> However, for some reason, this is indeed not working right now. It's a bug.
> Please report it.

SList doesn't implement remove, so perhaps DList can only guarantee the required complexity when given the range defined in DList, and for other types of ranges, it can only guarantee linear complexity?

On Sunday, October 07, 2012 04:14:58 cal wrote:
> On Sunday, 7 October 2012 at 01:14:48 UTC, Jonathan M Davis wrote:
> > The correct way is to use find combined with take (which is
> > what you're doing,
> > except that you're not using find). So, something like this
> > should work
> > 
> > void main()
> > {
> > 
> >     auto list = DList!int([1,2,3,4]);
> >     list.remove(find(list[], 3).take(1));
> > 
> > }
> > 
> > 
> > However, for some reason, this is indeed not working right now.
> > It's a bug.
> > Please report it.
> 
> SList doesn't implement remove, so perhaps DList can only guarantee the required complexity when given the range defined in DList, and for other types of ranges, it can only guarantee linear complexity?

singly-linked lists and doubly-linked lists are completely different beasts. A singly-linked list can't do it sanely, because it has to traverse the list to find the previous node so that it adjust the links. A node in a doubly-linked list has a link to the previous node in the list instead of just the next node, so it doesn't have that problem. You can add and remove elements from anywhere in a doubly-linked list in O(1). And if you're dealing with iterators, it won't affect any iterators except if they point at the element being removed (so it's a stable remove). With ranges, it would affect the elements in the range, but unless you're removing an element which is at the front or end of a range, it shouldn't invalidate the range at all. And that can be gotten around by letting that node continue to exist and point to what was the next node in the list (in which case, it would go away once no more ranges referred to it - the GC makes doing that fairly easy).

So, I don't see any reason why remove wouldn't be stable or non-linear. It's actually kind of hard to make it _un_stable in this case. And actually, looking at the code, stableLinearRemove (and linearRemove is an alias for stableLinearRemove in this case) calls remove, so overall, this is a bit bizarre. Regardless, it's a bug that normal remove doesn't work with the result of take.

- Jonathan M Davis

On Sunday, 7 October 2012 at 02:54:44 UTC, Jonathan M Davis wrote:
> On Sunday, October 07, 2012 04:14:58 cal wrote:
>> On Sunday, 7 October 2012 at 01:14:48 UTC, Jonathan M Davis wrote:
>> > The correct way is to use find combined with take (which is
>> > what you're doing,
>> > except that you're not using find). So, something like this
>> > should work
>> > 
>> > void main()
>> > {
>> > 
>> >     auto list = DList!int([1,2,3,4]);
>> >     list.remove(find(list[], 3).take(1));
>> > 
>> > }
>> > 
>> > 
>> > However, for some reason, this is indeed not working right now.
>> > It's a bug.
>> > Please report it.
>> 
>> SList doesn't implement remove, so perhaps DList can only
>> guarantee the required complexity when given the range defined in
>> DList, and for other types of ranges, it can only guarantee
>> linear complexity?
>
> singly-linked lists and doubly-linked lists are completely different beasts. A
> singly-linked list can't do it sanely, because it has to traverse the list to
> find the previous node so that it adjust the links. A node in a doubly-linked
> list has a link to the previous node in the list instead of just the next
> node, so it doesn't have that problem. You can add and remove elements from
> anywhere in a doubly-linked list in O(1). And if you're dealing with
> iterators, it won't affect any iterators except if they point at the element
> being removed (so it's a stable remove). With ranges, it would affect the
> elements in the range, but unless you're removing an element which is at the
> front or end of a range, it shouldn't invalidate the range at all. And that
> can be gotten around by letting that node continue to exist and point to what
> was the next node in the list (in which case, it would go away once no more
> ranges referred to it - the GC makes doing that fairly easy).
>
> So, I don't see any reason why remove wouldn't be stable or non-linear. It's
> actually kind of hard to make it _un_stable in this case. And actually,
> looking at the code, stableLinearRemove (and linearRemove is an alias for
> stableLinearRemove in this case) calls remove, so overall, this is a bit
> bizarre. Regardless, it's a bug that normal remove doesn't work with the
> result of take.
>
> - Jonathan M Davis

Righto, i'll put in a ticket, thanks for the help.

> On Sunday, 7 October 2012 at 01:14:48 UTC, Jonathan M Davis wrote:
> Regardless, it's a bug that normal remove doesn't work with the result of take.

I guess this is also true of insertAfter and co? Should they accept the result of take? (Currently they don't)

On Sunday, October 07, 2012 06:54:25 cal wrote:
> > On Sunday, 7 October 2012 at 01:14:48 UTC, Jonathan M Davis
> > wrote:
> > Regardless, it's a bug that normal remove doesn't work with the
> > result of take.
> 
> I guess this is also true of insertAfter and co? Should they accept the result of take? (Currently they don't)

Any function on a container in std.container which takes a range from that container should accept the result of take or takeExactly. It's something that was overlooked in the initial design and added later, so it hasn't necessarily been added consistently. But without it, those functions can't operate on the an element or elements in a range without operating on every element after them in the entire container.

- Jonathan M Davis

On Sat, 2012-10-06 at 19:42 -0700, Jonathan M Davis wrote: […]
> singly-linked lists and doubly-linked lists are completely different beasts. A singly-linked list can't do it sanely, because it has to traverse the list to find the previous node so that it adjust the links. A node in a doubly-linked

Not sure about the D implementation, but in other languages all the singly-linked list iterator has to do to allow for removal is to maintain a "front foot"/"back foot" state. This is needed for insert as well, so it is already there.

> list has a link to the previous node in the list instead of just the next node, so it doesn't have that problem. You can add and remove elements from anywhere in a doubly-linked list in O(1). And if you're dealing with iterators, it won't affect any iterators except if they point at the element being removed (so it's a stable remove). With ranges, it would affect the elements in the range, but unless you're removing an element which is at the front or end of a range, it shouldn't invalidate the range at all. And that can be gotten around by letting that node continue to exist and point to what was the next node in the list (in which case, it would go away once no more ranges referred to it - the GC makes doing that fairly easy).

Removal from a singly-linked list can be O(1) as well, it depends whether you are deleting using an iterator in progress.

> So, I don't see any reason why remove wouldn't be stable or non-linear. It's actually kind of hard to make it _un_stable in this case. And actually, looking at the code, stableLinearRemove (and linearRemove is an alias for stableLinearRemove in this case) calls remove, so overall, this is a bit bizarre. Regardless, it's a bug that normal remove doesn't work with the result of take.
> 
> - Jonathan M Davis

-- 
Russel. ============================================================================= Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder@ekiga.net 41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel@winder.org.uk London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder

On Sunday, October 07, 2012 10:09:06 Russel Winder wrote:
> Removal from a singly-linked list can be O(1) as well, it depends whether you are deleting using an iterator in progress.

IIRC that dcollections' singly-linked list is like this, but std.container.SList definitely isn't. I'm not a big fan of singly-linked lists in the first place and tend to think that they're useless, but std.container's is particularly bad in that regard.

- Jonathan M Davis