Re: ADT Lib (3)

["Eric W. Nikitin" <enikitin@apk.net>]

Hi!

I'm trying to keep up... but you guys are moving too fast for me :)

Michael van Acken wrote:
> I prefer the name `Rider' over `Iterator', because it is firmly
> established in the Oberon community, and extends also more readily to
> other areas.  

I don't think that Riders and Iterators are exactly the same things.  A
Rider traverses a collection, whereas an Iterator maps operations
(functions, procedures... whatever) to all elements of a collection.  I
think what we're calling a Rider is basically equivalent to
java.util.Enumeration.  In Java, the Enumeration interface defines exactly
two methods: 

 public abstract boolean hasMoreElements()
     Tests if this enumeration contains more elements. 

     Returns: 
          true if this enumeration contains more elements; false otherwise. 

 public abstract Object nextElement()
     Returns the next element of this enumeration. 

     Returns: 
          the next element of this enumeration. 
     Throws: NoSuchElementException 
          if no more elements exist. 


This is supported by what Michael wrote later:
> A container is probably the
> lowest level on which a iterator (or rider) can be defined.  And a
> definition would look like this:
> 
>  - a rider can be connected to the container
>  - data associated with the current rider position can be retrieved
>  - the rider can be moved forward

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

> In particular, no assumptions are made over the particular order in
> which data elements are visited.  

That depends on the ADT.  A java.util.Vector.elements() enumerates in index
order, whereas java.util.Hashtable.elements() (and keys()) enumerate in no
particular order.  

> The only guarantee is this: as long
> as the container is not modified between rider init and the rider
> reaching the end, all elements are enumerated.  A rider is no index,
> and it is not a bookmark for the container.  In fact, any changes to
> the container leave the rider in an undefined state, because the
> guarantee does no longer exist, that all elements will eventually be
> visited.

This is exactly right.

Maybe what we need is to provide different kinds of iteration, which is
based on what kind of ADT you're talking about.  Some ADTs don't support any
iteration (a Stack wouldn't allow riders, would it?), while others would
support reading, writing, and mapping.  The different kinds might be

  Rider (as described above)

  Modifier -- allows insertion and replacement of elements.
    (since you'd probably want to be able to examine an object before 
     modifying it, I'd guess this could be an extension of Rider)

  Iterator -- allows mapping of operations (functions) to elements of a
              collection.
    (would this extend Rider... or Modifier??)


Eric