Traversable Containers |

Data structures such as lists may want to provide their clients with a way to access and traverse their elements. This notion of traversal mechanism seems to be simple to design: one just has to add, using inheritance, the traversal operation features to the traversable container interfaces. However some data structures might have different traversal policies. For example, a tree structure might be traversed in preorder, postorder or breadth-first depending on its clients' needs. Including the operations for such different traversals in the data structures' class interface is hardly possible for two reasons: the class interface will rapidly be too complex, making more important features difficult to spot; and one cannot anticipate all possible traversal policies relevant to all clients of a data structure. Another important facility to take into account is to allow a data structure to be traversed more than once at the same time.

The use of the iterator pattern as described in Design Patterns solves the concerns expressed above. The key idea of this pattern is to take the responsibility for access and traversal out of the data structure and put it into an external cursor object. This way, it is very straightforward to traverse the same data structure at once: each cursor just has to keep track of its own traversal state. Moreover the traversal algorithm being held in cursors, it is very easy to switch from one traversal policy to another for a given data structure just by using a different kind of cursor.

However, programmers used to EiffelBase traversal mechanism sometimes prefer to have the iteration features included in the container class interface itself rather than having to create an external cursor object. This technique may indeed be just fine in many cases provided that the container is not traversed more than once simultaneously since there is only one internal cursor position in the data structure. For this reason the Gobo Eiffel Structure Library supports both internal and external cursor mechanisms.

## Classes `DS_TRAVERSABLE` and `DS_CURSOR`

Typically, traversable structures are heirs of class `DS_TRAVERSABLE`. In the external cursor pattern, this class is only responsible for providing its clients with new cursors (instances of class `DS_CURSOR`). This is achieved through feature `new_cursor`. Traversable structures are also equipped with the boolean-valued query `valid_cursor` providing a means to check whether a given external cursor can be used to traverse the current container. Cursors supplied by one data structure cannot be used to traverse another structure, even if the structures are of the same type. This is enforced by the fact that each cursor knows about the structure it is traversing. Apart from this container reference, class `DS_CURSOR` has a boolean-valued query `off` stating whether there is an element at the current cursor position, and `item` returning this element. Also useful are the two features `same_position` and `go_to` which respectively checks whether two cursors point to the same position in the container and moves the cursor to another cursor's position.

In the internal cursor pattern, all features from class `DS_CURSOR` are also available in class `DS_TRAVERSABLE`, the only difference being that feature `item` has been named `item_for_iteration` to avoid name clashes in descendant classes with feature `item` from `DS_INDEXABLE`.

Cursor objects are valid at any time during their existance. This means that they should be kept synchronized with their data structure, especially when the container is modified. For example a cursor pointing to an item which has been removed from the container won't be valid any more and should be resynchronized. It is the responsibility of the procedure that alters the container to keep the cursors (both internal and external) valid in a deterministic way. Each such procedure in descendant classes of `DS_TRAVERSABLE` will take the most appropriate action as possible and document it in its header comment. For example in lists, adding new items will not move the cursors currently traversing the container, but removing an item from the list will move any cursor which was at this position to its next position. So in order to know what will happen to cursors when altering a container, just check the header comment of the corresponding procedure first.

## Classes `DS_LINEAR` and `DS_LINEAR_CURSOR`

Linear structures are containers which can be traversed in a linear way, that is the traversal starts from one of its item and then sequencially moves to the next items until all items have been visited. Unless the data structure is an ordered container, two subsequent iterations may not traverse the items in the same order. An example of containers where items are traversed in a predictable order is list. Hash table on the other hand is an example of linear container which is not ordered since items will be inserted in the container depending on hash codes and table size and the order can change when the hash table is resized.

The features that are introduced in classes `DS_LINEAR` and `DS_LINEAR_CURSOR` are `start` to initiate the traversal, `forth` to move to the next item, `after` to indicate that all items have been visited, `is_first` to indicate whether the cursor is on the first item of the traversal and `go_after` to abort the traversal and move the cursor after the last item. Also of interest is the feature `search_forth` which moves the cursor to the next occurrence of an item according to the searchable mechanism criteria. Following is a typical example of a linear traversal:

>     a_cursor := a_linear.new_cursor
>     from a_cursor.start until a_cursor.after loop
>         do_something (a_cursor.item)
>         a_cursor.forth
>     end

Here is another straightforward example:

>     a_cursor := a_linear.new_cursor
>     from a_cursor.start until a_cursor.after loop
>         if a_cursor.item = 5 then
>             found := True
>             a_cursor.go_after
>         else
>             a_cursor.forth
>         end
>     end

Note that the examples above also work fine when the container is empty. This is because the feature `start` moves the cursor `after` when there is no items, hence exiting from the loop before the first iteration.

We saw in the previous section that it was the responsibility of the container to keep up-to-date the cursors currently traversing its items. This implies that the container internally keeps track of such cursors. Therefore, after a traversal and/or when the cursor is not needed anymore, it is important to give a clue to the container that it doesn't need to take care of this cursor anymore by calling `go_after`. This will allow the container to release its reference to this cursor and hence allow the garbage collector to reclaim its memory if necessary. Otherwise memory leaks as well as performance degradation may appear.

## Classes `DS_BILINEAR` and `DS_BILINEAR_CURSOR`

Bilinear containers are similar to linear containers except that they can be traversed both forward and backward. Therefore classes `DS_BILINEAR` and `DS_BILINEAR_CURSOR` introduce the counterpart set of features: `finish` to initiate the traversal, `back` to move to the previous item, `before` to indicate that all items have been visited, `is_last` to indicate whether the cursor is on the last item of the traversal, `go_before` to abort the traversal and move the cursor before the first item and `search_back` which moves the cursor to the previous occurrence of an item according to the searchable mechanism criteria.

## Classes `DS_INDEXED_CURSOR` and `DS_DYNAMIC_CURSOR`

The class `DS_INDEXED_CURSOR` associates the cursor's position with an integer value `index`. It comes with two other features, `valid_index` which checks whether a given integer is a valid index value, and `go_i_th` to move the cursor to a position specified by its index.

The class `DS_DYNAMIC_CURSOR` is equipped with features `replace` to change the item at the cursor position, and `swap` to exchange items between to cursors.