On 05/26/2010 07:38 AM, Jason House wrote:
> Andrei Alexandrescu Wrote:
>
>> On 05/25/2010 09:07 PM, Walter Bright wrote:
>>> Andrei Alexandrescu wrote:
>>>> On 05/25/2010 08:31 PM, Walter Bright wrote:
>>>>> Andrei Alexandrescu wrote:
>>>>>> On 05/25/2010 07:35 PM, Walter Bright wrote:
>>>>>>> Andrei Alexandrescu wrote:
>>>>>>>> I've uploaded a work in progress on the container design here:
>>>>>>>
>>>>>>> Great! Some nitpicky comments:
>>>>>>>
>>>>>>> 1. What's the difference between a value and an element?
>>>>>>
>>>>>> None.
>>>>>
>>>>> Then I suggest sticking with one or the other throughout the spec. Also,
>>>>> there's both an ElementType and a ValueType.
>>>>
>>>> Sorry, I was wrong. ValueType is defined for keyed containers to mean
>>>> the mapped type. Should I call it MappedType?
>>>
>>> Can a container have different ElementTypes from ValueTypes?
>>
>> For a hash K->V, KeyType is K, ValueType is V, and ElementType is
>> Tuple!(K, V).
>>
>> Andrei
>
> How about simple arrays? There's a lot of similarity between T[] and T[int]...

A simple array doesn't have a Tuple as the unit of storage. Indexing is a consequence of array's layout so I consider it different.

Andrei

On 2010-05-25 18:27:32 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> There are a bunch of "soft" primitives. Those are meant to put a stop to the iterator invalidation problems experienced in the STL. The container implementor may alias softXyz to xyz if she knows the operation won't mess the ranges currently iterating the container (which is the case for most node-based containers). I haven't yet discussed subtler cases in which a range starts with a removed element etc., but I plan to.

Looks good, but I think something is missing. While I agree with the idea of having distinguishable "soft" operations, to pass it to other functions you should be able to make a "soft" shell around your container and pass that shell mapping non-soft functions to soft ones, ensuring only soft functions can be called. It could look like this:

	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.

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

On 05/26/2010 01:45 AM, Don wrote:
> Andrei Alexandrescu wrote:
>> I've uploaded a work in progress on the container design here:
>>
>> http://erdani.com/d/phobos/std_container.html
>>
>> It's deceptively simple - the entire design is a nomenclature, really.
>> Any given container may choose to implement whichever primitives it
>> can, if (and only if) it can satisfy the requirements. Beyond that,
>> each container can define its own primitives.
>
> Looks great to me. A couple of comments:
>
>> There are a bunch of "soft" primitives. Those are meant to put a stop
>> to the iterator invalidation problems experienced in the STL. The
>> container implementor may alias softXyz to xyz if she knows the
>> operation won't mess the ranges currently iterating the container
>> (which is the case for most node-based containers). I haven't yet
>> discussed subtler cases in which a range starts with a removed element
>> etc., but I plan to.
>
> The softXXX primitives are listed as having the same complexity as the
> non-soft primitives. Should it be explicitly stated that non-soft should
> always be at least as fast as soft? (So that if you don't need the soft
> guarantee, you should always use the non-soft primitive?)
>
> Also, I agree with Jerry that something like "stable" would be more
> intuitive than "soft". I guess it's not exactly the same meaning as
> stableSort, but it's pretty close. A problem with the name "soft" is
> that it's a harder, stronger guarantee! It seems to be a concept of a
> "tame" removal as opposed to reckless, "savage" removal?

Renamed to "stable".

Andrei

On 05/26/2010 09:37 AM, Michel Fortin wrote:
> On 2010-05-25 18:27:32 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> said:
>
>> There are a bunch of "soft" primitives. Those are meant to put a stop
>> to the iterator invalidation problems experienced in the STL. The
>> container implementor may alias softXyz to xyz if she knows the
>> operation won't mess the ranges currently iterating the container
>> (which is the case for most node-based containers). I haven't yet
>> discussed subtler cases in which a range starts with a removed element
>> etc., but I plan to.
>
> Looks good, but I think something is missing. While I agree with the
> idea of having distinguishable "soft" operations, to pass it to other
> functions you should be able to make a "soft" shell around your
> container and pass that shell mapping non-soft functions to soft ones,
> ensuring only soft functions can be called. It could look like this:
>
> 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.


Andrei

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

On 05/25/2010 06:04 PM, Steven Schveighoffer wrote:
> What about the purge function of dcollections (i.e. removal while
> iterating)?

I operated a few changes to the nomenclature to introduce better support for removal, in particular removal while iterating. In particular I tightened the complexity of remove and added linearRemove.

http://erdani.com/d/phobos/std_container.html

There are two idioms of choice:

a) If the container supports remove(), then you can remove during iteration as follows:

Range r = container[];
while (!r.empty)
{
    if (remove_this_guy)
        r = container.remove(r.take(1));
    else
        r.popFront();
}

That's the case for many associative containers which have low cost for removal. Regular arrays won't be able to implement remove() because it must have logarithmic complexity.

