I've made som changes and here is a new suggestion for a common
interface of the new ADTs.
Common API for new ADTs in Pike
1. Introduction
This document describes a common platform for new ADTs in pike to stand on. The purpose of the platform is to make the new ADTs as flexible as possible and possible to use together with generic algorithms. The base of the platform is the Collection concept, being the base concepts of all the ADTs, and the Iterator concept making it possible to iterate over collections without knowing the underlying structure.
Besides the two base concepts this document also describes a few sub-concepts that are related to the two base concepts according to the two figures below.
Figur 1 Collection concepts
Collection
|-----------> Ordered Collection
| |
| |--------> Sequence
| |--------> Ordered Set <------|
| |--------> Ordered Map <--| |
|----> Map --------------------------------------| |
|----> Set ------------------------------------------|
Figur 2 Interface concepts
Iterator -------> Ordered Iterator
2. Collection concepts
2.1. 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. To implement a collection the following methods must be implemented
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. Return -1 if the size could not be decided or is truly unlimited.
array _values()
Return an array with the values in the ADT.
int _has_value(mixed value)
Returns 1 if value is in the value domain of collection, or 0 (zero) if not found
int _equal(mixed coll)
Decide if the collection coll and this collection contains the same elements, an if it is important, in the same order.
string _sprintf(int conversion_type, mapping(string:int)|void params)
Present the collection in a human readable way. For more information see _sprintf in the pike manual.
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.
iterator first()
Return an iterator for this ADT positioned at the first item in the ADT, same as _get_iterator().
iterator last()
Return an iterator for this ADT positioned at the last item in the ADT.
2.2. Set
Set is a collection containing any number of items but only one of each item. It is a sub-concept of Collection and must thereby besides implementing the methods below also implements the methods in Collections.
int '[](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.
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 insert(mixed item)
Add the item to the set if it isn't a part of the set. Return true if the item was added, else false.
mixed delete(mixed item)
Remove the item from the set. If the item was removed it will be returned otherwise a 0 zero_type is returned.
multiset cast("multiset")
The set should at least be able to cast to a multiset, additional castings are optional.
2.3. 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. To implement a Map the ADT must have all the methods in this concept and in the Collection concept.
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 get_iterator(mixed key)
Get an iterator for this ADT positioned at the key or null if the key could not be found.
mixed insert(mixed key, mixed item)
If the key doesn't exist or duplicates are allowed, associate the value with the key and return 0, otherwise don't modify the map and return the current value associated with the key.
mixed delete(mixed key)
Remove the pair with the key key. Return the keys value if it was removed, if the key could not be removed return zero_type.
mapping cast("mapping")
The map should at leas be able to cast to a mapping, additional castings are optional.
2.4. OrderedCollection
An OrderedCollection is a collection that has indices that could be used to find the values and the indices are strictly ordered is some way. Any type could be used as an index if it satisfies a few rules. See Index for more information. There is also nothing that prevents the use of the values as indices as long as the value satisfies the rules for an Index.
int _has_index(int index)
Returns 1 if index is in the index domain of collection, or 0 (zero) if not found
array _indices()
Return an array with the indices of the collection.
2.5. Sequence
A sequence is a sub-concept of an Ordered Collection. It is a linear collection that allows index-based access and automatically expands to accommodate new elements. A vector is a good example.
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
int _search(mixed item, void|int start)
Return the index of the first item in the sequence with the index start or higher that match the item item. -1 if no object was found. Throw an error if start is out of range.
void insert(index 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(0..1) delete(mixed item)
Remove the first value that are equal to item from the sequence. Return 1 if a item was removed, otherwise 0;
void add(mixed item)
Add the object item as fast as possible to the sequence.
int delete_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.
array cast("array")
The sequence should at least be able to cast to an array, additional castings are optional.
2.6. OrderedMap
An OrderedMap is a map where the keys are orderable and the iterator belonging to an OrderedMap will traverse the values in that order.
2.7. OrderedSet
An OrderedSet is a set were the values are orderable and the iterator belonging to an OrderedSet will traverse the values in that order.
3. Iterator concepts
3.1. Iterator
The iterator concept does not differ much from the present day iterator. Only a few new methods are added to make it possible to step backwards and compare iterators.
int(0
1) '!()
Should return 0 (zero) when not at end of collection, and 1 at end of collection
void '+=(int n)
Should advance the specified number of steps
iterator '-=(int n)
Move the iterator n steps backwards
int '==(iterator iter)
Return true if the two iterators is pointing to the same object. Throw an error if the two iterators belong to different collections.
mixed index()
Should return the current index.
mixed value()
Should return the current value
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 '!().
collection get_collection()
Return the collection this iterator iterates over.
Optional void set_value(mixed value)
Set the value of this iterator. This method should only be available if it is possible to set the value via an iterator.
Optional void add(mixed value)
Add a new item to the collection after the item the iterator currently is pointing at. This method should only be available if it is possible to add entries via the iterator
Optional mixed remove()
Remove the item the iterator currently is pointing at and move to the next item. This method should only be available if it is possible to remove entries via the iterator
3.2. OrderedIterator
An OrderedIterator is an iterator working on an OrderedCollection. It has two characteristics, first it traverse the collection in the same order each time it is traversed, if the there hasn't been any changes in the collection, beginning with the item with the lowest index and ending with the item with the highest index. Secondly it is possibly to say that an iterator is less then or greater then another iterator.
int(0..1) '<(OrderedIterator iter)
Return 1 if iter is positioned after this iterator, otherwise 0. Throw an error if the two iterators belong to different collections.
Int(0..1) '>(OrderedIterator iter)
Return 1 if iter is positioned before this iterator otherwise 0. Throw an error if the two iterators belong to different collections.
4. Index
If a type could be used as an index in an OrderedCollection then it must be possible to use the following operations on it.
'==
If the two indexes a and b is equal it should return 1 otherwise 0. The following rules must also be satisfied.
a == a must be true
a == b implies b == a
!(a == b) implies a != b
a == b and b == c implies a == c
'<
If the index a is ordered lower than b it should return 1 otherwise 0. The following rules must also be satisfied.
a < a must be false
a < b implies !(b < a)
a < b implies (b > a)
a < b and b < c implies a < c
'>
If the index a is ordered higher than b it should return 1 otherwise 0. The following rules must also be satisfied.
a > a must be false
a > b implies !(b > a)
a > b implies b < a
a > b and b > c implies a > c
