We need to rethink remove in std.container

[Steven Schveighoffer]

On Wed, 23 Feb 2011 08:33:03 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 2/22/11 8:41 AM, Steven Schveighoffer wrote:
>> On Tue, 22 Feb 2011 09:23:00 -0500, Andrei Alexandrescu
>> <SeeWebsiteForEmail at erdani.org> wrote:

>>> This may as well be The Great Unification that was needed to converge
>>> std.container with dcollections in a harmonious whole.
>>
>> I'm not sure what to think of this ;) Is this a "oh what could have
>> been" statement or a "let's reopen negotiations" statement?
>>
>> Note, I would love for dcollections to be mainstream Phobos, but I have
>> accepted the current reality and am fine with the way things are now  
>> too.
>
> Absolutely, and your collaboration on e.g. RedBlackTree and others is  
> very much appreciated.
>
> The way I was thinking is, there would a lot of convergence if  
> dcollections wiped the notion of "cursor" and replaced it with takeOne  
> throughout. One obvious objection to the range/cursor design is there  
> are two abstractions to deal with instead of one. I had the intuition  
> that ranges should be enough, but was not quite able to substantiate it  
> fully until just about now. With take, takeExactly, and takeOne, it  
> seems that indeed there is only need for the range interface, and that  
> particular range types can replace cursors.

I don't think this is possible.  When passing a range to a container for  
removal, the container needs to access the underlying implementation (e.g.  
pointer to tree node) in order to immediately know what element is being  
removed.  The takeOne range you propose does not allow this, you can't get  
at the underlying range.  Even if you could, only takeOne!(myrangetype)  
would work, which leaves us right back at supporting a small number of  
specific ranges.

In addition, a cursor points to one element, a range points to multiple  
elements.  *conceptually* takeOne is the same, but it still stores the  
range internally, so it's actually more expensive than a range to pass  
around (additional _empty member).

I was thinking more along the lines of ranges being able to generate  
cursors if it makes sense (i.e. base range is a range of the container).   
Dcollections already supports this with the two accessors begin() and  
end().  We might also need a last() which gets the last valid element in  
the range.  This would be akin to back().

Here is what I was thinking that can help with unifying interface.  I'll  
just show you as a code snippet:

void remove(C)(C c) if (is(C == mycursortype))
{
    // since we know the structure of c, we can use it to remove the  
element from the container
}

void remove(R)(R r) if (is(R == myrangetype))
{
   // possibly can be optimized
}

void remove(R)(R r) if (!is(R == myrangetype) && isInputRange!R &&  
is(typeof(r.begin) == mycursortype))
{
   while(!r.empty)
   {
     auto c = r.begin;
     r.popFront();
     remove(c);
   }
}

If wrapper ranges can "forward" the begin and end functions through their  
API, then you can construct arbitrary ranges that will be accepted as  
parameters to remove.  We could potentially add forwarding functions to  
all wrapper ranges, or we could pick ones that make the most sense (like  
take).

In addition, dcollections (and any collection that can verify its  
endpoints and cursor membership, SList obviously cannot) allows slicing  
based on cursors in a limited fashion.  Therefore, this allows  
constructing ranges from cursors if you have the original container.

As an example of what this could allow (assuming retro and take forward  
the begin(), end() and last() methods):

container.remove(take(retro(container[]), 5)); // remove the last 5  
elements from the container.

>
> I realize that there are other major differences in design between  
> dcollections and std.container, probably the largest one being the use  
> of a hierarchy vs. free-floating types, so probably full unification is  
> still not possible or quite remote. Nevertheless, keeping the  
> communication channels open would make both libraries better and all of  
> us a bit wiser.

As I've said in the past, the interface hierarchy is not critical at the  
moment because D has very little shared library support.  I'm willing to  
remove the interfaces as long as the types remain classes (which I believe  
you are more agreeable with lately).  This allows the interfaces to be  
added on later if it makes sense.

The cursor concept has to stay though.

-Steve