Andrei Alexandrescu wrote:

> On 05/26/2010 06:07 PM, Jonathan M Davis wrote:
>> Looks interesting overall. There is one function, however, which makes no
>> sense to me: removeElement()/stableRemoveElement().
>>
>> So, it basically removes a random element from the container? It could be quite consistent as to which element it removes from the container (it being implementation-dependent), but effectively, it removes a random element? What's the point of that? I can't remember the last time - if ever - that I wanted to remove an element from a container and I didn't care which. Or am I misunderstanding what it does?
>>
>> - Jonathan M Davis
> 
> If the container is a worklist with items to work on, it sometimes doesn't matter in which order you extract them.
> 
> Andrei

Well, my first reaction would be that that would be needed rarely enough that there's no point in putting it in the API. You could just use removeFront() or removeBack(), or you could grab a random element from the container and remove that. But maybe there are container types where it really makes sense, and having it in the API could be useful. Still, it strikes me as a really weird function to have. Of course, if you really think that it's going to be useful, leave it in. Unlike pretty much all the others though, it's not one I ever expect to use.

- Jonathan M Davis

On 05/26/2010 08:30 PM, Jonathan M Davis wrote:
> Andrei Alexandrescu wrote:
>
>> On 05/26/2010 06:07 PM, Jonathan M Davis wrote:
>>> Looks interesting overall. There is one function, however, which makes no
>>> sense to me: removeElement()/stableRemoveElement().
>>>
>>> So, it basically removes a random element from the container? It could be
>>> quite consistent as to which element it removes from the container (it
>>> being implementation-dependent), but effectively, it removes a random
>>> element? What's the point of that? I can't remember the last time - if
>>> ever - that I wanted to remove an element from a container and I didn't
>>> care which. Or am I misunderstanding what it does?
>>>
>>> - Jonathan M Davis
>>
>> If the container is a worklist with items to work on, it sometimes
>> doesn't matter in which order you extract them.
>>
>> Andrei
>
> Well, my first reaction would be that that would be needed rarely enough
> that there's no point in putting it in the API. You could just use
> removeFront() or removeBack(), or you could grab a random element from the
> container and remove that.

SList can't implement removeBack() and Array can't implement removeFront(). Only a few containers can implement grabbing a random element within the complexity constraints of removeElement().

> But maybe there are container types where it
> really makes sense, and having it in the API could be useful. Still, it
> strikes me as a really weird function to have. Of course, if you really
> think that it's going to be useful, leave it in. Unlike pretty much all the
> others though, it's not one I ever expect to use.

It might not be weird if you want to write container-independent code.


Andrei

On 26/05/2010 21:53, Andrei Alexandrescu wrote:
> On 05/26/2010 11:08 AM, BLS wrote:
>> On 26/05/2010 17:31, BLS wrote:
>>> regret a bit that you haven't picked up the idea of collection events.
>>> IMHO this is the smartest way to implement a UnDo/ReDo Stack or to
>>> create a MultiSet based on a simple Set.
>>
>> and since Dr. Dobbs is probably a more serious source.
>>
>> http://www.drdobbs.com/windows/199902700
>>
>> and a concrete implementation on page : 5
>>
>> http://www.drdobbs.com/windows/199902700;jsessionid=A10YNSK2DXVJ3QE1GHOSKH4ATMY32JVN?pgno=5
>>
>
> Whoa, that does look like a huge inheritance diagram.
>
> http://www.drdobbs.com/windows/199902700;jsessionid=CQ3Z0PZ33GJCRQE1GHOSKHWATMY32JVN?pgno=2
>
>
> I swear I saw a kitchen sink in there somewhere.
>


Yeah, I was afraid that exactly this happened...giving a link.. you guys are watching the complete collection lib.. and nobody cares about a simple,smart detail named collection update events.

beside, doable without creating an inheritance monster ;)

bls

>
>
> Andrei

On 2010-05-26 20:09:15 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> On 05/26/2010 06:07 PM, Jonathan M Davis wrote:
>> Looks interesting overall. There is one function, however, which makes no
>> sense to me: removeElement()/stableRemoveElement().
>> 
>> [...]
> 
> If the container is a worklist with items to work on, it sometimes doesn't matter in which order you extract them.