b) If the container doesn't support remove(), removal is done by packing towards the front the stuff to be kept, and then getting rid of it:

Range r = container[];
Range yank = r;
for (; !r.empty; r.popFront())
{
    if (!remove_this_guy)
    {
        yank.front = r.front;
        yank.popFront();
    }
}
container.linearRemove(yank);

See also the remove primitive in std.algorithm which does this (of course without the linearRemove call) using a predicate for remove_this_guy.


Andrei

On 05/25/2010 09:29 PM, Walter Bright wrote:
> Andrei Alexandrescu wrote:
>> On 05/25/2010 09:07 PM, Walter Bright wrote:
>>> Andrei Alexandrescu wrote:
>>>> On 05/25/2010 08:31 PM, Walter Bright wrote:
>>>>> Andrei Alexandrescu wrote:
>>>>>> On 05/25/2010 07:35 PM, Walter Bright wrote:
>>>>>>> Andrei Alexandrescu wrote:
>>>>>>>> I've uploaded a work in progress on the container design here:
>>>>>>>
>>>>>>> Great! Some nitpicky comments:
>>>>>>>
>>>>>>> 1. What's the difference between a value and an element?
>>>>>>
>>>>>> None.
>>>>>
>>>>> Then I suggest sticking with one or the other throughout the spec.
>>>>> Also,
>>>>> there's both an ElementType and a ValueType.
>>>>
>>>> Sorry, I was wrong. ValueType is defined for keyed containers to mean
>>>> the mapped type. Should I call it MappedType?
>>>
>>> Can a container have different ElementTypes from ValueTypes?
>>
>> For a hash K->V, KeyType is K, ValueType is V, and ElementType is
>> Tuple!(K, V).
>
> Ok, that makes it clear, and it needs to be in the spec.

Done.

Andrei

On 05/26/2010 12:40 AM, Jerry Quinn wrote:
> softXXX might be better named safeXXX or stableXXX.  The names might
> be more suggestive of preserving iteration.

Done. "stable". Thanks.

> The doc isn't quite clear whether make is a member function or
> standalone.  I assume it's standalone, but that's worth firming up.

make is standalone, the indentation should give that away.

>>> I don't like insertInstead, can we make it replace?
>>
>> replace was the original name. insertInstead is consistent with
>> the other two, so we have (softI|i)nsert[Before|After|Instead].
>
> I second the request for the name "replace".  Despite the
> consistency, I think replace is clear to programmers as well as being
> more familiar and comfortable.  Also, the operation really isn't
> "insert instead", it's "delete then insert instead".  So there is
> lack of symmetry because it removes elements while the other does
> not.

Good point. I inserted "replace" instead of "insertInstead" (and just inserted a pun, too).

> Another  issue I see is that opIndex and its brethren takes KeyType,
> but for something like vector, this should be size_t..  I don't think
> you want ElementType to be tuple!(size_t, ElementType) in this case.

Arrays don't define KeyType, yet they define opIndex. That doesn't go against the spec. That being said, I'd like to see a bit more unification between arrays and associative arrays.

> Related to this, do you intend removal of a single element to use
> remove(range) or removeKey?

I think remove(range.take(1)) should remove one element. I'm also thinking of simplifying matters by defining remove(range, k) where k is an "up to" number.

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

To recap:

a) arrays (but not associative arrays) can define c[a .. b] for integrals a and b.

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

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

d) lists can, with ho and hum, define c[0 .. a] for an integral a. The ho and hum comes from the fact that the range thus obtained is not a "proper" Range type, it's a Take!Range.

e) Any other cases?


Andrei

On 05/26/2010 07:44 AM, Pelle wrote:
> On 05/26/2010 11:44 AM, bearophile wrote:
>> Andrei A.:
>>
>>> I hope to work with ranges only.<
>>
>> Programming life is complex, you can't fit all of it in one schema ("A
>> foolish consistency is the hobgoblin of little minds").
>>
>
> Couldn't you just define opApply where you need it and it will be used
> where foreach is used by default, anyway?
>
>>
>>> Will look into it, sounds like an implementation matter.<
>>
>> Yes, right. But to implement this idea the foreach() has to change a
>> bit, to set the flag in nonrelease mode. If implemented this idea
>> lessens a bit the need for the stable ("soft") methods.
>>
>>
>>> Probably some trees could save some state if they exploit O(log n)
>>> length.<
>>
>> In general a length can be O(n) if for example you want to compute it
>> on a linked list that doesn't keep the number of items inserted. Are
>> you going to just not give a length attribute for such linked lists
>> (so users have to use something like walkLength)?
>>
>
> Isn't that a good thing? If I know length is fast, I can use it without
> worries, but if it might be O(n) you need to avoid it.

Yes, that's exactly the idea.

BTW, I'd misunderstood the question. Bearophile asked "Why O(log n) and not O(n)?" and I heard: "Why O(log n) and not O(1)?" So I'd gotten confused a bit and answered the wrong question.


Andrei

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

hth, bjoern