Re: container stuff
Jonathan M Davis: 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. You have probably missed my other answer. But I can add some more. That operation is common. You use it every time you have a container that doesn't define a deterministic order (like hash sets, hash associative arrays, and so on) and you want to process and consume its items. In such collection you can't ask to pop the last or first item because they are not defined. So you pop out one randomly. I have used it many times in my programs. Bye, bearophile
Re: container stuff
Andrei Alexandrescu: Done. removeAny was my choice as of a few months ago but I'd forgotten. I suggest to call it just pop. Bye, bearophile
Re: container stuff
On Thu, 27 May 2010 00:20:24 -0400, Jonathan M Davis jmdavisp...@gmail.com wrote: 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. OK. I think the point of removeAny is that it removes an element as fast as possible, however that can be implemented by the container. I.e. removing the back or front element may not be the fastest operation, think about something like a tree, where the fastest element to remove is probably the top element. -Steve
Re: container stuff
bearophile wrote: Jonathan M Davis: 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. You have probably missed my other answer. But I can add some more. That operation is common. You use it every time you have a container that doesn't define a deterministic order (like hash sets, hash associative arrays, and so on) and you want to process and consume its items. In such collection you can't ask to pop the last or first item because they are not defined. So you pop out one randomly. I have used it many times in my programs. When is it better to do it that way, rather than just iterating over all elements, and then completely empty the container? (Just curious -- I'm having trouble thinking of a use case for this feature).
Re: container stuff
Don: When is it better to do it that way, rather than just iterating over all elements, and then completely empty the container? (Just curious -- I'm having trouble thinking of a use case for this feature). I'm having troubles understanding why two persons have troubles seeing use cases for this feature :-) Iterating over the container and then emptying the container is two operations, you have to keep in mind to empty it, while if you pop items out of it progressively you just need to keep in mind to do one thing, and you avoid forgetting the final cleaning. Also, the progressive popping out of items allows you to have a collection that is correct in every moment, there is no risk of removing two times an item, so you can pass around the data structure in any moment of this process of wearing it away. This is what you suggest (Python code): s = set([ab, bc, de]) def process_item(item): print item for item in s: process_item(item) s.clear() # removes all items But this is better, you can print the correct collection in any moment and you can't forget the final clear: s = set([ab, bc, de]) def process_item(item): print item def show_data(items): print items while s: process_item(s.pop()) show_data(s) Bye, bearophile
Re: container stuff
bearophile wrote: Don: When is it better to do it that way, rather than just iterating over all elements, and then completely empty the container? (Just curious -- I'm having trouble thinking of a use case for this feature). I'm having troubles understanding why two persons have troubles seeing use cases for this feature :-) Iterating over the container and then emptying the container is two operations, you have to keep in mind to empty it, while if you pop items out of it progressively you just need to keep in mind to do one thing, and you avoid forgetting the final cleaning. Yes, but if I understand correctly, the only reason to have removeAny _as a primitive_ is for speed. And iterating over the container followed by a single removal is almost always going to be much faster. If, however, speed is not critical, removeAny can be a generic function -- call removeFront() if present, else call removeBack(). And your examples would work just fine with that. I'm having trouble identifying a use case where it needs to be a primitive.
Re: container stuff
On 05/27/2010 06:49 AM, Don wrote: bearophile wrote: Jonathan M Davis: 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. You have probably missed my other answer. But I can add some more. That operation is common. You use it every time you have a container that doesn't define a deterministic order (like hash sets, hash associative arrays, and so on) and you want to process and consume its items. In such collection you can't ask to pop the last or first item because they are not defined. So you pop out one randomly. I have used it many times in my programs. When is it better to do it that way, rather than just iterating over all elements, and then completely empty the container? (Just curious -- I'm having trouble thinking of a use case for this feature). Again, any worklist-based algorithm will remove and add work items without minding for a specific order. http://cseweb.ucsd.edu/classes/sp00/cse231/report/node12.html Andrei
Re: container stuff
On 27/05/2010 06:06, Andrei Alexandrescu wrote: 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 Thanks for taking the time to explain. Whatever direction D collections will take, I think we all agree that collections are the missing link in D. Once done, I am convinced that a number of D2 add on libs will grow drastically. Just can speak for myself, f.i. creating a dock /undock, tabbed MDI GUI without having a solid collection lib is not really a pleasure.. Bjoern
Re: container stuff
Don: Yes, but if I understand correctly, the only reason to have removeAny _as a primitive_ is for speed. And iterating over the container followed by a single removal is almost always going to be much faster. Most things in Python are designed to be handy first, and fast later. So I doubt performance has has any significance in this small piece of Python design. In both Python and D is pop() is useful because it allows your collection to represent coherently its decreased or increased number of items at all times (Andrei ha shown an example where you have to add and remove items continuously). Bye, bearophile
Re: container stuff
On Thu, May 27, 2010 at 5:44 AM, Don nos...@nospam.com wrote: bearophile wrote: Don: When is it better to do it that way, rather than just iterating over all elements, and then completely empty the container? (Just curious -- I'm having trouble thinking of a use case for this feature). I'm having troubles understanding why two persons have troubles seeing use cases for this feature :-) Iterating over the container and then emptying the container is two operations, you have to keep in mind to empty it, while if you pop items out of it progressively you just need to keep in mind to do one thing, and you avoid forgetting the final cleaning. Yes, but if I understand correctly, the only reason to have removeAny _as a primitive_ is for speed. And iterating over the container followed by a single removal is almost always going to be much faster. If, however, speed is not critical, removeAny can be a generic function -- call removeFront() if present, else call removeBack(). And your examples would work just fine with that. I'm having trouble identifying a use case where it needs to be a primitive. Think of a graph algorithm where you add all the nodes you know about to a Set. Pop one, process it, and then add any nodes it's connected to that you haven't seen yet back to the Set. Repeat until nothing left to pop. --bb
Re: container stuff
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? So, this is it really: the containers specification is a collection of capabilities. A given container picks the ones it can support meaningfully, and user code has the specification as semantic and complexity guarantees. This design is quite far removed from Steve's, which makes the integration with dcollection tenuous. But at a minimum, maybe we can work out something in which Steve offers, with credit, implementation for this design and also offers dcollections as a separate library. Andrei
Re: container stuff
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). 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)? Bye, bearophile
Re: container stuff
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]...
Re: container stuff
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.
Re: container stuff
On 05/26/2010 04: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). 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)? Correct, some collections (notably SList) will simply not provide length(). In fact I will implement SList soon as an illustration of the design. Andrei
Re: container stuff
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
Re: container stuff
On 2010-05-25 18:27:32 -0400, Andrei Alexandrescu seewebsiteforem...@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.for...@michelf.com http://michelf.com/
Re: container stuff
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
Re: container stuff
On 05/26/2010 09:37 AM, Michel Fortin wrote: On 2010-05-25 18:27:32 -0400, Andrei Alexandrescu seewebsiteforem...@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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
Andrei Alexandrescu: Will look into it, sounds like an implementation matter. Thinking a bit more about it, it's not just an implementation matter. If that suggestion of mine is accepted, then the foreach has to set and later reset one boolean value inside the data structure. So this boolean value if present must have a standard name, that has to be shown in that page about the standard API of the data structures :-) Bye, bearophile
Re: container stuff
Andrei Alexandrescu: http://erdani.com/d/phobos/std_container.html I have seen the updated version. Few small comments: ElementType: as Walter has said I think it's better to explain better what it is. The built-in AAs have the byKey() and byValue() methods. The same methods can be useful for the generic collections. Are length and dup properties? Bye, bearophile
Re: container stuff
On 2010-05-25 19:18:43 -0400, bearophile bearophileh...@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.for...@michelf.com http://michelf.com/
Re: container stuff
On 2010-05-26 11:13:38 -0400, Andrei Alexandrescu seewebsiteforem...@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.for...@michelf.com http://michelf.com/
Re: container stuff
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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
Andrei Alexandrescu Wrote: 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 if I understand your logic, then a trie would also lack a (key,value) tuple for the element type?
Re: container stuff
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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
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
Re: container stuff
On 2010-05-26 20:09:15 -0400, Andrei Alexandrescu seewebsiteforem...@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.for...@michelf.com http://michelf.com/
Re: container stuff
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
Re: container stuff
On 05/26/2010 09:29 PM, Michel Fortin wrote: On 2010-05-26 20:09:15 -0400, Andrei Alexandrescu seewebsiteforem...@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
Re: container stuff
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
Re: container stuff
On 05/26/2010 05:21 PM, Jason House wrote: Andrei Alexandrescu Wrote: 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 if I understand your logic, then a trie would also lack a (key,value) tuple for the element type? I'm not sure! Andrei
Re: container stuff
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.
Re: container stuff
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
Re: container stuff
On 05/26/2010 04:47 PM, Steven Schveighoffer wrote: 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. Yah, I meant sorted collections as well. 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... I don't know. When working on an abstraction I find it very, very useful to anchor it in concrete incarnations that I know of. (Such an approach has led to taming the gnarly UTF-8 strings into nice bidirectional ranges.) I'm not crazy about null-terminated strings, but slists are also sentinel terminated, they just aren't contiguous. Comparing and contrasting these and other concrete instantiations is great exercise that only makes the abstraction better. e) Any other cases? On a sorted AA, slicing using any two keys are possible (as long as the keys exist in the AA). Great. Andrei
Re: container stuff
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
Re: container stuff
On 05/26/2010 11:15 PM, Jonathan M Davis wrote: 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. Yeah, exactly. We're all in the same boat really. Time will tell how that really goes. Andrei
container stuff
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. The design is not fancy, which doesn't worry me in the least because I was aiming for the right design, not a fancy design. I feel this design is pretty close to what I really wanted. The major players are the containers themselves and the ranges they define. Most operations are defined in terms of ranges, not containers. The containers only need to support a modicum of primitives that affect the topology of containers, plus a few convenience functions. 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. So, this is it really: the containers specification is a collection of capabilities. A given container picks the ones it can support meaningfully, and user code has the specification as semantic and complexity guarantees. This design is quite far removed from Steve's, which makes the integration with dcollection tenuous. But at a minimum, maybe we can work out something in which Steve offers, with credit, implementation for this design and also offers dcollections as a separate library. Andrei
Re: container stuff
On Tue, 25 May 2010 18:27:32 -0400, Andrei Alexandrescu seewebsiteforem...@erdani.org 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. The design is not fancy, which doesn't worry me in the least because I was aiming for the right design, not a fancy design. I feel this design is pretty close to what I really wanted. The major players are the containers themselves and the ranges they define. Most operations are defined in terms of ranges, not containers. The containers only need to support a modicum of primitives that affect the topology of containers, plus a few convenience functions. 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. So, this is it really: the containers specification is a collection of capabilities. A given container picks the ones it can support meaningfully, and user code has the specification as semantic and complexity guarantees. This design is quite far removed from Steve's, which makes the integration with dcollection tenuous. But at a minimum, maybe we can work out something in which Steve offers, with credit, implementation for this design and also offers dcollections as a separate library. I take it from the comment in the docs that cursors can be an auxiliary range? Is there any reason not to define a mandatory cursor type (a cursor is elementary to define if a range is definable)? There is no remove(Range) function, this is a bad omission. It's one of the main reasons I created dcollections (quick element removal when element lookup is not quick). I don't like insertInstead, can we make it replace? What about the purge function of dcollections (i.e. removal while iterating)? What about opApply? Without opApply, you cannot use foreach to get both keys and values. 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
Re: container stuff
Andrei Alexandrescu: I feel this design is pretty close to what I really wanted. Good :-) How is opApply playing in the design of the containers? Can opSlice return a struct that defines opApply? There are a bunch of soft primitives. Those are meant to put a stop to the iterator invalidation problems experienced in the STL. I can suggest another thing, that doesn't replace this idea, but can make the nonsoft primitives a little safer when the program is compiled in nonrelease mode: http://d.puremagic.com/issues/show_bug.cgi?id=4179 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... (a StaticBitSet is a struct template I have defined, at compile time you give it its length and it gets allocated on the stack, and represents a set of integers in an intgerval, or something similar). Why is length O(log(n))? If a linked list has no length field, to compute its length it has to scan all of it. make(): this has just killed the new :-) Among the standard primitives is it useful to have something to ask the actual computational complexity of a specific operation of a specific container? There are some ways to implement this, the simplest is to define enum with the most common complexities, and then a collection can contain an enum (const) value for each operation, something like: enum lengthComplexity = CompComplexity.linear; I don't know if this can be useful (to choose collections, to infer code complexity, etc). Bye, bearophile
Re: container stuff
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? 2. What's the affect of clear() on the capacity? 3. Shouldn't KeyTypes be a type tuple?
Re: container stuff
On 05/25/2010 06:04 PM, Steven Schveighoffer wrote: On Tue, 25 May 2010 18:27:32 -0400, Andrei Alexandrescu seewebsiteforem...@erdani.org 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. The design is not fancy, which doesn't worry me in the least because I was aiming for the right design, not a fancy design. I feel this design is pretty close to what I really wanted. The major players are the containers themselves and the ranges they define. Most operations are defined in terms of ranges, not containers. The containers only need to support a modicum of primitives that affect the topology of containers, plus a few convenience functions. 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. So, this is it really: the containers specification is a collection of capabilities. A given container picks the ones it can support meaningfully, and user code has the specification as semantic and complexity guarantees. This design is quite far removed from Steve's, which makes the integration with dcollection tenuous. But at a minimum, maybe we can work out something in which Steve offers, with credit, implementation for this design and also offers dcollections as a separate library. I take it from the comment in the docs that cursors can be an auxiliary range? Is there any reason not to define a mandatory cursor type (a cursor is elementary to define if a range is definable)? Yes, but the cursor would have to pass scrutiny for usefulness just like anything else. There is no remove(Range) function, this is a bad omission. It's one of the main reasons I created dcollections (quick element removal when element lookup is not quick). I think it got lost when I reordered the code (I did a major reshuffling just before posting). I put it back. 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]. What about the purge function of dcollections (i.e. removal while iterating)? Removal while iterating is achieved through different means. I need to think through the details a bit more, but in essence it doesn't have to be a primitive. The primitives should allow implementation of a generic function that removes elements that satisfy a condition, something as follows: If the collection supports softRemove, if you want to remove an element while iterating with a range r, you can say coll.softRemove(r.take(1)). If it doesn't, I'm thinking of allowing the erase/remove idiom (http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Erase-Remove). For that, remove should return a range positioned right after the removed element. Let me think a bit more about that. What about opApply? Without opApply, you cannot use foreach to get both keys and values. I'd like to design without opApply as part of the primitives. You can use foreach to iterate tuples of keys and values. 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. Sounds promising! Andrei
Re: container stuff
On 05/25/2010 06:18 PM, bearophile wrote: Andrei Alexandrescu: I feel this design is pretty close to what I really wanted. Good :-) How is opApply playing in the design of the containers? Can opSlice return a struct that defines opApply? I hope to work with ranges only. There are a bunch of soft primitives. Those are meant to put a stop to the iterator invalidation problems experienced in the STL. I can suggest another thing, that doesn't replace this idea, but can make the nonsoft primitives a little safer when the program is compiled in nonrelease mode: http://d.puremagic.com/issues/show_bug.cgi?id=4179 Will look into it, sounds like an implementation matter. 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... (a StaticBitSet is a struct template I have defined, at compile time you give it its length and it gets allocated on the stack, and represents a set of integers in an intgerval, or something similar). I'm guessing some value container-like entities wouldn't harm if they can easily be converted to references. Why is length O(log(n))? If a linked list has no length field, to compute its length it has to scan all of it. I forgot the case I had in mind. I know that opSlice() must be O(log n) for e.g. tree traversals. Probably some trees could save some state if they exploit O(log n) length. make(): this has just killed the new :-) Among the standard primitives is it useful to have something to ask the actual computational complexity of a specific operation of a specific container? There are some ways to implement this, the simplest is to define enum with the most common complexities, and then a collection can contain an enum (const) value for each operation, something like: enum lengthComplexity = CompComplexity.linear; I don't know if this can be useful (to choose collections, to infer code complexity, etc). If it can be used gainfully, that would be great. Intriguing idea. Andrei
Re: container stuff
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. 2. What's the affect of clear() on the capacity? There is no guaranteed effect. 3. Shouldn't KeyTypes be a type tuple? Yes. At the end of the day you must be able to say KeyTypes!3 to get the fourth type there. You say it should be KeyTypes[3]. I see tuple trouble, sigh. With a template I feel I have more control. Andrei
Re: container stuff
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. 2. What's the affect of clear() on the capacity? There is no guaranteed effect. Should say so in the spec. 3. Shouldn't KeyTypes be a type tuple? Yes. At the end of the day you must be able to say KeyTypes!3 to get the fourth type there. You say it should be KeyTypes[3]. I see tuple trouble, sigh. With a template I feel I have more control. The reason I prefer a tuple for this is then I can ask KeyTypes.length, whereas with the template that's not specified by the spec.
Re: container stuff
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? Andrei
Re: container stuff
On 05/25/2010 08:31 PM, Walter Bright wrote: Andrei Alexandrescu wrote: 2. What's the affect of clear() on the capacity? There is no guaranteed effect. Should say so in the spec. I guess if it's missing then it's implied. 3. Shouldn't KeyTypes be a type tuple? Yes. At the end of the day you must be able to say KeyTypes!3 to get the fourth type there. You say it should be KeyTypes[3]. I see tuple trouble, sigh. With a template I feel I have more control. The reason I prefer a tuple for this is then I can ask KeyTypes.length, whereas with the template that's not specified by the spec. OK. Andrei
Re: container stuff
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?
Re: container stuff
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
Re: container stuff
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.
Re: container stuff
On 05/25/2010 06:04 PM, Steven Schveighoffer wrote: What about the purge function of dcollections (i.e. removal while iterating)? I changed remove and softRemove to return a range positioned to after the removed stuff. Andrei
Re: container stuff
Andrei Alexandrescu Wrote: On 05/25/2010 06:04 PM, Steven Schveighoffer wrote: On Tue, 25 May 2010 18:27:32 -0400, Andrei Alexandrescu seewebsiteforem...@erdani.org 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. 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. softXXX might be better named safeXXX or stableXXX. The names might be more suggestive of preserving iteration. 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. 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. 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. Related to this, do you intend removal of a single element to use remove(range) or removeKey? Finally, opSlice(begin, end) is not there. Was this intentional or overlooked? Jerry
