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
Previous text:
2002-10-28 15:45: Subject: Proposal for new ADT interface
I'm currently working on a thesis that should bring Pike some new ADTs. I'm currently working on a common interface for the new ADTs and this is a draft of how it might be. The goal of the interface is resemble as much as possible of the current types array, multiset and mapping. Another goal with the interface is to keep it as minimal as possible. No unnecessary methods. The reason is simple, lack of time. The time I've got on hand is far to little to do a trough out analysis of possible fields of application and methods in the ADTs. The solution is to keep the interface incomplete by sufficient to work with a few algorithms and let other add new methods when they develop new algorithms. The base of the interface is four different concepts, one base concept and three sub-concepts that inherit all the methods from the base concept.
Collection |---- Sequence |---- Set |---- Map
Additional sub-concepts to the sub-concepts could be added later, for example sorted set. If an ADT implements all the methods in a concept and its super concepts it is an implementation of the concept.
Collection Collection is the base concept of all the ADTs. The reason it is called collection is that all the ADTs in the library is in some way a collection of items. iterator _get_iterator() Return an iterator for this ADT positioned at the first item in the ADT.
int _sizeof() Return the current size of the ADT.
array _values() Return an array with the values in the ADT.
int is_empty() Return 0 if the ADT do has elements.
int max_size() Return the maximal size of the ADT if there is any, otherwise -1.
void clear() Clear the ADT.
void add_all(collection col) Add all the items in the collection col to this collection.
Sequence A sequence is a linear container that allows index-based access and automatically expands to accommodate new elements. A vector is a good example.
void insert(int ind, mixed item) Insert an item in the sequence at the index ind. The size of the sequence is increased by one and the items at index and above have their indices increases by one. Throw an error if ind is out of range.
int remove(mixed item) Remove the item item from the sequence. Return the number of removed items.
int index_of(int ind, mixed item) Return the index of the first item in the sequence with the index ind or higher that mach the item item. -1 if no object was found. Throw an error if ind is out of range.
void add(mixed item) Add the object item as fast as possible to the sequence.
Int remove_at(int ind) Remove the item at the index ind. The size of the sequence is decreased by one and the items above ind have their indices decreases by one. Return 0 if the removal failed. Throw an error if ind is out of range.
iterator get_iterator(int ind) Get an iterator for this ADT positioned at the index ind. Throw an error if ind is out of range.
mixed '[](int ind) Return the item at index ind in the sequence. Throw an error if ind is out of range.
Mixed '[]=(int ind, mixed item) Set the index ind to be item. Throw an error if ind is out of range
Set Set is a collection containing any number of items but only one of each item.
iterator get_iterator(mixed item) Get an iterator for this ADT positioned at the item or null if the item could not be found.
int '[](set set, mixed item) Return 1 if the item could be found in the set, 0 if it couldn't
int '[]=(mixed item, int exist) Add the item to the set if exist is true remove the item if exist is false.
Map A map is a data structure that allows you to associate a key with one or more values and then quickly retrieve those values using the key.
array _indices() Return an array with the indices in the map.
iterator get_iterator(mixed key) Get an iterator for this ADT positioned at the key or null if the key could not be found.
int remove(mixed key) Remove the pair with the key key. Return 0 if the key could not be removed.
mixed '[](mixed key) Return the item associated with the key if it could be found, 0 if it couldn't
mixed '[]=(mixed key, mixed item) If there is an item with the key key then the associated item will be overwritten with the supplied item. If there is no key in the map a new key-item pair will be added.
Iterator changes I've also analysed the current iterators and how well they would work with generic algorithms and I found that it is only one thing that really lacks, the possibility to walk backwards. Actually the possibility to walk backwards is already there, it just doesn't have it's own method.
iterator '-=(int n) Move the iterator n steps backwards
int has_previous() Return true if the iterator can move one step backwards.
int has_next() Return true if the iterator can move one step forwards. It have the same use as '! but since there is a has_previous I believe it should be a has_next to.
int '==(iterator iter) Return true if the two iterators is pointing to the same object.
Well this is briefly what I have in mind. If you have any questions or comments you're more then welcome.
/ Peta, jo det är jag