As you say, it feels a bit weird to use m_delete to remove from a set, have to think about that.
We could perhaps rename the lfun to _delete and add an _insert. Compatibility measures can always be devised.
The reason why I did not place add in the collection concept is that all the three sub concepts has a different syntax for add.
Ok, but note that you will have essentially the same problems in add_all wrt differences in index/value sets. For instance, what do you plan to do if a Set is added to a Sequence? Will the indices then be converted to values? I'm not at all certain that such dwim would be good.
The add_all() method also brings in a number of other issues. How are duplicates handled? How is the order defined, if there is any? Why handle that specific merge method and not the others (intersection, set difference etc)? If you should include this in your design (which I'd appreciate) then I think you should handle the generic merge case. There is of course a lot of already implemented behavior to take into account regarding the different merge operations (`+, `-, `|, `& and `^).
'Return true if the two iterators is pointing to the same item in the same collection.' Since you can't rust that a collection has a valid indexing and you can't always compare the values of the iterators since a collection can contain the same item twice.
Ok. Good point. Come to think about it, iterators in ordered collections ought to have `< and `> too.
· Unique vs multiple indices.
I guess you mean set/multiset. The multiset concept is a possible sub-concept to the set concept
No, that's just a special case. The same applies to Map too. It's actually not very clear what principal difference you use to tell a Map from a Set. It's probably that Sets lacks values, but other reasonable divisions are whether there can/can't be multiple indices, or whether there's a well defined order.
I've come to the conclusion that among those differences the order is the most fundamental, and that is also what I plan to make evident wrt mappings when I add the high level interface to the new multiset implementation.
Whether there can be values attached or not is just a minor difference that only affects what you can do with a specific element once it's allocated. It's easy to e.g. define a behavior for _values() when there are no values in the collection.
The difference between unique and duplicate indices is somewhat more profound, but I still think it's secondary. Handling of duplicate indices only implies that API must be extended a bit: The operations that locates a single element using a key must be extended to use some method of choice if several elements matches(*), the iterators must be able to keep their position among identical indices, and there should preferably be some operations to handle (the values of) all the matching elements as a group.
An alternative more concrete view of this issue is to consider the current mapping implementation, which is a hash table: It would be comparatively easy to extend it both to make the values optional and to allow duplicate indices, but imposing a well defined order would practically imply a rewrite from scratch, and it's not clear whether a hash table would still be useful then.
*) The new low level multiset implementation defines this to access the last element according to the order. If the mapping implementation would be extended to handle duplicate indices, it would reasonably define it to be random (i.e. take whatever element happens to be closest to the top in the hash bucket).
/ Martin Stjernholm, Roxen IS
Previous text:
2002-10-29 11:35: Subject: Proposal for new ADT interface
Great comments, agree on most, I've just have a few comments and questions.
o insert() - For the new multisets I'd like to add a global m_insert(), corresponding to the m_delete() that already exists. An lfun like this one would then be used, so this should be that lfun.
If the correspondence to m_delete should be kept, that lfun should then be called _m_insert. The problem with that is mainly that the "m" part is ugly and out of place in this ADT generalization.
As you say, it feels a bit weird to use m_delete to remove from a set, have to think about that.
o add() - Why here and not in Collection? Collection got add_all, so why not this one too?
The reason why I did not place add in the collection concept is that all the three sub concepts has a different syntax for add. They where later removed from Map and Set since they where redundant. The reason I kept them in Sequence was that often you just want to add a item to a sequence, no matter where and then add do it as fast as possible, with insert you have to know the under laying structure.
o `== - The criteria for equality strikes me as very arbitrary. What is the reason? A function to be able to get the collection the iterator uses seems more useful and makes the code easier to understand: iter1->get_collection() == iter2->get_collection().
Sorry me not being clear enough on that. The text should rather be. 'Return true if the two iterators is pointing to the same item in the same collection.' Since you can't rust that a collection has a valid indexing and you can't always compare the values of the iterators since a collection can contain the same item twice.
o An API to be able to insert and delete wrt to the iterator position.
Yes, at least a set_value() is needed, insert and remove is useful to, have to think about this one.
· Unique vs multiple indices.
I guess you mean set/multiset. The multiset concept is a possible sub-concept to the set concept
Ordering: unordered/using ordering function (or builtin order)/ stable order without ordering function. Perhaps also partial orders.
I believe that sorted set is a sub-concept of the set concept, same with sorted map, I add these to the API. Sequences on the other hand does not need a sorted concept but is best kept sorted with the help of a sort algorithm and a binary search algorithm, as I see it.
/ Peta, jo det är jag