May I suggest naming it "removeAny"? This fits better with "removeBack" and "removeFront" (where the second word represent the position), and makes clear that you don't really care which element is removed.

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

On 26/05/2010 23:59, Steven Schveighoffer wrote:
> I don't think it will be analogous to a Tango/Phobos separation.  Dcollections supports ranges, and the major interface to Andrei's containers is ranges, and if my implementations are accepted, both will probably even be using the same underlying implementations.  So I think the two libs will quite happily exist together.  I am disappointed that dcollections wasn't chosen, but given the eventual API that Andrei has come up with, I think it didn't really have a shot from the beginning.
>
I have not yet seen a statement regarding the replacement (hopefully hot swapped) feature of underlaying data structures

dCollections has support, std.collection... dunno

In case that Andrei decides to ignore that feature I can't see how Dcollections and std.collection will harmonize.

bjoern

On 05/26/2010 09:47 PM, BLS wrote:
> On 26/05/2010 23:59, Steven Schveighoffer wrote:
>> I don't think it will be analogous to a Tango/Phobos separation.
>> Dcollections supports ranges, and the major interface to Andrei's
>> containers is ranges, and if my implementations are accepted, both
>> will probably even be using the same underlying implementations. So I
>> think the two libs will quite happily exist together. I am
>> disappointed that dcollections wasn't chosen, but given the eventual
>> API that Andrei has come up with, I think it didn't really have a shot
>> from the beginning.
>>
> I have not yet seen a statement regarding the replacement (hopefully hot
> swapped) feature of underlaying data structures
>
> dCollections has support, std.collection... dunno
>
> In case that Andrei decides to ignore that feature I can't see how
> Dcollections and std.collection will harmonize.

It's even better than that, but you need to look at things a bit differently.

std.container will not contain hot-swappable components. It will contain components that could be used in some of the hot swaps. It's just one level lower than what you are discussing.

That doesn't make it any more or less incompatible with dcollections.


Andrei

On 05/26/2010 09:29 PM, Michel Fortin wrote:
> On 2010-05-26 20:09:15 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> said:
>
>> On 05/26/2010 06:07 PM, Jonathan M Davis wrote:
>>> Looks interesting overall. There is one function, however, which
>>> makes no
>>> sense to me: removeElement()/stableRemoveElement().
>>>
>>> [...]
>>
>> If the container is a worklist with items to work on, it sometimes
>> doesn't matter in which order you extract them.
>
> May I suggest naming it "removeAny"? This fits better with "removeBack"
> and "removeFront" (where the second word represent the position), and
> makes clear that you don't really care which element is removed.

Done. removeAny was my choice as of a few months ago but I'd forgotten. Thanks!

Andrei

Andrei Alexandrescu wrote:

> It might not be weird if you want to write container-independent code.

Well, I've never needed to do that particular operation on _any_ container, so it does strike me as weird regardless. I've basically always been looking to remove a specific element or elements or to remove the element at a specific location. I don't ever recall being in a situation where it made any sense to remove an element without caring which one. But that's obviously not to say that no one else would find it useful. And std.container does not and obviously should not revolve around what I alone would find useful.

As for container-independent code, there are certainly times when I've written code that was container-independent, but I don't think that it's something that I've done all that often. I agree that it can be quite useful and powerful to do so, but generally I've found that it breaks down because the various containers are too disparate both in function and performance. For instance, the STL makes it so that you at least _think_ that you can write container-independent code, but it's quite easy to run into instances where you really want to use a function that's specific to a container instead of the version in the algorithm library, or the functions are just different enough between container types that it doesn't work, or the operation that you're trying to do works fine with one container but would invalidate iterators on another, or... The list goes on. Effective STL certainly advises you to not really write container-independent code, generally-speaking, because it doesn't really work.

