Re: ADT Lib (3)

[Tim Teulings <tim@edge.ping.de>]

Hallo!

> This makes sense for the base Iterator class - there's no reason to presume
> that a particular order exists when you don't even know what you're looking
> at. This doesn't mean that this lack of a defined order need be inherited
> by the decendents of this class. Optimization is not the only reason to
> derive new iterator classes; you can also define them to iterate in a 
> particular direction or using a particular method.

My proposal for differnet reader iterators does not mean: Different
iteraotr with same interface but with different semantics. I propose to
think about, if all reader do have the same interface. MvA has compared
riders with file handles. Their you also have differnt cases: Files can
be readonly (we agree on that, there should be readers and writers) but
files can also only be read sequential (pipes; you can never seek
backwards in a pipe, its only "read-once") on some you can seek
randomly. My proposal is based an the design of the STL, which also
defines different Iteraotrs with more or less powerfull iterators.
However as I'm on holiay I do not have access to a STL documentation so
I cannot give thrilling examples. Howver I told that different
Iteraotrs are inrelevant when only using ADTs. They are only needed
when you try to create generic algorithms on ADTs that do interface
with the ADTs using iterators. For example: For sorting you need
somehow a random-seek iterator. You will scan forward and backward
over the ADT, possibly even directly indexing some elements. For this
you need a very powerfull iterator. A hash cannot be sorted (it just
makes so sense) and at the same time it cannot offer a random-access
iteraotr, just because this is not a native method of value access for a
hash table. As a result you cannot sort a hashtable (or a tree, or...)
because they simply do not offer a interface for it.

A possible iterator hierachie would be:

Sequential iterator - begin at start, iterator once to the end. No
skipping, no back iterating, no direct indexing. A iterator for nearly
all ADTs (obviously not stack and alike). However a ADT can offer various
iteraotr, e.g. a list can offer a iterator that starts at the end of the
list and iterates to the start. Possible algorithms are: Copying, Filtering,
Moving, Converting, Searching...

A Forward-Backward iterator (better name?) - Same as Sequential
iterator, but you can move back and forward, perhaps even skipping with
a linear performance (O(n)). Supported ADTs: Double linked lists, perhaps
trees, Arrays/Vectors, Sets, Queues (?). Possible algorithms are: Perhaps
simple sort algorithms like bubble sort. No other algorithms come to
mind mind, yet, but since pipes and "normal" files have some differnet
uses, there will be some more algorithms.

A random-access iterator - allows direct indexing of a member in O(1).
Supported ADTs: Arrays/Vectors, Sets (dependend of implementation).
Supported algorithms: Sorting of all kind.

> I have a question about the Write method mentioned earlier. Does it replace
> the current element or insert a new element at the current location? I think

For pracitcal purposes writers should always be inserting iterators.
Example: For copying all values from one ADTs to another a overwriting
writer would make things *very* difficult.

> that insertion semantics would be better implemented by an Insert method, but
> even that would only be appropriate to attach to an iterator if the item's
> position within the container means something outside of the context of the
> iterator's trip through the container, _and_ insertions can be made at any
> position. This won't always be the case.

The write iteraotr should be possitioned that way, that the order of
entry while copying values over a iterotr is not changes as long as a
special order is defined for a ADT (list versus hashtable).

> Would all this just depend on the particular Container/Iterator definition?

Much of it, yes. However the base functionality should be defined that
way that common algorithms work as exspected.

-- 
Gru...
       Tim.