Realised something similar when I was testing different algorithms yesterday. A lot of them were only useful on ordered collections. I shall try out a structure like this.
Collection |-----------> Ordered Collection | | | |--------> Sequence | |--------> Ordered Set <------| | |--------> Ordered Map <--| | |----> Map --------------------------------------| | |----> Set ------------------------------------------|
And two different iterators, the basic iterator and the ordered iterator where you are guaranteed to get the same order each time and index(), '<' and '>' make sense.
/ Peta, jo det är jag
Previous text:
2002-10-29 20:46: Subject: Proposal for new ADT interface
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