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
Previous text:
2002-10-28 20:17: Subject: Proposal for new ADT interface
It's a good goal to resemble the builtin types. I've therefore pointed out several cases where you don't use the standard callbacks (usually called "lfuns") that exists already.
Collection:
o You might want to consider handling collections that aren't bounded, e.g. they have an iterator that enumerates elements from some outside source whose size isn't known in advance, or that is unlimited. I suggest allowing the return value -1 from _sizeof() to flag this, and perhaps even have another return value to flag whether the collection is truly unlimited or only of (currently) unknown size.(*)
Handling collections with unknown size probably has consequences elsewhere too, but it is a very useful application, so it would be nice to include it in the design from the start.
o add_all() - A cast, `+ or `+= are more natural ways to perform this in Pike.
o An _equal() lfun would be useful to be able to do recursive comparison with equal().
o In the same vein, perhaps _encode() and _decode() should be mentioned too? (They're used for serialization with encode_value and decode_value). Maybe also _sprintf()?
Sequence:
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.
o index_of() - This functionality should be accessed through the global search() function for consistence. It currently have no lfun to handle objects, but a _search should clearly be added for that, imho.
o remove_at() - This is the _m_delete lfun.
o add() - Why here and not in Collection? Collection got add_all, so why not this one too?
Set:
o `[]= - Clearly inspired by the multisets. I think a prettier API is to use remove_at/remove/_m_delete to remove elements for symmetry with the other variants, and that the assign-zero-to-remove method should be delegated to a compatibility measure.
Map:
o remove() - This is also the _m_delete lfun. Inconsistent name wrt remove_at() in Sequence.
Iterators:
o Good improvements with has_next and has_previous.
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().
o An API to be able to insert and delete wrt to the iterator position.
o An API to be able to do various kinds of searches wrt to the iterator position, somewhat like index_of/_search.
Also, I consider the following properties fairly important, and it's not obvious how they fit into this hierarchy:
o Unique vs multiple indices. o Ordering: unordered/using ordering function (or builtin order)/ stable order without ordering function. Perhaps also partial orders.
*) An integer correspondence to Math.inf would be nice. I'll see if I can get around adding that when the cvs fork is done.
/ Martin Stjernholm, Roxen IS