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