The fact that the operations in std.container carry specific performance constraints will make it work much better I think. Also, D's ability to alter how a function is defined based on the attributes of a given container makes it much easier to write algorithms which are efficient for each container type without having to worry about calling member functions in some cases and non-member functions in others or anything like that. So, I think that std.container really looks like it could lead me to write good, container-independent code. However, I don't have much experience with writing container-independent code because it doesn't work very well in C++, and it can be quite detrimental to performance in other languages like Java because the performance characteristics of different containers vary so much.

In any case, std.container looks pretty good thus far. I just found removeElement() weird because I coudn't see why anyone would ever need such a function.

- Jonathan M Davis


P.S. I have to agree that removeAny() and removeAnyStable() are better names. It's certainly less confusing as to what they're doing.

On 05/26/2010 04:59 PM, Steven Schveighoffer wrote:
> BLS Wrote:
>
>> On 26/05/2010 01:04, Steven Schveighoffer wrote:
>>> I can probably submit my basic implementations, and use them from
>>> std.x to implement dcollections.  This way, the complex pieces
>>> are shared. Dcollections definitely fills needs that this
>>> collection package doesn't, and it should be mostly compatible.
>>>
>>> -Steve
>>
>> Not that I like the idea of having (once again) two libs instead of
>> one, but I am convinced that the separation between core data-
>> structures, say xxTree, xxList, xxNode etc. and the final
>> implementation f.i. Set, Dictionary/Map. is a very good thing.
>
> I don't think it will be analogous to a Tango/Phobos separation.

Same here.

> Dcollections supports ranges, and the major interface to Andrei's
> containers is ranges, and if my implementations are accepted, both
> will probably even be using the same underlying implementations.  So
> I think the two libs will quite happily exist together.  I am
> disappointed that dcollections wasn't chosen, but given the eventual
> API that Andrei has come up with, I think it didn't really have a
> shot from the beginning.

I much appreciate your kind willingness to essentially help push D forward before all else.

During a private talk of a couple of days ago, Walter gave me a vote of confidence by essentially saying: "Whatever container library makes it in Phobos, I want to to be by your vision, not someone else's." This is nice to know, but at the same time piles a high responsibility because it puts me in position to decide on e.g. integration of dcollection into Phobos.

Now say you put yourself in my place and Walter tells you that. You obviously have some idea on how you want a container library to be, because you wrote one! So most likely you'd put your design in, not mine or anyone else's, and you'd be using and accepting other designs and implementations only to the extent they satisfy your vision.

This is all rhetorical because it's clear to me you have such an understanding of the situation, but it's a sort of a public rehashing of the dynamics that's going on right now.


Andrei

Steven Schveighoffer wrote:

> Jonathan M Davis Wrote:
> 
>> Looks interesting overall. There is one function, however, which makes no
>> sense to me: removeElement()/stableRemoveElement().
>> 
>> So, it basically removes a random element from the container? It could be quite consistent as to which element it removes from the container (it being implementation-dependent), but effectively, it removes a random element? What's the point of that? I can't remember the last time - if ever - that I wanted to remove an element from a container and I didn't care which. Or am I misunderstanding what it does?
> 
> I think you are misunderstanding.  Random element means you can't tell which one is removed, but it doesn't *have* to be truly random :)  It most likely will be the most convenient element to remove (maybe that would be a better description).  In other words, you can't expect it to always be the last element, or the first element, or the lowest element, or whatever.
> 
> So essentially, I think that's what you were asking for, and I think that's what Andrei meant.
> 
> -Steve

I don't think that I misunderstood, but I may not have stated it well. No, the element is not _truly_ random, but it is removing an unspecified element which could be any element in the container, and is therefore random in the sense that you aren't telling it which one to remove. I've never been in a situation where it made any sense to do that. So, the function struck me as really weird.

If you wanted truly random, you'd have to implement a function that actually did random number generation or whatnot to decide which element to pick, and presumably, it would be abnormal to use that here (though I think that doing so would still follow the API). So, no, removeElement() (now removeAny()) is not truly random, but it isn't deterministic from the perspective of the programmer having any clue which one will be removed, and it may or may not be deterministic from the container's perspective.

- Jonathan M Davis