Um, that seems a lot like plain wrappers around existing types, so I'm curious: what's the intended benefit of using this wrapper interface instead of the existing types?
/ Leif Stensson, Lysator
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