ADT Lib (4.2)

[Michael van Acken <mvacken@t-online.de>]

Looks like I got many more responses than expected.  Here is the
second part of my summary.

TT> A possible iterator hierachie would be:
TT> 
TT> Sequential iterator - begin at start, iterator once to the end. No
TT> skipping, no back iterating, no direct indexing. A iterator for nearly
TT> all ADTs (obviously not stack and alike). However a ADT can offer
TT> various iteraotr, e.g. a list can offer a iterator that starts at the
TT> end of the list and iterates to the start. Possible algorithms are:
TT> Copying, Filtering, Moving, Converting, Searching...
TT> 
TT> A Forward-Backward iterator (better name?) - Same as Sequential
TT> iterator, but you can move back and forward, perhaps even skipping
TT> with a linear performance (O(n)). Supported ADTs: Double linked lists,
TT> perhaps trees, Arrays/Vectors, Sets, Queues (?). Possible algorithms
TT> are: Perhaps simple sort algorithms like bubble sort. No other
TT> algorithms come to mind mind, yet, but since pipes and "normal" files
TT> have some differnet uses, there will be some more algorithms.
TT> 
TT> A random-access iterator - allows direct indexing of a member in O(1).
TT> Supported ADTs: Arrays/Vectors, Sets (dependend of implementation).
TT> Supported algorithms: Sorting of all kind.

You seem mostly concerned about ways to position riders.  Each class
adds additional capabilties: the first extension is moving backward,
the other to allow arbitrary positioning, similar to the SetPos()
method of file riders.

This makes sense, and fits in nicely with the Container module I
posted previously.

Remaining problems: 

Where to declare such extended riders?  Since a plain `Container's
semantics do not support either of these extensions, I feel they need
to be defined together with other abstract classes.  If all things
fail, we can always throw them into Container.Mod, of course, either
by declaring extensions of `Rider', or by putting everything into
`Rider' (similar to the way Channel.Reader/Writer does it).

If the "positoning" capabilities of riders are implemented as
specialized subclasses: How can this can be combined with other rider
capabilities we might want to create?  If we have two orthoginal
capabilities, Oberon-2's single inheritance will prevent us from
implementing both as class specializations.

TT> > I have a question about the Write method mentioned earlier. Does it
TT> > replace the current element or insert a new element at the current
TT> > location? I think
TT> 
TT> For pracitcal purposes writers should always be inserting iterators.
TT> Example: For copying all values from one ADTs to another a overwriting
TT> writer would make things *very* difficult.

I believe you have been voted down on this.  For all practical
purposes, the _most basic_ rider can only replace, and sometimes it
can't even do that.  A rider (or writer, if you like) is not the
preferred method to create new container elements.


EN> Michael van Acken wrote:
EN> > I prefer the name `Rider' over `Iterator', because it is firmly
EN> > established in the Oberon community, and extends also more readily to
EN> > other areas.  
EN> 
EN> I don't think that Riders and Iterators are exactly the same things.  A
EN> Rider traverses a collection, whereas an Iterator maps operations
EN> (functions, procedures... whatever) to all elements of a collection.  

I prefer this distinction myself.  Therefore my inititial proposal for
iterators as functions Apply/Map/Select in my first posting of
List.Mod.  At least some Oberon related papers use both terms
interchangably: they talk about iterators, and call the implemented
class `Rider'.

EN> These should be all that are required by the rider interface.  Although, I
EN> would consider including a reset operation and a skip forward operation
EN> (which I would call Skip() instead of Forward(); in Oberon SA, N. Wirth has
EN> a standard procedure SKIP(r, n), and java.io.InputStream has a skip()
EN> method).

Ok, r.Skip(n) it is.

EN> > The only guarantee is this: as long
EN> > as the container is not modified between rider init and the rider
EN> > reaching the end, all elements are enumerated.  A rider is no index,
EN> > and it is not a bookmark for the container.  In fact, any changes to
EN> > the container leave the rider in an undefined state, because the
EN> > guarantee does no longer exist, that all elements will eventually be
EN> > visited.
EN> 
EN> This is exactly right.
EN> 
EN> Maybe what we need is to provide different kinds of iteration, which is
EN> based on what kind of ADT you're talking about.  Some ADTs don't support any
EN> iteration (a Stack wouldn't allow riders, would it?), while others would
EN> support reading, writing, and mapping.  The different kinds might be
EN> 
EN>   Rider (as described above)
EN> 
EN>   Modifier -- allows insertion and replacement of elements.
EN>     (since you'd probably want to be able to examine an object before 
EN>      modifying it, I'd guess this could be an extension of Rider)
EN> 
EN>   Iterator -- allows mapping of operations (functions) to elements of a
EN>               collection.
EN>     (would this extend Rider... or Modifier??)

This kind of distinction is exactly what I was hinting at in my
previous posting (whithout knowing this myself, of course).  The
`Modifier' will have additional methods, and will demand additional
properties from the data type it is operating on.  [Let me repeat
myself: I do not want to work out this part of the lib.]

I'm not sure what you mean with `Iterator'.  Myself, I see both
`Rider' and `Modifier' as something that is moved along by the user,
while an `Iterator' is something that is applied to a list (container,
whatever) as a whole, as an atomic action (from the callers point of
view).  Therefore I will quote again the relevant part of List.Mod
(they are list-centric, I know), and ask you to describe how your idea
of `Iterator' differs from mine:

PROCEDURE (l: List) Apply* (op: StdTypes.Operator);
(* Successively applies operator `op' to the elements of `l'.  *)
  END Apply;

PROCEDURE (l: List) Map* (fct: StdTypes.Function): List;
(* Successively applies the function `fct' to the elements of `l', and collects
   the results into a new list.  The list `l' is not destroyed.  *)
  END Map;

PROCEDURE (l: List) Select* (pred: StdTypes.Predicate);
(* Successively applies the predicate `fct' to the elements of `l'.  All nodes,
   for which `pred' evaluates to TRUE, are collected into a new list.  The
   original list `l' is not modified.  *)
  END Select;

-- mva