Re: ADT Lib (3)

[Brian Hawley <brian.hawley@bigfoot.com>]

Hi all.

Sorry to let you all think that you were alone in your ADT obsession.
I've been working under several deadlines :(

Some quick comments...

TT = Tim Teulings
MvA = Michael van Acken

TT> Sure? I'm not sure, but I think that itertaors can be applied to trees
TT> without problem if you reduce the functionality of the iterator to be a
TT> serial one. I must think about that, I admit. Tree are long ago :-)
TT> A serial iterator lets you just go once from the start to the end, you
TT> cannot skip nor you can go back.

MvA> Yes.  Check your trees again.  And I want to remind you, that both
MvA> of you stated, that a module interface should not contain any things
MvA> unnatural to the type.  The sequential iterator/rider we are
MvA> discussing here is unnatural to, say, a binary tree, and to include
MvA> it into the tree's module interface is very questionable.

Actually, if you are using a generic iterator interface with specific
versions related to your specific container, there is no reason that
you would not be able to define one for a binary tree. In fact, you
should define several kinds. Each kind would traverse the tree in a
different direction, such as preorder, inorder, postorder.

(earlier...)

MvA> Call me stupid, but I don't see how you classify iterators, at least
MvA> beyond the reader/writer distinction.  A container is probably the
MvA> lowest level on which a iterator (or rider) can be defined.  And a
MvA> definition would look like this:
MvA> 
MvA>  - a rider can be connected to the container
MvA>  - data associated with the current rider position can be retrieved
MvA>  - the rider can be moved forward

(Later arguments in favor of this agreed with, and snipped :)
 
I agree with MvA's arguments about the Rider interface - you would be
required to lock the container to maintain the consistency of your link
to an element of the list if you don't make that link an atomic action.

However...

MvA> In particular, no assumptions are made over the particular order in
MvA> which data elements are visited.  The only guarantee is this: as long
MvA> as the container is not modified between rider init and the rider
MvA> reaching the end, all elements are enumerated.

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.

For example:
MODULE Trees; (* Binary tree *)
IMPORT StdTypes, Iterators;
TYPE
  Tree* = POINTER TO TreeDesc;
  TreeDesc* = RECORD (* Insert implementation here... *) END;
  InOrderIterator* = POINTER TO InOrderIteratorDesc;
  InOrderIteratorDesc* = RECORD (IteratorDesc) T: Tree END;
...
PROCEDURE (T: Tree) NewInOrderIterator: InOrderIterator;
...
(* Ditto for PreOrder, etc. *)
END Trees.

The iterator defined for hash tables (or sets) can keep the lack of defined
order of the base Iterator class. A doubly-linked list could add a Previous
method to its iterator. An array-based list could add a SetPos method.

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
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.

Even if Write has replacement semantics, how would that affect containers that
have an inherent reordering semantics to their elements (SortedList, Balanced-
Tree)? Does the iterator work on a snapshot of the state of the container as
of the time that it was created (like Interbase) or can Write potentially send
the iterator into an endless loop? Is the "next position" that Write sends you
to based on the old value of the previous position or the new value?

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

Am I just making things difficult? :)

Next, persistence... (Insert maniacal laugh here)

Brian