On 2010-05-25 19:18:43 -0400, bearophile <bearophileHUGS@lycos.com> said:

> Andrei Alexandrescu:
> 
>> any container must be a reference type, whether implemented as a class or struct.<
> 
> This probably makes their usage simpler, so this can be the right decision. But then you can't define something like a TinyHashSet or a StaticBitSet that are better allocated on the stack...

Well, in a way I think you can, but you have to stretch the definition a bit. A value-type container you can move but can't copy (because you used "@disable this(this)") is semantically indistinguishable to a reference-type container with a unique non-copiable (but moveable) reference. The only problem is that most algorithms probably won't work with such a thing, they'll expect a copy of the reference right in their function arguments.

This does bother me a little. That it allows statically allocated collections is something I like a lot of the C++ container model.


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

On 2010-05-26 11:13:38 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> On 05/26/2010 09:37 AM, Michel Fortin wrote:
> 
>> insertAtRandomPlace(myContainer.soft, element);
>> 
>> Now you know insertAtRandom won't and *can't* invalidate your
>> iterators/ranges, and you don't need to write a separate
>> "softInsertAtRandom" that only calls soft functions.
> 
> Initially I thought containers that naturally support soft (well, "stable" since 5 minutes ago) operations would simply alias the non-stable versions and the stable versions to the same call.
> 
> But now you got me thinking that a container might want to take advantage of both to implement slightly different approaches. I haven't met such a container yet, but that doesn't mean they aren't possible.

While it's true that a container could implement a different approach for stable and unstable operations, I was more concerned with the need to guaranty that only stable operations are performed when passing the container to other functions, hence the need for a "soft" (now "stable") container wrapper.


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

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.



Andrei

On 2010-05-26 17.31, 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.
>
> std.structures std.algorithm std.container/collection
>
> --
> Next, what's wrong with simple collections, stack, queue etc. Guess too
> simple for u guys ;)
> --
>
> I 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.
>
> Bjoern

Yes, events would be nice to have. Just simulating C# events or something similar.

-- 
/Jacob Carlborg

Andrei Alexandrescu Wrote:


> > Finally, opSlice(begin, end) is not there.  Was this intentional or
> > overlooked?
> 
> I'm still mulling over that. As was discussed in this group, $ is easy to detect statically but 0 is not. Some containers don't like nonzero beginning anchors, and I wouldn't want to make that a runtime test.

It would most likely not violate an O(lg(n)) requirement to check that the beginning anchor was indeed the beginning.  In fact, it would be about as much work as opSlice(), since you have to find that beginning anchor anyways...

> If Walter won't make a language change, I'd have to define begin() as an anchor, and before you know it, cursors are in :o).

I'm all for a language change and cursors ;)

> b) associative arrays can define c[a .. b] for a, b key types. It's nontrivial but it can be done.

I decided for dcollections that this only makes sense on sorted maps.  It is a little questionable to check in runtime that b > a on something like a hash map, but besides that point, it's non deterministic.  Slicing with keys on c[a..b] might work before a rehash, and not work after one.  This latter point is what made me disallow it.

> 
> c) sentinel-terminated arrays (e.g. C stringz) can only define c[a .. $] for an integral a.

I really hope we are not considering null-terminated strings when deciding container functions...

> e) Any other cases?

On a sorted AA, slicing using any two keys are possible (as long as the keys exist in the AA).

-Steve

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.  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 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.

I don't know much about it.  If it makes sense to be used in dcollections, I might do it.  Right now, however, I want to concentrate on getting dcollections out of beta.

-Steve

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

Jonathan M Davis:
> There is one function, however, which makes no sense to me: removeElement()/stableRemoveElement().

I have a similar function in my dlibs1, it's called pop (works with arrays and AAs), it's similar to the pop method function you find in Python sets and lists.

On lists it removes and returns the last item:

>>> l = [1, 2, 3]
>>> l
[1, 2, 3]
>>> l.pop()
3
>>> l.pop()
2
>>> l.pop()
1
>>> l
[]

But sets are not ordered, so it has to pop out items in a unpredictable way (but if you need items in a truly random order this is not the right thing to do):

>>> s = set(["ab", "cd", "ef"])
>>> s
set(['ab', 'ef', 'cd'])
>>> s.pop()
'ab'
>>> s.pop()
'ef'
>>> s
set(['cd'])
>>> s.pop()
'cd'
>>> s
set([])

So I think this is an useful method. But I think its name is too much long and not clear enough, because it's not a delete, it also returns the item. So I think I'd like to call it just pop()/stablePop() :-)

Bye,
bearophile

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

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