View source for EiffelBase2

[[Category:Library]]

==Overview==

EiffelBase2, currently under development, is a general-purpose data structures library for Eiffel. It is intended as the future replacement for the [[EiffelBase]] library ("Classic EiffelBase" in this document), which has for many years played a central role in Eiffel development. 

==Design goals==

The design goals for EiffelBase2 are:

*Verifiability. The library is designed to allow proofs of correctness.

*Full contracts. Partly as a result of the verifiability goal, but also for clarity and documentation, the contracts associated with classes and features should describe the relevant semantics in its entirety.

*Simple and consistent hierarchy, in particular avoidance of descendant hiding and of "taxomania" (classes not representing a meaningful abstraction, unnecessary inheritance links).

*As in Classic EiffelBase, application of a systematic classification (a theory) of fundamental data structures.

*Full traversal mechanisms, based on external cursors (with internal cursors also provided when useful).

*Client-interface compatibility with corresponding classes in Classic EiffelBase, whenever it does not conflict with the preceding goals.

==Design overview==
===Traversal mechanisms and classification criteria===
A design decision that significantly influenced the architecture of the library is using external iterators to traverse containers as apposed to internal ones available in classic EiffelBase.
In the design inspired by external iterators we found it natural to separate ''containers'' (with their measurements and modification means) from interfaces to access elements of containers, here called ''observers''.

On the observer side we distinguish ''maps'' (with the defining property "accessing elements by unique keys") and iterators (providing linear traversal). An observer can be either ''used'' by a container (as a supplier) or ''inherited'' by it. The first case produces an external access mechanism and is useful when multiple instances of an observer for the same container can exist at the same time; the second case results in an internal access mechanism and allows only one instance of an observer per container at a time. In the rest of the library maps are mostly inherited and iterators are mostly used, but this is not enforced by the design. For infinite sequences like <e>RANDOM</e> it makes sense to ''inherit'' from an iterator, because they cannot have more than one active iterator.

On the other side, a ''container'' is a finite storage of values. Containers are deliberately confined to finite structures and understood real, physical storage. Infinite structures, instead, are usually represented as functions or mechanisms that are external to a program. Most of the time we can only access their elements (not add or remove) and for this purpose we have observers: maps and iterators (the latter in the infinite case are called ''streams'').

Containers may be classified based on different means of modification, but previous experience shows that a complete and clean classification here is impossible (there are two many kinds of modification, basically one per "concrete" data structure). So concrete data structures mostly just inherit directly from <e>CONTAINER</e>. There is one exception: <e>SEQUENCE</e>, which represents a sequence of values accessible by indices from a continuous interval. It serves as a common ancestor for ARRAY and LIST and factors out their common search and replacement mechanisms.

Below you can find the class diagram of EiffelBase2, split into two hierarchies (according to connectedness). The first one is a hierarchy of containers and maps. Note: dash-bordered ovals stand for classes that might be included in the library, but are not the first priority of the developers.  
[[Image:eb2_container.png|800px|thumb|none|Container class hierarchy]]

The second one is a hierarchy of streams and iterators.
[[Image:eb2_iterator.png|800px|thumb|none|Iterator class hierarchy]]

===Comparison criteria===
Another important design decision for a data structures library is how to represent and modify comparison criteria for container elements.
Adjustable comparison criterion is used is search operations and to define the uniqueness property in sets and tables (uniqueness of keys).
# Classic EiffelBase uses the boolean <e>object_comparison</e> attribute in <e>CONTAINER</e> for this purpose.
# Gobo.structures uses another approach: storing equivalence as an object of a specific class, which can be redefined by the user to implement an arbitrary equalivalence relation.
# A similar approach would be to use agents to store the equalivalence relation (no need to create classes). The downside is that agents do not serialize well.
# Another approach is to make <e>has (x: G)</e> and <e>search (x: G)</e> always use <e>=</e>, but also introduce <e>exists (p: PREDICATE [ANY, TUPLE [G]])</e> and <e>satisfy (p: PREDICATE [ANY, TUPLE [G]])</e>. This is more flexible (better fits cases when the predicate is not an equivalence), but duplicates the number of search features and doesn't solve the problem with sets.

Additional question (if the comparison criterion is stored in the container) is whether it can be changed during the object lifetime. A well known practice is that in sets it is not allowed to change if the set is not empty. This gives rise to <e>changeable_comparison_criterion</e> query in CONTAINER.
Note that for most set and table implementations (hashed, sorted) the comparison critearion is defined by the corresponding hash function, order, etc. and cannot be modified arbitrary even when the set or table is empty.

The strategy chosen in EiffelBase2 is to treat differently comparison criteria on which a set or a table is based and ones just used for search. For the first the Gobo approach is taken (2 in the list above), because it is more flexible than in EiffelBase, as we can use whatever equivalence relation we want instead of just <e>is_equal</e> (useful for library classes). Moreover, the equivalence relation is passed as an argument to the creation procedure and cannot be changed afterward. 

For search operations the approach 4 is taken, because it doesn't clutter the container state with properties that don't pertain to the container itself, but to specific search operations.

===Indexing===
The current version of EiffelBase2 is using the same policy for indexing as the one used in the classic EiffelBase: indexing of lists (and iterators) always starts from 1, whereas for arrays the starting index can be set to an arbitrary value. However, during the code review in the Chair of Software Engineering (17.03.2010) is was decided that the possibility to start arrays from an arbitrary index is not crucial and is used very rarely, but complicates the API. Thus it will probably be changed in future so that array indexing, like in other indexed data structures, always starts at 1.

==Model-based contracts==

==Status and roadmap==

Development of EiffelBase has started as a project at ETH Zurich; see the [http://eiffelbase2.origo.ethz.ch/ project page]. Documentation and other material will soon be transferred to the present page.

===ToDo list===
Below you can see a list of most important changes planned for EiffelBase2.
* Test extensively with AutoTest.
* Implement <e>HASH_SET</e> and <e>HASH_TABLE</e>.
* Implement <e>PREORDER_ITERATOR</e> and <e>POSTORDER_ITERATOR</e> to traverse binaries in pre- and postorder.
* Iterator management: currently the situation when a container is modified through one iterator while it's being traversed with another is not handled anyhow.
* Finish the implementation of the MML library.
* Rewrite loops using the <e>accross</e> where appropriate.
* Implement <e>RANDOM</e> and <e>STANDARD_INPUT</e> streams.
* Add an iterator over keys for <e>TABLE</e>.
* Make the library void-safe.
* Implement more efficient data structures: e.g., tables with fast lookup both ways, heaps, skip lists, treaps, etc.